A Practically Scalable Approach to the Closest Vector Problem for Sieving via QAOA with Fixed Angles

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

• 배경: 정수 소인수분해 (Integer Factorization) 의 난이도는 RSA 와 같은 현대 공개키 암호 체계의 안전성을 보장하는 핵심 요소입니다. 최근 Yan 등 [1] 은 양자 근사 최적화 알고리즘 (QAOA) 을 사용하여 체 (Sieving) 기법을 가속화하고, 이를 통해 소인수분해에 필요한 '부드러운 관계 쌍 (smooth relation pairs, sr-pairs)'을 찾는 방법을 제안했습니다.
• 핵심 문제: Yan 등의 연구는 체 (Sieving) 과정의 병목 현상인 sr-pairs 탐색을 양자 알고리즘으로 해결하려 했으나, 다음과 같은 한계가 지적되었습니다.
  1. 공간 복잡도 과소평가: 기존 연구는 $O(\log N / \log \log N)$ 개의 큐비트만 필요하다고 주장했으나, 이는 이론적 가정의 오류로 인해 실제 필요한 자원을 과소평가한 것으로 보입니다.
  2. 시간 복잡도 분석 부재: 실용적인 유용성을 고려한 시간 복잡도 분석이 생략되었습니다.
  3. 매개변수 최적화의 비효율성: QAOA 는 일반적으로 각 문제 인스턴스마다 최적의 각도 (angles, $\gamma, \beta$) 를 찾는 외부 최적화 루프가 필요하여 계산 비용이 매우 큽니다.
• 목표: 이 논문은 Yan 등의 접근법을 기반으로 하되, 고정된 각도 (Fixed Angles) 를 가진 QAOA 를 사용하여 CVP (Closest Vector Problem) 를 해결하는 방법의 실용적 확장성 (Scalability) 과 시간 복잡도를 분석하는 것을 목표로 합니다. 특히, 소인수분해의 성공 여부보다는 CVP 문제 자체에서의 양자 우위 가능성을 검증하는 데 중점을 둡니다.

2. 방법론 (Methodology)

이 연구는 CVP 문제를 QAOA 를 통해 해결하기 위한 새로운 파이프라인을 제시합니다.

A. 문제 변환: 소인수 분해에서 CVP 로

• 소인수분해는 작은 정수들의 곱이 $N$에 가까운 관계를 찾는 문제로 변환되며, 이는 소수 (Prime) 기반 격자 (Prime Lattice) 상의 CVP 문제로 재정의됩니다.
• Prime Lattice ($L(B_{n,c})$): 소수 기저 (Factor basis) 에 기반한 격자를 구성하며, 목표 벡터 $t$는 $N$의 로그 값과 관련이 있습니다.
• 근사 해의 정제 (Refinement): Babai 의 최近平면 알고리즘 (Nearest Plane Algorithm) 을 사용하여 CVP 의 초기 근사 해 ($b_{op}$) 를 구한 후, 이 해를 중심으로 단위 이웃 (Unit Neighbourhood) 내에서 더 좋은 해를 찾는 '정제' 과정을 수행합니다.

B. QAOA 와 고정 각도 (Fixed Angles) 전략

• 최소 고유 상태 문제: 정제 과정은 이진 변수 $z_j$를 사용하여 격자 벡터의 조합을 최적화하는 QUBO (Quadratic Unconstrained Binary Optimization) 문제로 변환되며, 이는 Ising 해밀토니안으로 매핑되어 QAOA 로 해결됩니다.
• 사전 학습 (Pre-training) 및 고정 각도:
  • 기존 QAOA 는 매 인스턴스마다 각도를 최적화해야 하지만, 이 논문은 사전 학습 (Pre-training) 을 통해 한 번에 좋은 각도 집합을 찾아 고정하는 방식을 도입합니다.
  • 알고리즘 1 (Pre-training Scheme):
    1. 작은 크기의 훈련 데이터셋에서 여러 각도 집합을 학습합니다.
    2. 검증 데이터셋 (Validation set) 에서 각도 집합이 큰 문제 인스턴스로 확장될 때 성능이 어떻게 감소하는지 (Decay) 평가합니다.
    3. 가장 낮은 감쇠율 (Scaling parameter $\alpha$) 을 보이는 각도 집합을 선택하여 고정합니다.
  • 이 방식은 과적합 (Overfitting) 을 방지하고, 큰 문제 인스턴스에 대한 일반화 능력을 확보합니다.

C. 실험 설정

• 데이터: $m$ 비트의 합성수 $N$에 대해 격자 차원 $n \approx m / \log m$을 설정합니다.
• QAOA 깊이: $p=1$부터 $p=10$까지의 다양한 깊이 (Layers) 로 실험합니다.
• 성능 지표: 초기 근사 해 ($b_{op}$) 보다 더 좋은 해를 찾을 확률 ($q(n)$) 을 분석하며, 이 확률의 감쇠율이 $1/2^{\alpha n}$ 형태인지 확인합니다.

3. 주요 기여 (Key Contributions)

1. 강건한 사전 학습 (Pre-training) 체계 제안: CVP 해를 정제하는 데 필요한 계산 요구량을 획기적으로 줄이는 단순하지만 강력한 사전 학습 알고리즘을 개발했습니다. 이는 고정 각도 QAOA 의 실용성을 입증합니다.
2. 새로운 시간 복잡도 분석: Khattar 와 Yosri [36] 의 구현을 기반으로 한 자체 QAOA 구현을 통해, 고정 각도 QAOA 를 사용한 체 (Sieving) 방법의 시간 복잡도를 분석했습니다.
3. Grover 알고리즘을 능가하는 양자 우위:
   • 고정된 깊이 $p$ (최대 10) 에서 QAOA 는 무차별 대입 (Brute-force) 대비 다항식적 우위를 보였습니다.
   • 특히 $p=10$일 때, 감쇠 계수 $\alpha \approx 0.225$로, Grover 알고리즘의 제곱근 속도 향상 (Quadratic speed-up, $\alpha=0.5$) 을 크게 상회하는 5 차 (Fifth-order) 에 가까운 속도 향상을 보였습니다.
   • 이는 $O(2^{0.225n})$의 시간 복잡도를 의미하며, 오류 정정이 필요 없는 얕은 회로 (Shallow circuit) 에서도 달성 가능합니다.

4. 실험 결과 (Results)

• 각도의 수렴 (Convergence): Fig. 6 에서 보듯, 문제의 비트 길이가 증가함에 따라 최적의 QAOA 각도 ($\gamma, \beta$) 가 안정적으로 수렴하는 것을 확인했습니다. 이는 작은 인스턴스에서 학습한 각도가 큰 인스턴스에도 적용 가능함을 의미합니다.
• 확률 감쇠율 (Scaling Parameter):
  • Fig. 2 및 Fig. 7 에서 $p$가 증가함에 따라 확률 감쇠율 $\alpha$가 감소하는 경향을 보였습니다.
  • $p=10$일 때 $\alpha \approx 0.225$를 달성했으며, $p>20$일 경우 $\alpha \approx 0.1$까지 감소할 것으로 외삽되었습니다.
  • 이는 Grover 알고리즘 ($\alpha=0.5$) 대비 월등히 우수한 성능입니다.
• 해의 품질: 격자 차원이 커짐에 따라 정제된 해의 품질 (거리 개선 정도) 은 지수적으로 감소하지 않고 서지수적으로 감소하는 것으로 관찰되었으나, 여전히 체 (Sieving) 에 필요한 수준을 달성하기에는 부족할 수 있음이 지적되었습니다.

5. 의의 및 한계 (Significance & Limitations)

의의

• 양자 암호 안전성 재평가: 고정 각도 QAOA 를 사용한 변분 알고리즘 (Variational Algorithms) 이 격자 기반 암호 (Lattice-based Cryptography) 에 대한 잠재적 위협이 될 수 있음을 시사합니다. 이는 NIST 표준화 된 포스트 양자 암호의 안전성 파라미터 (격자 차원 등) 를 재검토해야 할 필요성을 제기합니다.
• 실용적 양자 알고리즘: 오류 정정이 필요 없는 NISQ (Noisy Intermediate-Scale Quantum) 장치에서도 적용 가능한, 고정 각도 QAOA 의 효율성을 입증했습니다.

한계 및 주의점

1. 제한된 검색 공간: 이 연구는 Yan 등의 가정을 따라 격자 차원을 $O(n)$으로 제한했습니다. 하지만 SVP(Shortest Vector Problem) 와 관련된 기존 연구들은 $O(n \log n)$의 검색 공간이 필요하다고 주장합니다. 현재 설정은 최적 해를 보장하지 못할 수 있으며, 이는 Schnorr 의 소인수분해 주장의 한계와도 연결됩니다.
2. 구체적인 격자 구조: 연구는 소인수분해에 특화된 '소수 격자 (Prime Lattice)'의 특수한 구조 (대칭성 등) 를 활용하여 사전 학습을 수행했습니다. 이 방법이 일반적인 CVP 문제나 더 복잡한 격자 구조로 일반화될 수 있는지는 미지수입니다.
3. 소인수분해 성공 보장 부재: 이 논문은 CVP 문제 해결의 효율성에 초점을 맞췄을 뿐, 이것이 실제로 RSA 와 같은 암호를 깨뜨리는 소인수분해로 이어지는지는 입증하지 않았습니다. (부록 B 에서 Schnorr 의 방법론에 대한 논쟁적 가정을 비판적으로 다룸)

결론

이 논문은 고정 각도 QAOA 를 사용하여 격자 기반 CVP 문제를 해결할 때, 사전 학습을 통해 확장성을 확보하고 Grover 알고리즘을 능가하는 속도 향상을 달성할 수 있음을 실증적으로 보여주었습니다. 이는 근미래의 양자 하드웨어에서 격자 기반 암호 체계의 안전성에 대한 새로운 관점을 제시하며, 암호학계와 양자 컴퓨팅 연구계에 중요한 시사점을 제공합니다.