Sampling (noisy) quantum circuits through randomized rounding

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

• 배경: 현재 NISQ (Noisy Intermediate-Scale Quantum) 시대의 양자 프로세서는 수백에서 수천 개의 잡음 있는 큐비트를 보유하고 있습니다. 이러한 장치를 활용하여 실용적인 문제를 해결하려는 관심이 높아지고 있습니다.
• 주요 문제:
  • 기존 연구들은 주로 관측량의 기대값 (Expectation Values) 을 추정하거나 잡음을 제거 (Error Mitigation) 하는 데 초점을 맞추었습니다.
  • 그러나 조합 최적화 문제 (Combinatorial Optimization, 예: Max-Cut, QUBO) 의 경우, 단순히 기대값만 아는 것만으로는 충분하지 않습니다. 실제 해답은 비트 문자열 (Bit-strings) 자체에 인코딩되어 있어야 합니다.
  • 현재 잡음이 있는 양자 회로에서 직접 샘플링 (측정) 을 수행하는 것은 비용이 많이 들며, 최근 연구에 따르면 특정 임계값 이상의 잡음에서는 단순한 고전적 알고리즘이 양자 알고리즘보다 성능이 더 좋을 수 있음이 밝혀졌습니다.
  • 핵심 질문: "양자 회로를 직접 실행하지 않고도, 양자 회로가 생성하는 잡음 있는 샘플과 유사한 성능을 내는 비트 문자열을 고전적으로 효율적으로 생성할 수 있는가?"

2. 방법론 (Methodology)

저자들은 가우스 랜덤화 반올림 (Gaussian Randomized Rounding) 기법을 사용하여 양자 회로의 잡음 있는 출력을 모방하는 고전적 샘플링 알고리즘을 제안했습니다. 이 방법은 Goemans-Williamson 알고리즘의 아이디어를 확장한 것입니다.

• 입력 데이터: 양자 회로 $C$ (또는 잡음 있는 회로 $[C]_N$) 에서 얻은 2-큐비트 한계 분포 (Two-qubit marginals), 즉 기대값들입니다.
  • 평균 벡터 $\mu_i = \langle Z_i \rangle$
  • 공분산 행렬 $\Sigma_{ij} = \langle Z_i Z_j \rangle$
  • 참고: 이 기대값들은 최근 Pauli 역전파 (Pauli backpropagation) 기법 등을 통해 고전적으로 다항 시간 내에 효율적으로 계산할 수 있음이 입증되었습니다.
• 알고리즘 절차 (Algorithm 4.1):
  1. 계산된 평균 $\mu$ 와 공분산 행렬 $\Sigma$ 를 파라미터로 갖는 다변량 가우스 분포 (Multivariate Gaussian Distribution) 에서 벡터 $y \in \mathbb{R}^n$ 을 샘플링합니다.
  2. 샘플링된 벡터 $y$ 의 각 성분을 부호 (Sign) 에 따라 반올림합니다 ($z_i = \text{sign}(y_i)$).
  3. 결과적으로 $\{-1, +1\}^n$ 의 비트 문자열 $z$ 를 생성하여 최적화 문제의 해답으로 사용합니다.
• 핵심 아이디어: 양자 회로의 2-점 상관관계 (2-body correlations) 가 최적화 문제의 목적 함수 (Cost Function) 를 결정하는 주요 요소이므로, 이 상관관계를 보존하는 가우스 분포를 통해 양자 회로의 출력 분포를 근사할 수 있습니다.

3. 주요 기여 및 이론적 결과 (Key Contributions & Theoretical Results)

저자들은 제안된 알고리즘이 잡음 있는 양자 회로의 샘플을 고전적으로 복제할 수 있음을 수학적으로 증명했습니다.

• Max-Cut 문제에 대한 결과:

  • 잡음 없는 경우: Goemans-Williamson 알고리즘의 성능 보장 (최적해의 약 0.878 배) 을 만족합니다.
  • 잡음 있는 경우 (국소 탈분극 잡음, Local Depolarizing Noise): 회로의 깊이 $D$ 와 잡음 강도 $p$ 에 대해, 제안된 샘플러가 얻는 비용의 기대값과 잡음 있는 양자 장치가 얻는 비용의 기대값 사이의 회복 비율 (Recovery Ratio, $\alpha$) 을 분석했습니다.
  • 주요 정리 (Theorem 4.2): $\alpha \ge 1 - O((1-p)^D)$ 를 보였습니다. 즉, 잡음이 증가하거나 회로 깊이가 깊어질수록 양자 회로의 출력이 무작위 분포에 가까워지는데, 이 때 고전적 반올림 알고리즘이 양자 회로의 샘플을 매우 정확하게 복제함을 의미합니다.
  • 이는 특정 임계값을 넘어서면 양자 우위가 사라질 뿐만 아니라, 고전적 알고리즘이 양자 회로의 출력 분포 자체를 모방할 수 있음을 시사합니다.

• QUBO (Quadratic Unconstrained Binary Optimization) 문제에 대한 결과:

  • Max-Cut 을 일반화한 QUBO 문제에서도 유사한 분석이 수행되었습니다 (Theorem 5.1).
  • 잡음 있는 환경에서 회복 비율이 $1 - O(\Delta n (1-p)^D)$ 형태로 하한을 가지며, 잡음이 커질수록 성능이 개선됨을 보였습니다.

• 실용적 의미:

  • 이 방법은 양자 회로의 깊이와 잡음 수준에 상관없이 작동하며, 오히려 잡음이 클수록 고전적 모방이 더 정확해집니다.
  • 이는 "잡음 있는 양자 최적화 회로"를 고전적으로 샘플링하는 단순하면서도 강력한 대안을 제공합니다.

4. 실험 결과 (Numerical Results)

저자들은 IBMQ 하드웨어와 대규모 시뮬레이션을 통해 이론적 결과를 검증했습니다.

• 하드웨어 실험: IBM의 127-큐비트 양자 칩을 사용하여 Max-Cut 및 QUBO 인스턴스에 QAOA (Quantum Approximate Optimization Algorithm) 회로를 실행했습니다.
• 분포 일치성 (Distribution Matching):
  • 단순히 기대값 (평균) 만이 아닌, 전체 에너지 분포 (Full Energy Distribution) 가 고전적 반올림 샘플과 양자 하드웨어 샘플 간에 매우 잘 일치함을 확인했습니다 (Figure 5).
  • 특히 분포의 꼬리 (Tail, 즉 최상위 해답들) 에서도 양자 하드웨어의 샘플링 결과를 고전적으로 잘 재현함을 보였습니다.
• 잡음 모델 확장: 탈분극 잡음뿐만 아니라 진폭 감쇠 (Amplitude Damping) 잡음 모델에서도 유사한 경향 (잡음 증가 시 회복 비율 향상) 을 관찰했습니다 (Figure 6).
• 성능 비교: 고전적 샘플링 알고리즘은 이론적 최악의 경우 (Worst-case) 보다 실제 인스턴스에서 훨씬 더 좋은 성능을 보였습니다.

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

• NISQ 장치의 한계 명확화: 이 연구는 조합 최적화 문제를 해결하는 데 있어 잡음 있는 양자 장치의 실제 능력을 정량적으로 평가하는 기준을 제공합니다. 충분히 잡음이 있는 회로는 고전적 알고리즘으로 충분히 모방 가능함을 보여줍니다.
• 고전적 대리 모델 (Classical Surrogate): 양자 하드웨어를 직접 실행하지 않고도, 양자 회로의 기대값 (이는 고전적으로 계산 가능) 만을 사용하여 양자 회로와 유사한 품질의 샘플을 생성할 수 있는 효율적인 방법을 제시했습니다.
• 향후 방향:
  • 이 방법은 차세대 오류 완화 (Error Mitigation) 기법이나 오류 정정 (Fault Tolerance) 을 위한 벤치마크로 활용될 수 있습니다.
  • 고차 상호작용 문제나 퀴딧 (Qudit) 시스템으로의 확장 가능성이 열려 있습니다.

요약하자면, 이 논문은 잡음 있는 양자 최적화 회로의 출력을 고전적으로 샘플링하는 새로운 패러다임을 제시하며, "양자 우위"가 존재하기 위해서는 단순한 기대값 추정뿐만 아니라 샘플링 자체에서도 고전적 알고리즘을 능가해야 함을 강조합니다. 또한, 현재 NISQ 장치의 잡음 수준에서는 고전적 랜덤화 반올림 기법이 양자 회로의 행동을 매우 정확하게 모방할 수 있음을 증명했습니다.