Linear Time & Storage Simulation of Non-Clifford Circuits via Symmetric Cartesian Collapse: A Trajectory-Based Solution to the Exponential Bottleneck

기술 요약: 대칭적 카테시안 붕괴(Symmetric Cartesian Collapse)를 통한 비클리포드 회로의 선형 시간 및 저장소 시뮬레이션

문제 정의
본 논문은 범용 양자 회로의 고전적 시뮬레이션을 가로막는 두 가지 주요 지수적 병목 현상을 식별한다:

1. 비클리포드 회전 병목 현상 (The Non-Clifford Rotation Bottleneck): 클리포드 연산(Gottesman-Knill 정리)은 효율적으로 추적할 수 있는 반면, 비클리포드 회전(예: T-게이트, 임의의 $R_z(\theta)$)은 복잡한 위상 인자를 도입한다. 표준 상태 벡터 프레임워크에서 이러한 연산은 희소 표현(sparse representation)을 밀집 배열로 강제하며, 이는 "매직 상태(magic state)" 추적을 위한 메모리 요구량을 급증시킨다.
2. 다중 큐비트 얽힘 병목 현상 (The Multi-Qubit Entanglement Bottleneck): 표준 시뮬레이터는 얽힌 상태를 표현하기 위해 텐서 곱에 의존하며, 이는 $2^n$개의 복소 진폭을 추적해야 함을 의미한다. 이는 약 50 큐비트를 넘어서는 시점에서 고전적 하드웨어의 치명적인 메모리 실패를 초래한다.

기존의 "밀집 행렬(Dense Matrix)" 시뮬레이터는 모든 확률적 결과를 동시에 계산하려고 시도하는데, 저자는 이것이 단일, 이산 궤적 모델링의 잠재력을 무시함으로써 양자 하드웨어의 물리적 본질을 근본적으로 오해하고 있다고 주장한다.

방법론: 대칭적 카테시안 붕괴 (Symmetric Cartesian Collapse, SCC)
제안된 해결책인 SCC는 밀집 상태 벡터 행렬을 3D 공간 벡터 리스트를 사용하는 궤적 기반 접근 방식으로 대체한다. 이 방법론은 세 가지 핵심 기둥에 기초한다:

1. 기하학적 표현 (좌표 등가성, Coordinate Equivalence):
   시스템은 각 큐비트를 $2^n$ 차원의 힐베르트 공간 내의 복소 진폭으로 저장하는 대신, 3D 유클리드 공간($\mathbb{R}^3$) 내의 실수 값 벡터 $V_i = (x_i, y_i, z_i)^T$로 표현한다. 계산 기저 상태는 Z축의 극점(poles)에 매핑되며, 중첩 상태는 X 및 Y 축에 매핑된다. 이는 전역 메모리 오버헤드를 $O(2^n)$에서 $O(n)$으로 감소시킨다.

2. 통합 기하학적 회전 (Unified Geometric Rotations):
   단일 큐비트 게이트(클리포드 및 비클리포드 모두)는 유니타리 행렬 곱이 아닌, **로드리게스 회전 공식(Rodrigues' Rotation Formula)**을 사용한 순수 3D 유클리드 회전으로 실행된다. 모든 게이트를 특정 축을 기준으로 하는 기하학적 벡터 회전으로 취급함으로써, 비클리포드 연산은 표준 클리포드 게이트와 동일한 선형 메모리 발자국과 실행 시간을 상속받아 "매직 상태"의 복잡성 페널티를 제거한다.

3. 양방향 얽힘 및 위상 킥백 (Bidirectional Entanglement and Phase Kickback):
   다중 큐비트 얽힘 연산(예: CNOT)은 전역 텐서 곱이 아닌 국소적이고 양방향인 궤적 연산으로 모델링된다:

   • 순방향 게이트 작용 (Forward Gate Action): 제어 큐비트의 로컬 Z-좌표가 타겟 게이트의 활성화 여부를 결정한다.
   • 역방향 위상 킥백 (Backward Phase Kickback): 타겟 큐비트의 게이트 축에 대한 기하학적 정렬이 제어 큐비트에 피드백 회전(위상 킥백)을 가한다. 이는 전역 위상 추적 없이 상관관계를 보존한다.

4. 대칭 3축 해상 (The Collapse):
   중간 단계에서의 정보 손실을 방지하기 위해, 프레임워크는 **카테시안 정점 공리(Cartesian Vertex Postulate)**를 도입한다. 상태를 단일 Z축으로 투영하여 X/Y 위상 정보를 파괴하는 대신, 시스템은 연속적인 벡터를 세 축 모두에 대해 대칭적으로 동시에 해상한다. 상태는 경계 입방체의 가장 가까운 정점 $V_{cartesian} = (\pm 1, \pm 1, \pm 1)$로 붕괴한다.

   • 이 해상은 확률 잠금(probability-locked) 방식이다: 임의의 축에서 $+1$ 또는 $-1$로 붕괴할 확률은 해당 좌표의 붕괴 전 기대값에 의해 결정된다.
   • 이 메커니즘은 이산 정수 공간 내에서 "방향성 이력(directional history)"과 위상 결맞음(phase coherence)을 보존한다.

주요 기여 및 결과
논문은 지수적 스케일링 문제를 해결한다고 주장하는 이론적 프레임워크와 경험적 벤치마크를 제시한다:

• 선형 스케일링 검증: 저자는 메모리 풋프린트가 게이트 깊이나 비클리포드 게이트의 존재와 관계없이 큐비트 수에 따라 엄격하게 선형적($O(n)$)으로 스케일링됨을 입증한다.
• 이중 하다마르 테스트 (The Double Hadamard Test): 가역성 테스트로서, $|0\rangle$ 상태가 하다마르 게이트를 거치고, 확률적 3축 붕괴를 거친 후, 두 번째 하다마르 게이트를 수행한다. 결과는 시스템이 $|0\rangle$ 상태로 성공적으로 돌아왔음을 보여주며, 이는 중간의 확률적 붕괴가 3축 정보를 유지할 경우 위상 결맞음을 보존함을 증명한다.
• 1000-큐비트 병렬 벨 테스트 (1000-Qubit Parallel Bell Test): 시뮬레이터는 500개의 얽힌 쌍을 포함한 1,000개의 큐비트를 시뮬레이션하기 위해 표준 소비자용 PC(8GB RAM)에서 실행되었다. 실험은 최종 빈도를 수집하기 위해 1,000개의 독립적인 궤적을 통해 1,000-큐비트 회로를 실행하는 과정을 포함했다.
  • 얽힘 보존: 시뮬레이터는 얽힌 쌍 사이의 강력한 상관관계를 유지했으며, 보고된 데이터에서 유효하지 않은 혼합 상태(예: $|01\rangle$ 또는 $|10\rangle$)의 경험적 빈도는 0.00%(반올림된 값)로 기록되었다.
  • 정확도: 다양한 회전 각도($\theta = 30^\circ, 45^\circ, 60^\circ$)에 대한 경험적 빈도는 이론적인 양자 역학 예측과 매우 유사했다 (예: $\theta=45^\circ$에 대해 84.9% 대 85.36%).
• 비클리포드 효율성: 벤치마크는 T-게이트와 임의의 회전이 포화된 회로가 클리포드 전용 회트와 동일하게 스케일링됨을 확인하였으며, 계산 비용의 지수적 급증을 보이지 않았다.

의의 및 주장
논문은 SCC 프레임워크가 양자 시뮬레이션의 패러다임을 "모든 가능성을 계산하는 것"에서 "단일, 확률 잠금 궤적을 추적하는 것"으로 근본적으로 전환한다고 주장한다.

• 50-큐비트 장벽 돌파: 저자는 이 방법이 1,000개 이상의 큐비트를 8GB RAM 머신에서 시뮬레이션할 수 있게 한다고 단언하며, 이 접근법이 "10초 미만"에 이를 수 있음을 언급한다 (단, 1,000-큐비트 벤치마크의 구체적인 실행 시간은 텍스트에 명시적으로 상세히 기술되지 않았다).
• 병목 현상의 역전: 이 연구는 지수적 메모리 병목 현상이 물리적 한계가 아니라 시뮬레이션 방법의 산물이라고 주장한다. 대칭적 3축 붕괴를 강제함으로써, 프레임워크는 전역 밀도 행렬 없이도 양자 결맞음을 보존한다.
• 하이브리드 잠재력: 궤적 기반 모델은 고전적 알고리즘이 양자 게이트와 직접 상호작용할 수 있는 새로운 아키텍처를 시사하며, 이는 쇼어 알고리즘(Shor's algorithm)의 복잡한 연산을 양자 궤적에 통합된 고전 함수로 취급함으로써 모듈로 산술과 같은 복잡한 연산을 단순화할 수 있음을 의미한다.

인정된 한계점
논문은 SCC가 지수적 메모리 요구량을 제거하지만, 계산적 과제를 **게이트 구성(gate construction)**으로 전이시킨다는 점을 겸허히 인정한다. 자연스럽게 단순한 기하학적 회전에 대응하지 않는 연산(예: 양자 푸리에 변환 또는 모듈로 산술)은 기본 회전 게이트의 시퀀스로 분해되어야 하며, 이는 합성 게이트를 위한 효율적인 설계 방법을 요구한다. 프레임워크는 모든 어려움을 제거하는 것이 아니라, 저장소에서 구성으로 그 위치를 옮기는 것이다.