Verifiable quantum advantage in extremely low depth

양자 컴퓨터의 진정한 힘을 이해하려는 탐구 속에서, 과학자들은 끊임없이 매우 단순해 보이는 질문을 던진다: 클래식 컴퓨터가 풀 수 없는 문제를 해결하기 위해 실제로 얼마나 많은 양자 기계적 장치가 필요한가? 수십 년 동안 지배적인 견해는 양자 시스템이 결정적인 우위를 점하기 위해서는 수천 개의 연산을 길고 복잡한 시퀀스로 엮어내는, 복잡하고 깊은 계산을 수행해야 한다는 것이었다. 이러한 깊이가 일반적인 컴퓨터에는 숨겨져 있는 가능성을 탐색하는 기계의 독특한 능력의 원천이라고 생각되었다. 그러나 새로운 연구 흐름은 이러한 직관에 도전하며, 단 몇 번의 연산만을 수행하는 가장 제한적이고 얕은 버전의 양자 회로가 여전히 최고의 클래식 알고리즘을 능가할 수 있는지 조사하고 있다. 이 문제의 이해관계는 매우 높다. 왜냐하면 만약 이러한 최소한의 양자 시스템이 어려운 문제를 풀 수 있다면, 이는 양자 우위가 단순히 거대하고 오류가 발생하기 쉬운 기계의 특징이 아니라, 심지어 가장 단순한 양자 구조의 근본적인 속성임을 증명하는 것이기 때문이다. 결정적으로, 이러한 우위가 유용하기 위해서는 표준 컴퓨터를 사용하는 인간 관찰자가 결과를 빠르고 확실하게 검증할 수 있어야 하며, 이를 통해 이론적 가능성을 실질적인 테스트로 전환할 수 있어야 한다.

한 연구자가 이제 이 현상을 입증하는 특정한 수학적 퍼즐을 설계했다. 그는 양자 컴퓨터가 믿을 수 없을 정도로 얕은 회로를 사용하여 해결할 수 있는 과업을 설계했는데, 이 회로는 너무 짧아서 기본적인 논리 게이트 수준을 겨우 넘어서는 정도이다. 그러나 동일한 퍼즐을 푸는 것은 특정 표준 수학적 난제들이 유효하다는 가정하에, 합리적인 시간 내에 작동하는 그 어떤 클래식 컴퓨터에게도 사실상 불가능하다. 이 성취를 특히 놀랍게 만드는 것은 그 해답이 '블랙박스'가 아니라는 점이다. 클래식 관찰자는 답을 효율적으로 확인하고 양자 기계가 실제로 그 과업을 수행했음을 확증할 수 있다. 연구자는 두 가지 다른 방식의 양자 솔버를 구축함으로써 이를 달성했다. 첫 번째는 약간 더 깊지만 큐비트 간의 표준적이고 단순한 연결에만 의존하는 회로를 사용한다. 두 번째는 훨씬 더 인상적인데, 문제의 크기가 커지더라도 깊이가 늘어나지 않는 상수 깊이(constant depth)를 사용하지만, 한 번에 많은 입력을 처리할 수 있는 특수한 유형의 게이트를 필요로 한다. 두 버전 모두 클래식 컴퓨터가 실패하는 지점에서 성공하며, 둘 다 결과를 즉각적으로 검증할 수 있다. 또한, 언바운디드 팬-인(unbounded fan-in) 회로는 언바운디드 팬-아웃(unbounded fan-out) 회로로 시뮬레이션될 수 있기 때문에, 해당 과업은 후자에 의해서도 해결 가능하다. 다만 저자는 상수 깊이 언바운디드 팬-인 버전을 더 중요한 성취로 강조한다.

이 발견의 핵심은 연구자가 알려진 암호학적 도전을 이러한 얕은 기계에 적합한 형식으로 어떻게 변환했느냐에 있다. 그는 노이즈가 섞인 데이터에서 숨겨진 패턴을 찾는 것의 어려움으로 알려진 '오류를 포함한 학습(learning with errors)' 개념에 기반한 문제로 시작했다. 유사한 아이디어를 사용하여 양자 우위를 증명하려 했던 이전의 시도들에서, 양자 컴퓨터는 계산 중간에 측정을 수행하고 그 결과를 다시 기계에 피드백하여 다음 단계를 안내하는 긴 다단계 과정을 거쳐야 했다. 이러한 "상호작용적" 접근 방식은 양자 상태가 오랫동안 결맞음(coherence)과 안정성을 유지해야 함을 의미하며, 이는 유지하기 어려운 작업이다. 새로운 연구는 이를 완전히 우회한다. 연구자는 양자 컴퓨터가 단 하나의 짧고 끊김 없는 연산 시퀀스를 실행하고 마지막에 단 한 번의 측정만으로 결과를 얻을 수 있도록 문제를 인코딩하는 방법을 개발했다. 이는 중간 단계의 측정과 피드백의 필요성을 제거하여 하드웨어 요구 사항을 크게 단순화한다.

이 작업을 성공시키기 위해, 연구자는 이전 연구들에 사용된 것보다 약간 더 강력한 수학적 가설들에 의존해야 했다. 그는 모듈러 시스템에서 숫자를 더할 때 특정 정보 비트, 즉 캐리 비트(carry bits)가 어떻게 행동하는지에 관한 구체적인 조건을 도입했다. 이 가정은 아직 표준 수학에 의해 증명되지는 않았으나, 저자는 그 타당성을 뒷받침하는 강력한 증거를 제시했다. 그는 만약 클래식 컴퓨터가 이 퍼즐을 풀 수 있다면, 이는 밑바탕이 되는 수학적 가정들을 깨뜨리는 획기적인 사건을 의미하며, 이는 널리 불가능하다고 믿어지는 일이라고 주장했다. 결과는 얕은 양자 회로가 클래식하게 어려운 문제를 해결할 수 있는 충분한 내부 구조를 갖추고 있음을 보여주는 견고한 입증이다. 연구자는 양자 기계가 많은 가능한 입력들의 중첩 상태를 준비하고, 국소적이고 얕은 인코딩을 통해 이를 처리한 다음, 출력을 측정하여 솔루션을 인코딩하는 패턴을 드러낸다는 것을 보여주었다.

이 연구의 함의는 두 가지 측면에서 중요하다. 첫째, 이 연구는 이론적으로 가능한 영역과 근시-단기 양자 장치(near-term quantum devices)를 통해 실질적으로 달성 가능한 영역 사이의 간극을 좁힌다. 상수 깊이 회로가 이러한 우위를 달성할 수 있음을 보여줌으로써, 이 연구는 미래의 "양자성(quantumness)" 테스트가 현재의 엔지니어링 역량을 벗어난 거대하고 깊은 회로를 필요로 하지 않을 수도 있음을 시사한다. 둘째, 양자 역량과 클래식 역량 사이의 경계를 명확히 한다. 연구자는 자신의 결과가 언바운디드 팬-아웃 게이트(unbounded fan-out gates)를 사용하는 회로에도 적용된다고 명시했는데, 이는 그들의 상수 깊이 언바운디드 팬-인 모델보다 계산적으로 더 강력한 것으로 알려진 다른 유형의 강력한 연산이다. 대신, 그들의 성공은 특정 인코딩 구조와 기초가 되는 격자 문제(lattice problems)의 난이도에 의존한다. 이 연구는 범용 양자 컴퓨터를 구축하는 문제를 해결했다고 주장하거나, 이 얕은 회로들이 큰 수를 인수분해하거나 현재의 암호를 해독할 수 있다고 제안하는 것이 아니다. 오히려, 이는 명확하고 검증 가능한 샘플링 과업을 제공하는 것이다.

이 구성은 검증자가 증명자에게 공개 키를 보내는 챌린지-응답 프로토콜을 포함한다. 증명자는 양자 기계로서 양자 상태를 준비하고, 얕은 회로를 적용한 뒤, 숫자 세트를 반환한다. 검증자는 그 숫자들이 특정 관계를 만족하는지 확인한다. 만약 증명자가 클래식 컴퓨터라면, 최선의 전략을 사용하더라도 네 번 중 세 번 이상은 올바른 관계를 만들어내는 데 실패할 것이다. 반면 정직한 양자 기계라면 거의 매번 성공한다. 연구자는 자신의 양자 구현이 다항식 너비(polynomial width), 즉 문제의 크기에 따라 큐비트 수가 합리적으로 증가하면서도 깊이는 극도로 낮게 유지됨을 확인했다. 이러한 낮은 깊이, 클래식한 난해함, 그리고 효율적인 검증의 균형은 양자 우위의 최소 요건을 이해하는 데 있어 중요한 진전이다.

비록 이 연구가 아직 완전히 증명되지 않은 가정들에 의존하고 있지만, 저자는 자신의 결과를 이러한 수학적 믿음들에 조건부로 프레임화하며 신중을 기하고 있다. 그는 자신이 사용하는 특정 "캐리-프레디케이트(carry-predicate)" 가정이 이 분야의 새로운 추가 사항임을 인정하면서도, 그것이 타당할 가능성이 높다는 부분적인 증거를 제공했다. 이러한 투명성은 과학계가 해당 가정을 더욱 테스트하고 정교화할 수 있도록 보장한다. 또한 이 작업은 현재 접근 방식의 한계를 강조한다. 예를 들어, 특수한 팬-인 게이트 없이 표준 게이트만을 사용하도록 회로 깊이를 더 줄이는 것은 여전히 미해결 과제로 남아 있다고 언급했다. 연구자는 진정한 상수 깊이 회로를 단순한 게이트만으로 구현하는 것이 현재 찾기 어려운 새로운 수학적 구성을 필요로 할 수 있다고 제안한다.

궁극적으로, 이 논문은 양자 시스템이 최소한의 자원으로 클래식 시스템을 능가할 수 있는 구체적인 사례를 제공한다. 이는 추상적인 복잡도 이론에서 손에 잡히는 검증 가능한 프로토콜로 대화의 주제를 옮겨 놓았다. 깊은 회로와 중간 단계의 측정을 제거함으로써, 연구자는 양자 우위의 본질이 매우 얕은 구조 안에서도 발견될 수 있음을 보여주었다. 이 발견은 초기 양자 장치로 무엇이 가능할지에 대한 지평을 넓히며, 기계가 진정으로 양자 역학을 활용하고 있는지 테스트하기 위한 새롭고 엄격한 기준을 제공한다. 앞으로의 과제는 이러한 가정들을 정교화하고 유사한 기술이 다른 암호학적 과업에도 적용될 수 있는지 탐구하는 것이지만, 핵심 결과는 변함이 없다: 얕은 양자 회로가 클래식 컴퓨터에게는 어렵고 검증하기는 쉬운 문제를 실제로 해결할 수 있다는 것이다.