The cost of simulating classically tractable quantum circuits and dynamics

기술 요약: 클래식하게 추적 가능한 양자 회로 및 역학 시뮬레이션의 비용

문제 정의
본 연구에서 다루는 핵심 문제는 이론적으로 클래식 시뮬레이션이 가능한 양자 진화(quantum evolutions)를 시뮬레이션할 때의 실질적인 효율성입니다. 특정 구조를 가진 양자 프로세스(예: 클리포드 회로, 자유 페르미온 역학, 저엔탱글먼트 시스템)가 다항 시간 클래식 알고리즘을 가짐은 이미 확립되어 있으나, 이는 다항 시간 복잡도가 점근적(asymptotic) 성질이라는 점을 유의해야 합니다. 이는 다항 시간 복잡도가 반드시 클래식 시뮬레이션이 직접적인 양자 하드웨어 실행보다 실질적으로 선호될 수 있음을 보장하지는 않습니다.

저자들은 결정적인 격차를 식별합니다: 서로 다른 다항식 스케일링은 특히 비용이 많이 드는 전처리나 양자 데이터 획득이 필요할 때 매우 상이한 계산 비용을 초래할 수 있습니다. 본 논문은 다음과 같은 질문을 던집니다: 만약 양자 진화가 클래식하게 시뮬레이션 가능하다면, 이를 클래식하게 시뮬레이션하는 것이 양자 하드웨어에서 실행하는 것보다 실제로 자원 효율적인가? 이 질문은 알려지지 않은 입력 상태에 대한 정보를 획득하는 비용을 고려할 때, 클래식 시뮬레이션 가능성이 유한한 시스템 크기에서는 보장되지 않을 수 있다는 사실에 의해 동기 부여되었습니다.

방법론
저자들은 $T$개의 회로 인스턴스에 대해 기대값 $f_U(\rho, O) = \text{Tr}[U\rho U^\dagger O]$를 추정하기 위해 두 가지 계산 경로를 비교합니다:

1. 양자 시뮬레이션 (QS): 양자 하드웨어에서의 직접 실행. 양자 장치가 상태를 준비하고, 진화시키며, 측정합니다. 클래식 컴퓨터는 결과를 처리하고 파라미터를 업데이트합니다.
2. 클래식 시뮬레이션 (CS): 양자 진화를 다항 시간 클래식 계산(대리 모델, surrogate)으로 대체하는 "양자 영감(quantum-inspired)" 접근 방식입니다. 결정적으로, 만약 초기 상태 $\rho$를 알 수 없는 경우, CS는 $\rho$를 특징짓기 위한 초기 양자 데이터 획득 단계(예: 클래식 섀도우 또는 토모그래피)를 필요로 할 수 있습니다. 이 데이터는 이후의 회로 인스턴스들을 위해 재사용됩니다.

비교에는 세 가지 자원 지표가 사용됩니다:

• 양자 샘플 복잡도 (Quantum Sample Complexity): $\rho$의 복사본(회로 샷)이 필요한 횟수.
• 양자 시간 복잡도 (Quantum Time Complexity): 단일 샘플을 위한 회로 깊이.
• 클래식 시간 복잡도 (Classical Time Complexity): 기초적인 클래식 연산의 횟수.

분석은 클래식하게 시뮬레이션 가능한 7가지 회로 제품군을 다룹니다:

1. 클리포드 회로 (Clifford circuits)
2. 얕은 국소 회로 (Hardware Efficient Ansatz)
3. 매치게이트 (Matchgate, 자유 페르미온) 회로
4. $S_n$-등변 회로 ($S_n$-equivariant circuits)
5. $U(1)$-등변 회로 ($U(1)$-equivariant circuits)
6. 양자 합성 신경망 (QCNNs)
7. ADAPT-VQE 회로

각 제품군에 대해 저자들은 QS와 CS의 자원 복잡도를 도출하며, 일회성 비용(예: 대리 모델 구축, 상태 데이터 획득)과 인스턴스당 비용(예: 새로운 파라미터에 대한 대리 모델 평가)을 구분합니다. 이들은 Gottesman-Knill 시뮬레이션, g-sim (리 대수적 시뮬레이션), Pauli Propagation, 그리고 Majorana Propagation과 같은 프레임워크를 활용합니다.

주요 결과
본 논문은 이론적 복잡도 경계를 대표적인 하드웨어 사양(IonQ, IBM, Google, Rigetti, Quantinuum)과 클라우드 가격 모델을 사용하여 추정된 벽시계 시간(wall-clock time) 및 화폐 비용으로 변환합니다.

1. 다항 시뮬레이션 가능성 $\neq$ 실질적 이점: 다항 시간 클래식 알고리즘의 존재가 유한한 시스템 크기에서 CS가 QS보다 빠르거나 저렴하다는 것을 보장하지는 않습니다. 상대적인 이점은 인스턴스의 수($T$)와 지배적인 비용의 특정 다항 차수에 크게 의존합니다.
2. 일회성 비용과 인스턴스당 비용 간의 트레이드오프:
   • QS는 모든 인스턴스에 대해 샘플링 및 회로 실행 비용을 발생시킵니다.
   • CS는 종종 대규모의 일회성 양자 데이터 획득 및 전처리 비용을 발생시키지만, 이후의 인스턴스당 대리 모델 평가 비용은 낮습니다.
   • 초기 오버헤드를 상쇄할 만큼 $T$가 충분히 커질 때만 CS가 더 효율적이게 되는 "교차점(crossover point)"이 존재합니다.
3. 입력 상태에 대한 지식의 영향:
   • 만약 입력 상태가 클래식하게 알려져 있다면 (예: ADAPT-VQE의 Hartree-Fock), CS는 양자 데이터 획득 과정을 완전히 피할 수 있으므로 훨씬 빠르고 저렴할 수 있습니다.
   • 만약 입력 상태를 알 수 없다면, 이를 특징짓는 비용(섀도우를 통한)은 CS를 매우 비싸게 만들 수 있으며, 이는 이후의 시뮬레이션이 다항 시간임에도 불구하고 CS를 실행 불가능하게 만들 수 있습니다.
4. 페르미온 국소성 및 시스템 크기: Matchgate 회로의 경우, 관측량의 페르미온 국소성($\kappa$)이 CS 비용에 극심한 영향을 미칩니다. 높은 $\kappa$(예: $\kappa=6$)는 클래식 텐서 수축 비용($O(Tn^7)$)과 섀도우 샘플 복잡도를 증가시켜, CS가 다항 점근적 스케일링을 가짐에도 불구하고 중간 규모의 시스템 크기에서는 QS가 더 빠른 경우가 많습니다.
5. 벽시계 시간 vs 화폐 비용: 벽시계 시간 측면에서 더 빠른 접근 방식이 반드시 가장 저렴한 것은 아닙니다.
   • CS는 반복적인 양자 실행 시간을 줄일 수 있지만, 대규모의 일회성 양자 데이터 획득 예산을 필요로 할 수 있습니다.
   • 작은 $T$에 대해서는 QS가 더 저렴한 경우가 많으며, 큰 $T$에 대해서는 CS가 더 저렴해질 수 있지만, 그 교차점은 하드웨어 플랫폼과 회로 제품군에 따라 달라집니다.
6. 메모리 제약: 본 논문은 메모리 요구량(공간 복잡도)이 시간보다 더 심각한 병목 현상이 될 수 있음을 강조합니다. 예를 들어, 대규모 시스템을 위한 클래식 섀도우 데이터나 중간 텐서를 저장하는 것은 테라바이트 단위의 메모리를 요구할 수 있으며, 이는 실행 시간 추정치가 포착하지 못하는 물리적 제약을 부과합니다.

의의 및 주장
본 논문은 다항 자원을 가진 클래식 시뮬레이션 가능성의 보장만으로는 선호되는 구현 방식을 결정하기에 불충분하다고 결론짓습니다.

• 효율성의 구별된 개념들: 클래식 시뮬레이션 가능성, 벽시계 시간 이점, 그리고 화폐적 이점은 서로 구별되는 개념입니다. 어떤 방법은 다항 시간 내에 시뮬레이션 가능하더라도 큰 상수 계수, 높은 차수의 다항식, 또는 값비싼 일회성 오버헤드로 인해 실질적으로 실행 불가능할 수 있습니다.
• 맥락 의존성: QS와 CS 사이의 선택은 특정 문제 파라미터, 즉 인스턴스 수($T$), 입력 상태에 대한 지식, 관측량의 국소성, 그리고 특정 하드웨어 접근 비용에 따라 달라집니다.
• 실무적 지침: 본 연구는 클래식하게 시뮬레이션 가능한 양자 계산을 언제 실제로 클래식하게 실행해야 하는지를 평가하기 위한 프레임워크를 제공합니다. 이는 알려지지 않은 입력 상태를 가진 문제나 높은 페르미온 국소성을 가진 문제의 경우, 다항 시간 클래식 알고리즘이 존재함에도 불구하고 직접적인 양자 실행이 여전히 더 자원 효율적인 옵션이 될 수 있음을 시사합니다.

저자들은 본 분석이 확정적인 하드웨어 벤치마크라기보다는 유한한 자원에 대한 비교임을 강조하며, 오류 완화(error mitigation), 결함 허용(fault tolerance), 병렬화 등의 요소가 이러한 정량적 교차점을 변화시킬 수 있다고 언급합니다. 그러나 "일회성 오버헤드 대 반복 샘플링 비용"이 실질적 효율성을 결정한다는 근본적인 메커니즘은 견고하게 유지됩니다.