기술 요약: 저깊이 및 측정을 활용한 피드백 기반 양자 최적화

문제 정의

피드백 기반 양자 최적화 알고리즘(FALQON)은 고전적인 파라미터 최적화 없이 조합 최적화 문제를 해결하기 위해 설계된 하이브리드 양자-고전 알고리즘이다. 이 알고리즘은 변분 양자 알고리즘(VQA)에 내재된 훈련의 어려움을 피할 수 있지만, 표준 FALQON은 과도한 회로 깊이(circuit depth) 문제를 겪는다. 이러한 깊이는 문제 해밀토니안의 기댓값이 단조 감소하도록 보장하기 위해 작은 이산 시간 단계($\Delta t$)가 필요하기 때문에 발생한다. 더 큰 단계는 트로터 분해(Trotter decomposition) 오차를 유발하여 진동을 일으키고 수렴을 방해한다.

이를 해결하기 위해 Arai 등은 비용 함수 차이의 2차 테일러 전개를 사용하는 2차 FALQON(SO-FALQON)을 제안했다. 이를 통해 더 큰 $\Delta t$를 사용할 수 있어 회로 깊이를 크게 줄일 수 있다. 그러나 SO-FALQON은 매 레이어마다 두 개의 추가적인 복잡한 해밀토니안($B_k$ 및 $C_k$)을 추정해야 하는 상당한 측정 오버헤드를 발생시킨다. 이는 단계당 측정 횟수를 기존 FALQON에 비해 약 2.3배 증가시켜, 자원이 제한된 노이즈 중간 단계 양자(NISQ) 장치에 새로운 병목 현상을 만든다.

방법론: BLS-FALQON

저자들은 백트래킹 라인 서치(Backtracking Line Search, BLS) 이론에서 영감을 얻은 휴리스틱 변형인 BLS-FALQON을 제안한다. 이 방법은 SO-FALQON의 높은 측정 오버헤드를 피하면서 SO-FALQON의 낮은 회로 깊이를 달하는 것을 목표로 한다.

핵심 메커니즘

복잡한 해밀토니안 측정이 필요한 2차 제어 계수 $\beta^{(SO)}$를 계산하는 SO-FALQON과 달리, BLS-FALQON은 1차 제어 계수 $\beta^{(FO)}$를 유지하면서 백트래킹 메커니즘을 사용하여 이를 동적으로 조정한다:

1. 초기 단계: 알고리즘은 표준 1차 계수 $\beta^{(FO)}_{k+1} = -A_k$를 계산한다. 여기서 $A_k$는 교환자 $[H_d, H_p]$의 기댓값이다.
2. 모니터링: 각 단계에서 알고리즘은 문제 해밀토니안의 기댓값 $E_k = \langle H_p \rangle$를 함께 추정한다.
3. 백트래킹 트리거: 만약 $E_k$가 단조 감소하지 못하면(즉, $E_k > E_{k-1}$), 이는 트로터 오차나 노이즈로 인한 잠재적 오조향(misdirection)을 나타내며, 알고리즘은 백트래킹 루프를 트리거한다.
4. 교정: 제어 계수는 음의 인자 $\tau \in (-1, 0)$에 의해 반복적으로 스케일링된다:
   $$\beta^{(FO)}_k \leftarrow \tau \beta^{(FO)}_k$$
   음의 부호는 오조향을 바로잡기 위해 제어 방향을 반전시키며, 크기 감소는 진동을 억제한다. 상태는 단조 감소가 관찰될 때까지 재준비(re-prepared)되고 $E_k$가 재평가된다.

측정 효율성

BLS-FALQON의 주요 이론적 이점은 복잡한 해밀토니안 $B_k$와 $C_k$를 추정할 필요가 없다는 것이다. Max-Cut과 같이 문제 해밀토니안 $H_p$가 2-local $ZZ$ Pauli string으로 구성된 문제의 경우, $E_k$의 추정은 $A_k$에 사용되는 기존의 큐비트별 가환(qubit-wise commuting) 부분 집합에 흡수될 수 있다. 결과적으로, 그래프 크기가 $n \ge 12$인 경우 BLS-FALQON의 단계당 측정 기저(measurement bases)는 기존 FALQON과 동일하며, SO-FALQON의 2.3배 오버헤드를 피할 수 있다.

주요 기여

1. 알고리즘 혁신: 2차 해밀토니안 추정의 필요성을 제거하기 위해 1차 제어 계수를 휴리스틱하게 조정하는 수정된 백트래킹 라인 서치 전략을 통합한 BLS-FALQON을 도입하였다.
2. 이론적 분석:
   • 오차 경계: 백트래킹 메커니즘이 유한한 단계 내에 종료됨을 증명하여, 트로터 오차로 인해 초기 방향이 잘못되더라도 유효한 하강 단계가 존재함을 보장한다.
   • 이차 랜드스케이프: 휴리스틱 계수가 (SO-FALQON처럼) 정확한 최적 정점(optimal vertex)은 아닐지라도, 하강 조건(descent condition)을 만족하여 수렴 안정성을 보장함을 분석하였다.
3. 자원 절감: 방법론이 SO-FALQON의 높은 측정 오버헤드를 피하면서도, 최첨단 기술인 SO-FALQON과 유사한 회로 깊이를 유지함을 입증하였다.

실험 결과

수치 시뮬레이션

시뮬레이션은 Qiskit 프레임워크를 사용하여 $n \in \{8, \dots, 20\}$개의 정점을 가진 가중치 없는 3-정규 그래프(unweighted 3-regular graphs)에 대해 수행되었다. 목표는 근사 비율 $r_{GW} = 0.932$ (Goemans-Williamson 경계)이다.

• 측정 오버헤드: BLS-FALQON은 SO-FALQON 대비 37.7%, 표준 FALQON 대비 88.1% 감소된 총 측정 횟수를 기록했다.
• 회로 깊이: BLS-FALQON은 목표 근사 비율에 도달하기 위해 SO-FALQON보다 약 2.5% 더 많은 레이어를 필요로 했다. 이는 백트래킹 계수의 휴리스틱한 특성으로 인한 미미한 증가이다. 그러나 이 깊이는 여전히 표준 FALQON보다 약 11배 낮았다.
• 확장성: 측정 절감 효과는 문제 규모가 커짐에 따라 일관되게 유지되었다.

실제 양자 하드웨어 실험

실험은 Zuchongzhi2 초전도 양자 프로세서를 탑재한 Tianyan-176 양자 컴퓨터에서 수행되었다. 테스트는 결맞음 시간(coherence time) 제약으로 인해 최대 $L=10$ 레이어의 소규모 인스턴스($n \in \{4, 6, 8\}$)로 제한되었다.

• 실행 시간: BLS-FALQON은 SO-FAL_QON 대비 추정 평균 하드웨어 실행 시간을 43% 단축했다. 이 감소는 단계당 필요한 측정 기저의 수가 줄어든 데 직접적으로 기인한다.
• 강건성: 실제 하드웨어 노이즈 환경에서 BLS-FALQON은 세 알고리즘 중 가장 높은 평균 근사 비율을 달야냈으며, $n=4$와 $n=6$에서 가장 좁은 수렴 대역을 보였다.
• 노이즈 영향: 백트래킹 메커니즘은 하드웨어 유도 노이즈에 대한 교정 효과를 제공했다. 노이즈로 인해 $E_k$가 가짜 상승을 보일 때, $\beta$의 교대 부호 스케일링(alternating sign scaling)은 추가적인 해밀토니안 측정 없이도 유효한 하강 계수를 식별하여 제어 방향의 오조향을 부분적으로 보상했다.

의의 및 주장

본 논문은 BLS-FALQON이 회로 깊이와 측정 오버헤드 사이의 트레이드오프를 성공적으로 해결한다고 주장한다. 백트래킹 라인 서치 이론을 활용함으로써, 이 방법은 다음과 같은 성과를 거두었다:

• 낮은 깊이 유지: 최선책인 SO-FALQON과 유사한 회로 깊이를 달성하여, 결맞음 시간이 제한적인 NISQ 장치에서도 사용 가능하다.
• 측정 비용 감소: SO-FALQON에 비해 총 측정 횟수를 크게 낮추었으며, 이는 측정 연산이 시간이 많이 걸리는 실제 하드웨어에서 전체 시간 복잡도를 줄이는 데 매우 중요하다.
• 안정성 향상: 백트래킹 메커니즘은 트로터 분해 오차와 하드웨어 노이즈 모두에 대한 안정화 장치 역할을 하여, 표준 1차 방법들이 진동할 수 있는 곳에서도 단조 수렴을 보장한다.

저자들은 BLS-FALQON이 현재의 NISQ 하드웨어에서 소규모 조합 최적화 문제를 해결하기 위한 실용적이고 효과적인 알고리즘이며, 회로 깊이와 측정 효율성 모두에서 균형 잡힌 개선을 제공한다고 결론짓는다. 또한 현재의 장치 제한으로 인해 하드웨어 결과와 이상적인 시뮬레이션 사이에 격차가 존재하지만, 알고리즘의 설계는 강건하고 확장 가능하다고 언급하였다.