Cross-Platform Benchmarking of Near-Term Quantum Optimisation Algorithms

논문 요약: 근접 미래 양자 최적화 알고리즘의 크로스 플랫폼 벤치마킹

이 논문은 양자 컴퓨팅의 실용적 이점 (Quantum Advantage) 을 입증하기 위한 체계적인 벤치마킹 프레임워크를 제시하며, 게이트 기반 양자 컴퓨터와 양자 어닐링 장치를 포함한 상용 양자 하드웨어에서 다양한 최적화 알고리즘의 성능을 비교 분석합니다. 연구의 핵심은 밀집형 (Dense) Quadratic Unconstrained Binary Optimization (QUBO) 문제를 해결하는 데 있어 양자 알고리즘과 고전 알고리즘의 성능을 공정하게 평가하는 것입니다.

1. 연구 문제 (Problem)

• 테스트 케이스: 결함이 있는 그래핀 구조의 최저 에너지 구성을 찾는 문제. 이는 가장 밀집된 k-서브그래프 (Densest k-Subgraph, DkS) 문제의 한 형태로 모델링됩니다.
• 문제 정의: $N$개의 사이트가 있는 그래핀 시트에서 특정 개수 (본 연구에서는 3 개) 의 원자를 제거하여, 남은 원자 - 원자 결합 (bond) 의 수를 최대화 (에너지 최소화) 하는 구성을 찾는 것입니다.
• 수식화: 이 문제는 QUBO (Quadratic Unconstrained Binary Optimization) 형식으로 변환됩니다.
  • 목적 함수: 남은 결합 수를 최대화 (에너지 최소화).
  • 제약 조건: 제거된 원자의 개수가 정확히 3 개여야 함. 이는 페널티 항 (Penalty term, $\lambda$) 을 사용하여 목적 함수에 포함됩니다.
  • 특징: 제약 조건이 추가된 후 QUBO 행렬은 완전 연결 (Fully-connected, 100% 밀도) 그래프가 됩니다. 이는 현재 양자 하드웨어의 제한된 연결성 (Connectivity) 으로 인해 큰 도전 과제를 제기합니다.

2. 방법론 (Methodology)

연구진은 다양한 알고리즘을 동일한 QUBO 인스턴스에 적용하여 비교하는 크로스 플랫폼 벤치마킹 프레임워크를 구축했습니다.

• 사용된 알고리즘:

  1. 고전 알고리즘:
     • Brute Force (완전 탐색): 정확한 해를 제공하지만 지수적 시간 복잡도로 인해 작은 문제에만 적용 가능.
     • Simulated Annealing (SA): 확률적 최적화 기법.
     • Random Sampling: 무작위 샘플링 (베이스라인).
  2. 양자 알고리즘:
     • VQE (Variational Quantum Eigensolver): 게이트 기반 양자 컴퓨터 (IBM ibm_fez, 156 큐비트) 와 상태 벡터 시뮬레이터에서 실행. 하이브리드 양자 - 고전 루프를 사용하며, CVaR (Conditional Value at Risk) 목적 함수를 사용하여 수렴성을 개선했습니다.
     • Quantum Annealing (QA): 양자 어닐링 장치 (D-Wave Advantage 6.4, 5612 물리 큐비트) 에서 실행.

• 성능 지표 (Metrics):

  • 최적 해 확률 ($P_s$): 최적 해 (Ground State) 를 찾을 확률.
  • 근사 비율 (Approximation Ratio, AR): 찾은 해의 에너지가 이론적 최소/최대 에너지 범위 내에서 어디에 위치하는지.
  • 실행 시간: 사용자 런타임 (User Runtime, 인코딩 + 대기 + 장치 실행) 과 QPU 시간 (장치가 실제 문제를 푸는 시간).
  • 후처리 (Post-selection): 제약 조건 (원자 3 개 제거) 을 위반한 해를 제거하여 $P_s$와 AR 을 재계산하는 과정.

• 임베딩 (Embedding):

  • 완전 연결 QUBO 를 물리 큐비트에 매핑하기 위해 마이너 임베딩 (Minor Embedding, D-Wave 기본) 과 클릭 임베딩 (Clique Embedding, 완전 연결 문제에 최적화) 두 가지 기법을 비교했습니다.

3. 주요 기여 (Key Contributions)

1. 공정한 비교 프레임워크: 게이트 기반 변분 알고리즘, 양자 어닐링, 고전 알고리즘을 동일한 QUBO 인스턴스와 메트릭으로 비교하는 체계적인 벤치마킹 방법론을 제시했습니다.
2. 대규모 문제 해결: 상용 QCaaS (Quantum Computing as a Service) 하드웨어를 활용하여 최대 72 변수의 완전 연결 QUBO 문제를 해결했습니다.
3. 확장성 분석:
   • 고전 시뮬레이티드 어닐링 (SA) 은 시스템 크기 $N$에 대해 다항식 시간 (Polynomial time) 으로 확장되는 효율적인 해를 찾았습니다 (최대 388 변수까지).
   • 양자 어닐링은 클릭 임베딩을 사용할 때 제한된 문제 크기에서 다항식 확장성의 징후를 보였습니다.
4. 기술적 통찰 도출:
   • 페널티 계수 ($\lambda$): 작은 $\lambda$를 사용하되 후처리 (Post-selection) 를 결합하면 최적 해를 찾을 확률이 높아짐을 발견했습니다.
   • 임베딩 오버헤드: 양자 어닐링에서 임베딩 시간이 전체 런타임의 대부분을 차지하며, 클릭 임베딩이 완전 연결 문제에서 더 효율적임을 확인했습니다.
   • VQE 의 한계: 잡음 (Noise), 바렌 플래토 (Barren Plateaus), 초기 파라미터의 무작위성으로 인해 VQE 의 수렴이 불안정하고, 고전적 오버헤드 (컴파일, 최적화) 가 실행 시간을 크게 증가시킴을 보였습니다.

4. 결과 (Results)

• 성능 비교 (18 변수 문제 기준):
  • Simulated Annealing: 가장 우수한 성능을 보였습니다. $P_s \approx 0.99$, AR $\approx 0.99$이며, 실행 시간도 가장 짧았습니다.
  • Quantum Annealing: $P_s \approx 0.40$ (후처리 후), AR $\approx 0.63$. QPU 시간은 짧았으나 임베딩 및 대기 시간으로 인해 전체 런타임은 SA 보다 길었습니다.
  • VQE (QPU): $P_s \approx 0.60$ (후처리 후), AR $\approx 0.76$. 잡음과 수렴 문제로 인해 상태 벡터 시뮬레이터보다 성능이 떨어졌으며, 실행 시간은 SA 보다 2 차수 이상 길었습니다.
  • Brute Force: 정확한 해를 제공하지만 18 변수 이상에서는 계산 불가능.
• 확장성 (Scaling):
  • VQE: 50 변수를 초과하면 수렴이 실패하거나 최적 해 확률이 0 에 수렴했습니다. 72 변수에서는 부분 최적 해를 찾았지만 실행 시간이 너무 길어 반복 실험이 불가능했습니다.
  • Quantum Annealing: 마이너 임베딩은 72 변수까지 실행 가능했으나 $P_s$가 급격히 감소했습니다. 클릭 임베딩은 50 변수까지는 가능했으나 그 이상에서는 $P_s$가 0 이 되었습니다.
  • Simulated Annealing: 338 변수까지 성공적으로 해결하며 다항식 확장성을 입증했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 현실적 평가: 현재 (NISQ) 시대의 양자 하드웨어와 알고리즘은 고전적인 시뮬레이티드 어닐링보다 성능이나 속도 면에서 우위를 점하지 못했습니다. 특히 밀집형 (Dense) QUBO 문제의 경우 연결성 제한과 임베딩 오버헤드가 큰 병목 현상이 됩니다.
• 벤치마킹의 중요성: 하드웨어의 발전뿐만 아니라 알고리즘의 개선 방향 (예: 임베딩 최적화, 페널티 계수 조정, CVaR 사용 등) 을 파악하기 위해 투명하고 공정한 벤치마킹이 필수적임을 강조했습니다.
• 미래 전망: 하드웨어 연결성 개선 (예: IBM 의 Nighthawk 프로세서, D-Wave 의 Advantage2) 과 오류 완화 기술, 그리고 문제 구조를 활용한 알고리즘 개선 (Warm start, 파라미터 집중 등) 이 이루어진다면 향후 양자 우위 달성의 가능성이 열릴 것으로 기대됩니다.

이 연구는 양자 최적화 알고리즘의 현재 상태를 객관적으로 평가하고, 향후 연구가 집중되어야 할 기술적 난제 (연결성, 잡음, 임베딩 효율성) 를 명확히 제시했다는 점에서 중요한 의의를 가집니다.