QALM: Escaping Local Minima via Interleaved Exploration and Exploitation in Quantum Circuit Optimization

이 논문은 규칙 기반의 효율성과 탐색 기반의 탐험을 교차시켜 국소 최적해를 효과적으로 탈출함으로써, 기존 방식들에 비해 계산 효율성을 유지하면서도 우수한 회로 감소율과 충실도를 달성하는 하이브리드 양자 회로 최적화 도구인 QALM을 소개한다.

핵심

당신이 광활하고 안개가 자욱한 산맥에서 가장 낮은 지점을 찾으려 한다고 상상해 보십시오. 당신의 목표는 가장 깊은 골짜기(전역 최솟값, global minimum)의 절대적인 바닥에 도달하는 것이며, 이는 가장 효율적이고 오류가 없는 양자 회로를 의미합니다.

문제는 지형이 매우 까다롭다는 점입니다. 곳곳에 작은 움푹 파인 곳들(지역 최솟값, local minima)이 있는데, 이들은 마치 바닥처럼 보이지만 실제로는 그렇지 않습니다.

기존의 방식들: 두 가지 결함이 있는 전략

이 논문이 나오기 전, 연구자들은 이 문제를 해결하기 위해 두 가지 주요 방법을 시도했으나, 둘 다 중대한 결함을 가지고 있었습니다.

1. "탐욕스러운 등산객" (규칙 기반 최적화 도구):
   발 바로 밑의 지면만을 살피는 등산객을 상상해 보십시오. 만약 아래로 내려가는 계단이 보이면 그 길을 택하고, 위로 올라가는 계단이 보이면 무시합니다.

   • 장점: 믿을 수 없을 정도로 빠르게 움직입니다.
   • 단점: 처음 발견한 작은 웅덩이에 갇혀 버립니다. 만약 몇 걸음 위로 올라갔다가 결국 훨씬 더 깊은 골짜기로 미끄러져 내려갈 수 있다는 사실을 결코 깨닫지 못합니다. 효율적이긴 하지만, 종종 수준 미달의 결과를 얻게 됩니다.

2. "눈먼 탐험가" (탐색 기반 최적화 도구):
   언덕 너머에 무엇이 있는지 보기 위해 기꺼이 언덕을 오르는 등산객을 상상해 보십시오. 이들은 작은 웅덩이를 벗어나기 위해 원을 그리며 걷거나 언덕을 오르는 것을 마다하지 않습니다.

   • 장점: 가장 깊은 골짜기를 찾아낼 가능성이 훨씬 높습니다.
   • 단점: 믿을 수 없을 정도로 느립니다. 어떤 오르막길이 더 좋은 골짜기로 이어지는 길인지, 아니면 그냥 막다른 길인지 알 수 없기 때문에 모든 경로를 눈먼 채로 일일이 다 시도해야 합니다. 이 과정은 기하급수적으로 오래 걸리며, 종종 최선의 해답을 찾기도 전에 시간이 다 되어버립니다.

새로운 솔루션: QALM (스마트 가이드)

이 논문의 저자들은 QALM이라는 새로운 시스템을 만들었습니다. QALM을 탐욕스러운 등산객의 속도와 눈먼 탐험가의 철저함을 영리하게 교차하며 결합한 '스마트 가이드'라고 생각하십시오.

QALM이 작동하는 방식은 다음과 같습니다 ("정찰과 질주" 비유):

1. 질주 (Exploitation): QALM은 탐욕스러운 등산객처럼 시작합니다. 현재 있는 작은 골짜기의 바닥을 찾기 위해 근처의 언덕을 향해 빠르게 달려 내려갑니다. 이는 빠르고 효율적입니다.
2. 정찰 (Exploration): 포기하는 대신, QALM은 이 골짜기의 가장자리를 살펴보기 위해 "정찰병"을 보냅니다. 정찰병은 더 깊은 골짜기로 가는 숨겨진 경로를 찾기 위해 몇 걸음 정도 언덕 위로 올라가는 것이 허용됩니다.
3. 검증 (Verification): 이것이 마법 같은 기술입니다. 만약 정찰병이 유망해 보이는 지점을 언덕 위에서 발견한다면, QALM은 계속해서 눈먼 채로 방황하지 않습니다. 즉시 그 새로운 지점에서 "질주 팀"을 투입합니다.
   • 만약 질주 팀이 깊은 골짜기를 찾아낸다면, 성공입니다! 그들은 그곳에 머뭅니다.
   • 만약 그들이 단지 또 다른 작은 웅덩이를 발견했다면, 그 지점은 유망하지 않았다는 것을 알게 됩니다.

왜 이것이 더 나은가요?
"눈먼 탐험가"는 언덕을 오르고 헤매며 언젠가 내려갈 길을 찾기를 희망하며 시간을 낭비합니다. QALM은 이 과정을 피합니다. 후보지를 찾기 위해 언덕을 오직 '필요한 만큼만' 올라간 뒤, 그 후보지가 더 나은 곳으로 이어지는지 즉시 테스트하기 때문입니다. 이를 통해 길고 눈먼 방황을 건너뜁니다.

결과: 빠르고 정확함

연구진은 248개의 서로 다른 양자 회로(복잡한 퍼즐 248개라고 생각하십시오)를 대상으로 QALM을 테스트했습니다. 그리고 이를 기존의 가장 강력한 도구들(탐욕스러운 등산객과 눈먼 탐험가)과 비교했습니다.

• 속도: QALM은 단순한 탐욕적 도구들만큼 빠르게 작동합니다.
• 품질: 탐욕적인 도구들보다 훨씬 더 나은 솔루션(더 깊은 골짜기)을 찾아냅니다.
• 승자: **83.9%**의 사례에서 QALM은 동일한 시간을 사용했을 때 기존의 가장 강력한 도구들과 대등하거나 더 나은 결과를 만들어냈습니다.

더 놀라운 점은, 연구진이 퍼즐을 풀기 위해 QALM에게 단 1분의 시간만 주었을 때도, 다른 도구들이 1시간 동안 달성한 결과보다 더 뛰어난 성과를 냈다는 것입니다.

핵심 요약

QALM은 "속도와 품질" 사이의 절충안을 해결합니다. 빠르거나 똑똑하거나 둘 중 하나를 선택할 필요가 없다는 것을 증려합니다. 빠른 하강과 짧고 표적화된 탐색을 번갈아 수행함으로써, QALM은 다른 최적화 도구들을 혼란에 빠뜨리는 "함정"을 탈출하여, 이전에는 불가능하다고 생각했던 속도로 최적의 양자 회로를 찾아냅니다.

기술 요약

기술 요약: QALM – 양자 회로 최적화에서 인터리브된 탐색과 활용을 통한 로컬 미니마 탈출

1. 문제 정의

양자 회로 최적화는 회로 비용 지형(cost landscape)에서 로컬 미니마(local minima)를 탈출하는 어려움으로 인해 효율성과 최적화 품질 사이의 근본적인 트레이드오프에 직면해 있습니다.

• 규칙 기반 옵티마이저(예: VOQC, Qiskit)는 비용을 줄이는 탐욕적(greedy) 변환을 적용합니다. 이는 계산적으로 효율적이지만, 더 나은 영역을 탐색하기 위해 일시적인 비용 증가를 수용할 수 없기 때문에 로컬 미니마에 빠르게 갇히게 됩니다.
• 탐색 기반 옵티마이저(예: Quartz, QUESO, GUOQ)는 로컬 미니마를 탈출하기 위해 비용이 증가하는 이동을 허용하며 회로 공간을 탐색합니다. 그러나 이들은 합리적인 시간 예산 내에서 "유망한" 고비용 영역과 막다른 길을 구별할 수 있는 메커리즘이 부족합니다. 결과적으로, 고비용 지점이 더 깊은 로컬 미니마로 이어지는지 확인하기 위해 기하급수적으로 많은 단계를 맹목적으로 탐색해야 하며, 이는 과도한 실행 시간으로 이어집니다.

식별된 핵심 한계는 기존의 탐색 기반 방법들이 유망한 지점을 저렴하게 검증할 수 없다는 것이며, 이로 인해 고품질의 최적화를 위해서는 기하급수적인 시간이 필요하다는 타협을 강요받게 됩니다.

2. 방법론: QALM 프레임워크

저자들은 규칙 기반 및 탐색 기반 최적화를 단일 제어 루프로 통합하는 하이브리드 프레임워크인 QALM(Quantum Adaptive Local Minima)을 제안합니다. QALM은 탐색(exploration)과 활용(exploitation)을 별개의 단계로 취급하거나 정적으로 균형을 맞추는 대신, 이를 동적으로 **인터리브(interleave, 교차 실행)**합니다.

2.1 최적화 스펙트럼

QALM은 탐색 깊이 $k$로 매개변수화된 회로 공간의 순회로 모델링합니다:

• $k=0$: 순수 규칙 기반 (탐욕적).
• $k \to \infty$: 순수 탐색 기반 (전수 조사).
• $0 < k < \infty$: QALM이 작동하는 하이브리드 영역.

2.2 알고리즘

QALM은 탐색 깊이 $k$가 점진적으로 증가하는 반복 패스(pass)를 실행합니다. 각 패스에서:

1. 후보 선택: 우선순위 큐는 비용에 따라 정렬된 회로 후보들을 유지합니다.
2. 탐색 단계: 선택된 후보로부터 브랜칭(branching)을 수행하고, 비용 증가를 허용하는 $k$ 단계의 탐색 기반 탐색을 수행합니다. 이 단계에서는 Quartz에서 유래된 변환 규칙(구체적으로 (5, 3)-complete ECC 세트)을 사용합니다.
3. 활용 단계: $k$ 단계의 탐색 직후에 규칙 기반 옵티마이저(ROQC)를 즉시 적용합니다. 이 "활용(exploit)" 단계는 탐색된 지점으로부터 탐욕적으로 하강하여 가장 가까운 로컬 미니마를 찾습니다.
4. 검증: 탐색 직후 즉시 하강함으로써, QALM은 고비용 지점이 진정으로 유망했는지를 단 한 번의 규칙 기반 패스로 검증하며, 순수 탐색이 비용 감소를 확인하기 위해 거쳐야 하는 기하급수적인 대기 시간을 우회합니다.

2.3 주요 구현 구성 요소

• ROQC (Rule-based Optimizer for Quantum Circuits): VOQC(예: Hadamard reduction, gate cancellation)와 PhasePoly(예: $R_z$ 병합을 위한 태깅)의 기술을 통합한 커스텀 규칙 기반 엔진입니다.
• 탐색 구성 요소: 의존적인 최적화 시퀀스를 발견하기 위해 최근에 수정된 영역에 편향된 Quartz의 변환 규칙을 활용합니다.
• 그리디 모드(Greedy Mode): 초기 패스($k=1, 2$)에서 QALM은 개선 사항을 찾는 즉시 브랜치를 조기에 종료하는 "그리디 모드"를 채택합니다. 이는 더 깊고 비용이 많이 드는 탐색에 자원을 투입하기 전에 "낮게 매달린 과일(low-hanging fruit)"을 빠르게 수확합니다.
• 스케줄링: 프레임워크는 풀 크기($N_{pool}$)와 브랜치 인자($N_{branch}$)를 사용합니다. 실험 결과 $N_{pool}=1$ 및 $N_{branch}=3$이 다양성과 탐색 노력 사이의 최적의 균형을 제공함을 보여줍니다.

3. 주요 기여

1. 통합 제어 루프: 본 논문은 규칙 기반 및 탐색 기반 전략이 상호 배타적인 것이 아니라, 속도-품질의 경계(frontier)를 극복하기 위해 서로 인터리브될 수 있음을 입증합니다.
2. 유망한 지점의 효율적 검증: QALM은 탐색 기반 옵티마이저의 "맹목적 탐색" 문제를 해결합니다. 짧은 탐색 직후에 규칙 기반 활용을 즉시 적용함으로써, 기하급수적인 탐색 단계 없이도 유망한 영역을 검증합니다.
3. 동적 깊이 진전: $k$를 점진적으로 증가시키는 방식은 얕은 수준의 최적화를 먼저 소진하여, 더 깊고 복잡한 변환이 필요할 때만 계산 예산을 할당할 수 있게 합니다.
4. 구현: ROQC와 Quartz 기반 탐색을 통합하고, 메모리 효율적인 가지치기(pruning) 전략(우선순위 큐에 상위 1,000개의 회로 유지)을 포함한 완전한 QALM 구현을 제시합니다.

4. 실험 결과

저자들은 248개의 회로(QAOA, VQE, 산술 회로 및 양자 알고리즘 포함)를 대상으로 최첨단 베이스라인인 GUOQ, QUESO, VOQC, Quartz와 QALM을 평가했습니다.

• 게이트 감소: 1시간의 시간 예산이 주어졌을 때, QALM은 가장 강력한 베이스라인보다 5.97% 더 많은 총 게이트 수 감소를 달お성했습니다. 심지어 1분의 예산에서도, 모든 베이스라인의 1시간 결과보다 뛰어난 성능을 보였습니다.
• 충실도(Fidelity): QALM은 가장 강력한 베이스라인의 충실도와 일치하거나 이를 능가하는 성능을 **83.9%**의 회로에서 보여주었습니다.
• GUOQ와의 비교: GUOQ는 2-큐비트 게이트 수를 효과적으로 최적화했지만, 종종 과도한 단일 큐비트 게이트를 도입했습니다(음의 총 게이트 감소). QALM은 두 지표의 균형을 맞추어, 거의 동일한 2-큐비트 감소량(24.61% 대 25.41%)을 달성하면서도 훨씬 우수한 총 게이트 감소량(52.34% 대 -2.63%)을 기록했습니다.
• Quartz와의 비교: Quartz의 벤치마크에 사용된 26개 회로에 대해, QALM은 단 하나의 회로를 제외하고 모두에서 가장 낮거나 동일한 게이트 수를 기록하며, (사전 처리 과정을 거친) Quartz보다 절대적 게이트 감소량 측면에서 4.6% 더 높은 성능을 보였습니다.
• 절제 연구(Ablation Studies):
  • 그리디 모드: 비-그리디 탐색에 비해 32% 게이트 감소에 도달하는 속도를 11배 향상시켰습니다.
  • 탐색 깊이 ($k$): 고정된 $k$ 값은 점진적으로 증가하는 $k$ 스케줄보다 성능이 떨어졌으며, 이는 얕게 시작하여 깊게 만드는 방식의 이점을 확인시켜 줍니다.
  • 브랜칭: $N_{branch}=3$인 브랜치 인자가 탐색 노력을 희석하지 않으면서 로컬 미니마를 탈출하기 위한 "스윗 스팟(sweet spot)"임을 확인했습니다.

5. 의의 및 주장

본 논문은 QALM이 역사적인 최적화 속도와 품질 간의 트레이드오프를 제거한다고 주장합니다.

• 병목 현상 극복: 저자들은 유망한 지점과 막다른 길을 저렴하게 구별할 수 없는 능력이 속도-품질 타협의 근본 원인이라고 주장합니다. QALM은 규칙 기반 활용을 통해 탐색 후보를 즉시 검증함으로써 이를 해결합니다.
• 성능: 결과는 QALM이 단순히 균형을 잡는 것을 넘어, 기존의 순수 규칙 기반 및 순수 탐색 기반 옵티마이저를 동시에 능가한다는 것을 보여줍니다. QALM은 규칙 기반 시스템의 계산 효율성을 달성하는 동시에 탐색 기반 시스템의 최적화 품질을 확보합니다.
• 확장성: 단순한 제거(cancellation)에 대한 깊은 탐색에 낭비되는 것을 방방지하기 위해 규칙 기반 전처리를 사용하여 탐색 공간을 축소함으로써, QALM은 실질적인 시간 예산 내에서 깊은 탐색을 가능하게 합니다.

저자들은 이러한 인터리브된 접근 방식이 NISQ 시대와 그 이후를 위한 고품질 회로 최적화의 실질적인 솔루션을 제공하며, 향-카운트(T-count) 및 회로 깊이와 같은 다른 지표를 최적화하는 후속 연구가 계획되어 있다고 결론지었습니다.