A polynomial-time classical sampler for noisy quantum circuits from statistical mechanics

기술 요약: 노이즈가 있는 양자 회로에 대한 다항 시간 고전적 샘플링

문제 정의
본 논문은 노이즈가 존재하는 상황에서 양자 우위(quantum advantage)의 한계를 규명하는 문제를 다룹니다. 이상적인 양자 컴퓨터는 고전 컴퓨터보다 지수적으로 뛰어난 성능을 발휘할 수 있지만, 실험적 장치들은 일반적으로 계산 능력을 저하시키는 노이즈의 영향을 받습니다. 기존의 일반적인 노이즈 회로에 대한 고전적 시뮬레이션 방법들은, 노이즈가 전역 상태를 사소한 균등 분포(uniform distribution)로 몰아넣기 위해서는 회로 깊이($d$)가 시스템 크기에 대해 로그 함수보다 빠르게 성장($d \sim \omega(\log n)$)해야 한다고 요구합니다. 여전히 남아있는 핵심적인 미해결 과제는, 노이즈 강도가 0이 아닐 때, 노이즈가 있는 양자 회로를 시스템 크기와 무관한 깊이(상수 깊이)에서도 고전적으로 시뮬레이션할 수 있는가 하는 점입니다. 구체적으로, 저자들은 "최악의 경우"를 가정했을 때, 노이즈가 있는 기하학적 국소 양자 회로가 출력 분포가 균등 분포로 수렴하기 전에 고전적으로 시뮬레이션 가능한지 조사합니다.

방법론
저자들은 통계 역학과 양자 정보 이론의 기법을 결합한 새로운 고전 샘플링 알고리즘을 개발했습니다. 핵심 방법론은 다음 세 단계로 구성됩니다:

1. 폴리머 모델로의 매핑 (Mapping to Polymer Models):
   저자들은 노이즈가 있는 양자 회로의 출력 분포의 주변 확률(marginal probabilities)을 통계 역학의 추상적인 폴리머 모델의 분배 함수(partition function)로 매핑합니다.

   • 격자를 변의 길이가 $2d$인 거친 입도(coarse-grained) 블록으로 분해합니다.
   • "폴리머"를 이 블лок들의 연결된 집합으로 정의합니다.
   • 폴리머의 가중치는 해당 폴리머의 서포트(support) 내로 제한된 파울리 관측량(Pauli observables)의 하이젠베르크 진화(Heisenberg evolution)를 통해 정의됩니다.
   • 회로의 기하학적 국소성 덕분에, 인접하지 않은 블록들은 서로 분리된 역방향 광추(backward light cones)를 가집니 다. 따라서 분배 함수는 호환 가능한(중첩되지 않고 인접하지 않은) 폴리머 구성들의 합으로 인수분해될 수 있습니다.

2. 절단된 클러스터 전개 (Truncated Cluster Expansion):
   분배 함수(및 그에 따른 로그 주변 확률)를 계산하기 위해 저자들은 클러스터 전개 기법을 사용합니다.

   • 이 알고리즘은 분배 함수의 로그를 "클러스터"들의 합으로 전개합니다.
   • 알고리즘은 이 전개를 $O(\log n)$개의 블록에 의해 지지되는 클러스터들만 합산하도록 절단합니다.
   • 이 근사의 정확도는 "가중치 감소(weight decay)" 성질, 즉 폴리머의 기여도가 그 크기(블록의 수)에 따라 지수적으로 감소해야 한다는 성질에 의존합니다.

3. 하이퍼컨트랙티비티(Hypercontractivity)를 통한 가중치 감소 증명:
   핵심적인 기술적 기여는 회로 깊이 $d$가 시스템 크기와 무관한 임계값을 초과할 때 폴리머 가중치가 지수적으로 감소함을 증명하는 것입니다.

   • 저자들은 **양자 하이퍼컨트랙티비티(quantum hypercontractivity)**와 데폴라라이징 채널(depolarizing channels)에 대한 $\ell_2$-노름 수축(contraction) 경계 조건을 활용합니다.
   • 저자들은 노름 변환 경로를 구축합니다: $\ell_\infty$ 노름에서 시작하여, $\ell_{1+(4d)^D}$ 및 $\ell_2$ 노름을 거쳐, 최종적으로 $\ell_1$로 돌아옵니다.
   • 하이퍼컨트랙티비티를 적용하여 노름 간 전환을 수행하고, 데폴라라이징 채널의 수축성(Fact 5.2)을 사용하여 노이즈가 국소적으로 축적됨을 보여줍니다. 시스템은 기하학적으로 국소적이기 때문에, 노이즈에 의해 도입된 엔트로피(부피에 비례)는 생성되는 속도(경계에 비례)만큼 빠르게 탈출할 수 없으며, 이는 상관관계가 지수적으로 감소하는 국소적인 고온 상(high-temperature phase)을 유도합니다.

주요 결과
본 논문은 다음과 같은 주요 정리(비형식적)를 확립합니다:

• 정리: 단일 큐비트 데폴라라이징 노이즈 강도 $p$가 각 레이어 이후에 적용되는 유니탈 연산(unital operations)으로 구성된 모든 기하학적 국소 양자 회로에 대하여, 회로 깊이 $d$가 다음을 만족할 때 역 다항 시간의 전역 변동 거리(total variation distance) 및 주변 확률에 대한 상대 오차를 가지며 출력 분포로부터 샘플링할 수 있는 다항 시간 고전 알고리즘이 존재한다:
  $$d > d_{crit} = O(p^{-1} \log p^{-1})$$
• 알고리즘 능력: 제공된 알고리즘은 출력 분포의 임의의 주변 확률에 대한 완전 다항 시간 근사 스킴(FPTAS)입니다. 이는 노이즈가 없는 회로나 $O(p^{-1})$ 깊이 미만의 노이즈가 있는 회로에서는 고전적으로 어려운 작업으로 알려진 상대 오차 샘플링을 달성합니다.
• 복잡도 영역: 이 결과는 노이즈가 있는 회로의 복잡도 지형에서 새로운 영역을 식별합니다. 이전 연구들이 $O(p^{-1})$ 깊이까지의 어려움과 $\log n$ (또는 $\omega(\log n)$)으로 스케일링되는 시뮬레이션 가능성을 보여준 반면, 본 연구는 깊이가 $O(p^{-1} \log p^{-1})$를 초과하면 시스템 크기($n$)와 무관한 상수 깊이에서도 시뮬레이션이 가능하다는 것을 증명했습니다.

의의 및 주장
저자들은 자신들의 작업이 왜 비유니탈(non-unital) 또는 비국소적 자원(예: 피드백이 있는 중간 회로 측정 또는 큐비트 리셋)이 시스템 크기에 따라 스케일링되는 계산 깊이를 달성하는 데 근본적으로 필요한지에 대한 더 철저한 근거를 제공한다고 설명합니다.

• 양자-고전 전이 (Quantum-to-Classical Transition): 본 논문은 이 결과를 개방형 양자 시스템에서 열(엔트로피)의 축적에 의해 발생하는 "양자-고전 전이"로 해석합니다. 저자들은 열을 배출할 저온 욕조(low-temperature bath)가 없다면(즉, 비유니탈 연산이 없다면), 시스템은 자연스럽게 임계 깊이 이후 고전적으로 시뮬레이션 가능한 고온 상으로 전이된다고 상정합니다.
• 타이트함 (Tightness): 저자들은 $O(p^{-1})$ 미만의 깊이에서는 상대 오차 샘플링이 어렵다는 것이 증명되었으므로, 자신들의 경계가 로그 인자를 제외하고는 타이트하다고 언급합니다.
• 일반성: 이 결과는 제한된 게이트 세트나 특정 노이즈 모델에 국한되었던 이전 연구들을 포괄하며, 데폴라라이징 노이즈를 가진 모든 유니탈 연산 기반의 기하학적 국소 회로에 적용됩니다.
• 철학적 맥락: 이 연구는 "그 자체로서의" 개방형 양자 시스템의 계산 복잡도를 다루며, 노이즈가 있는 다체(many-body) 시스템의 자연스러운 역학이 통계 역학적 도구를 사용하여 엄밀하게 규명할 수 있는 고전성으로의 전이를 보인다는 점을 시사합니다.

본 논문은 특정 실험 장치를 시뮬레이션하거나 새로운 하드웨어를 제안하는 것이 아니라, 광범위한 클래스의 노이즈가 있는 양자 역학의 시뮬레이션 가능성에 대한 이론적 경계를 제공합니다. 이는 그러한 시스템에서의 "양자 우위"가 매우 얕은 깊이에서는 취약하며, 특정 비유탈 에러 수정 메커니즘이 사용되지 않는 한 제한적임을 시사합니다.