Counting with the quantum alternating operator ansatz

본 논문은 양자 교대 연산자 안사 (QAOA) 를 기반으로 한 변분 알고리즘 'VQCount'를 제안하여 난해한 계산 문제의 근사 계산을 기존 방법보다 지수적으로 효율적으로 수행하고, 텐서 네트워크 시뮬레이션을 통해 성공 확률과 샘플링 균일성 간의 균형을 활용한 실증적 성능 향상을 입증했습니다.

핵심

이 논문은 **"양자 컴퓨터를 이용해 '해답의 개수'를 빠르게 세는 새로운 방법 (VQCount)"**을 소개합니다.

기존의 양자 알고리즘들은 주로 "가장 좋은 해답 하나를 찾는 것 (최적화)"에 집중해 왔습니다. 하지만 이 논문은 **"해답이 총 몇 개인지 대략적으로 추정하는 것 (계수)"**에 초점을 맞췄습니다. 이는 훨씬 더 어려운 문제지만, 인공지능이나 신뢰성 분석 등 실생활에 매우 중요한 문제입니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드리겠습니다.

---

1. 문제 상황: 거대한 도서관의 책 찾기

상상해 보세요. 여러분은 거대한 도서관에 있습니다. 이 도서관에는 수억 권의 책이 있지만, 그중에서 **'진짜 이야기 (해답)'**가 쓰인 책들만 몇 권 있습니다. 문제는 이 '진짜 이야기' 책들이 도서관 구석구석에 숨겨져 있다는 것입니다.

• 기존의 방법 (고전 컴퓨터): 도서관을 한 권 한 권 직접 찾아다니며 세는 것입니다. 책이 너무 많으면 평생 걸려도 다 셀 수 없습니다.
• 기존의 양자 방법: 양자 컴퓨터의 마법 같은 힘으로 책을 빠르게 뒤집어 보는 시도들이 있었지만, '진짜 이야기' 책들이 너무 많을 때는 여전히 세는 데 시간이 너무 오래 걸렸습니다.

2. 새로운 아이디어: VQCount (양자 계수기)

저자들은 **"정확하게 하나하나 세지 말고, 무작위로 뽑아본 뒤 그 비율로 전체를 추정하자"**는 아이디어를 냈습니다.

이를 위해 두 가지 핵심 도구를 섞어 썼습니다.

도구 A: JVV 알고리즘 (나무 가지치기)

이것은 "거대한 나무를 잘게 자르는" 방법입니다.

• 도서관이 너무 크면, "첫 번째 책장이 'A'로 시작하는 책들만 모아서 세자"라고 나눕니다.
• 그다음 "그중에서 두 번째 책장이 'B'인 것만 모아서 세자"라고 또 나눕니다.
• 이렇게 나무 가지처럼 문제를 쪼개어가면, 처음엔 거대한 도서관이 나중엔 작은 책상 하나만 있는 공간이 됩니다.
• 핵심: 이 과정을 성공하려면, 각 단계에서 '진짜 이야기' 책들을 골고루 (균일하게) 뽑아낼 수 있어야 합니다.

도구 B: QAOA (양자 사냥꾼)

이것은 **"양자 컴퓨터가 도서관에서 책을 찾는 사냥꾼"**입니다.

• 이 사냥꾼은 책을 빠르게 찾아내지만, 약간의 편향이 있을 수 있습니다. (예: 빨간 책만 더 잘 찾거나, 특정 구역만 잘 찾음)
• 논문에서는 이 사냥꾼을 두 가지 버전으로 실험했습니다.
  1. 정직한 사냥꾼 (GM-QAOA): 책을 절대 편견 없이 골고루 찾습니다. 하지만 책을 찾는 속도가 느립니다.
  2. 빠른 사냥꾼 (일반 QAOA): 책을 아주 빠르게 찾지만, 특정 책만 선호하는 편향이 있습니다.

3. 발견된 사실: "속도 vs 공평함"의 트레이드오프

저자들은 흥미로운 사실을 발견했습니다.

• 완벽한 공평함 (GM-QAOA): 책을 골고루 찾지만, 찾는 데 시간이 너무 오래 걸려서 전체적인 효율이 떨어집니다.
• 빠른 속도 (일반 QAOA): 편향은 있지만, 찾는 속도가 매우 빨라 전체적인 효율이 더 좋습니다.

비유하자면:

• GM-QAOA는 "모든 학생을 공정하게 뽑으려다 보니, 뽑는 데 1 시간 걸리는 선생님"입니다.
• 일반 QAOA는 "약간 편향되지만 10 분 만에 뽑는 선생님"입니다.

논문의 결론은 **"완벽하게 공평할 필요는 없다. 조금은 편향되더라도 훨씬 빠르게 찾을 수 있다면, 그 편향을 계산에 넣어서 전체를 추정하는 것이 더 효율적이다"**는 것입니다.

4. 결과: 왜 이것이 중요한가?

이 새로운 방법 (VQCount) 은 다음과 같은 성과를 냈습니다.

1. 기존 양자 방법보다 훨씬 빠름: 같은 정확도를 얻기 위해 필요한 시뮬레이션 횟수가 기존 방법보다 지수적으로 (엄청나게) 줄어듭니다.
2. 실용성: 현재의 잡음 많은 양자 컴퓨터 (NISQ) 에서도 작동할 수 있는 얕은 회로 (단순한 알고리즘) 로도 좋은 결과를 냅니다.
3. 한계: 아직은 최첨단 고전 컴퓨터 (전통적인 슈퍼컴퓨터) 보다 빠르지는 않습니다. 하지만 양자 컴퓨터가 발전하면 이를 따라잡을 가능성이 열렸습니다.

요약: 한 줄로 정리하면?

"거대한 도서관에서 책의 개수를 세려면, 완벽하게 공평하게 하나하나 세느라 시간을 낭비하지 말고, 양자 컴퓨터라는 '빠른 사냥꾼'을 이용해 무작위로 뽑아낸 샘플을 분석하면 훨씬 효율적으로 전체 수를 추정할 수 있다."

이 연구는 양자 컴퓨터가 단순한 '문제 해결기'를 넘어, 복잡한 '통계와 추정'의 영역에서도 실용적인 도구가 될 수 있음을 보여주는 중요한 첫걸음입니다.

기술 요약

논문 요약: 양자 교대 연산자 안사츠 (QAOA) 를 이용한 계수 (Counting)

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

• 계수 문제 (Counting Problems): 주어진 결정 문제 (Decision Problem) 의 해가 몇 개인지 세는 문제는 계산 복잡도 이론에서 #P-hard 클래스에 속합니다. 이는 NP-hard 최적화 문제보다 더 높은 복잡도 계층에 위치하며, 정확한 해를 구하는 다항 시간 알고리즘은 존재하지 않을 것으로 추정됩니다.
• 기존 접근법의 한계:
  • 정확한 계수: 텐서 네트워크 (Tensor Networks) 나 컴포넌트 캐싱 같은 고전적 휴리스틱은 수백 개의 변수까지 처리할 수 있지만, 그 이상으로 확장하기 어렵습니다.
  • 근사 계수 (Approximate Counting): Jerrum-Valiant-Vazirani (JVV) 알고리즘은 '근사 계수'와 '무작위 샘플링'이 동치임을 증명했습니다. 즉, 해를 균일하게 (uniformly) 샘플링할 수 있다면 근사 계수가 가능합니다.
  • 양자 알고리즘의 도전: 기존 양자 근사 최적화 알고리즘 (QAOA) 은 최적화 문제에 특화되어 있어, 해의 진폭을 균일하게 분포시키지 못하거나 해를 찾을 확률 (Success Rate) 이 낮아 계수 문제 적용에 한계가 있었습니다. 특히 해의 수가 기하급수적으로 많을 때, 모든 해를 탐색하는 데 필요한 샘플 수가 지수적으로 증가하는 문제가 있었습니다.

2. 제안된 방법론: VQCount (Methodology)

저자들은 VQCount라는 새로운 변분 양자 알고리즘을 제안했습니다. 이는 JVV 알고리즘의 프레임워크에 양자 회로 (QAOA) 를 서브루틴으로 결합한 것입니다.

• 핵심 아이디어:

  • JVV 알고리즘과의 결합: JVV 알고리즘은 문제를 재귀적으로 분해하여 (Self-reducibility) 각 단계에서 조건부 확률을 추정함으로써 전체 해의 개수를 근사합니다. VQCount 는 이 과정에서 해를 샘플링하는 '생성기 (Generator)' 역할을 QAOA 가 수행하도록 설계되었습니다.
  • QAOA 변형체 비교:
    1. 기존 QAOA (Quantum Approximate Optimization Algorithm): 해를 찾는 데는 효율적일 수 있으나, 해의 분포가 균일하지 않을 수 있습니다 (Non-uniformity).
    2. Grover-Mixer QAOA (GM-QAOA): Grover 알고리즘의 요소를 도입하여 해 공간 내에서 **완벽한 균일 분포 (Uniform Distribution)**를 보장합니다. 하지만 깊은 회로 (Deep Circuit) 가 필요하고 성공 확률이 낮을 수 있습니다.
  • 상호 보완적 전략: VQCount 는 GM-QAOA 의 균일성 보장과 기존 QAOA 의 높은 성공 확률 사이의 트레이드오프를 활용합니다. 특히 얕은 회로 (Shallow Circuits) 환경에서는 기존 QAOA 가 더 효율적인 샘플링 백엔드가 될 수 있음을 보여줍니다.

• 알고리즘 흐름:

  1. 문제 (SAT 등) 를 Ising 모델 해밀토니안으로 매핑합니다.
  2. QAOA (또는 GM-QAOA) 회로를 최적화하여 해의 중첩 상태를 생성합니다.
  3. 측정 후 해 (Solution) 만을 선별 (Post-selection) 합니다.
  4. JVV 알고리즘에 따라 변수를 하나씩 고정하며 조건부 확률을 추정하고, 이를 곱하여 전체 해의 개수를 근사합니다.

3. 주요 기여 (Key Contributions)

1. 샘플 복잡도의 지수적 개선: 이전의 변분 양자 계수 알고리즘 [18] 과 비교하여, VQCount 는 임의의 작은 곱셈 오차 범위 내에서 근사 계수를 얻기 위해 필요한 샘플 수를 지수적으로 줄임을 이론적으로 증명했습니다.
   • 기존 방법: $O(\sqrt{N})$ 스케일 (N 은 해의 개수)
   • VQCount: $O(n^2 / (r \epsilon^2))$ 스케일 (r 은 성공 확률). 해의 개수 N 이 $2^n$일 때 지수적 이득을 얻습니다.
2. 균일성과 성공 확률 간의 트레이드오프 규명: GM-QAOA 는 균일성을 보장하지만 성공 확률이 낮고, 기존 QAOA 는 성공 확률은 높지만 균일성이 떨어질 수 있음을 실험적으로 확인했습니다. 저자들은 이 트레이드오프를 활용하여 실제 효율성을 극대화했습니다.
3. 실용적 성능 검증: 텐서 네트워크 시뮬레이션을 통해 #NAE3SAT 와 #1-in-3SAT 두 가지 #P-hard 문제에 대해 VQCount 의 성능을 평가했습니다.

4. 실험 결과 (Results)

• 시뮬레이션 설정: #NAE3SAT (변수 6~20 개) 와 #1-in-3SAT (변수 24 개까지) 에 대해 깊이 $p=3$의 얕은 회로를 사용했습니다.
• 성능 비교:
  • 샘플 수: VQCount 는 단순 거절 샘플링 (Naive Rejection Sampling) 과 Grover 기반 양자 계수 (BHMT 알고리즘) 보다 지수적으로 적은 샘플 수로 근사 계수를 달성했습니다.
  • QAOA vs GM-QAOA:
    • GM-QAOA: 해의 분포가 완벽하게 균일하지만, 성공 확률이 매우 낮아 많은 샘플이 필요했습니다.
    • 기존 QAOA: 해의 분포는 불균일했으나, 성공 확률이 훨씬 높아 전체적으로 더 적은 샘플 수로 동일한 정확도를 달성했습니다. 특히 해가 드물고 멀리 떨어진 경우 (Hard regime) QAOA 가 더 우세했습니다.
  • 확장성: 회로 깊이 (Depth) 가 증가할수록 성공 확률은 증가하고 필요한 샘플 수는 감소하는 경향을 보였습니다.
• 한계: 현재 VQCount 의 전체적인 스케일링 (Scaling) 은 해당 문제를 해결하는 최첨단 고전적 정확 해법 (Tensor Network 기반 등) 보다 느립니다. 하지만 근사 계수 문제에서 변분 양자 알고리즘이 가질 수 있는 잠재력을 보여줍니다.

5. 의의 및 결론 (Significance)

• 양자 우위 가능성 제시: #P-hard 문제와 같이 고전 컴퓨터에게는 매우 어려운 계수 문제에 대해, 변분 양자 알고리즘 (VQA) 이 유효한 근사 해법을 제공할 수 있음을 입증했습니다.
• 실용적 접근법: 오류 정정이 필요 없는 NISQ (Noisy Intermediate-Scale Quantum) 시대의 하드웨어에 적합한 얕은 회로를 사용하여, 고전적 방법과 양자 자원을 적절히 절충 (Trade-off) 하는 새로운 패러다임을 제시했습니다.
• 향후 전망: 현재는 시뮬레이션 단계이지만, 회로 깊이를 늘리거나 문제 인지형 믹서 (Problem-aware mixers) 및 파라미터 최적화 기법을 개선하면 고전적 휴리스틱과 경쟁 가능한 성능을 달성할 가능성이 있습니다. 또한, 균일하지 않은 샘플링을 허용하더라도 근사 계수가 가능하다는 기존 이론 [56] 을 VQCount 에 적용할 여지가 있습니다.

요약하자면, 이 논문은 QAOA 를 기반으로 한 VQCount 알고리즘을 제안하여, #P-hard 계수 문제에서 샘플링 효율성을 획기적으로 개선하고, 균일성과 성공 확률 간의 균형을 통해 변분 양자 알고리즘이 근사 계수 분야에서 실용적인 도구가 될 수 있음을 보여주었습니다.