기술 요약: 양자-고전 모멘트 쌍대성을 이용한 양자 최적화 및 회로 절단 인증

1. 문제 정의

본 논문은 근미래 양자 컴퓨팅의 두 가지 핵심 과제를 다룹니다:

1. 성능 인증의 부재: QAOA(Quantum Approximate Optimization Algorithm) 및 VQPM(Variational Quantum Power Method)과 같은 변분 양자 알고리즘(VQA)은 종종 엄격한 상태별 성능 보증을 제공하지 못합니다. 이들의 근사 비율(approximation ratios)은 빈번하게 인스턴스에 의존하거나 전역 최적해로의 수렴에 의존하므로, 노이즈가 있거나 조기 종료된 실행 상황에서의 인증 공백을 남깁니다.
2. 회로 절단 오버헤드: 제한된 하드웨어에서 실행하기 위해 대규모 양자 회로를 더 작은 서브 회로로 분해하는 것(회로 절단)은 최적의 이분할(bipartition)을 찾고자 할 때 NP-완전(NP-complete) 문제입니다. 기존의 휴리스틱은 종별 기하학적 가정이나 무차별 탐색에 의존하며, 측정 가능한 상관관계 데이터에 기반한 엄격한 오차 한계가 부족합니다.

저자들은 두 점의 파울리-Z 상관관계 데이터만을 사용하여 이 두 문제를 해결하기 위해 "양자-고전 모멘트 쌍대성"을 활용하는 통합 프레임워크를 제안합니다.

2. 방법론: 양자-고전 모멘트 사전 (The Quantum–Classical Moment Dictionary)

핵심 방법론은 임의의 양자 상태의 물리적 특성과 고전적인 합-의-제곱(Sum-of-Squares, SoS) 완화 공간 사이의 직접적인 매핑을 구축하는 것입니다.

2.1 매핑

$\rho$를 $n$개 큐비트 상의 임의의 양자 상태(밀도 행렬)라고 합시다. 저자들은 단일 큐비트 및 2-큐비트 파울리-Z 기댓값을 추출하여 행렬 $Y_{\text{quantum}}$를 구성하는 매핑 $\Phi$를 정의합니다:
Y_{\text{quantum}} = \Phi(\rho) = \begin{pmatrix} 1 & \langle Z_1 \rangle_\rho & \cdots & \langle Z_n \rangle_\rho \\ \langle Z_1 \rangle_\rho & 1 & \cdots & \langle Z_1 Z_n \rangle_\rho \\ \vdots & \vdots & \ddots & \vdots \\ \langle Z__n \rangle_\rho & \langle Z_n Z_1 \rangle_\rho & \cdots & 1 \end{pmatrix}
여기서 $\langle O \rangle_\rho = \text{Tr}(\rho O)$입니다.

2.2 이론적 토대

정리 2.1 (엄격한 실행 가능성 유지): 본 논문은 어떠한 유효한 양자 상태 $\rho$에 대해서도, 결과 행렬 $Y_{\text{quantum}}$는 항상 고전적인 차수-2 SoS 콘(degree-2 SoS cone, 즉 Goemans–Williamson SDP 완화)의 실행 가능한 점임을 증명합니다.

• 증명 논리: 대각 성분이 1인 이유는 $Z_i^2 = I$이기 때문입니다. 행렬이 양의 준정부호(positive semidefinite, PSD)인 이유는 임의의 벡터 $v$에 대해 $v^T Y_{\text{quantum}} v = \text{Tr}(\rho O_v^2)$이며, 여기서 $O_v$는 에르미트 관측량입니다. $\rho$와 $O_v^2$가 모두 PSD이므로, 이들의 트레이스 곱은 비음수입니다.

이 관찰은 "보편적 안전망"을 생성합니다. 양자 상태 자체가 연속적인 세미데피니트 콘의 기하학적 구조 내에서 능동적인 최적화 프록시 역할을 수행하며, 추가적인 능동적 SDP 풀이를 요구하지 않습니다.

3. 주요 기여

3.1 Max-Cut을 위한 보편적 인증

$Y_{\text{quantum}}$가 차수-2 SoS SDP에 대해 실행 가능함을 확립함으로써, 저자들은 Goemans–Williamson(GW) 랜덤 하이퍼플레인 라운딩을 양자 유도 행렬에 직접 적용합니다.

• 결과: 어떤 상태 $\rho$에 대해서도, GW 라운딩을 통해 얻은 기대 컷 가중치 $E[\text{Cut}]$은 다음을 만족합니다:
  $$E[\text{Cut}] \geq \alpha_{GW} \langle H \rangle_\rho$$
  여기서 $\alpha_{GW} \approx 0.87856$이고 $\langle H \rangle_\rho$는 Max-Cut 해밀토니안의 양자 기댓값입니다.
• 의의: 이는 모든 상태에 대해 근사 비율에 대한 인증된 하한을 제공하며, 성능 인증을 알고리즘의 수렴으로부터 분리합니다. 이는 알고리즘이 노이즈가 있거나, 지역 최솟값에 갇히거나, 조기에 종료된 경우에도 유효합니다.

3.2 상관관계 기반 회로 절단

동일한 모멘트 행렬은 상태의 얽힘 구조를 포착하여, 기저 유니터리 $U$의 텐서 곱 분해를 감지하는 다항 시간 절차를 가능하게 합니다.

• 정확한 감지: 만약 유니터리 $U$가 $A_S \otimes B_T$로 인수분해된다면, 연결된 상관관계 $C_{ij} = \langle Z_i Z_j \rangle - \langle Z_i \rangle \langle Z_j \rangle$는 모든 $i \in S, j \in T$에 대해 0이 됩니다. 저자들은 임계값 처리가 된 상관관계를 사용하여 그래프를 구축할 것을 제안하며, 여기서 끊어진 컴포넌트들이 정확한 절단 지점을 나타냅니다.
• 근사적 절단: 정확한 곱 상태가 아닌 상태의 경우, 이 방법은 $|C_{ij}|$를 엣지 가중치로 사용하는 가중 최소 컷 문제를 정식화하여 인터-파티션(inter-partition) 상관관계를 최소화하는 이분할을 찾습니다.
• 오차 한계: 저자들은 원래의 상태와 최적의 곱 상태 근사치 사이의 거리를 정량화하는 엄격한 오차 한계를 제공합니다:
  • 단일 프로브(Single-probe): 거리는 $\sqrt{I(S:T)}$에 의해 제한됩니다 (여기서 $I(S:T)$는 양자 상호 정보량입니다).
  • 글로벌 인증: Choi 상태를 사용하여, 저자들은 $\|U - A_S \otimes B_T\|_\infty$에 대한 연산자 노름 거리에 대한 한계를 도출하여, 특정 상태뿐만 아니라 임의의 입력에 대해서도 분해가 유효함을 보장합니다.

4. 결과 및 검증

본 프레임워크는 두 가지 측면에서 수치적으로 검증되었습니다:

1. 변분 알고리즘 (QAOA 및 VQPM):

   • QAOA ($p=1$ on 4-Cycle): 연구 결과, GW 라운딩된 하한 $F(\gamma, \beta)$는 원시 에너지 $E_\rho$가 최적이 아닐 때조차 최적화 궤적 전체에서 해석적 바닥값 $\alpha_{GW} E_\rho$보다 엄격히 높게 유지됨을 입증했습니다.
   • VQPM: 이 방법은 "큐비트 락킹(qubit locking)" 휴리스틱을 포함한 Variational Quantum Power Method에 적용되었습니다. 결과에 따르면, 모멘트 행렬 인증은 공격적인 락킹 이후에도 유효하게 유지되어, 조기 수렴에 대한 안전망을 제공했습니다. 인증된 하한은 실제 성능을 일관되게 추적하였으며, 상태가 계산 기저 솔루션에 도달했을 때 정확한 Max-Cut 값으로 수렴했습니다.

2. 회로 절단 (무작위 상태):

   • $n=6$ 큐비트에 대한 Haar-무작위 상태를 사용하여, 저자들은 상관관계 기반 절단을 전수 조사(exhaustive search)와 비교 테스트했습니다.
   • 정확도: 모멘트 행렬을 통해 발견된 절단의 상호 정보량($I_Y$)은 전수 조사로 발견된 최적의 상호 정보량($I_{\text{best}}$)과 거의 완벽하게 일치했습니다.
   • 오차 한계: 실제 상태와 재구성된 곱 상태 사이의 2-노름 오차는 이론적 한계인 $\sqrt{I(S:T)}$ 미만으로 일관되게 관찰되었습니다.
   • 성공률: 정확한 곱 상태의 경우, 알고리즘은 다양한 서브시스템 크기에 걸쳐 100%의 성공률로 올바른 텐서 곱 구조를 식별했습니다.

5. 의의 및 주장

본 논문은 다음과 같은 근본적인 구조적 통찰을 주장합니다: 임의의 양자 상태의 2-큐비트 파울리-Z 상관관계 행렬은 자동으로 고전적 차수-2 SoS 콘의 실행 가능한 점이 됩니다.

이 발견은 세 가지 주요한 함의를 갖습니다:

1. 수동적 인증 (Passive Certification): 경계값을 찾기 위해 능동적으로 SDP를 푸는 이전 연구들과 달리, 이 방법은 양자 장치를 단순히 측정 데이터를 생성하는 용도로만 사용합니다. 따라서 인증은 표준 에너지 추정 외에 추가적인 양자 자원을 요구하지 않는 사후 처리 단계입니다.
2. 수렴과 인증의 분리: 이는 변분 알고리즘을 위한 "안전망"을 제공하여, 클래식 최적화 도구가 수렴했는지 또는 하드웨어에 노이즈가 있는지와 관계없이 성능 하한을 보장합니다.
3. 효율적인 회로 절단: 이는 엄격한 오차 한계를 가진 다항 시간의 기하학 불가지론적(geometry-agnostic) 회로 절단 방법을 제공하며, 이를 통해 최적의 절단을 찾는 NP-완전 복잡성을 우회합니다.

저자들은 이 연구를 양자 최적화와 고전적 볼록 완화(convex relaxation) 사이를 잇는 "보편적 안전망"으로 규정하며, 고차 상관관계 측정이나 복잡한 토모그래피 없이도 솔루션의 품질(Max-Cut)과 회로의 구조(절단) 모두에 대한 엄격한 보증을 제공한다고 강조합니다.