State Synthesis with an NP oracle

양자 세계에서 정보는 단순한 0과 1이 아니라, 섬세하고 일렁이는 확률의 파동으로 저장됩니다. 유용한 양자 컴퓨터를 구축하기 위해 과학자들은 이 파동을 특정 모양으로 조각하는 법을 배워야 하며, 이 과정은 '상태 준비(state preparation)'라고 불립니다. 빛으로 독특하고 복잡한 조각상을 만든다고 상상해 보십시오. 문제는 이 조각상을 위한 지침을 작성하는 것이 믿기 힘들 정도로 어려울 수 있으며, 어떤 기계라도 빠르게 수행하기에는 불가능해 보이는 수준의 계산을 요구할 수 있다는 점입니다. 수년 동안 연구자들은 이러한 양자 상태를 만드는 것의 난이도가 특정 고전적 퍼즐을 푸는 난이도와 연결되어 있는지 궁금해했습니다. 만약 컴퓨터가 특정 유형의 어려운 퍼즐을 풀 수 있다면, 그에 상응하는 양자 상태를 즉각적으로 소환할 수도 있을까요? 이 질문은 두 거대한 분야, 즉 문제 해결의 난이도를 연구하는 분야와 양자 기계가 현실을 조작하는 방식을 연구하는 분야의 교차점에 놓여 있습니다.

텍사스 대학교 오스틴 캠퍼스의 아니루다 Aniruddha Sen의 새로운 논문은 이 질문에 놀라운 답을 제시합니다. 이 연구는 양자 컴퓨터가 특정 유형의 문제 해결 도우미를 사용할 수 있다면, 합리적인 시간 내에 극도로 정밀하게 원하는 모든 양자 상태를 생성할 수 있음을 입증합니다. 이 시나리오에서 사용된 도우미는 'NP 오라클(NP oracle)'로, 이는 복잡한 퍼즐의 제안된 해답이 옳은지 즉각적으로 검증할 수 있는 이론적 도구입니다. 이 연구 이전에는 훨씬 더 강력하고, 어쩌면 더 추상적인 유형의 도우미인 'PP 오라클'이 필요했습니다. Sen의 알고리즘은 컴퓨터가 만들고자 하는 양자 상태를 정의하는 가공되지 않은 숫자들을 엿볼 수 있다면, 더 약한 수준인 NP 도우미만으로도 충분하다는 것을 보여줍니다. 이 발견은 해답을 검증하는 능력이 양자 물질을 생성하는 데 있어 문제를 해결하는 능력만큼이나 강력하다는 것을 시사합니다.

이 성과의 핵심은 알고리즘이 상태를 구축하는 방식에 있습니다. 전통적으로 복잡한 양자 상태를 만드는 것은 건물을 한 층씩 쌓아 올리는 것과 같아서, 각 새로운 층은 아래층의 정확한 무게에 의존합니다. 이를 수행하기 위해 컴퓨터는 보통 엄청난 수의 가능성의 합을 계산해야 하며, 이는 일반적으로 강력한 PP 오라클을 필요로 하는 작업입니다. 그러나 Sen의 접근 방식은 영리한 2단계 전략을 사용합니다. 먼저, NP 오라클을 사용하여 상태의 대략적인 근사 버전을 얻습니다. 이것은 완벽하지는 않지만, 토대로 삼기에 충분할 만큼 근접합니다. 그다음, 알고리즘은 동일한 NP 오라클을 사용하여 이 근사치와 실제 목표 사이의 차이를 확인하는 두 번째 과정을 수행합니다. 이 두 가지를 비교함으로써 컴퓨터는 오차를 분리하고 수정할 수 있습니다.

이 수정을 작동시키기 위해 알고리즘은 '양자 거부 샘플링(quantum rejection sampling)'이라 불리는 기술을 채택합니다. 이 과정에서 컴퓨터는 올바른 부분은 약간 증폭되고 잘못된 부분은 억제되는 중첩 상태를 만듭니다. 이는 마치 맞는 모래알은 통과시키고 틀린 모래알은 걸러내는 체와 비슷하지만, '체'가 확률 파동의 수학적 회전으로 작용하는 양자 영역에서 일어납니다. 일단 오류가 걸러지면, '진폭 증폭(amplitude amplification)'이라는 마지막 단계가 올바른 결과의 확률을 거의 확실해질 때까지 높입니다. 그 결과, 오차 발생 확률이 1000조 분의 1보다도 작은 수준으로 매우 높은 정밀도를 가진 양자 상태가 만들어집니다.

또한 이 논문은 이 능력의 한계를 다룹니다. Sen은 NP 오라클이 이 과업을 효율적으로 달성할 수 있는 가장 약한 수준의 도우미라는 강력한 증거를 제시합니다. 연구에 따르면, 만약 컴퓨터가 쉬운 문제를 풀 수 있는 표준적인 'P 오라클'만을 사용하도록 제한된다면, 작업을 완수하기 위해 기하급수적으로 많은 질문을 던져야 합니다. 이는 쉬운 문제에서 NP 문제로 넘어가는 지점이 효율적인 양자 상태 생성을 위한 결정적인 임계값임을 의미합니다. 저자는 더 약한 오라클을 사용하는 알고리즘이 합리적인 시간 내에 근본적인 탐색 문제를 해결하는 데 실패함을 보여줌으로써, 이 특정 양자 과업에 더 단순한 도구를 사용할 가능성을 사실상 배제하며 이를 증명합니다.

알고리즘의 메커니즘을 넘어, 이 연구는 양자 복잡도 이론 전반에 중요한 시사점을 던집니다. 이는 양자 상태를 준비하는 어려운 작업, 즉 숨겨진 증인을 찾는 과정이 해당 상태를 설명하는 숫자를 계산하는 더 단순한 작업으로 환원될 수 있음을 시사합니다. 이는 양자 증명을 위한 복잡도 클래스인 QMA의 양자 세계와 NP의 고전 세계를 연결합니다. 또한 이 연구 결과는 더 큰 질문으로 향하는 문을 열어줍니다. 만약 우리가 NP 오라클로 어떤 양자 상태든 만들 수 있다면, 동일한 도구를 사용하여 모든 양자 연산, 즉 유니터리(unitary)를 구축할 수도 있을까요? 이 논문이 이 더 큰 퍼즐을 해결하지는 못하지만, 동일한 기술이 더 일반적인 문제인 양자 유니터리 합성에도 적용될 수 있음을 시사하며 명확한 경로를 제시하고 있습니다.

이 연구는 제한된 자원으로 양자 컴퓨터가 무엇을 성취할 수 있는지에 대한 우리의 이해를 정교화하는 작업입니다. 상대적으로 겸손한 수준의 오라클만으로도 모든 양자 상태를 생성할 수 있음을 보여줌으로써, 이 논문은 이론적 가능성과 실제 구현 사이의 간극을 좁힙니다. 이는 복잡한 양자 상태를 만드는 장벽이 극복할 수 없는 계산 능력의 벽이 아니라, 알려진 복잡도 클래스 범위 내에 있는 특정한 유형의 논리적 검증 문제임을 확인시켜 줍니다. 분야가 실제 양자 기계를 구축하는 방향으로 나아감에 따라, 이러한 빛의 상태를 조각하는 데 정확히 어느 정도의 도움이 필요한지 아는 것은 공학적 퍼즐의 필수적인 조각이 될 것입니다.