Resource-Efficient Digitized Adiabatic Quantum Factorization

기술 요약: 자원 효율적인 디지털화된 단열 양자 인수분해

문제 정의
본 논문은 디지털화된(게이트 기반) 양자 컴퓨터에서 효율적인 단열 양자 인수분해를 구현하는 과제를 다룹니다. Peng 등 [1]이 제안한 표준 방식은 정수 인수분해를 다항 비제약 이진 최적화(PUBO) 함수로부터 유도된 문제 해밀토니안의 바닥 상태 탐색으로 공식화합니다. 이러한 공식화는 3-큐비트 및 4-큐비트 상호작용 항($Z^3$ 및 $Z^4$)을 포함하는 비로컬 해밀토니안을 생성합니다. 디지털 장치에서 이러한 고차 상호작용은 여러 개의 네이티브 2-큐비트 게이트(예: CNOT)로 분해되어야 하므로, 높은 게이트 수를 가진 깊은 회로를 초래합니다. 이러한 복잡성은 알고리즘의 충실도와 확장성을 심각하게 제한하며, 머신 러닝 기법을 사용하더라도 91보다 큰 숫자에 대해서는 성공 확률이 급격히 떨어집니다.

방법론
저자들은 이차 비제약 이진 최적화(QUBO) 프레임워크를 사용하여 인수분해 문제를 재구성하는 새로운 디지털 단열 알고리즘을 제안합니다. 핵심적인 방법론적 변화는 두 가지 주요 변경 사항을 포함합니다:

1. 커널 부공간 인코딩 (Kernel Subspace Encoding): 솔루션을 제곱 함수 $F^2$의 바닥 상태(에너지 최소값)로 인코딩하는 대신, 저자들은 문제 해밀토니안 $\hat{H}_{LP}$를 선형 함수 $F(N, \hat{p}', \hat{q}')$ 자체로 정의합니다. 이 공식화에서 솔루션은 해밀토니안의 제로 에너지 고유상태(커널 부공간)에 해당하며, 이는 전체 스펙트럼에 대해 들뜬 상태(excited state)입니다.
2. QUBO 공식화: 선형 함수를 활용함으로써, 결과 해밀토니안은 2-바디 상호작용만을 포함하게 되어 QUBO 문제로 분류됩니다. 이를 통해 PUBO 문제를 QUBO로 매핑하는 데 일반적으로 필요한 NP-어려운 다항 축소 및 보조 변수의 필요성을 제거합니다.

알고리즘은 변분 양자 알고리즘(구체적으로 QAOA)을 사용하여 구현됩니다. 프로토콜은 균일 중첩 상태(구체적으로 $\hat{H}_{LP}$의 영-부공간과 일치하도록 $|+\rangle|-\rangle\dots$ 사용)에서 시스템을 초기화하고, 비용 해밀토니안($\hat{H}_{LP}$)과 혼합 해밀토니안($\hat{H}_M$)에서 유도된 교대 유니터리를 사용하여 진화시킵니다. 클래식 옵티마이저에 의해 최소화되는 비용 함수는 제로 고유값 솔루션으로의 수렴을 보장하기 위해 해밀토니안의 절댓값의 기댓값인 $C_{LP} = \langle |\hat{H}_{LP}| \rangle$로 정의됩니다.

주요 기여

• 회로 단순화: 제안된 QUBO 접근 방식은 문제 해밀토니안을 2-바디 상호작용으로 감소시킵니다. 이는 복잡한 다중 큐비트 게이트의 분해를 제거하여 회로 깊이를 크게 줄입니다.
• 새로운 인코딩 전략: 본 논문은 바닥 상태가 아닌 커널 부공간(제로 에너지 들뜬 상태)을 목표로 함으로써 단열 인수분해가 성공적으로 수행될 수 있음을 입증하며, PUBO 공식화의 한계를 우회합니다.
• 강건성 분석: 저자들은 해밀토니안의 스펙트럼 밀도를 분석하여, QUBO 공식화가 PUBO 공식화에 비해 솔루션 부근에서 더 희소한 상태 밀도를 제공하며, 이것이 최적화 과정에서의 로컬 미니마 및 배런 플래토(barren plateaus)를 피하는 데 도움이 됨을 보여줍니다.

결과
저자들은 8비트 정수(구체적으로 $N=25, 119, 143$)를 인수분해하기 위해 QUBO 기반 알고리즘을 표준 PUBO 접근 방식과 벤치마킹했습니다.

• 게이트 복잡도: QAOA 회로의 단일 레이어에 대해, QU độ 방식은 현저히 적은 수의 CNOT 게이트를 요구합니다. 예를 들어, $N=25$를 인수분해할 때 QUBO 방식은 레이어당 8개의 CNOT가 필요한 반면, PURO 방식은 (3- 및 4-큐비트 게이트 분해 후) 34개의 CNOT가 필요합니다.
• 충실도 및 신뢰도: QUBO 알고리즘은 올바른 인수를 식별하는 데 있어 실질적으로 높은 충실도를 보여줍니다. $N=119$ 및 $N=143$과 같은 더 큰 숫자의 경우, PUBO 방식은 올바른 솔루션에 확률 진폭을 집중시키지 못해 낮은 신뢰도 점수와 높은 섀넌 엔트로피를 초래합니다. 반면, QUBO 방식은 올바른 솔루션 상태를 성공적으로 채웁니다.
• 비용 함수 수렴: QUBO 알고리즘은 PUBO 방식(최대 2 orders of magnitude)보다 더 깊은 비용 함수 감소(최대 3 orders of magnitude, $N=143$ 기준)를 달ีก하여 더 효과적인 최적화를 나타냅니다.
• 스펙트럼 분석: 에너지 스펙트럼 분석 결과, PUBO 해밀토니안은 솔루션 근처에 높은 상태 밀도를 가져 클래식 옵티마이저를 방해하는 "평탄한" 지형을 만드는 반면, QUBO 해밀토니안은 커널 부공간 근처에서 더 넓게 퍼진 스펙트럼과 더 큰 에너지 갭을 보여 상태 준비를 용이하게 합니다.

의의 및 주장
본 논문은 이 연구가 디지털화된 단열 양자 인수분해를 위한 자원 효율적인 경로를 제공한다고 주장합니다. 주요 의의는 회로 복잡도의 상당한 감소와 그에 따른 알고리즘 충실도의 향상에 있으며, 이는 근접 미래의 장치(near-term devices)에서 더 큰 정수의 인수분해를 가능하게 합니다.

저자들은 들뜬 상태(커널)를 목표로 하는 것이 양자 어닐러에게는 바닥 상태의 결맞음 보호(decoherence protection)가 부족하여 어려울 수 있지만, 디지털 양자 어닐러에게는 유리하다고 강조합니다. 결맞음이 주로 국소적인 단일 큐비트 붕괴에 의해 지배되는 게이트 기반 시스템에서는, QUBO 방식의 감소된 게이트 수가 총 실행 시간과 오류 노출을 최소화합니다. 결과는 QUBO 기반 공식화가 특정 문제 구조에서 PUBO가 필요하거나 우월하다고 가정했던 기존 문헌의 가설에 도전하며, QAOA 기반 최적화에서 PUBO 기반 방식보다 뛰어날 수 있음을 시사합니다. 이 연구는 더 광범위한 수론적 문제와 복잡한 해밀토니안에 대한 디지털 단열 프로토콜의 탐구를 촉발합니다.