Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization

본 논문은 회로 복잡성을 다항식 샘플링 오버헤드로 전환함으로써 복잡한 양자 회로를 최적화 작업에 효율적으로 분해하는 보조 큐비트가 없는 푸리에 기반 유니터리 선형 결합 (LCU) 프레임워크를 제안하여, QAOA 와 같은 알고리즘의 엄격한 성능 보장을 유지하면서 근미래 양자 장치에 하드웨어 친화적인 구현을 가능하게 한다.

핵심

거대한, 매우 복잡한 퍼즐을 풀려고 한다고 상상해 보세요. 양자 컴퓨팅 세계에서는 이 퍼즐이 종종 최적화 문제입니다: 사물들의 가장 이상적인 배치를 찾는 것 (가장 효율적인 배송 경로나 최고의 투자 포트폴리오와 같은 것들).

카레라 바스케즈, 에거, 그리고 워너의 논문은 아직 초기 단계인 '잡음'이 있는 개발 단계에 있는 양자 컴퓨터를 사용하여 이러한 퍼즐을 해결하는 교묘한 새로운 방법을 제시합니다.

간단한 비유를 사용하여 그들의 아이디어를 분해해 보겠습니다:

문제: "전원 동원" 회로

전통적으로 양자 컴퓨터에서 이러한 퍼즐을 해결하려면 퍼즐의 모든 조각이 동시에 서로 다른 모든 조각과 대화하는 특정 기계 (양자 회로) 를 구축해야 합니다.

• 비유: 100 명의 손님이 모두 정확히 같은 시간에 서로 다른 모든 손님과 악수를 해야 하는 파티를 조직하려고 상상해 보세요. 실제 방에서는 이것이 불가능합니다; 사람들이 서로 부딪히고, 방이 너무 붐비며, 행사가 실패할 것입니다.
• 양자 현실: 양자 용어로, 이는 '모든 대 모든 연결성'과 매우 깊고 복잡한 회로를 필요로 합니다. 현재의 양자 컴퓨터는 작은 방과 같습니다; 실수 (잡음) 를 범하지 않고는 그렇게 많은 동시 악수를 처리할 수 없습니다.

해결책: "레시피 책" 접근법 (LCU)

저자들은 **선형 단위 조합 (Linear Combination of Unitaries, LCU)**이라는 새로운 전략을 제안합니다. 불가능한 '전원 동원' 기계를 구축하려고 시도하는 대신, 복잡한 작업을 훨씬 더 간단하고 작은 작업들의 목록으로 분해합니다.

• 비유: 한 번에 거대하고 정교한 웨딩 케이크를 굽는 것 (붕괴될 수 있음) 대신, 100 개의 간단하고 작은 컵케이크를 굽습니다.
  • 일부 컵케이크는 바닐라, 일부는 초콜릿, 일부는 스프링클이 있습니다.
  • 거대한 오븐이 필요하지 않습니다; 하나씩 또는 작은 배치로 구울 수 있습니다.
  • 그 후, 결과를 접시에 섞습니다. 올바른 비율로 섞으면 접시의 '맛'이 원하는 거대 웨딩 케이크와 정확히 같은 맛이 납니다.

논문에서 이러한 '컵케이크'는 단일 큐비트 게이트 (한 사람이 다른 한 사람과 악수하는 것) 만 필요한 간단한 양자 회로입니다. '섞기'는 양자 부분이 끝난 후 고전적으로 (일반 컴퓨터에서) 발생합니다.

비밀 소스: 푸리에 변환

어떤 컵케이크를 구워야 하고 각각을 얼마나 섞어야 하는지 어떻게 알까요? 그들은 푸리에 변환이라는 수학적 도구를 사용합니다.

• 비유: 복잡한 노래를 생각해보세요. 푸리에 변환은 그 노래를 개별 음 (주파수) 으로 분해합니다. 저자들은 이를 사용하여 복잡한 양자 '노래' (회로) 를 일련의 간단하고 반복적인 음 (단일 큐비트 회전) 으로 분해합니다.
• 결과: 그들은 매우 어렵고 복잡한 양자 연산을 매우 쉬운 연산들의 가중 합으로 표현할 수 있습니다.

트레이드오프: 품질 대 양

단점이 있습니다. 거대 기계를 직접 구축하지 않기 때문에 신뢰할 수 있는 답을 얻기 위해 '컵케이크' 실험을 훨씬 더 많이 수행해야 합니다.

• 비유: 군중의 평균 키를 알고 싶다면, 모든 사람을 한 번 측정할 수 있습니다 (모두가 움직이고 있다면 어렵습니다). 또는 10 명의 무작위 사람을 측정하고, 그 다음 10 명, 그 다음 10 명을 더 측정하여 평균을 낼 수 있습니다. 같은 결과를 얻지만 더 많은 측정을 해야 합니다.
• 논문의 주장: 저자들은 간단한 회로를 더 많이 실행해야 하지만 ('샘플링 오버헤드'), 추가 실행 횟수가 관리 가능 (다항식) 하지 불가능하지 않음을 보여줍니다. 이 트레이드오프는 그렇지 않으면 불가능했을 현재의 하드웨어에서 문제를 실행할 수 있게 합니다.

현실 세계 적용: "가장 조밀한 부분 그래프"

이것이 작동하는지 증명하기 위해, 그들은 '가장 조밀한 k-부분 그래프 (Densest k-Subgraph)'라는 특정 문제 (거대한 소셜 네트워크에서 가장 끈끈한 친구 그룹 찾기) 에 대해 이를 테스트했습니다.

1. 소규모: 수학이 완벽하게 작동함을 보이기 위해 12 노드 그래프 (작은 동네와 같은) 에서 시뮬레이션했습니다.
2. 대규모: 106 개의 큐비트를 가진 실제 IBM 양자 컴퓨터 (큰 동네) 에서 실행했습니다.
   • 그들은 고품질 솔루션을 성공적으로 찾았습니다.
   • 그들은 두 가지 방법을 비교했습니다: 하나는 '페널티' (규칙 위반에 대한 벌금과 같은) 를 사용한 방법이고, 다른 하나는 특별한 '믹서' (규칙을 따르는 춤) 를 사용한 방법입니다.
   • 발견: '믹서' 접근법은 새로운 푸리에 방법과 결합되어 매우 잘 작동했으며, 실제 잡음이 있는 하드웨어에서도 이론상 최선과 거의 같은 솔루션을 찾았습니다.

"도움 없는" 트릭

보통 이러한 '컵케이크'들을 섞기 위해 수학을 추적하는 추가적인 '도움' 큐비트 (안실라) 가 필요합니다.

• 혁신: 저자들은 도움 없이 이를 수행하는 방법을 개발했습니다.
• 비유: 어느 팀이 득점했는지 알려주는 심판이 필요한 대신, 선수들이 무작위로 플레이하게 한 후 승자를 파악하기 위해 나중에 점수판을 살펴봅니다. 이는 양자 회로에서 엄청난 복잡성을 제거하여 오늘날의 기계에 훨씬 더 친숙하게 만듭니다.

요약

이 논문은 오늘날의 불완전한 하드웨어에서 복잡한 양자 최적화 알고리즘을 실행하는 새로운 방법을 제시합니다. 모든 것을 서로 연결하는 거대하고 취약한 기계를 구축하려고 시도하는 대신, 그들은 문제를 많은 작고 간단한 조각으로 분해하고, 그 조각들을 실행한 후 결과를 고전적으로 결합합니다.

그들은 106 큐비트 양자 컴퓨터에서 어려운 그래프 문제를 해결함으로써 이를 증명했으며, '회로 복잡성' (기계를 구축하는 난이도) 을 '샘플링 오버헤드' (테스트를 실행해야 하는 횟수) 로 교환함으로써 오늘날 더 크고 복잡한 문제들을 해결할 수 있음을 보여주었습니다.

기술 요약

기술 요약: 유니터리들의 효율적인 푸리에 기반 선형 결합 및 양자 최적화 응용

문제 제기
양자 최적화 알고리즘, 특히 양자 근사 최적화 알고리즘 (QAOA) 은 근미래 하드웨어에서 구현에 상당한 장벽에 직면해 있습니다. 최적화 문제, 특히 제약 조건 (예: 카디널리티 제약) 을 포함하는 문제의 수학적 구조는 종종 고연결성 (모든 대 모든 상호작용), 깊은 회로 깊이, 그리고 수많은 2-큐비트 게이트를 필요로 하는 양자 회로를 요구합니다. 이러한 요구 사항은 현재의 초전도 양자 프로세서의 능력을 자주 초과합니다. 회로 절단이나 회로 근사와 같은 전략들이 존재하지만, 이러한 방법들은 종종 복잡성을 위해 솔루션의 품질을 희생하거나 엄격한 성능 보장이 없이 상당한 샘플링 오버헤드를 요구합니다.

방법론
저자들은 복잡한 양자 회로를 단순하고 하드웨어 친화적인 회로의 앙상블로 근사하도록 설계된 푸리에 기반 유니터리 선형 결합 (LCU) 프레임워크를 제안합니다. 핵심 방법론은 다음과 같습니다:

1. 샘플링을 위한 어시클라 없는 LCU: 유니터리들의 선형 결합을 일관성 있게 구현하기 위해 어시클라 큐비트를 사용하는 표준 LCU 구현 (제어 연산 필요) 과 달리, 이 연구는 샘플링 기반 응용에 초점을 맞춥니다. 준확률 분해 (QPD) 와 관련된 부호 인자를 제거하고 어시클라를 고전적 무작위성으로 대체함으로써, 이 방법은 어시클라 큐비트와 제어 게이트의 필요성을 제거합니다. 이는 샘플링 오버헤드가 $\Gamma$ 인자로 정량화되는 단순한 회로의 확률적 혼합으로 구현을 변환합니다.
2. 대각 유니터리를 위한 푸리에 분해: 비용 함수 및 페널티 항에서 흔히 나타나는 대각 유니터리의 경우, 저자들은 이산 푸리에 변환을 활용합니다. 목표 유니터리 $U_f(\gamma) = \sum_x e^{-i\gamma f(g(x))} |x\rangle\langle x|$는 종종 단일 큐비트 $R_Z$ 게이트의 레이어에 불과한 더 단순한 유니터리 $V(\theta_j)$들의 선형 결합으로 분해됩니다. 계수는 유니터리를 정의하는 함수의 푸리에 변환에서 유도됩니다. 이 접근법은 복잡한 다중 큐비트 상호작용 (예: $O(n^2)$ 게이트가 필요한 2 차 페널티) 을 샘플링 오버헤드 $\Gamma \le m+1$의 대가로 단일 큐비트 레이어로 대체합니다.
3. 비대각 치환 불변 유니터리로의 확장: 프레임워크는 해밍 무게 제약을 보존하는 데 사용되는 완전히 연결된 XY-믹서와 같은 비대각 유니터리로 일반화됩니다. Schur-Weyl 쌍대성과 $SU(2)$의 표현론을 활용하여, 저자들은 치환 불변 유니터리를 집단적 단일 큐비트 회전$R(g)^{\otimes n}$의 연속 선형 결합으로 표현합니다. 이를 통해 이론적 샘플링 오버헤드가$O(n^3)$으로 제한되는 단일 큐비트 게이트만을 사용하여 매우 비국소적인 믹서를 구현할 수 있습니다.
4. 라그랑주 완화와의 연결: 이 논문은 푸리에 기반 양자 페널티와 고전적 라그랑주 완화 사이의 공식적인 연결을 확립합니다. LCU 분해의 단일 분기를 최적화하는 것이 라그랑주 매개변수를 최적화하는 것과 동등함이 입증되어, 제약 조건 처리에 대한 통합된 관점을 제공합니다.

주요 기여

• 프레임워크 개발: 광범위한 클래스의 대각 및 비대각 유니터리를 단일 큐비트 게이트 레이어의 앙상블로 분해하는 어시클라 없는 푸리에 기반 LCU 프레임워크 도입.
• 하드웨어 효율성: 카디널리티 페널티 및 XY-믹서와 같은 복잡하고 모든 대 모든 연결된 연산자가 회로 깊이와 연결성을 다항식 샘플링 오버헤드로 교환하여 훨씬 더 단순한 회로로 대체될 수 있음을 입증.
• 이론적 보장: LCU 접근법에서 고품질 비트열을 샘플링할 확률이 $1/\Gamma$로 스케일링된 일관성 확률에 의해 하한이 보장됨을 보여주는 엄격한 성능 한계 제공. 또한 조건부 위험 가치 (CVaR) 최적화를 이러한 한계와 연결함.
• 확장성 검증: 실제 IBM 양자 하드웨어에서 최대 106 개 큐비트까지의 인스턴스에 대한 가장 조밀한 $k$-서브그래프 문제에 프레임워크를 성공적으로 적용하여, 이러한 제약 조건에 대한 완전한 일관성 구현으로는 이전까지 처리 불가능했던 규모를 달성함.

실험 결과
저자들은 12 노드 인스턴스에 대한 정확한 상태 벡터 시뮬레이션과 106 큐비트 장치에서의 대규모 실험을 통해 접근법을 검증했습니다:

• 12 노드 시뮬레이션: 완전한 일관성 QAOA 와 푸리에 기반 LCU 접근법 간의 비교에서, LCU 회로의 원시 기대값은 샘플링 오버헤드로 인해 낮았으나, 단일 LCU 기저 회로(LCU 에서 유도된 변분 안사츠) 를 최적화하는 것이 최적 솔루션을 샘플링할 확률을 가장 높게 만들어 특정 지표에서 일관성 기준을 능가했습니다.
• 106 노드 하드웨어 실험: 106 큐비트 헤비-헥스 그래프 (SWAP 레이어를 통해 확장됨) 에서 페널티 기반 및 XY-믹서 기반 LCU 접근법이 실행되었습니다. 결과는 실제 샘플링 오버헤드가 최악의 경우 이론적 한계 ($\Gamma \approx 10^4$) 보다 현저히 낮음을 보여주었습니다. 단일 분기 LCU 안사츠는 2.7% 에서 4.8% 사이의 실현 가능한 확률로 고품질 솔루션 (가장 조밀한 서브그래프에서 최대 81 개의 엣지) 을 성공적으로 찾아냈으며, 이는 대규모 문제에 대한 방법의 타당성을 나타냅니다.
• XY-믹서 대 페널티: XY-믹서 기반 LCU 접근법은 일반적으로 페널티 기반 접근법보다 우수했으며, 특히 단일 최적화 기저 회로를 사용할 때 제약 조건을 보존하는 믹서가 이러한 분해와 결합될 때 더 효과적임을 시사했습니다.

의의 및 주장
이 논문은 푸리에 기반 LCU 프레임워크가 근미래 양자 최적화의 실용적 범위를 확장하는 체계적인 경로를 제공한다고 주장합니다. 복잡한 일관성 연산을 더 단순한 회로의 가중치 결합으로 대체함으로써, 이 방법은 현재 하드웨어에서 실행 가능한 문제 인스턴스 (특히 전역 제약 조건을 가진 인스턴스) 의 범위를 확장합니다. 저자들은 이 접근법이 목표 분포의 정확한 재현을 요구하는 것이 아니라 고품질 솔루션을 샘플링하는 데 초점을 맞추며, 이는 최적화 작업에 잘 부합한다고 강조합니다. 이 연구는 회로 복잡성과 샘플링 오버헤드 간의 절충이 유리함을 시사하는데, 그 이유는 이론적 한계가 실제 상황에서 종종 느슨하며, 이 방법이 그렇지 않으면 하드웨어 능력 밖이었던 알고리즘 및 문제 인스턴스 연구를 가능하게 하기 때문입니다. 논문은 이것이 QAOA 의 제약 조건 처리를 위한 더 하드웨어 친화적인 양자 알고리즘을 위한 유연한 설계 원칙을 제공한다고 결론지었습니다.