From Period Finding to Lattice Sampling: Experimental Insights into Shor's and Regev's Factoring Algorithms

기술 요약: 주기 찾기에서 격자 샘플링으로

문제 정의
쇼어 알고리즘(Shor's algorithm)은 이론적으로 정수 분해를 다항 시간 내에 해결하지만, 현재의 노이즈가 있는 중간 규모 양자(NISQ) 하드웨어에서의 실제 구현은 회로 깊이, 게이트 오류 및 결맞음(decoherence)에 의해 심각하게 제한됩니다. 이러한 한계는 문제를 1차원 주기 찾기 문제가 아닌 고차원 격자 샘플링 과제로 재구성하는 레게브 알고리즘(Regev's algorithm)과 같은 대안적 인수분해 알고리즘에 대한 관심을 불러일으켰습니다. 그러나 기존의 실험적 분석은 서로 다른 알고리즘 구조가 실제 하드웨어 노이즈와 어떻게 상호작용하는지 이해하기 위한 체계적인 다중 백엔드 비교가 부족한 경우가 많습니다. 본 연구는 쇼어 알고리즘과 레게브 알고리즘을 실제 양자 하드웨어에서 실험적으로 비교함으로써 이들의 상대적인 견고성과 실패 모드를 규명하고자 합니다.

방법론
저자들은 벤치마크 인스턴스 $N = 15$를 사용하여 통제된 실험 연구를 수행했습니다. 두 알고리즘 모두 Qiskit을 사용하여 구현되었으며, 두 개의 서로 다른 양자 백엔드인 CESGA(Centro de Supercomputación de Galicia)의 QMIO 양자 컴퓨터와 IBM의 오픈 액세스 양자 프로세서(ibm_torino)에서 실행되었습니다. 이상적인(노이즈가 없는) 시뮬레이션은 참조 베이스라인으로 사용되었습니다.

• 알고리즘 구성:
  • 쇼어 알고리즘: 기저 $a=2$, 제어 레지스터 $k=3$ 큐비트를 사용하여 위수(order) $r=4$를 찾는 데 사용되었습니다. 회로의 깊이를 최소화하기 위해 일반적인 산술 연산 대신 치환(permutation)에 기반한 특화된 얕은 모듈러 지수 연산 구조를 활용했습니다.
  • 레게브 알고리즘: 2차원 인스턴스($d=2$, 기저 $a_1=4, a_2=49$)로 구성되었습니다. $\mathbb{Z}^d$ 상의 가우시안 중첩(Gaussian superposition)을 적용한 후, 이중 격자(dual lattice)의 벡터를 근사하기 위해 푸리에 샘플링을 수행했습니다.
• 컴파일 및 실행: 각 백엔드의 네이티브 게이트 세트와 연결성에 맞춰 조정된 파라미터를 사용하여 Qiskit으로 회로를 트랜스파일했습니다. 모든 하드웨어 실행에는 4,096회의 샷(shots)이 사용되었습니다.
• 평가 지표: 모든 실행에 대해 완전한 고전적 재구성을 수행하지 않고도 노이즈의 영향을 정량화하기 위해, 저자들은 분포 기반 지표를 도입했습니다:
  • 샤논 엔트로피 ($H(p)$): 확률 분포의 분산 정도를 측정합니다.
  • 유효 지원 크기 ($N_{eff}$): 분포에 유의미하게 기여하는 결과값의 수를 추정합니다.
  • Top-K 질량 ($M_4$): 가장 빈도가 높은 4개의 결과에 포함된 총 확률의 비율입니다.

주요 기여

1. 통제된 실험적 벤치마크: 본 논문은 동일한 문제 인스턴스($N=15$)에 대해 여러 하드웨어 플랫폼 및 이상적인 시뮬레이션 환경에서 쇼어 알고리즘과 레게브 알고리즘을 직접적이고 저수준(low-level)에서 비교하는 벤치마크를 제공합니다.
2. 다중 백엔드 평가: IBM 및 QMIO 장치 모두에 대한 결과를 보고하여, 서로 다른 하드웨어 아키텍처가 알고리즘 성능에 미치는 영향에 대한 통찰을 제공합니다.
3. 정보 인코딩 해석: 연구는 "정보 집중"(쇼어) 대 "정보 분산"(레게브)이라는 관점을 통해 실험 결과를 해석합니다. 이는 이러한 구조적 차이가 측정 히스토그램에서 어떻게 질적으로 다른 노이즈 유발 퇴화를 초래하는지 보여줍니다.
4. 재현성: 저자들은 실험적 분포를 생성하는 데 사용된 구체적인 알고리즘 파라미터와 컴파일 파이프라인을 보고합니다.

결과
실험 데이터는 NISQ 제약 조건 하에서 두 알고리즘의 뚜렷한 실패 모드를 드러냅니다:

• 쇼어 알고리즘 (정보 집중):

  • 이상적인 시뮬레이션에서 확률 질량은 소수의 스펙트럼 피크에 고도로 집중됩니다 (낮은 엔트로피, $N_{eff} \approx 4$, $M_4 = 1.0$).
  • IBM 하드웨어에서는 분포가 넓어지지만 지배적인 피크를 유지하며 ($M_4 = 0.921$), 이를 통해 위수 복구의 부분적 성공이 가능합니다.
  • 더 노이즈가 많은 QMIO 장치에서는 스펙트럼 피크가 크게 평탄화되고 가려져 ($M_4 = 0.564$, $N_{eff} \approx 7.8$), 고전적 재구성에 필요한 주기적 구조의 상실을 초래합니다.
  • 관찰: 쇼어 알고리즘은 위상 오류(phase error)에 매우 민다감합니다. 일단 노이즈에 의해 날카로운 피크가 넓어지면, 알고리즘은 유용한 정보를 제공하지 못하고 실패합니다.

• 레게브 알고리즘 (정보 분산):

  • 이상적인 시뮬레이션에서 분포는 쇼어보다 본질적으로 더 분산되어 있지만, 여전히 이중 격자와 일치하는 일련의 지배적인 벡터들을 나타냅니다 ($N_{eff} \approx 2.34$, $M_4 = 0.944$).
  • IBM 하드웨어에서는 분포가 더 퍼지지만 ($M_4 = 0.645$), 일부 결과값이 여전히 격자 축소(lattice reduction)를 지원할 만큼 지배적인 상태를 유지합니다.
  • QMIO에서는 기하학적 신호가 강력하게 희석되어 ($M_4 = 0.29$, $N_{eff} \approx 15.8$), 확률 질량이 많은 벡터에 균등하게 퍼지면서 격자 구조를 효과적으로 가려버립니다.
  • 관찰: 레게브 알고리즘은 여러 상관된 샘플 간의 통계적 편향에 의존합니다. 비록 더 얕은 회로 깊이를 사용함에도 불구하고 (표 2에서 레게브의 컴파일된 깊이가 두 플랫폼 모두에서 쇼어보다 낮음을 확인), 다차원 샘플링 단계에서 발생하는 노이즈 민감도가 기하학적 신호의 급격한 분산을 초래합니다.

• 회로 깊이 대 견고성: 레게브 알고리즘이 더 얕은 컴파일된 회로 깊이를 가짐에도 불구하고 (예: IBM에서 147 대 210), 이러한 감소가 현재 하드웨어에서의 우수한 견고성으로 이어지지는 않았습니다. 노이즈 발생 시 레게브의 측정 분포가 쇼어에 비해 더 빠르게 분산되었습니다.

의의 및 주장
본 논문은 작은 $N$ 영역($N=15$)의 현재 NISQ 장치에서 두 알고리즘 중 어느 것도 서로에 대해 실질적인 우위를 점하지 못한다는 점을 겸허히 주장합니다. 대신, 본 연구는 다음과 같은 근본적인 트레이드오프를 강조합니다:

• 쇼어 알고리즘은 노이즈가 적을 때는 매우 구조화되고 집중된 출력을 얻지만, 위상 결맞음(phase coherence)을 잃으면 치명적으로 실패합니다.
• 레게브 알고리즘은 정보를 고차원 공간에 분산시키며, 이는 더 큰 문제에 대해 다른 스케일링 특성을 제공할 수 있으나, 현재는 다차원 샘플링에서의 노이즈 민감도 증가로 인해 어려움을 겪고 있습니다.

저자들은 이러한 결과가 알고리즘 설계 선택의 실제적인 함의를 이해하기 위한 실험적 벤치마킹의 가치를 강조한다고 결론짓습니다. 그들은 결함 허용(fault-tolerant) 환경에서의 점근적 관계가 NISQ 하드웨어에서 동일한 동작을 보장하지 않음을 강조하며, 정보의 인코딩 방식(집중 vs 분산)이 노이즈가 어떻게 나타나고 알고리즘이 어떻게 실패하는지를 결정한다고 설명합니다. 향후 연구로는 더 큰 $N$으로 벤치마크를 확장하고 이러한 특정 트레이드오프를 겨냥한 오류 완화 전략을 탐구하는 것이 제안되었습니다.