Rigetti·퍼듀대, 양자 전처리로 조합 최적화 탐색 속도 100배 향상

QPU를 전처리기로 재정의하다

이 연구의 핵심 설계 방향은 양자 처리장치(QPU)를 독립 솔버로 사용하는 대신, 고전 분기한정(branch-and-bound) 탐색을 유도하는 구조 학습 전처리기로 활용하는 것이다. 그래프 분할이나 병렬 과학 계산, 물류 라우팅처럼 균형 제약이 수반되는 조합 최적화 문제는 NP-난해 범주에 속해, Gurobi 같은 상용 솔버도 방대한 탐색 트리를 전부 순회해야 하는 구조적 부담을 안고 있다. 연구팀은 이 병목을 줄이기 위해 QAOA 회로를 먼저 실행해 문제 구조 정보를 추출한 뒤 이를 고전 최적화기에 전달하는 하이브리드 파이프라인을 구성했다.

양자 상관 행렬 생성과 MIP 통합 방식

QAOA 회로는 균형 제약을 비용 해밀토니안 내 연성 페널티 항(ρ)으로 인코딩해 실행된다. 이 회로 측정 결과로부터 결정 변수 쌍들의 정렬 패턴을 담은 두 점 상관 행렬 Zij가 생성되며, 이것이 원래 목적 함수의 간선 가중치 행렬 Wij를 대체한다. 이 단계에서 원래의 균형 제약은 제거되지 않고 MIP 솔버에 경성 제약으로 그대로 이어진다. Gurobi는 재구성된 목적 함수를 풀면서, 양자 회로가 포착한 변수 쌍 선호 정보를 분기 결정의 암묵적 신호로 활용하게 된다. 콜백 궤적 데이터는 이 방식이 솔버로 하여금 탐색 초기 단계에서 훨씬 빠르게 고품질 실행 가능해를 발견하도록 이끈다는 사실을 보여준다.

벤치마크 성능

검증은 노드 수 n = 40인 완전 연결 밀집 그래프 50개 인스턴스를 대상으로 진행됐다. 전처리 적용 시 Gurobi는 기준 전역 최적값의 1% 이내(ε = 0.01) 해를 1초 미만에 발견했다. 동일 조건에서 전처리 없이 실행한 경우에는 같은 품질의 해를 구하는 데 수 시간이 소요됐다. 특히 회로 깊이 p = 1, 즉 단 한 층의 QAOA 반복만으로 대부분의 가속 효과가 실현됐다는 점이 주목된다. 이는 회로를 깊게 쌓지 않아도 실용적 이득을 얻을 수 있어, 현세대 양자 하드웨어의 노이즈 제약 안에서도 활용 가능한 방식임을 시사한다.

파라미터 전이 가능성과 확장성

변분 최적화 비용이 문제 규모에 비례해 급증하는 문제를 완화하기 위해, 연구팀은 n = 20 그래프에서 최적화한 QAOA 파라미터를 재조정 규칙(γℓ ∝ 1/√n)에 따라 더 큰 인스턴스에 이전하는 전략을 시험했다. 성능 저하 없이 파라미터 전이가 성립함을 확인했으며, 이는 매번 새로운 변분 탐색을 수행하지 않아도 된다는 점에서 실용 배포 비용을 낮추는 요인이 된다.

의의와 한계

이 연구는 현세대 NISQ 하드웨어에서 측정 가능한 고전 최적화 가속을 이끌어내는 실용적 경로를 제시한다는 점에서 의미가 있다. 다만 검증 범위는 n = 40 규모의 완전 연결 그래프에 국한돼 있어, 실제 산업 환경에서 마주치는 희소 그래프나 더 큰 규모 인스턴스에 대한 성능은 추가 검증을 필요로 한다. 연성 페널티 항 ρ의 조율 방식이 결과 품질에 미치는 영향 역시 다양한 문제 유형에 걸쳐 체계적으로 분석되지는 않은 상태다.