Succinct Infinite-Horizon Lyapunov and LQR Value Problems Are BQP-Complete

공학 및 물리학의 세계에서, 시스템이 시간이 지남에 따라 어떻게 행동할지 예측하는 것은 끊임없이 요구되는 과제입니다. 안정적인 교량을 설계하든, 우주선을 유도하든, 혹은 전력망을 조절하든, 엔지니어들은 시스템이 사용할 총 에너지를 계산하거나 궤도를 유지하는 데 드는 비용을 산출하기 위해 수학적 모델에 의존합니다. 단순한 시스템의 경우 이러한 계산은 간단합니다. 하지만 시스템이 수백만 개의 상호작용하는 부품들로 구성되어 거대해지면, 수학적 밀도가 너무 높아져서 가장 강력한 슈퍼컴퓨터조차 합리적인 시간 내에 답을 찾는 데 어려움을 겪게 됩니다. 바로 이 지점에서 컴퓨터가 할 수 있는 일과 할 수 없는 일 사이의 경계가 흐릿해지기 시작합니다. 과학자들은 오랫동안 양자 컴퓨터가 아원자 입자의 기묘한 법칙에 따라 작동함으로써, 이러한 특정 유형의 거대한 계산 문제들을 기존의 고전적 기계보다 훨씬 빠르게 해결할 수 있을 것이라고 믿어 왔습니다. 그러나 이 믿음이 단순한 희망을 넘어 실체가 되기 위해서는, 단순히 양자 컴퓨터가 빠르다는 사실뿐만 아니라, 이 문제들이 본질적으로 고전 컴퓨터에게 어렵다는 증거가 필요했습니다.

워털로 대학교의 연구팀은 이제 제어 이론의 계산 한계에 대한 오랜 의문을 해결하며 그 증거를 제시했습니다. 그들은 두 가지 특정 작업에 집중했습니다: 안정적인 시스템의 총 에너지 출력을 계산하는 것과, 무한한 미래에 걸쳐 시스템을 제어하기 위한 최적의 비용을 결정하는 것입니다. 현실 세계에서 이것들은 엔지니어가 시스템의 효율성과 안전성을 보장하기 위해 반드시 알아야 하는 숫자들입니다. 연구진은 이 문제들을 최대한 어렵게 묘사하기 위해 '간결한(succinct)' 표현법을 사용했습니다. 거대한 행렬의 모든 숫자를 일일이 나열하는 대신(이는 테라바이트 단위의 메모리를 차지할 것입니다), 그들은 마치 컴퓨터 프로그램처럼 숫자를 필요할 때마다 생성할 수 있는 압축된 논리적 명령 세트를 사용했습니다. 이를 통해 연구진은 그 자체의 설명은 단 한 페이지에 들어갈 정도로 작게 유지하면서도, 명시적으로 써 내려가는 것이 불가능할 정도로 거대한 차원의 시스템을 묘사할 수 있었습니다.

연구팀은 그다음 근본적인 질문을 던졌습니다. 표준 컴퓨터가, 설령 계산 속도를 높이기 위해 확률적 무작위성을 사용하더라도, 이렇게 간결하게 묘사된 문제들을 빠르게 풀 수 있는가? 그들의 대답은 단호한 '아니오'였습니다. 그들은 이러한 특정 에너지 및 제어 문제를 푸는 것이 임의의 양자 컴퓨터를 시뮬레이션하는 것만큼이나 어렵다는 것을 증명했습니다. 컴퓨터 과학의 언어로, 그들은 이 제어 문제들이 'BQP-완전(BQP-complete)'임을 보여주었습니다. 이는 만약 고전 컴퓨터가 이러한 제어 문제를 효율적으로 해결할 수 있다면, 양자 컴퓨터가 해결할 수 있는 모든 문제 또한 해결할 수 있음을 의미합니다. 대부분의 전문가가 고전 컴퓨터가 이 일을 수행할 수 없다고 믿기 때문에, 연구진은 어떤 정교하거나 무작위적인 알고리즘을 사용하더라도 고전 컴퓨터는 입력 크기에 따라 합리적인 시간 내에 이러한 특정 제어 문제를 해결할 수 없다고 결론지었습니다.

이 결론에 도달하기 위해 연구진은 단순히 추측한 것이 아니라 수학적 가교를 구축했습니다. 그들은 양자 컴퓨터가 수행하는 모든 계산이 이러한 제어 문제 중 하나로 직접 번역될 수 있음을 입증했습니다. 만약 복잡한 양자 실험의 결과를 알고 싶다면, 그 실험을 시스템의 에너지나 제어 비용에 대한 설명 속에 인코딩할 수 있습니다. 만약 고전 컴퓨터가 그 에너지 질문에 대한 답을 빠르게 알려줄 수 있다면, 그것은 사실상 당신을 대신해 양자 실험을 실행하고 있는 것과 같습니다. 연구진은 이 번역이 가능한 모든 양자 작업에 대해 작동함을 보여줌으로써, 제어 문제의 난이도가 양자 계산 자체의 난이도와 정확히 일치한다는 것을 증명했습니다.

또한 이 연구는 양자 컴퓨터가 이러한 문제들을 효율적으로 해결할 수 있다는 점도 보여주었습니다. 이러한 유형의 행렬 계산을 처리하도록 설계된 특정 양자 알고리즘을 사용함으로써, 양자 기계는 시스템이 커짐에 따라 매우 느리게 증가하는 시간 내에 답을 찾을 수 있습니다. 이는 명확한 경계를 만듭니다. 즉, 문제는 고전 컴퓨터에게는 (양자과 고전의 능력이 근본적으로 다르다는 널리 받아들여지는 믿음을 전제로 할 때) 확실히 어렵지만, 양자 컴퓨터에게는 쉽다는 것입니다. 연구진은 단순히 수학을 더 빨리 푸는 방법을 찾아낸 것이 아니라, 양자 역학의 힘을 측정하는 리트머스 시험지 역할을 하는 특정 공학적 질문의 범주를 식별해 낸 것입니다.

이 연구는 논의의 차원을 추측에서 확신으로 옮겨 놓았다는 점에서 중요합니다. 수년간 양자 컴퓨팅이 공학 분야에서 약속했던 가능성은 양자 기계가 단순히 선형 대수를 더 빨리 처리할 것이라는 생각에 기반해 왔습니다. 이 논문은 시스템의 안정성과 제어에 관한 특정 핵심 질문들에 대해, 그 우위가 단순히 속도의 문제가 아니라 '능력'의 문제임을 확인해 주었습니다. 이는 고전 컴퓨터가 아무리 많은 시간이나 메모리를 투입하더라도 도달할 수 없는 실질적인 공학적 질문들이 존재함을 입증합니다. 연구진은 제트 엔진이나 전력망을 위한 양자 제어기를 만들었다고 주장한 것이 아니지만, 그러한 제어기를 위한 수학적 토대가 오직 양자 컴퓨터만이 발을 들일 수 있는 영역에 속해 있음을 증명했습니다.

또한 이 연구 결과는 난이도의 본질을 명확히 합니다. 이 문제들이 어려운 이유는 숫자가 지저분하거나 시스템이 혼돈 상태이기 때문이 아닙니다. 정보가 설명 속에 압축되어 있는 방식이, 고전 컴퓨터가 전체 양자 과정을 시뮬레이션하지 않고서는 뚫고 나올 수 없는 복잡성을 숨기고 있기 때문입니다. 연구진은 시스템이 엄격하게 안정적이고 잘 통제되더라도, 숨겨진 정보의 규모 자체가 장벽을 만든다는 것을 보여주었습니다. 이 장벽은 더 나은 알고리즘이 부족해서 생기는 일시적인 현상이 아니라, 고전적 계산의 구조적 한계입니다.

결국, 이 논문은 선을 긋습니다. 특정하고 중요한 범주의 무한 시간 제어 문제에 대해, 효율적인 계산의 미래는 오직 양자 기술에 달려 있다는 점을 분명히 합니다. 만약 엔지니어들이 압축된 논리적 규칙으로만 설명될 수 있을 만큼 엄청난 규모의 시스템을 최적화해야 한다면, 그들은 반드시 양자 기계에 의존해야 할 것입니다. 고전적인 접근 방식은, 그 모든 확률적 기교를 동원하더라도 결국 벽에 부딪힐 것입니다. 이 결과는 단순히 양자 우위의 목록에 새로운 항목을 추가하는 것이 아니라, 양자 세계가 단순한 선택지가 아닌 유일한 경로가 되는 새로운 문제의 범주를 정의하고 있습니다.