Setting angles in quantum approximate optimization at utility-scale

이 논문은 근사 기법과 전이 학습 전략을 벤치마킹함으로써 유틸리티 규모(100개 이상의 큐비트)에서 양자 근사 최적화 알고리즘(QAOA)의 최적 파라미터를 결정하는 과제를 다루며, 현재 및 미래의 양자 하드웨어에서 효율적인 엔드 투 엔드 실행을 위한 실행 가능한 운영 지침을 제공한다.

핵심

당신이 100개의 서로 다른 도시를 방문하면서 길을 잃거나 연료를 낭비하지 않고 가장 완벽한 배송 트럭 경로를 찾으려고 한다고 상상해 보세요. 이것은 전형적인 "조합 최적화(combinatorial optimization)" 문제입니다. 양자 컴퓨팅의 세계에는 이 퍼즐을 해결하는 데 도움을 줄 수 있는 **양자 근사 최적화 알고리합(QAOA)**이라는 특별한 도구가 있습니다.

하지만 QAOA는 마치 고성능 라디오 튜너와 같습니다. 가장 선명한 신호(최적의 해답)를 얻으려면, $\beta$와 $\gamma$라고 불리는 두 개의 다이얼인 **각도(angles)**를 정확한 위치로 돌려야 합니다. 만약 아주 조금이라도 잘못 돌린다면, 신호는 잡음이 섞인 상태가 되고 당신은 나쁜 답을 얻게 됩니다.

문제는, 거대한 퍼즐(100개 이상의 도시, 또는 "유틸리티 규모")의 경우, 이 다이얼을 올바르게 돌리는 것이 매우 어렵다는 점입니다. 이는 마치 배터리가 다 되어가는, 소음이 심하고 고장 난 라디오를 들으며 라디오 주파수를 맞추려는 것과 같습니다. 노이즈가 너무 심해서 양자 컴퓨터에 직접 답을 물어볼 수도 없고, 일반 컴퓨터로 답을 시뮬레이션하기에는 너무 느립니다.

이 논문은 저자들이 노이즈 없는 완벽한 양자 컴퓨터 없이도 이 다이얼을 올바르게 돌리는 방법을 알아내기 위해 30가지의 서로 다른 전략을 테스트한 거대한 "현장 테스트" 결과입니다. 그들이 발견한 내용을 쉽게 설명하면 다음과 같습니다.

1. "추측하고 확인하기" vs "지도"

저자들은 올바른 각도를 찾는 두 가지 주요 방법을 테스트했습니다.

• "지도" (매개변수 전이, Parameter Transfer): 처음부터 다시 시작하는 대신, 이미 해결한 더 작고 단순한 퍼즐들을 살펴보았습니다. 그들은 "만약 20개 도시 경로에 적합했던 각도가 100개 도시 경로에도 적합할까?"라고 물었습니다. 알고 보니, 많은 문제에서 작은 퍼즐의 설정을 큰 퍼즐로 "복사하여 붙여넣기" 할 수 있습니다. 이는 자신의 동네를 항해하기 위해 그린 지도를 이용해 도시 전체를 탐색하는 것과 같습니다. 완벽하지는 않겠지만, 즉시 올바른 방향으로 안내해 줍니다.
• "추측하고 확인하기" (반복법, Iterative Methods): 이는 조각가가 조각상을 만드는 것처럼, 대략적인 추측에서 시작하여 층을 쌓듯 천천씩 정교하게 다듬어 나가는 방식입니다. 이 방법은 종종 매우 최적의 각도를 찾아내지만, 돌을 깎아내는 데 시간이 아주 오래 걸립니다.

2. "시뮬레이터" 문제

그들은 100개 도시의 전체 퍼즐을 완벽한 양자 컴퓨터에서 실행할 수 없었기 때문에, 각도를 테스트하기 위해 "시뮬레이터"(양자 컴퓨터인 척하는 일반 컴퓨터)를 사용해야 했습니다. 그들은 두 가지 유형의 시뮬레이터를 사용했습니다.

• "거친 스케치" (MPS): 답을 근사적으로 보여주는 더 빠르고 단순한 시뮬레이션입니다.
• "상세한 설계도" (Pauli Propagation): 수학을 더 정밀하게 추적하는 더 복잡한 시뮬레이션입니다.

놀라운 사실: 때때로 실제 양자 하드웨어에서 테스트를 수행했을 때, "상세한 설계도"보다 "거친 스케치"가 더 좋은 결과를 주는 경우가 있었습니다. 이는 거칠게 손으로 그린 지도가 실제 교통 상황에 혼란을 느끼는 초정밀 GPS보다 운전자에게 더 잘 안내할 수 있는 것과 같습니다. 저자들은 항상 가장 완벽한 시뮬레이션이 필요한 것은 아니며, 단지 당신을 올바른 방향으로 안내해 줄 수 있는 것이 중요하다는 것을 배웠습니다.

3. "속도 vs 품질"의 절충

저자들은 시간과 품질 사이의 최적의 균형을 그래프 위에 선으로 나타내는 방식인 "파레토 프런티어(Pareto Frontier)"를 만들었습니다.

• 급행 차선: 만약 빠르게 괜찮은 답을 얻고 싶다면(몇 초 이내), "고정된 각도"(문제 유형에 따라 미리 설정된 다이얼)나 "매개변수 전이"가 승자입니다. 당신은 거의 즉시 최상의 솔루션의 80~85%를 얻을 수 있습니다.
• 완행 차선: 만약 각도를 "깎아내는 데"(반복법) 몇 시간 또는 며칠을 소비한다면, 아주 약간의 품질(약 1~2%)을 더 끌어올릴 수는 있지만, 그 추가적인 노력은 흔히 가치가 없습니다. 왜냐하면 실제 양자 컴퓨터는 너무 노이즈가 심해서 "완벽한" 각도와 "충분히 좋은" 각도의 차이를 구분조차 할 수 없기 때문입니다.

4. 모든 것에 통용되는 정답은 없다

그들은 다양한 유형의 퍼즐(예를 들어, 친구들을 두 팀으로 나누는 MaxCut이나, 서로 모르는 사람 중 가장 큰 그룹을 찾는 MIS)에 대해 테스트했습니다.

• 교훈: 한 유형의 퍼즐에 완벽하게 작동하는 전략이 다른 유형의 퍼즐에서는 처참하게 실패할 수 있습니다. 예를 들어, "푸리에(Fourier)"라는 방법은 친구들을 팀으로 나누는 데는 형편없었지만, 낯선 사람들의 그룹을 찾는 데는 매우 뛰어났습니다. 당신은 특정 작업에 맞는 적절한 도구를 선택해야 합니다.

결론

이 논문의 결론은, 오늘날의 노이즈가 있는 양자 컴퓨터를 사용할 때는 완벽주의자가 될 필요가 없다는 것입니다.

수학적으로 완벽한 각도 설정을 찾는 것은 종종 시간과 에너지 낭비가 될 수 있는데, 왜냐하면 하드웨어가 그 정밀함의 이점을 누릴 만큼 정교하지 않기 때문입니다. 대신, "유틸리티 규모"의 문제(100 큐비트 이상)를 위한 최선의 접근 방식은 다음과 같습니다.

1. 미리 설정된 각도를 사용하거나, 유사한 작은 문제로부터 각도를 전이하십시오.
2. 검토를 위해 빠르고 근사적인 시뮬레이션을 사용하십시오.
3. 너무 오래 걸리면서 실제 기계에서는 제대로 작동하지 않을 수도 있는 "완벽한" 솔루션을 쫓기보다는, 빠르게 얻을 수 있는 "충분히 좋은" 솔루션을 받아들이십시오.

요약하자면: 튜닝에 너무 깊이 고민하지 마세요. 좋은 지도를 사용하고, 차에 올라타서, 그냥 달리세요.

기술 요약

기술 요약: 유틸리티 규모의 양자 근사 최적화에서의 각도 설정

문제 정의
양자 근사 최적화 알고리즘(QAOA)은 양자 하드웨어에서 조합 최적화 문제를 해결하기 위한 선도적인 휴리스틱입니다. 그러나 QAOA 회로를 위한 최적의 변분 파라미터(각도 $\theta$)를 식별하는 것은 특히 "유틸리티 규모"(여기서는 $\sim100$ 큐비트 이상으로 정의)에서 중요한 병목 현상으로 남아 있습니다. 이 규모에서는 양자 회로의 정확한 고전적 시뮬레이션이 불가능하며, 노이즈, 제한된 결맞음 시간, 큐 대기 시간 등으로 인해 양자 하드웨어와의 폐쇄 루프(closed-loop) 최적화는 비용이 매우 많이 듭니다. 또한, 이론적 결과에 따르면 최적의 각도를 찾는 것은 NP-hard이며, 최적화 지형(landscape)에는 로컬 미니마(local minima)가 산재해 있습니다. 결과적으로, 자원이 많이 소모되는 양자-고전 피드백 루프에 의존하지 않고 대규모 문제에 대해 어떤 각도 설정 전략이 최상의 솔루션을 제공하는지에 대한 경험적 가이드라인이 부족한 실정입니다.

방법론
저자들은 QAOTA 실무자들에게 운영 지침을 제공하기 위해 종합적인 벤치마킹 연구를 수행합니다. 방법론은 다음과 같습니다:

1. 분류 체계 구축: 기존의 각도 설정 방법을 네 가지 범주(물리 기반(예: 선형 램프, 역대각 성분(counterdiabatic)), 파라미터 전이(예: 고정 각도, 클러스터링), 반복적(예: 보간법, 레이어별 최적화), 머신 러닝)로 분류합니다.
2. 근사 에너지 평가: 정확한 고전적 시뮬레이션이나 즉각적인 하드웨어 접근의 필요성을 우회하기 위해, 본 연구는 훈련 단계 동안 비용 함수 $\langle H_C \rangle$를 평가하기 위해 근사적인 고전적 방법들을 사용합니다. 구체적으로 다음을 활용합니다:
   • 행렬 곱 상태 (Matrix Product States, MPS): 얽힘 구조를 처리하기 위해 최적화된 큐비트 매핑(SAT 매핑)을 사용하는 텐서 네트워크를 사용합니다.
   • 파울리 전파 (Pauli Propagation, PP): 파울리 연산자의 변환을 추적하는 하이젠베르크 묘사 기반의 역전파 방법으로, 희소 그래프(sparse graphs)에 효과적입니다.
3. 벤치마킹 프로토콜: 저자들은 세 가지 문제 클래스(MaxCut, Maximum Independent Set (MIS), Low Autocorrelation Binary Sequence (LABS))에 대해 30가지의 서로 다른 각도 설정 전략을 테스트합니다.
   • 규모: 벤치마크는 정확한 상태 벡터(statevector) 시뮬레이션이 가능한 소규모 인스턴스(20–50 큐비트)부터 유틸리티 규모 인스턴스(최대 144 큐비트)까지 범위를 가집니다.
   • 하드웨어 검증: 선택된 최적 각도는 실제 양자 하드웨어(IBM Quantum 장치, 구체적으로 ibm_boston 및 ibm_fez)에서 실행되어 실제 근사 비율을 측정하고 고전적 훈련 결과를 검증합니다.
4. 자원 분석: 본 연구는 계산 예산(고전적 최적화 및 양자 샘플링을 포함한 총 실행 시간)과 솔루션 품질 사이의 트레이드오프를 분석하기 위해 확률적 벤치마크(Stochastic Benchmark) 프레임워크를 활용합니다.

주요 기여

• 경험적 분류 및 벤치마킹: 본 논문은 소규모의 고전적 시뮬레이션 가능 인스턴스를 넘어, 유틸리티 규모에서의 QAOA 각도 설정 방법에 대한 최초의 대규모 체계적 비교를 제공합니다.
• 근사 방법의 검증: 고전적 근사 방법(MPS 및 PP)이 최대 144 큐비트까지의 문제에 대해 각도 최적화를 효과적으로 가이드할 수 있음을 입증하며, 특히 특정 그래프 토폴로지(heavy-hex)에서 PP가 하드웨어 결과와 더 우수한 상관관계를 보임을 보여줍니다.
• 하드웨어 검증: 근사 방법으로 고전적으로 최적화된 각도가 실제 하드웨어에서 의미 있는 성능으로 전환됨을 검증하지만, 회로 깊이가 깊어질수록 노이즈로 인해 방법 간의 구분이 어려워짐을 확인했습니다.
• 운영 가이드라인: 자원 제약 및 문제 유형에 따라 실무자가 사용할 수 있는 구체적인 권장 사항을 도출하며, 실행 시간과 솔루션 품질 사이의 최적의 트레이드오프를 제공하는 방법을 식별합니다.

결과

• 방법론의 성능:
  • 선형 램프(Linear Ramps) 및 보간(Interpolation) 방법은 대부분의 그래프 유형과 에너지 평가 기법에 대해 일반적으로 가장 좋은 각도를 제공했습니다.
  • 고정 각도(Fixed Angles) (무작위 정규 그래프를 위해 도출된)는 유사한 문제 인스턴스로 전이되었을 때 매우 뛰어난 성능을 보였으며, 최소한의 최적화만으로도 90% 이상의 근사 비율을 달성하는 경우가 많았습니다.
  • 파라미터 전이(Parameter Transfer) 전략(고정 각도 또는 소규모에서 대규모 인스턴스로의 전이 사용)은 매우 효율적이었으며, 종종 반복적 방법보다 시간 대비 솔루션 품질 측면에서 우수한 성능을 보였습니다.
  • 푸리에(Fourier) 방법은 높은 분산을 보였으며, MIS와 같은 일부 사례에서는 다른 방법들을 능가하기도 했으나 MaxCut에서는 성능이 저조했습니다.
• 근사 평가기:
  • **파울리 전파(PP)**는 일반적으로 MPS보다 하드웨어 상의 실제 에너지 지형을 더 잘 근사하였으며, 특히 heavy-hex 그래프에서 추정된 근사 비율과 하드웨어 근사 비율 사이에 강한 양의 상관관계(0.89–0.93)를 보였습니다.
  • MPS는 특정 토폴로지에서 더 빨랐으나, 작은 사이클이 있는 라인 기반 그래프에서 하드웨어 결과와 음의 상관관계를 보이는 문제가 있었습니다.
• 하드웨어의 현실: 유틸리티 규모(144 큐비트, 깊이 $p=10$)에서, 노이즈는 서로 다른 각도 설정 방법 간의 구별 능력을 크게 저하시켰습니다. 반복적 방법(예: Interp.)이 시뮬레이션에서는 고품질의 각도를 생성했지만, 실제 하드웨어에서는 고정 각도나 선형 램프와 같은 더 빠른 비반복적 방법들에 비해 그 이점이 줄어들었습니다.
• 자원 트레이드오프: 파레토 프런티어(Pareto frontier) 분석 결과, 저비용 전략(파라미터 전이, 고정 각도)이 고품질 솔루션에 도달하는 가장 빠른 경로임을 밝혀냈습니다. 반복적 방법은 하드웨어 근사 비율에서 미미한 이득을 얻기 위해 상당한 계산 비용(종종 $>10^4$ 초)을 소모합니다.

의의 및 주장
본 논문은 "유틸리티 규모" 시대의 필수적인 운영 가이드를 제공한다고 주장합니다. 저자들은 최적의 각도를 찾는 것이 이론적으로는 어렵지만, 다음과 같은 방식을 활용하면 실질적인 워크플로우가 성공할 수 있다고 주장합니다:

1. 전이 학습(Transfer Learning): 소규모 또는 대표적인 인스턴스에서 훈련된 고정 각도나 파라미터를 사용하여 대규모 인스턴스의 최적화를 초기화합니다.
2. 근사 훈련(Approximate Training): 각도를 찾기 위해 폐쇄 루프 양자 하드웨어 훈련에 의존하는 대신, 고전적 근사 시뮬레이터(MPS/PP)를 활용하고 하드웨어 접근은 최종 샘플링을 위해서만 예약합니다.
3. 비용 인식 선택(Cost-Aware Selection): 실행 시간과 품질 사이의 균형을 맞추는 방법을 우선시합니다. 저자들은 많은 실제 응용 분야에서 광범한 각도 최적화의 "수익 체감(diminishing returns)" 현상은, 하드웨어 노이즈가 작은 성능 차이를 가릴 때 빠른 전이 기반 방법들이 복잡한 반복적 최적화보다 선호될 수 있음을 시사합니다.

본 연구는 하드웨어 토폴로지와 일치하는 문제들에 대해 $p \le 10$ 깊이의 표준 QAOA를 이러한 전략들을 사용하여 엔드 투 엔드로 효율적으로 실행할 수 있다고 결론짓습니다. 또한 이러한 통찰이 대칭성이나 국소성(locality)과 같은 구조적 장애물을 극복하는 QAOA 변형 모델(예: warm-start, R-QAOA)에도 전이될 수 있을 것으로 보고 있습니다.