기술 요약: 다양한 최적화 문제에 대한 Pauli Correlation Encoding의 벤치마크

1. 문제 정의

본 논문은 NISQ(Noisy Intermediate-Scale Quantum) 시대의 변분 양자 알고리즘(VQA)이 직면한 확장성 한계를 다룹니다. 구체적으로, 이 연구는 클래식 조합 최적화 문제를 인코딩할 때 필요한 큐비트의 수가 일반적으로 이진 변수의 수와 선형적으로 비례하여 증가하는 문제를 겨냥합니다. 이러한 선형적 스케일링은 현재 하드웨어에서 해결 가능한 문제의 크기를 제한합니다.

저자들은 $m$개의 이진 변수를 $m \gg n$인 다항식 개수의 큐비트 $n$을 사용하여 표현할 수 있는 최근 제안된 인코딩 방식인 **Pauli Correlation Encoding (PCE)**를 조사합니다. 핵심 문제는 PCE를 변분 프레임워크와 결합했을 때, 샷 기반 실행(shot-based execution) 및 하드웨어 노이즈의 제약 조건 하에서도 솔루션의 품질과 실행 가능성을 유지하면서 클래식 최적화 문제를 효과적으로 해결할 수 있는지 평가하는 것입니다.

2. 방법론

본 연구는 비용 함수가 PCE 체계에 맞게 조정된 파라미터화된 양자 회로(PQC)를 최적화하는 하이브리드 양자-클래식 프레임워크를 채택합니다.

2.1 인코딩 방식

PCE는 $m$개의 이진 변수 $\vec{z} \in \{-1, 1\}^m$를 부분 집합 $\Pi$인 무표식(traceless) Pauli string들의 기댓값으로 매핑합니다. 변수는 다음과 같이 복원됩니다:
$$z_i := \text{sgn}(\langle \Psi | \Pi_i | \Psi \rangle)$$
여기서 $|\Psi\rangle$는 양자 상태입니다. 인코딩은 항등(identity)이 아닌 $k$개의 Pauli 행렬의 텐서 곱으로 형성된 Pauli string을 선택하는 압축 차수(compression order) $k$를 사용합니다. 이를 통해 $n$개의 큐비트로 최대 $m = 3 \binom{n}{k}$개의 변수를 인코딩할 수 있습니다.

2.2 회로 안사츠(Ansatz) 및 최적화

• 안사츠(Ansatz): 문제 불가지론적(problem-agnostic)이며 하드웨어 효율적인 벽돌 구조(brick-like structure)가 사용됩니다. 이는 인접한 큐비트 상의 파라미터화된 단일 큐비트 회전($R_X, R_Y, R_Z$)과 2-큐비트 회전($R_{XX}, R_{YY}, R_{ZZ}$) 레이어를 교대로 배치합니다. 회로 깊이는 $O(m^{1-1/k})$로 스케일링됩니다.
• 완화(Relaxation): 최적화를 용이하게 하기 위해 이산적인 부호 함수(sign function)를 쌍곡 탄젠트($\tanh$)를 사용하여 완화합니다: $z_i := \tanh(\alpha \langle \Pi_i \rangle)$. 또한 기댓값이 0 근처에 집중되도록 하는 정규화 항도 포함됩니다.
• 클래식 최적화 도구: 로컬 미니마를 피하고 비용 경관(cost landscape)을 탐색하기 위해 그래디언트 프리(gradient-free) 최적화 도구인 차분 진화(Differential Evolution, DE)가 사용됩니다.
• 후처리(Post-processing): 완화된 솔루션에 대해 실행 가능성을 강제하고 솔루션 품질을 높이기 위해 클래식 후처리 단계가 적용됩니다 (예: MCP를 위한 비트 플리핑, BPP를 위한 빈 재할당, TSP를 위한 2-opt).

2.3 벤치마크 및 문제

프레임워크는 세 가지 클래식 문제에 대해 QOPTLib 벤치마크를 사용하여 평가됩니다:

1. 최대 컷 문제 (Maximum Cut Problem, MCP): 10개 인스턴스 ($N \in \{10, \dots, 300\}$).
2. 빈 패킹 문제 (Bin Packing Problem, BPP): 10개 인스턴스 ($N \in \{3, \dots, 14\}$).
3. 외판원 문제 (Travelling Salesman Problem, TSP): 10개 인스턴스 ($N \in \{3, \dots, 25\}$).

결과는 LeapHybridBQMSampler의 결과물을 포함하여 벤치마크의 참조 솔루션과 비교됩니다.

2.4 노이즈 및 실행 분석

연구에는 CUNQA 에뮬레이터(IBM Sherbrooke 백엔드 모사)를 사용한 **샷 기반 실행(shot-based execution)**에 대한 섹션이 포함되어 있습니다. 여기서는 다음을 분석합니다:

• 샷 수에 따른 평균 절대 오차(MAE) 및 최대 오차의 스케일링.
• 하드웨어 노이즈(게이트 비효율성, 결맞음 현상)가 기댓값 추정에 미치는 영향.
• 최적화 도구가 로컬 미니마를 탈출하는 데 노이즈가 기여할 수 있는 잠재적 역할.

3. 주요 기여 및 결과

3.1 조합 문제에 대한 성능

• 최대 컷 (MCP): PCE 프레임워크는 경쟁력 있는 성능을 달성합니다. 대부분의 인스턴스에서 근사 비율(approximation ratio)은 1에 가깝습니다. 높은 압축 차수($k$)는 모델의 표현력(변리 파라미터 증가)을 높여주기 때문에, 회로 깊이와의 트레이드오프에도 불구하고 일반적으로 더 나은 솔루션 품질을 제공합니다.
• 빈 패킹 (BPP): 이 접근 방식은 강력한 잠재력을 보여주지만 하이퍼파라미터에 매우 민감합니다.
  • 실행 가능성: 낮은 압축 차수($k=2, 3$)는 큰 규모의 인스턴스($N > 8$ 및 $N > 12$ 각각)에 대해 실행 가능한 솔루션을 생성하지 못합니다. 오직 $k=4$만이 테스트된 모든 인스턴스에서 일관되게 실행 가능한 솔루션을 생성합니다.
  • 품질: 후처리는 초기 솔루션을 크게 개선하여 종종 사용되는 빈의 수를 줄여줍니다. 이 방법은 광범위한 인스턴스에 대해 좋은 품질의 솔루션을 생성하지만, 문제 크기가 커짐에 따라 실행 가능성 비율이 감소합니다.
• 외판원 (TSP): BPP와 유사하게, 실행 가능성은 압축 차수에 크게 의존합니다. $k=2$는 $N > 10$인 인스턴스에서 실패하는 반면, $k \in \{3, 4\}$는 $N \le 15$에 대해 높은 실행 가능성을 유지합니다.
  • 솔루션 품질: 초기 솔루션은 특히 $k \in \{3, 4\}$인 경우 벤치마크 품질과 일치하거나 이를 상회합니다. 후처리(2-opt)는 최종 투어 길이를 일관되게 개선합니다.

3.2 하이퍼파라미터 민감도

연구는 완화된 변수의 이진화를 제어하는 하이퍼파라미터 $\alpha$의 결정적인 역할을 강조합니다.

• $\alpha$: 큰 값은 변수가 강력하게 이진화되도록 보장함으로써(즉, $\tanh$의 선형 영역을 피함) 일반적으로 더 나은 결과를 가져옵니다. 작은 $\alpha$ 값은 0.5 근처의 모호한 솔루션을 초래하여 재구성 품질을 저하시킵니다.
• $\beta$ (정규화): 성능 향상을 목적으로 함에도 불구하고, 실험 결과 $\beta=0$이 0이 아닌 값과 유사한 결과를 보여주었습니다. 이는 정규화 항의 영향이 문맥 의존적이거나 다른 요인에 의해 약화될 수 있음을 시사합니다.
• 패널티 가중치 (Penalty Weights): 논문은 패널티 가중치를 선택하는 것의 어려움("Big-M 문제")을 언급합니다. 과도하게 큰 가중치는 진정한 이진화보다는 "평균화된" 제약 조건 충족(분수 형태의 값)을 초래하여, 유효한 조합 솔루션의 재구성을 방해할 수 있습니다.

3.3 노이즈 및 샷 분석

• 이상적 환경 vs 노이즈 환경: 이상적인 시뮬레이션에서는 샷 수를 늘리면 오차가 $10^{-3}$ 또는 $10^{-4}$까지 감소합니다. 그러나 노이즈가 있는 백엔드(IBM Sherbrooke 에뮬레이션)에서는 노이즈가 지배적이며, 샷 수와 관계없이 오차가 약 $0.025$ 수준에서 정체됩니다.
• 최적화 역학: 역설적이게도, 노이즈의 존재가 최적화 도구가 서브옵티멀(suboptimal) 로컬 미니마를 탈출하도록 도와 특정 케이스에서 이상적인 노이즈 없는 실행보다 개선된 성능을 보이는 것이 관찰되었습니다.
• 실행 시간: 저자들은 샷 기반 샘플링을 포함한 전체 최적화가 계산 비용이 많이 들지만(천만 번 이상의 평가), 병렬화 전략을 통한 고성능 컴퓨팅(HPC) 환경에서 실행 가능하다고 추정합니다.

4. 의의 및 주장

본 논문은 PCE 기반 프레임워크가 NISQ 및 근사 내결함(near fault-tolerant) 시대의 양자 최적화를 위한 유망한 인코딩 전략이라고 주장합니다. 주요 의의는 다음과 같습니다:

1. 확장성: 표준적인 QAOA와 같은 방식의 선형 스케일링 병목 현상을 극복하고, 다항식 개수의 큐비트를 사용하여 수백 개의 변수를 가진 문제를 인코딩할 수 있음을 입증했습니다.
2. 경쟁력 있는 성능: 적절한 하이퍼파라미터와 압축 차수가 튜닝된다면, MCP, BPP, TSP에 대해 확립된 벤치마크(하이브리드 양자-클래식 솔버 포함)와 대등하거나 더 우수한 솔루션을 달성합니다.
3. 실용적 타당성: 샷 기반 실행 및 하드웨어 노이즈 하에서의 현실적인 평가를 제공하여, 추정 정밀도 및 실행 시간에 대한 기준 범위를 설정했습니다.

저자들은 성능이 특정 문제 구조, 압축 차수의 선택, 그리고 하이퍼파라미터($\alpha, \beta$, 패널티 가중치)의 정밀한 캘리브레이션에 크게 의존한다는 점을 인정하며 신중한 어조를 유지합니다. 결론적으로, PCE가 상당한 잠재력을 보여주기는 하지만, 실제 양자 하드웨어에서 그 능력을 완전히 실현하기 위해서는 안사츠, 클래식 최적화 도구, 그리고 하이퍼파라미터 선택 간의 상호작용을 최적화하기 위한 추가 연구가 필요하다고 밝히고 있습니다.