Computational Power of Clifford and Ising Quantum Computers

기술 요약: 클리포드(Clifford) 및 이싱(Ising) 양자 컴퓨터의 계산 능력

문제 정의
본 논문은 두 가지 제한된 양자 계산 모델인 클리포드 양자 컴퓨터와 이싱 양자 컴퓨터(이싱 애니온 기반의 위상 양자 컴퓨터)의 정밀한 계산 능력을 조사한다. 클리포드 회로를 고전적으로 효율적으로 시뮬레이션할 수 있다는 점(고테스만-클리니 정리)은 잘 알려져 있으나, 그 역관계—즉, 클리포드 컴퓨터가 고전적 계산을 효율적으로 시뮬레이션할 수 있는지 여부—는 미묘한 복잡도 이론적 문제로 남아 있다. 또한, 이싱 애니온 시스템에서의 브레이딩(braiding) 연산이 클리포드 게이트에 해당한다는 것은 알려져 있으나, 측정(특히 간섭계 측정)의 추가가 이싱 양자 컴퓨터의 계산 능력을 클리포드 회로 이상으로 향상시키는지 여부는 미해결 과제였다. 저자들은 이 컴퓨터들을 위한 모델을 엄격하게 정의하고, 이들이 결정하는 복잡도 클래스를 규명하며, 측정이 이싱 모델에 힘을 더하는지를 판별하고자 한다.

방법론
저자들은 복잡도 이론과 위상 양자 장론(구체적으로 유니터리 모듈러 카테고리, UMC)의 결합을 활용한다.

1. 복잡도 이론 프레임워크: 논문은 "회로 생성기"(양자 회로 기술을 생성하는 고전적 기계)의 역량에 기초하여 클리포드 계산의 다양한 모델을 정의한다. 저자들은 입력에 완전히 접근할 수 있는 생성기와 입력 길이만을 보는 생성기를 구분한다. 저자들은 $\oplus L$ (parity-L) 복잡도 클래스를 활용하여, 이 클래스가 CNOT 회로의 시뮬레이션으로 로그 공간 환원 가능한 문제들과 동등함을 증명한다. 또한, 제한된 입력 접근성을 가진 클리포드 계산을 모델링하기 위해 새로운 복잡도 클래스인 $P_{USC}$와 $L_{USC}$ (다항 시간 및 로그 공간 균일 스테빌라이저 회로)를 도입한다.
2. 아핀 언어(Affine Languages): 저자들은 이진 인코딩에 대한 $\mathbb{F}_2$ 상의 선형 방정식으로 결정 가능한 "아핀 언어"를 정의한다. 저자들은 언어가 아핀하기 위한 필요충분조건으로서 "직사각형 조건(rectangle condition)"과 "XOR 분리 가능성(XOR separability)"을 확립한다.
3. 위상적 시뮬레이션: 이싱 양자 컴퓨터를 위해, 저자들은 이싱 유니터리 모듈러 카테고리(Ising UMC)의 그래픽 계산법을 사용한다. 저자들은 이싱 애니온의 조밀한 큐비트 인코딩을 분석한다. 저자들은 $F$-move(결합성)와 $R$-move(브레이딩)를 사용하여 브레이딩 연산과 간섭계 측정을 기저 상태들의 선형 결합으로 수학적으로 분해한다. 저자들은 이러한 연산들이 특정 클리포드 게이트 및 파울리 측정에 대응함을 입증한다.

주요 기여 및 결과

• 클리포드 계산의 규명:

  • 제한 없는 입력: 만약 회로 생성기가 입력에 완전히 접근할 수 있고 다항 시간 내에 작동한다면, 결정되는 문제의 클래스는 단순히 $P$이다(스테빌라이저 회로는 효율적으로 시뮬레이션 가능하므로).
  • 제한된 입력 (로그 공간 생성기): 만약 생성기가 로그 공간으로 제한되고 전체 입력에 접근할 수 있다면, 결정되는 문제의 클래스는 정확히 $\oplus L$이다.
  • 제한된 입력 (길이 전용 생성기): 만약 생성기가 (입력 내용에는 눈을 감고) 입력 길이만을 본다면, 저자들은 $P_{USC}$와 $L_{USC}$를 정의한다. 저자들은 $P_{USC}$가 정확히 $P$에 포함된 아핀 언어($AFF \cap P$)임을 증명한다. 또한 $L_{USC}$가 모든 $L$ 내의 아핀 언어를 포함하며, $\oplus L$ 내의 아핀 언어에 포함됨($AFF \cap L \subseteq L_{USC} \subseteq AFF \cap \oplus L$)을 보여준다.
  • 복잡도 분리 함의: 본 논문은 만약 클리포드 양자 컴퓨터(로그 공간 생성기 사용 시)가 $P$의 모든 문제를 효율적으로 해결할 수 있다면, 이는 $P \neq PSPACE$임을 의미한다는 상세한 증명을 제공한다. 이는 $\oplus L \subseteq SPACE((\log n)^2)$이며, 공간 계층 정리(space hierarchy theorem)에 의해 $PSPACE$에 엄격히 포함되기 때문이다.

• 이싱 계산의 규명:

  • 브레이딩: 저자들은 조밀한 인코딩에서의 이싱 애니온 브레이딩이 클리포드 게이트(위상을 제외한 $\sqrt{X}$ 및 $CZ$)에 대응함을 확인한다. 이는 고전적으로 시뮬레이션 가능하다.
  • 측정: 논문의 두 번째 주요 결과(정리 4.4)는 조밀한 큐비트 인코딩에서 이싱 애니온에 대한 모든 형태의 간섭계 측정이 투영 파울리 측정(projective Pauli measurements)과 동등함을 증명한다.
  • 시뮬레이션: 결과적으로, 저자들은 이싱 양자 컴퓨터가 임의의 간섭계 측정을 사용하더라도 고전적 확률론적 컴퓨터에 의해 효율적으로 시뮬레이션될 수 있음을 증명한다. 이는 이싱 애니온 시스템에 대한 고테스만-클리니 정리의 아날로그를 확립한다.

의의 및 주장
본 논문은 측정이 이싱 양자 컴퓨터의 계산 능력을 클리포드 한계 이상으로 향상시키지 않는다는 것을 입증하는 최초의 엄격한 수학적 증명을 제공함으로써, 특히 간섭계 측정에 대해 증명이 누락되었던 기존 문헌의 공백을 메웠다고 주장한다.

클리포드 컴퓨터와 관련하여, 본 논문은 회로 생성기의 역량에 따라 그 능력을 정의하는 방식의 미묘한 차이를 명확히 한다. 저자들은 (Aaronson과 Gottesman이 사용한 것처럼) 전체 입력을 보는 생성기를 가정하면 클래스가 $\oplus L$이 되지만, 입력 길이만을 보는 생성기를 사용하면 훨씬 더 제한적인 아핀 언어 클래스가 된다는 점을 강조한다. 저자들은 이러한 구분이 범용 양자 회로(BQP)와 비교했을 때 스테빌라이저 회로의 한계를 이해하는 데 매우 중요하다고 강조한다. 이는 BQP에서는 인코딩 변환이 자명하지만, 클리포드의 경우 아핀 변환에 국한된다는 점과 대조적이다.

논문은 마지막으로 $P \subseteq L_{STAB}$ (이것이 성립하면 $P$와 $PSPACE$가 분리됨), $L_{USC}$와 경계값 $AFF \cap L$ 및 $AFF \cap \oplus L$ 사이의 정확한 관계, 그리고 보조 큐비트(ancilla qubits)의 추가가 이싱 애니온이 전체 클리포드 군을 생성할 수 있게 하는지 여부 등의 미해결 과제들을 나열하며 마무리한다.