Probabilistic modeling over permutations using quantum computers

1. 문제 정의 (Problem)

• 배경: 다중 객체 추적 (Multi-object tracking) 이나 추천 시스템과 같은 분야에서 데이터는 종종 $n$개의 객체 순열 (permutation) 의 형태로 나타납니다. 이러한 순열 구조의 데이터에 대한 확률적 모델링은 중요한 과제입니다.
• 고전적 한계:
  • 순열의 집합인 대칭군 $S_n$의 크기는 $n!$로, $n$이 커질수록 초지수적 (super-exponential) 으로 증가합니다.
  • 기존 고전적 접근법 (Kondor, Huang 등) 은 비가환 조화 분석 (Non-Abelian harmonic analysis) 을 사용하여 모델의 푸리에 스펙트럼을 활용하지만, 계산 복잡도 때문에 스펙트럼을 저주파수 성분으로만 제한 (Band-limiting) 해야 합니다. 이는 고차 상관관계를 무시하게 만듭니다.
  • 푸리에 공간과 직접 공간 (Direct space) 사이를 오가는 고속 푸리에 변환 (FFT) 의 고전적 복잡도는 $O(n! n^2)$으로, 정확한 추론을 수행하는 것이 계산적으로 불가능합니다.
  • 따라서 고전 컴퓨터에서는 정확한 확률 모델을 구축하거나 고차 상관관계를 포함한 추론을 수행하는 데 근본적인 한계가 있습니다.

2. 방법론 (Methodology)

이 논문은 대칭군 $S_n$에 대한 양자 푸리에 변환 (Quantum Fourier Transform, QFT) 의 능력을 활용하여 위 한계를 극복하는 양자 알고리즘을 제안합니다.

• 핵심 아이디어:

  • Markov Chain 프레임워크: Kondor 와 Huang 이 제안한 확률적 모델링 프레임워크를 따릅니다. 이 모델은 확산 (Diffusion) 과 조건부 업데이트 (Conditioning) 두 단계가 교차하는 마르코프 체인으로 구성됩니다.
    • 확산 (Diffusion): 불확실성을 모델링하기 위해 Cayley 그래프 (전치환으로 생성됨) 위에서의 랜덤 워크를 수행합니다. 이는 푸리에 공간에서 대각 행렬 연산으로 구현됩니다.
    • 조건부 업데이트 (Conditioning): 새로운 관측 데이터 (훈련 데이터) 를 바탕으로 베이즈 정리를 적용하여 확률 분포를 갱신합니다. 이는 직접 공간에서 점별 곱 (Point-wise product) 으로 구현됩니다.
  • QFT 의 역할: 확산은 푸리에 공간에서, 조건부 업데이트는 직접 공간에서 각각 효율적으로 수행됩니다. 양자 컴퓨터는 $O(n^3 \log n)$ 시간 복잡도로 $S_n$에 대한 QFT 를 수행하여 두 공간 사이의 전환을 효율적으로 가능하게 합니다. 이는 고전 FFT 의 $O(n! n^2)$ 복잡도를 초지수적으로 개선합니다.

• 구현 세부 사항:

  • 인코딩: $n!$개의 순열을 $O(n \log n)$개의 큐비트로 인코딩하기 위해 Lehmer 코드를 사용합니다. 이는 계승 수 체계 (Factorial number system) 와 호환되어 QFT 구현에 필수적입니다.
  • 블록 인코딩 (Block-encoding): 비유니터리 연산인 확산 커널과 조건부 업데이트 연산자를 유니터리 연산자로 인코딩하기 위해 블록 인코딩 기법을 사용합니다.
    • 확산 연산자는 푸리에 공간에서 전치환의 특성을 이용한 스칼라 곱으로 구현됩니다.
    • 조건부 업데이트는 관측 데이터에 따라 확률 질량을 조정하는 연산자로, 부분 순위 (Partial ranking) 나 부분 할당 (Partial assignment) 과 같은 제약 조건을 효율적으로 처리하기 위해 Reorder-update 접근법을 사용합니다.
  • 진폭 증폭 (Amplitude Amplification): 블록 인코딩 과정에서 발생하는 실패 확률을 보정하기 위해 진폭 증폭 (또는 고정점 진폭 증폭) 을 적용하여 성공 확률을 높입니다.

3. 주요 기여 (Key Contributions)

1. 정확한 확률 모델의 양자 인코딩: 고전적으로 계산 불가능한 정확한 확률 분포 (Band-limiting 없이) 를 양자 상태의 진폭에 인코딩하는 알고리즘을 최초로 제안했습니다.
2. 비가환 QFT 의 실용적 활용: 그간 추상적인 이론이나 그래프 동형사상 문제에만 국한되었던 대칭군 $S_n$에 대한 QFT 를 머신러닝 (확률적 모델링) 에 적용하는 구체적인 경로를 제시했습니다.
3. 확산과 조건부 업데이트의 효율적 구현:
   • 푸리에 공간에서의 확산 (대각 연산) 과 직접 공간에서의 베이즈 업데이트 (점별 곱) 를 QFT 를 통해 효율적으로 연결하는 아키텍처를 설계했습니다.
   • Lehmer 코드를 활용한 순열 인코딩과 Reorder-update 기법을 통해 조건부 업데이트의 계산 비용을 줄였습니다.
4. 생성 모델링 및 MAP 추정 전략:
   • 진폭 인코딩 (Amplitude Encoding): 상태의 진폭이 확률 분포에 비례하도록 하여, 측정 시 분포의 제곱에 비례하는 샘플링이 가능하게 합니다 (고차 확률 분포 강조).
   • 보른 인코딩 (Born Encoding): 진폭이 확률의 제곱근이 되도록 하여, 측정 시 실제 사후 확률 분포에서 샘플링이 가능하게 합니다.
   • 최대 사후 확률 (MAP) 추정: 양자 특이값 변환 (QSVT) 을 사용하여 분포의 피크를 증폭하고 낮은 확률 영역을 억제함으로써, 가장 유력한 순열 (Top-k) 을 찾는 최적화 문제를 해결할 수 있는 가능성을 제시했습니다.

4. 결과 및 성능 (Results & Scalability)

• 시간 복잡도: 알고리즘의 주요 병목은 $S_n$에 대한 QFT 실행 시간인 $O(n^3 \log n)$입니다. 이는 고전적 정확한 방법 ($O(n! n^2)$) 에 비해 초지수적 (Super-exponential) 인 속도 향상을 제공합니다.
• 확산 성공 확률: 확산 단계의 성공 확률 (블록 인코딩의 성공 확률) 에 대한 하한을 증명했습니다.
  • "Lazy Walk" (대기 확률 $p > 1/2$) regime 에서는 $n$에 무관한 상수 하한을 가집니다.
  • 일반적인 유리수 $p$에 대해서는 $n$에 대한 다항식 하한을 가짐을 보였습니다. 이는 진폭 증폭을 통해 효율적으로 성공 확률을 높일 수 있음을 의미합니다.
• 확장성: $n$이 15~30 정도의 중간 규모에서도 고전 컴퓨터로는 처리 불가능한 문제 크기를 다룰 수 있으며, 양자 하드웨어의 발전과 함께 실용적인 적용이 가능할 것으로 전망됩니다.

5. 의의 및 시사점 (Significance)

• 머신러닝을 위한 새로운 양자 원리: 이 연구는 양자 컴퓨터가 단순히 암호 해독이나 수학적 문제 해결을 넘어, 비가환 조화 분석 (Non-Abelian harmonic analysis) 을 통한 머신러닝에 혁신적인 도구가 될 수 있음을 보여줍니다.
• 스펙트럴 방법의 부활: 고전적 한계로 인해 사용이 제한되었던 스펙트럴 방법 (Spectral methods) 을 양자 컴퓨터를 통해 완전히 구현할 수 있게 되었습니다. 이는 고차 상관관계를 포착하는 강력한 모델링 능력을 제공합니다.
• 실제 응용 가능성: 다중 객체 추적, 추천 시스템, 순위 학습 등 순열 구조가 중요한 실제 문제들에 대해, 고전적 근사법보다 정밀하고 효율적인 솔루션을 제공할 잠재력이 있습니다.
• 향후 과제: 실제 양자 하드웨어에서의 게이트 오버헤드 최적화, 실제 데이터셋에 대한 벤치마킹, 그리고 오류 정정 양자 컴퓨터에서의 구현 가능성 검증이 향후 연구 과제로 남아있습니다.

결론적으로, 이 논문은 대칭군 $S_n$에 대한 양자 푸리에 변환의 고유한 능력을 활용하여, 고전적으로 풀기 어려운 순열 기반 확률적 모델링 문제를 해결할 수 있는 최초의 실현 가능한 양자 알고리즘을 제시함으로써, 양자 머신러닝의 새로운 지평을 열었습니다.