Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice

논문 요약: 실용적 관점에서의 변분 양자 알고리즘 벤치마킹

1. 연구 배경 및 문제 정의 (Problem)

• 배경: 변분 양자 알고리즘 (VQA), 특히 변분 양자 고유값 솔버 (VQE) 의 변형들은 조합 최적화 (CO) 문제를 해결하기 위해 제안되었습니다. 이러한 접근법은 현재의 잡음이 있는 중규모 양자 (NISQ) 하드웨어에 적합한 얕은 회로 (shallow circuits) 를 사용합니다.
• 문제: 이론적으로 VQA 는 유망하지만, 실제로 얕은 변분 양자 회로를 훈련하는 데 필요한 리소스 (샘플 수 등) 는 문제 크기에 따라 초다항식 (superpolynomial) 적으로 증가하는 것으로 알려져 있습니다.
• 핵심 질문: 이러한 "초다항식 스케일링"이 실제 조합 최적화 문제 해결에 어떤 의미를 갖는지, 그리고 고정된 리소스 하에서 VQA 가 기존 고전 알고리즘이나 단순 무작위 샘플링보다 우월한 성능을 발휘할 수 있는지 여부는 명확하지 않습니다.
• 벤치마크 대상: 본 연구는 대표적인 조합 최적화 문제인 Max-Cut 문제를 사용하여 3-정규 그래프 (3-regular graphs) 의 작은 인스턴스들을 대상으로 수치적 조사를 수행합니다.

2. 방법론 (Methodology)

연구진은 고정된 리소스 (총 목적 함수 평가 횟수 $N_{evals} = 10^6$) 하에서 다음 세 가지 알고리즘의 평균 성능을 비교했습니다.

1. 변분 양자 고유값 솔버 (VQE):

   • 회로 구조: 하드웨어 효율적인 얕은 회로 사용. 초기 $|0\rangle$ 상태에서 시작하여 단일 층의 파라미터화된 $RY$ 회전 게이트와 벽돌 모양 (brick-like) 의 CNOT 게이트로 구성된 얕은 회로를 사용합니다.
   • 비용 함수: 조합 최적화 성능 향상을 위해 제안된 CVaR (Conditional Value at Risk) 비용 함수를 사용하며, 상위 10% ($\gamma=0.1$) 의 결과만 고려합니다.
   • 최적화: 기울기 없는 COBYLA 알고리즘을 사용하여 파라미터를 업데이트합니다.
   • 초기화: VQE 의 초기 파라미터를 사용하여 양자 회로를 한 번 실행하여 얻은 계산 기저 상태 (computational basis state) 를 Greedy 알고리즘의 초기점으로 동일하게 설정하여 공정한 비교를 시도했습니다.

2. 대체 샘플링 (Sampling with replacement):

   • 문제의 구조를 전혀 활용하지 않고, 계산 기저 상태를 무작위로 균일하게 샘플링하는 가장 단순한 방법입니다.
   • VQE 가 단순히 무작위 추측을 하고 있는지 확인하기 위한 기준선 (baseline) 으로 사용됩니다.

3. Greedy 알고리즘:

   • 현재 상태에서 비트 1 개를 뒤집었을 때 목적 함수가 가장 크게 개선되는 상태로 이동하는 고전적 휴리스틱 알고리즘입니다.
   • VQE 와 동일한 초기 상태에서 시작하여, VQE 가 초기화하는 상태가 Greedy 알고리즘에게도 좋은 시작점인지 분석합니다.

성능 지표:

• 근사 비율 (Approximation Ratio): 찾은 해의 목적 함수 값과 최적 해 (Gurobi 솔버로 구함) 의 비율.
• 성공 확률: 정확한 해를 찾은 실행 비율 (작은 문제의 경우).
• 상관 분석: 인스턴스별 (instance-by-instance) 로 알고리즘 간 성능의 상관관계를 분석하기 위해 이진화된 통계 (binned statistics) 를 사용했습니다.

3. 주요 결과 (Key Results)

• 작은 문제 크기 (N=11, 21):

  • VQE 는 무작위 샘플링보다 성능이 더 나빴습니다.
  • 특히 $N=11$의 경우, VQE 가 높은 근사 비율을 보였으나 이는 단순히 문제 공간이 작아 무작위 샘플링으로도 쉽게 좋은 해를 찾기 때문이었으며, VQE 는 오히려 샘플링보다 못한 결과를 보였습니다.
  • $N=21$에서도 초기 몇 단계 외에는 VQE 가 Greedy 알고리즘 및 샘플링보다 열등했습니다.

• 중간 크기 문제 (N > 30):

  • 샘플링 대비 우위: 문제 크기가 30 을 넘어서면 계산 기저 상태의 수가 기하급수적으로 증가하여 무작위 샘플링의 성능이 급격히 떨어집니다. 이때 VQE 는 샘플링보다 일관되게 우수한 성능을 보였습니다 (예: $N=31$에서 약 95% 의 인스턴스에서 우위).
  • Greedy 알고리즘 대비 우위:
    • Greedy 알고리즘은 매우 빠르게 지역 최적점 (local minima) 에 수렴합니다.
    • VQE 는 초기에는 Greedy 알고리즘보다 성능이 낮았으나, 반복이 진행됨에 따라 더 나은 지역 최적점으로 수렴하여 결국 Greedy 알고리즘을 능가했습니다.
    • VQE 가 Greedy 알고리즘의 성능을 추월하는 데 필요한 반복 횟수는 문제 크기가 커질수록 증가했습니다 (N=31: 약 100 회, N=61: 약 600 회).

• 성능 차이의 경향성:

  • 샘플링 대비: 문제 크기가 커질수록 VQE 의 우위가 증가했습니다 ($N=61$에서 평균 근사 비율 차이 약 0.11).
  • Greedy 알고리즘 대비: 문제 크기가 커질수록 VQE 의 우위는 오히려 감소했습니다 ($N=31$에서 최대 차이 약 0.025, $N=61$에서 약 0.005). 이는 Greedy 알고리즘이 큰 문제에서도 일정한 평균 성능을 유지하는 반면, VQE 의 훈련 난이도가 증가하기 때문입니다.

• 상관성 분석:

  • VQE vs 샘플링: 약한 상관관계가 관찰되었으며, 이는 샘플링이 VQE 의 핵심 구성 요소이기 때문입니다.
  • VQE vs Greedy: 두 알고리즘 간에는 전혀 상관관계가 없었습니다. 이는 VQE 와 Greedy 알고리즘이 근본적으로 다른 메커니즘을 사용하며, VQE 에게 좋은 초기점이 Greedy 알고리즘에게도 좋은 초기점이 아님을 의미합니다.

4. 기여 및 의의 (Contributions & Significance)

1. 실용적 벤치마킹의 중요성 강조:

   • 많은 VQA 연구가 "원리 증명 (proof-of-principle)" 수준에 머무르거나, 고전 솔버가 쉽게 해결할 수 있는 매우 작은 문제를 다룹니다. 본 연구는 고정된 리소스 하에서 실제적인 비교를 통해, VQA 가 유의미한 우위를 보이기 위해서는 문제 크기가 일정 수준 (약 30 변수 이상) 이상이어야 함을 입증했습니다.

2. 샘플링에 대한 엄격한 비교:

   • VQA 가 단순히 무작위 추측보다 나을지조차 확인되지 않는 작은 문제 영역에서는 VQA 의 성능이 오히려 떨어질 수 있음을 보여주었습니다. 이는 NISQ 시대의 알고리즘 평가에 있어 샘플링을 강력한 베이스라인으로 삼아야 함을 시사합니다.

3. 초기화 전략에 대한 통찰:

   • VQE 의 초기 파라미터가 생성한 상태가 Greedy 알고리즘의 초기점으로 사용되었을 때, 두 알고리즘의 성능이 서로 예측할 수 없음을 보였습니다. 이는 VQA 의 초기화 (Warm start) 전략이 고전 알고리즘의 관점과는 완전히 다를 수 있음을 의미합니다.

4. 향후 연구 방향 제시:

   • 물리 시스템 (예: 기저 상태 에너지 계산) 에 적용되는 VQA 들은 조합 최적화와 달리 계산 기저 상태가 해가 아닌 경우가 많습니다. 본 연구의 벤치마킹 프레임워크가 Markov Chain Monte Carlo (MCMC) 와 같은 고전적 방법과 비교하여 물리 문제 해결에 어떻게 확장될 수 있는지에 대한 논의도 포함하고 있습니다.

결론

이 논문은 얕은 회로를 사용하는 VQE 가 조합 최적화 문제에서 실제로 유효한지 여부를 정량적으로 분석했습니다. 그 결과, 작은 문제에서는 VQA 가 무작위 샘플링이나 간단한 Greedy 알고리즘보다 열등할 수 있으며, 유의미한 이점을 얻으려면 문제 크기가 충분히 커져야 함을 보여주었습니다. 이는 NISQ 시대의 양자 알고리즘 개발과 평가에 있어 현실적인 자원 제약과 문제 크기를 고려한 신중한 접근이 필요함을 강조합니다.