Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling

이 논문은 선형 램프(linear-ramp) QAOA의 두 매개변수를 최적화하기 위한 외삽법을 제안하며, 이 접근 방식이 최대 28 큐비트까지의 포트폴리오 최적화 문제에 대해 고전 알고리즘보다 우수한 런타임 스케일링을 달성함을 입증한다.

핵심

당신은 거대하고 믿을 수 없을 정도로 복잡한 퍼즐을 풀려고 노력 중이라고 상상해 보세요. 당신에게는 오늘날 우리가 가진 최고의 인간 두뇌나 슈퍼컴퓨터보다 더 빠르게 문제를 해결할 수 있을지도 모르는 새로운 첨단 도구(양자 컴퓨터)가 있습니다. 하지만 함정이 하나 있습니다. 이 도구를 작동시키려면 그 조절 나사들을 완벽하게 맞춰야 한다는 것입니다. 만약 나사를 잘못 맞추면, 그 도구는 쓸모없게 됩니다.

이 논문은 처음부터 모든 설정을 일일이 테스트하는 힘든 작업을 하지 않고도, 이 조절 나사들을 튜닝할 수 있는 영리한 지름길에 관한 이야기입니다.

다음은 이들의 여정을 쉽게 설명한 내용입니다:

1. 문제: "양자 라디오" 튜닝하기

그들이 사용하는 도구는 QAOA(양자 근사 최적화 알고리즘)라고 불립니다. QAOA를 많은 잡음 속에서 특정하고 선명한 신호(문제의 최적해)를 찾으려는 라디오라고 생각해 보세요.

• 기존 방식: 보통 신호를 선명하게 만들기 위해서는 수십 개의 조절 나사(파라미터)를 돌리며 반복해서 테스트해야 합니다. 퍼즐이 커질수록 조절해야 할 나비의 개수는 폭발적으로 늘어나고, 튜닝 과정은 영원히 끝나지 않을 것처럼 오래 걸립니다. 이는 마치 100개의 조절 나사가 달린 라디오를 손으로 직접 튜닝하려는 것과 같습니다. 결코 끝낼 수 없을 것입니다.
• 새로운 아이디어 (Linear-Ramp): 연구진은 이를 단순화하는 방법을 찾아냈습니다. 수많은 나비 대신, 오직 두 가지 주요 설정(이를 "속도"와 "방향"이라고 부릅시다)과 하나의 "깊이"(얼마나 오래 들을 것인가) 설정만 조정하면 된다는 사실을 깨달았습니다. 이것이 바로 Linear-Ramp 방식입니다. 이는 마치 볼륨 조절기와 튜닝 다이얼만 있는 라디오를 갖게 되어 사용하기 훨씬 쉬워진 것과 같습니다.

2. 해결책: "작은 퍼즐" 기법 (외삽법)

단 두 개의 조절 나비만 있더라도, 거대한 퍼즐(예: 28조각)의 완벽한 설정을 찾는 것은 여전히 어렵습니다. 단순히 추측할 수는 없습니다.

저자들은 영리한 트릭인 **외삽법(Extrapolation)**을 고안해 냈습니다.

• 비유: 당신이 100마일 트랙에서 경주 자동차가 얼마나 빨리 달릴지 알고 싶다고 가정해 봅시다. 100마일을 전부 달리는 대신(시간이 오래 걸리고 연료도 많이 소모됩니다), 4마일, 6마일, 8마일 구간을 달립니다. 그리고 그 구간에서의 속도를 측정합니다.
• 예측: 그런 다음 그 속도들을 연결하는 선을 그려서, 전체 100마일 트랙에서 자동차가 얼마나 빨리 달릴지 예측합니다.
• 논문에서의 적용: 그들은 자신들의 크고 어려운 문제들(최대 28개의 "비트" 또는 퍼즐 조각)을 아주 작고 쉬운 버전(4, 6, 8 또는 10개 조각)으로 나누었습니다. 그리고 이 작은 버전들에 대한 완벽한 조절 나사 설정을 찾아냈습니다. 그런 다음 수학을 사용하여 이 설정들을 "늘려서" 28조각짜리 큰 문제에 적합한 설정을 예측했습니다.

3. 테스트: 양자 컴퓨터가 이길 수 있을까?

그들은 이 방법을 네 가지 다른 유형의 실제 세계 퍼즐에 테스트했습니다:

1. 포트폴리오 최적화 (Portfolio Optimization): 수익을 극대화하고 리스크를 최소화하기 위해 최적의 주식 조합을 선택하는 것.
2. 특징 선택 (Feature Selection): 머신러닝 모델을 위한 가장 중요한 데이터 포인트를 선택하는 것.
3. 클러스터링 (Clustering): 유사한 항목들을 그룹화하는 것 (예: 빨간색과 파란색 구슬을 분류하는 것).
4. MaxCut: 네트워크를 두 그룹으로 나누어, 그룹 간의 연결이 최대한 강하게 만드는 것.

그들은 이 퍼즐들을 시뮬레이션된 양자 컴퓨터(슈퍼컴퓨터에서 실행되는 완벽하고 노이즈가 없는 버전)에서 실행하여, 결과를 찾는 데 걸린 시간을 기존의 클래식(일반) 컴퓨터 방식과 비교했습니다.

4. 결과: 주식에서는 승리했지만, 다른 곳에서는 아니다

결과는 다음과 같았습니다:

• 주식 시장 퍼즐 (포트폴리오 최적화): 이곳에서 마법이 일어났습니다. 그들의 "작은 퍼즐" 예측 기법을 사용한 양자 방식은 문제가 커짐에 따라 클래식 방식보다 더 빨라졌습니다. 이는 잠재적인 우위를 보여주었습니다. 마치 양자 자동차가 트랙이 길어질수록 인간 운전자를 앞지르기 시작한 것과 같습니다.
• 다른 퍼즐들: 나머지 세 가지 유형의 문제(데이터 선택, 항목 그룹화, 네트워크 분할)의 경우, 양자 방식은 실제로 더 느리거나 클래식 방식과 비슷했습니다. "예측 트릭"은 작동했지만, 양자 도구가 이 특정 사례들에서 인간의 도구를 이기지는 못했습니다.

5. "보편적" 지름길

연구진은 주식 시장 퍼즐을 위한 "완벽한" 조절 나사 설정이 단순한 패턴을 따른다는 것을 발견했습니다. 그들은 매번 새로운 퍼즐마다 설정을 계산할 필요가 없다는 것을 깨닫고, 보편적인 공식(모두에게 적용되는 단 하나의 규칙)을 사용할 수 있었습니다.

• 이 보편적인 규칙을 적용했을 때, 다른 세 가지 퍼즐에 대한 양자 성능이 크게 향상되어 클래식 방식만큼 성능이 좋아졌지만, 그보다 더 뛰어나지는 않았습니다.

핵심 요점

이 논문은 다음과 같이 주장합니다:

1. 큰 문제를 위해 양자 컴퓨터를 튜닝하는 비용이 많이 들고 느린 과정을, 먼저 작은 문제를 테스트하고 수학적으로 나머지를 예측함으로써 건너뛸 수 있습니다.
2. 이 방법은 포트폴리오 최적화의 경우, 문제가 매우 커질 때 양자 컴퓨터가 클래식 컴퓨터보다 더 빠르게 문제를 해결할 수 있음을 보여주는 데 효과적입니다.
3. 테스트된 다른 문제들에 대해서는 양자 컴퓨터가 아직 승리하지는 못했지만, 이 방식은 양자 컴퓨터를 경쟁력 있게 만들어 주었습니다.

중요 참고 사항: 저자들은 이것이 완벽한 컴퓨터에서의 시뮬레이션이라는 점을 주의 깊게 밝히고 있습니다. 그들은 이것이 실제 노이즈가 있는 양자 하드웨어에서도 작동한다는 것을 증명하지 못했으며, 28조각보다 더 큰 문제를 해결하지도 못했습니다. 하지만 "작은 것에서 큰 것으로" 가는 예측 기법은 미래에 양자 컴퓨터를 유용하게 만들 수 있는 유망한 방법으로 보입니다.

기술 요약

기술 요약: 선형 램프(Linear-Ramp) QAOA 파라미터 최적화를 위한 외삽법

문제 정의
양자 근사 최적화 알고리즘(QAOA)은 조합 최적화 문제를 해결하기 위한 유력한 후보이지만, 표준 변분 형태는 상당한 확장성 문제를 안고 있습니다. 표준 방식은 고전적인 루틴을 통해 방대한 수의 회로 파라미터($p$ 깊이에 대해 $2p$개의 파라미터)를 최적화해야 하며, 이는 계산 비용이 많이 들고 지역 최솟값(local minima)에 빠지기 쉽습니다. 이러한 최적화 병목 현상은 잠재적인 양자 런타임 이점을 입증하는 데 걸림돌이 됩니다. 선형 램프 QAOA(LR-QAOA)와 같이 고정된 스케줄을 사용하는 방식은 파라미터 공간을 단 두 개의 자유 파라미터($\Delta\gamma, \Delta\beta$)와 깊이 $p$로 줄여주지만, 큰 문제 크기($N$)에 대해 이러한 파라미터의 최적값을 찾는 것은 여전히 쉽지 않은 과제입니다.

방법론
저자들은 작은 하위 문제(sub-problems)에서 수행된 최적화를 외삽(extrapolation)함으로써 큰 문제 크기에 적합한 LR-QAOA 파라미터를 결정하는 방법을 제안합니다. 이 방법론은 세 가지 주요 구성 요소로 이루어져 있습니다:

1. 문제 정식화: 네 가지 조합 최적화 문제(포트폴리오 최적화, 특성 선택, 클러스터링(Moons 및 Blobs 데이터셋 사용), 가중치 MaxCut)를 이차 불변 이진 최적화(QUBO) 문제로 정식화합니다.
2. 고전적 벤치마킹: 고전적 솔버(CPLEX, Gurobi, Goemans-Williamson, MQLib/Burer2002)의 런타임 스케일링을 평가합니다. MQLib/Burer2002 휴리스틱은 상용 솔버에서 발견되는 최적성 경계(optimality bounds)의 오버헤드를 피하면서 낮은 절대 런타임과 일관된 스케일링 동작을 보이므로 주요 고전적 벤치마크로 선택되었습니다.
3. LR-QAOA 및 외삽 스키마:
   • 선형 램프 안사츠(Linear-Ramp Ansatz): 변분 최적화 대신, 파라미터를 선형 안사츠 $\gamma_j = \Delta\gamma x_j$ 및 $\beta_j = \Delta\beta(1-x_j)$에서 샘플링합니다 (여기서 $x_j$는 선형 램프 변수입니다).
   • 하위 문제 최적화: 목표 문제 크기 $N$(최대 28 큐비트)을 위해, 더 작은 크기의 무작위 하위 인스턴스($\tilde{N} \in \{4, 6, 8, 10\}$)를 생성합니다. 이 작은 인스턴스들에 대해 그리드 탐색(grid search)을 수행하여 최적의 $\Delta\gamma$와 $\Delta\beta$를 찾습니다.
   • 피팅 및 외삽: 높은 확률 영역의 중심을 찾기 위해 최적의 파라미터를 다변량 스큐 가우시안(multivariate skew Gaussian) 함수로 피팅합니다. 이 중심값들은 $\log(\text{parameter})$ 대 $\log(N)$의 로그-로그 스케일 상에서의 선형 관계를 가정하여 목표 크기 $N$으로 외삽됩니다.
   • 깊이 최적화: 회로 깊이와 최적해를 찾는 데 필요한 중앙값 샷(shot) 수의 곱으로 정의되는 총 양자 런타임($D = d \cdot N_{shots}$)을 최소화하도록 QAOA 깊이 $p$를 최적화합니다.
   • 보편적 스케일링(Universal Scaling): 안정성을 높이고 이상치(outlier)를 줄이기 위해, 저자들은 외삽된 데이터를 기반으로 "보편적" 파라미터 스케일링 법칙($f(N) = a \cdot N^b$)을 도출하며, 이를 특정 인스턴스마다 최적화하는 대신 주어진 문제 클래스의 모든 인스턴스에 적용합니다.

주요 결과
본 연구는 노이즈가 없는 양자 에뮬레이터 상에서 문제 크기 $N=28$까지의 양자 런타임 스케일링(총 깊이 $D$로 표현됨)을 고전적 스케일링과 비교 평가합니다.

• 포트폴리오 최적화: 외삽된 파라미터를 사용한 LR-QAOA는 고전적 벤치마크(MQLib/Burer2002)의 $\alpha_{cl} \approx 0.323$보다 현저히 낮은 $\alpha \approx 0.219$ (여기서 $D \propto 2^{\alpha N}$)의 스케일링 지수를 보여줍니다. 이는 잠재적인 양자 스케일링 이점을 나타냅니다.
• 특성 선택, 클러스터링, MaxCut: 초기에는 이 문제들이 고전적 대응물보다 높은 양자 스케일링 지수를 보였습니다. 그러나 외삽 데이터로부터 도출된 "보편적" 파라미터 스케일링을 적용했을 때, 양자 스케일링이 크게 개선되었습니다.
  • 특성 선택 및 MaxCut의 경우, 양자 스케일링은 고전적 벤치마크와 대등한 수준에 도달했습니다 ($\alpha \approx 0.202$ 대 $0.197$및$\alpha \approx 0.163$대$0.156$).
  • 클러스터링(Moons)의 경우, 고전적 벤치마크($\alpha_{cl} \approx 0.051$)가 양자 접근 방식($\alpha \approx 0.163$)보다 여전히 우세했습니다.
• 안정성: 보편적 파라미터를 사용하는 것은 파라미터가 각 인스턴스별로 결정될 때 관찰되었던 극단적인 이상치(매우 큰 깊이를 갖는 인스턴스)의 발생을 크게 감소시켰습니다.
• 확률 거동: 포트폴리오 최적화 및 MaxCut의 경우, 최적해를 측정할 확률($P_{opt}$)은 $N$에 따라 일정하거나 약간 증가하는 반면, 회로 깊이는 대수적으로(algebraically) 스케일링되었습니다. 이는 특정 문제 클래스에 대해 중앙값 런타임의 다항 시간 스케일링 가능성을 시사합니다.

의의 및 주장
본 논문은 큰 회로에 대한 값비싼 변분 최적화 없이 LR-QAOA 파라미터를 결정하는 확장 가능한 방법을 제시한다고 주장합니다. 작은 하위 문제로부터의 외삽을 활용함으로써, 저자들은 다음을 입증합니다:

1. 런타임 이점: 포트폴리오 최적화에서 고전적 휴리스틱 대비 양자 스케일링 이점이 관찰되었습니다.
2. 확장성: 외삽법을 통해 매우 작은 시스템($N \le 10$)의 시뮬레이션을 바탕으로 더 큰 시스템($N=28$)에 대한 파라미터를 효율적으로 추정할 수 있습니다.
3. 보편적 법칙: 파라미터($\Delta\gamma, \Delta\beta, p$)에 대한 대수적 스케일링 법칙의 식별은 이 파라미터들을 특정 문제 인스턴스와 독립적으로 결정할 수 있음을 시사하며, 이는 알고리즘의 견고성을 향상시킵니다.

저자들은 특정 인스턴스(일정한 $P_{opt}$와 대수적 깊이 스케일링으로 나타남)에 대해 다항 시간 솔루션의 가능성을 시사하지만, 더 큰 문제 크기($N > 28$)와 결함 허용(fault-tolerant) 양자 하드웨어에서 이러한 결과를 검증하기 위해 추가 연구가 필요하다는 점을 들어 신중하게 결론을 내립니다. 그들은 자신의 연구가 런타임 구성 요소로서의 파라미터 최적화 비용 자체를 해결하기보다는, 파라미터를 효율적으로 찾을 수 있다고 가정할 때의 LR-QAOA의 일반적인 잠재력을 다루고 있음을 강조합니다.