Locally Acting Grover Mixers for Constraint-Preserving QAOA

이 논문은 GM-QAOA의 비용이 많이 드는 전역적 다중 제어 위상 변이 게이트를 서로 겹치지 않는 큐비트 하위 시스템에 대한 효율적인 국소 연산으로 대체하는 국소적으로 작용하는 그로버 믹서를 제안하며, 이를 통해 exact cover 및 traveling salesman problem과 같은 문제들에 대해 원래 방식과 유사한 수렴도를 달성하는 동시에 회로 깊이와 게이트 수를 크게 줄인다.

핵심

당신이 모든 도시를 정확히 한 번씩 방문하는 최적의 경로를 찾는 것과 같은 거대하고 복잡한 퍼즐을 풀려고 노력 중이라고 상상해 보세요. 당신에게는 수백만 개의 가능성을 동시에 시도할 수 있는 초지능형 컴퓨터(양자 컴퓨터)가 있습니다. 하지만 이 컴퓨터는 현재 다소 "노이즈(잡음)"가 많고 취약합니다. 마치 섬세한 유리 조각품과 같습니다. 만약 너무 복잡한 일을 시키면, 컴퓨터는 고장 나거나 실수를 저지릅니다.

이 논문은 이 취약한 컴퓨터가 고장 나지 않고 더 잘 문제를 해결할 수 있도록 안내하는 새로운 방법을 소개합니다.

문제점: "글로벌(Global)" 규칙 책

연구진은 QAOA(Quantum Approximate Optimization Algorithm)라고 불리는 방법으로 작업하고 있습니다. QAOA를 안개 낀 골짜기에서 가장 낮은 지점(최적의 해답)을 찾으려는 등산객이라고 생각해 보세요. 이 등산객이 일을 수행하기 위해서는 두 가지 도구가 필요합니다.

1. 지도 (위상 분리, Phase Separation): 어디가 "나쁜" 지점인지 보여줍니다.
2. 나침반 (믹서, The Mixer): 등산객이 새로운 곳을 탐색하기 위해 움직일 수 있도록 돕습니다.

표준 버전의 이 방법(이를 GM-QAOA라고 부릅니다)에서 "나침반"은 **글로벌 다중 제어 게이트(Global Multi-Controlled Gate)**입니다.

• 비유: 100명의 사람들이 춤 파티를 열려고 한다고 상상해 보세요. 표준 방식의 나침반은 "만약 모든 사람이 특정한 대형으로 서 있다면, 모든 사람이 함께 움직여야 한다"라는 하나의 거대한 규칙과 같습니다.
• 문제점: 오늘날의 노이즈가 많은 양자 컴퓨터에서 이 규칙을 강제하려면, 모든 100명을 한꺼번에 확인하는 거대하고 복잡한 기계가 필요합니다. 이 기계는 매우 크고 공간을 많이 차지하며, 고장(오류 발생)이 날 가능성이 매우 높습니다.

해결책: "로컬(Local)" 자율 방범대

연구진은 이 나침반을 만드는 더 똑똑한 방법을 제안합니다. 그들은 이를 **로컬 액팅 그로버 믹서(Locally Acting Grover Mixers)**라고 부릅니다.

• 비유: 방 전체에 적용되는 하나의 거대한 규칙 대신, 사람들을 더 작고 독립적인 그룹(예: 10명씩 앉은 10개의 테이블)으로 나눕니다. 이제 모든 사람을 한꺼번에 확인하는 하나의 거대한 기계 대신, 10개의 작고 단순한 기계를 갖게 됩니다. 각 기계는 자신의 테이블만 확인합니다.
  • 1번 테이블의 기계: "1번 테이블의 모든 사람이 대형을 갖추었다면, 움직여라."
  • 2번 테이블의 기계: "2번 테이블의 모든 사람이 대형을 갖추었다면, 움직여라."
• 결과: 이 작은 기계들은 훨씬 만들기 쉽고, 공간을 적게 차지하며, 고장 날 확률도 훨씬 낮습니다. 결정적으로, 이 그룹들이 독립적이기 때문에 전체적인 결과는 거대한 기계와 마찬가지로 우수합니다.

어떻게 구현했는가

연구진은 많은 퍼즐에서 모든 규칙을 시작 설정에 강제로 집어넣을 필요가 없다는 점을 깨달았습니다.

1. 부분 인코딩 (Partial Encoding): 컴퓨터가 모든 규칙을 준수하는 완벽한 해답에서 시작하도록 강요하는 대신, 일부 규칙만을 준수하는 해답에서 시작하도록 허용합니다. 이는 "곱 구조(product structure)"(앞서 언급한 독립적인 그룹들)를 생성합니다.
2. 로컬 믹싱 (Local Mixing): 그런 다음 이 새로운 "로컬 나침반"을 사용하여 해당 작은 그룹 내에서 변화를 줍니다.

증명: 엑잭트 커버(Exact Cover)와 외판원 문제(Traveling Salesman)

그들은 이 아이디어를 두 가지 유명한 퍼즐에 대해 테스트했습니다:

1. 엑잭트 커버 문제 (Exact Cover Problem): 항목을 정확히 한 번씩 덮는 논리 퍼즐입니다.
2. 외판원 문제 (Traveling Salesman Problem, TSP): 여러 도시를 방문하는 가장 짧은 경로를 찾는 문제입니다.

연구 결과:

• 동일한 품질: 새로운 "로컬" 방식은 기존의 "글로벌" 방식만큼 좋은 해답을 찾아냈습니다.
• 훨씬 더 단순함: 새로운 방식은 복잡한 "얽힘(entanglement)" 게이트(회로에서 가장 고장이 나기 쉬운 부분)를 87% 적게 사용했습니다.
• 트레이드오프 (Trade-off): 새로운 방식은 설정을 조정하기 위해 컴퓨터가 회로를 약간 더 많이 실행해야 합니다(조절해야 할 노브가 더 많기 때문). 하지만 회로 자체가 훨씬 단순하고 고장에 강하기 때문에, 이러한 트레이드오프는 오늘날의 노이즈가 많은 컴퓨터에게 큰 승리입니다.

핵심 요약

이 논문은 우리가 현재 가지고 있는 양자 컴퓨터(작고 노이즈가 많은)를 위해서는 "로컬" 전략을 사용하는 것이 더 낫다고 주장합니다.

• 기존 방식: 모든 것을 완벽하게 수행하려고 노력하지만 쉽게 고장 나는 거대하고 복잡한 기계를 만드는 것.
• 새로운 방식: 서로 협력하는 작고 단순한 기계들을 많이 만드는 것. 설정을 맞추기 위해 몇 번 더 시도해야 할 수도 있지만, 훨씬 더 신뢰할 수 있으며 현재의 하드웨어에도 적합합니다.

요약하자면, 저자들은 정답의 품질을 희생하지 않으면서도 제약 조건이 있는 문제에 대한 양자 알고리즘을 더 가볍고, 단순하며, 견고하게 만드는 방법을 찾아냈습니다.

기술 요약

기술 요약: 제약 조건 보존을 위한 국소적으로 작용하는 그로버 믹서(Locally Acting Grover Mixers)

문제 정의
양자 근사 최적화 알고리즘(QAOA)과 그 일반화된 형태인 양자 교대 연산 안사츠(QAOA)는 조합 최적화를 위한 저명한 변분 알고리즘이다. 제약 조건이 있는 문제에 이러한 알고리즘을 적용할 때 발생하는 핵심 과제는 양자 진화가 문제의 제약 조건에 의해 정의된 가용 부분 공간(feasible subspace) 내에 머물도록 보장하는 것이다. 그로버 믹서 QAOA(GM-QAOA)는 초기 상태에 대한 투영 연산자로 생성된 믹싱 연산자를 사용함으로써 이를 해결하며, 이는 수학적으로 가용 부분 공간의 보존을 보장한다.

그러나 표준 GM-QAOA 믹서는 모든 $n$개의 큐비트에 작용하는 전역 다중 제어 위상 변화 게이트(global multi-controlled phase-shift gate)를 필요로 한다. 1-큐비트 및 2-큐비트 연산만을 기본적으로 지원하는 근미래의 노이즈가 있는 중간 규모 양자(NISQ) 장치에서, 이러한 전역 게이트를 기초 게이트로 분해하는 것은 상당한 회로 오버헤드를 초래한다. 이러한 분해 과정에서 회로의 깊이와 게이트 수는 큐비트 수에 따라 급격히 증가하며, 이는 실질적인 구현에 큰 장벽이 되고 하드웨어 노이즈에 대한 취약성을 높인다.

본 논문은 초기 상태가 서로 소인 큐비트 서브시스템들에 대해 **곱 구조(product structure)**를 갖는 경우에 맞춤화된 "국소적으로 작용하는(locally acting)" 변형 그로버 믹서를 제안한다. 이 접근 방식은 많은 조합 문제에서 제약 조건의 일부를 초기 상태 준비 단계에 인코딩함으로써 나머지 제약 조건을 비용 해밀토니안의 페널티 항으로 처리할 수 있다는 관찰에 기반한다.

1. 곱 구조를 가진 초기 상태: 이 방법은 초기 상태 $|\psi_0\rangle$가 $|\psi_0\rangle = |\psi^{(1)}_0\rangle \otimes |\psi^{(2)}_0\rangle \otimes \dots \otimes |\psi^{(\ell)}_0\rangle$와 같이 인수분해될 수 있다고 가정한다. 여기서 각 $|\psi^{(j)}_0\rangle$는 서로 소인 큐비트 집합에 존재한다. 이러한 구조는 문제 제약 조건의 일부만을 초기 상태 준비 단계에 인코딩함으로써 달성되며, 남은 제약 조건은 비용 해밀토니안을 통해 처리된다.
2. 국소 믹싱 유니터리: 단일 전역 믹서 $e^{-i\beta |\psi_0\rangle\langle\psi_0|}$ 대신, 제안된 방법은 텐서 곱 형태의 국소 유니터리로 믹싱 유니터리를 구성한다:
   $$U_M(\beta^{(1)}, \dots, \beta^{(\ell)}) = \bigotimes_{j=1}^{\ell} e^{-i\beta^{(j)} |\psi^{(j)}_0\rangle\langle\psi^{(j)}_0|}$$
   각 국소 유니터리는 해당 서브시스템 내에 국한된 다중 제어 위상 변화 게이트를 사용하여 독립적으로 작용한다.
3. 매개변수화: 이 안사츠는 각 서브시스템에 대해 독립적인 변분 매개변수 $\beta^{(j)}$를 도입한다. $p$-레이어 회로의 경우, 총 믹싱 매개변수의 개수는 원래의 GM-QAOA가 가진 $p$개와 달리 $p\ell$개가 된다. 이는 클래식 최적화 지형의 차원을 증가시키지만, 하나의 거대한 전역 게이트를 $\ell$개의 작은 국소 게이트로 대체한다.

주요 기여

• 회로 효율성: 주요 기여는 전역 다중 제어 위상 변화 게이트를 $\ell$개의 국소 연산으로 대체한 것이다. 이는 믹싱 단계에 필요한 얽힘 게이트(특히 CNOT)의 수와 회로 깊이를 획기적으로 줄여준다.
• 제약 조건 인코딩 전략: 본 논문은 모든 제약 조건을 초기 상태에 인코딩하는 것과 일부만을 인코딩하는 것 사이의 트레이드오프를 조사한다. 국소 믹서가 요구하는 곱 구조를 가능하게 하는 부분적 제약 조건 인코딩이, 비록 탐색 공간의 크기를 줄이더라도 전체적인 회로를 더 간결하게 만들 수 있음을 입증한다.
• 가용성 보존: 이 방법은 믹싱 연산자가 초기 상태에 의해 정의된 탐색 공간을 보존하여, 알고리즘이 불가능한 영역으로 벗어나지 않도록 보장한다는 GM-QAOA의 핵심 이점을 유지한다.

결과
저자들은 수치 시뮬레이션을 통해 Exact-Cover 문제와 외판원 문제(TSP)에서 제안된 방법을 평가하였다.

• Exact-Cover 문제: 7-큐비트 인스턴스에 대해, 제안된 방법은 원래의 GM-QAOA와 유사한 수렴 동작을 보였다. 결정적으로, 믹싱 유니터리를 $\{RX, RY, RZ, CNOT\}$ 게이트 집합으로 분해했을 때, CNOT 개수가 기존 218개에서 제안된 방식의 28개로 감소하여 약 87%의 감소율을 보였다.
• 외판원 문제 (TSP): 4개 도시 TSP 인스턴스(9-큐비트)에 대한 시뮬레이션 결과, 제안된 방법은 다양한 레이어 깊이 $p$에 대해 GM-QAOA와 대등한 솔루션 확률을 유지함을 보여주었다.
  • 노이즈 탄력성: 디폴라이징 노이즈 모델 하에서, 제안된 방법은 감소된 회로 깊이와 게이트 수 덕분에 원래의 GM-QAOA에 비해 비용 해밀토니안의 기댓값에 대한 상대 오차가 현저히 낮게 나타났다.
  • 자원 트레이드오프: 제안된 방법은 증가된 변분 매개변수로 인해 클래식 최적화 과정 중 더 많은 회로 실행을 필요로 하지만, 양자 회로 복잡도(믹싱 연산자당 CNOT 수가 572개에서 54개로 감소)의 감소가 노이즈가 있는 하드웨어에서 이를 더 실행 가능하게 만든다.
  • 부분적 vs 전체 인코딩: TSP의 경우, 시간 단계 제약($P_1$)만을 초기 상태에 인코딩(부분 인코딩)하고 국소 믹서를 결합했을 때 최적 성능($p=7$)에서 회로 깊이가 450이었다. 반면, 시간 단계와 도시 방문 제약($P_1$ 및 $P_2$)을 모두 초기 상태에 인코딩(전체 인코딩)하면 전역 믹서가 필요하며, $p=1$일 때 $p=1$일 때 회로 깊이가 4142에 달했다(높은 솔루션 확률에 더 빠르게 도달함에도 불구하고). 저자들은 부분 인코딩이 더 유리한 전체 회로 복잡도를 제공한다고 결론지었다.

의의 및 주장
본 논문은 제안된 국소적으로 작용하는 그로버 믹서가 근미래 양자 장치에서 제약 조건 보존 QAOA를 구현하기 위한 실질적인 경로를 제공한다고 주장한다. 가용 부분 공간의 곱 구조를 활용함으로써, 이 방법은 높은 품질의 솔루션으로 수렴하는 알고리즘의 능력을 유지하면서도 구현 비용(게이트 수 및 깊이)을 크게 낮춘다.

저자들은 늘어난 매개변수가 클래식 최적화 오버헤드를 증가시키고 잠재적으로 더 복잡한 최적화 지형을 만든다는 점을 인정하면서도, 게이트 충실도가 주요 제한 요소인 NISQ 장치에서는 양자 회로 복잡도의 감소가 더 지배적인 요소라고 언급하였다. 이 연구는 매개변수 수와 회로 깊이 사이의 트레이드오프가 제안된 접근 방식에 유리하다는 것을 시사한다. 본 논문은 완화된 믹싱 구조가 왜 대등한 수렴 성능을 달eric는지에 대한 이론적 질문을 해결하려는 것이 아니라, 이를 향후 연구를 위한 열린 방향으로 식별하였다.