Automorphism-Assisted QAOA: A Classical-Estimator Speedup for QAOA Simulation on Graphs with Non-Trivial Symmetry

기술 요약: 오토모피즘 보조 QAOA (AA-QAOA)

문제 정의
양자 근사 최적화 알고리즘(QAOA)은 가중치가 없는 MaxCut 문제와 같은 NP-어려운 조합 최적화 문제를 해결하기 위한 선도적인 하이브리드 양자-고전 접근 방식입니다. 특히 QPU(양자 프로세싱 유닛) 접근이 제한되어 고전 상태벡터 시뮬레이터에 의존하는 연구 그룹들에게 있어, QAOA 연구의 주요 병목 현상은 고전적 최적화 루프의 계산 비용입니다. 구체적으로, 매 최적화 반복 단계마다 문제 해밀토니안 $H_C$의 기댓값을 계산해야 합니다. $|E|$개의 에지를 가진 그래프의 경우, 표준 상태벡터 추정기는 $\langle Z_i Z_j \rangle$ 형태의 항 $|E|$개를 집계합니다. 각 항은 상태벡터 진폭에 대해 $O(2^n)$ 번의 패스(pass)를 요구하므로, 최적화 반복당 발생하는 벽시계 시간(wall-time) 비용은 $O(|E| \cdot 2^n)$으로 스케일링됩니다. 이 집계 비용은 낮은 회로 깊이($p$)에서도 에지가 많은 그래프의 경우 전체 시뮬레이션 시간을 지배하는 경우가 많습니다.

방법론: 오토모피즘 보조 QAOA (AA-QAOA)
본 논문은 그래프의 대칭성을 활용하여 QAOA의 고전적 상태벡터 시뮬레이션을 가속화하는 방법인 AA-QAOA를 제안합니다. 핵심 통찰은 그래프의 비자명한 오토모피즘 군(automorphism group) $\text{Aut}(G)$를 가진 그래프에 대해, QAOA 안사츠(ansatz)가 $\text{Aut}(G)$의 작용에 대해 불변인 상태 $|\psi(\vec{\beta}, \vec{\gamma})\rangle$를 준비한다는 점입니다.

방법론은 다음과 같습니다:

1. 에지 궤도(Edge Orbit) 식별: Nauty 패키지를 사용하여 알고리즘은 그래프의 오토모피즘 군의 생성원(generators)을 계산합니다. 이 생성원들은 에지 집합 $E$를 동치 클래스(equivalence classes), 즉 궤도(orbits) $\tilde{S}_m$으로 분할하는 데 사용됩니다. 동일한 궤도 내의 에지들은 그래프의 대칭성 하에서 구조적으로 동일합니다.
2. 관측량 치환: 방법론은 전체 비용 해밀토니안 $H_C = \frac{1}{2} \sum_{(i,j) \in E} (1 - Z_i Z_j)$ 대신, 축소된 관측량 $H_{\text{red}}$를 사용합니다. 이 축소된 해밀토니안은 각 에지 궤도의 크기로 가중치를 둔 하나의 대표 ZZ 항만을 유지합니다:
   $$H_{\text{red}} = \frac{1}{2} \sum_{m=1}^{|O_E|} |\tilde{S}_m| (1 - Z_{i_m} Z_{j_m})$$
   여기서 $|O_E|$는 에지 궤도의 수입니다.
3. 정확한 등가성: 저자들은 표준 QAOA 안사츠에 의해 준비된 $\text{Aut}(G)$-불변 상태에 대해 $\langle H_{\text{red}} \rangle = \langle H_C \rangle$라는 기댓값이 동일함을 증명합니다. 결과적으로, 최적화 지형(optimization landscape), 최적 변분 파라미터 $(\vec{\beta}^*, \vec{\gamma}^*)$, 그리고 최종 근사 비율(approximation ratio)은 변하지 않습니다.
4. 파이프라인 구현: QAOA 안사츠 회로는 (표준 QAOA와 동일한 상태 준비를 보장하기 위해) 전체 해밀토니안 $H_C$를 사용하여 구축됩니다. 그러나 고전 최적화 루프 동안, 추정기는 오직 $|O_E|$개의 항을 사용하는 $H_{\text{red}}$를 사용하여 기댓값을 계산합니다.

주요 기여

• 고전적 집계 가속화: 주요 기여는 상태벡터 추정기의 고전적 후처리 비용을 줄이는 것입니다. 집계 비용은 반복당 $O(|E| \cdot 2^n)$에서 $O(|O_E| \cdot 2^n)$으로 감소합니다. 가속화 계수는 궤도 비율 $|E|/|O_E|$에 의해 결정됩니다.
• 역 인과적 원뿔(Reverse Causal Cone, RCC)과의 분리: 본 논문은 회로 깊이나 큐비트 범위를 줄이기 위해 RCC를 활용하는 이전 연구들과 자신의 메커니즘을 명확히 구분합니다. 저자들은 AA-QAOA의 가속화가 대표 RCC의 큐비트 범위와 독립적임을 입증했습니다. 단일 대표 에지의 RCC가 모든 큐비트를 포괄하는 경우라도(완전 그래프의 경우처럼), 가속화는 지속되는데 이는 절감이 양자 회로 실행이나 상태 진화가 아닌, 항들의 고전적 합산 과정에서 발생하기 때문입니다.
• 정확성: 이 방법은 근사가 아닌 정확한 치환을 제공합니다. $H_{\text{red}}$에 대한 최적화는 $H_C$에 대한 최적화와 동일한 해에 수렴합니다.

결과
저자들은 다양한 그래프 패밀리에 대해 $p=1$ 및 $p=2$ 레이어를 사용하여 AA-QAOA를 벤치마킹했습니다:

• 트리 구조 그래프: 최대 34개의 정점을 가진 이진 트리 및 균형 트리에 대해, 이 방법은 상당한 벽시계 시간 단축을 달밀했습니다. 34개 정점의 이진 트리의 경우, 최적화 시간은 전체 해밀토니안 사용 시 $>3600$초에서 축소된 해밀토니안 사용 시 $360.56$초로 감소하여 90% 이상의 단축을 보여주었습니다. 피크 메모리 사용량 또한 크게 감소했습니다.
• 진단 제어 실험: 메커니즘을 격리하기 위해 저자들은 다음을 테스트했습니다:
  • 완전 그래프 ($K_n$): 단일 에지 궤도($|O_E|=1$)를 가지며 대표 RCC가 모든 큐비트에 걸쳐 있음에도 불구하고, $K_{16}$은 약 $8\times$의 가속화를 보였습니다. 이는 가속화가 RCC의 큐비트 범위를 줄이는 것에 의존한다는 가설을 반박합니다.
  • 스타 그래프 (Star Graphs): 오버헤드가 최소화되었을 때 궤도 비율에 부합하는 가속화를 보여주었습니다.
  • 무작위 3-정규 그래프 (Random 3-Regular Graphs): 자명한 오토모피즘 군($|O_E| \approx |E|$)을 가진 그래프에서는 가속화가 관찰되지 않았으며, 이는 이득이 엄격하게 대칭성에 묶여 있음을 확인시켜 줍니다.
• 아키텍처 독립성: CPU 및 GPU 백엔드 모두에 대한 테스트를 통해 가속화가 고전적 집계 단계에 내재된 것이며 특정 하드웨어 가속기의 산물이 아님을 확인했습니다.
• 근사 비율: 테스트된 모든 인스턴스에서 근사 비율 $R_{\text{red}}$와 $R_{\text{full}}$은 최적화 오차 범위 내에서 동일하였으며, 이는 정확한 등가성에 대한 이론적 주장을 검증합니다.

의의 및 범위
본 논문은 AA-QAOA를 고전적 상태벡터 시뮬레이션 파이프라인을 위한 특화된 가속기로 포지셔닝합니다. 이는 QPU 접근 권한이 없는 연구 그룹들이 QAOA 연구를 수행하는 주요 도구입니다.

• 한계: 저자들은 AA-QAOA가 양자 프로세서(QPU) 상에서는 가속을 제공하지 않는다고 명시적으로 밝힙니다. 하드웨어 상에서는 관측되는 관측량과 상관없이 전체 회로가 실행되며, 대각 성분인 ZZ 항들의 집계는 $O(|E| \cdot 2^n)$의 비용을 발생시키는 상태벡터 시뮬레이션과 달리 고전 비트스트링에 대한 사소한 후처리 단계에 불과하기 때문입니다.
• 적용 가능성: 이 방법은 높은 대칭성을 가진 구조적 그래프(예: 트리, 사이클, 완전 그래프, 하이퍼큐브)에서 궤도 비율 $|E|/|O_E|$가 클 때 가장 유용합니다. 일반적인 비대칭 그래프(예: 무작위 3-정규 그래프)에서는 효과가 떨어집니다.
• 오버헤드: 오토모피즘 계산(Nauty 사용)에는 비용이 발생하지만, 이는 보고된 반복당 시간에서 상쇄되지 않는 비용입니다. 그러나 많은 최적화 반복이나 파라미터 스윕을 포함하는 전형적인 QAOA 연구에서, 이 사전 계산 비용은 누적된 시뮬레이션 절감액에 비해 무시할 수 있는 수준입니다.

요약하자면, AA-QAOA는 그래프 대칭성을 활용하여 양자 회로나 솔루션의 품질을 변경하지 않고도 비용 기대값 집계의 항 개수를 줄임으로써, 고전적 QAOA 시뮬레이션의 계산 병목을 줄이는 엄격하고 정확한 방법을 제공합니다.