Rigetti, 양자 사전조건화 알고리즘으로 고전 최적화 속도 최대 432배 향상 시연

알고리즘 설계: 고전 솔버를 대체하지 않고 보강한다

양자 사전조건화의 핵심 아이디어는 양자 컴퓨터가 최적화 문제를 직접 풀도록 강요하는 대신, 고전 솔버가 더 빠르게 수렴할 수 있도록 입력 형태를 변환하는 데 있다. 구체적으로는 매개변수형 양자 회로를 실행해 양자 상관 행렬(quantum correlation matrix)을 계산하고, 이를 시뮬레이티드 어닐링이나 Burer-Monteiro 솔버 같은 기존 고전 최적화기의 입력값으로 대체해 넣는다. 회로 심도 p를 높일수록 사전조건화 효과가 커지지만, 현 세대 양자 하드웨어에서는 낮은 p 값부터 실용성을 검증하는 방식을 택했다.

이 접근법은 QAOA(양자 근사 최적화 알고리즘)와 같은 매개변수형 회로 구조를 활용하면서도, QAOA가 고전 경쟁자를 앞서려면 필요한 대규모 회로 요건에서 비교적 자유롭다. 기존 최적화 파이프라인에 추가 수정 없이 접목할 수 있다는 점도 실용적 강점으로 꼽힌다.

수치 벤치마크: 4,096변수 최대 절단 문제

Rigetti 연구팀은 Sherrington-Kirkpatrick 스핀 유리 모델과 3-정규 그래프 최대 절단 문제를 표준 벤치마크로 사용했다. 변수 4,096개짜리 최대 절단 문제에서 99.9% 정확도를 목표로 설정했을 때, 시뮬레이티드 어닐링은 최소 9배, Burer-Monteiro 솔버는 최소 432배 빠른 수렴 속도를 기록했다. 이 수치는 동일한 정확도 기준을 사전조건화 없이 달성하는 경우와의 반복 횟수 비교에 근거한다.

전력망 실증: 사우스캐롤라이나 데이터셋

수학적 벤치마크에서 나아가, 공개 데이터셋을 바탕으로 사우스캐롤라이나 전력망의 최대 전력 교환 단면 문제를 풀었다. 410개 변수를 포함하는 이 문제에서 사전조건화 단계는 Ankaa-3 시스템에서 수행됐으며, 회로 심도는 p=1로 설정됐다. Burer-Monteiro 솔버는 사전조건화된 입력을 받을 경우 99.95% 정확도 해를 원래 문제 대비 4분의 1 수준의 반복 횟수로 도출했다. 충실도가 완벽하지 않은 현실적인 조건에서도 상대적 우위가 관찰됐다는 점이 주목된다.

미해결 과제: 사전조건화 시간 예산

연구팀은 사전조건화 단계 자체에 소요되는 시간을 전체 성능 평가에 포함시켜야 한다고 명시했다. 양자 회로 실행 시간까지 더했을 때 전체 파이프라인이 고전 솔버 단독 실행보다 빠른지를 따지는 '시간 예산' 분석이 향후 핵심 과제다. 초전도 플랫폼은 마이크로초 단위 회로 실행이 가능하다는 장점이 있으나, 이를 실질적인 이점으로 전환하기 위한 추가 최적화가 필요하다. 이 연구는 미국 에너지부 산하 SQMS 센터의 지원을 받았다.

의미와 한계

양자 사전조건화는 현 세대 하드웨어의 큐비트 수와 충실도 제약 안에서 동작 가능하도록 설계됐다는 점에서 실용성이 부각된다. 그러나 전체 런타임 우위 입증은 아직 미완이며, p=1 수준의 낮은 사전조건화 깊이에서 얻은 결과를 더 복잡한 실문제로 일반화하기 위해서는 추가 연구가 필요하다.