Partitioned-Constraint QAOA (PC-QAOA): Structural State Preparation and Penalty Enforcement for Quantum Optimization

본 논문은 실행 가능 상태 준비와 Grover 믹서를 통해 구조적으로 불연속 제약 조건을 강제하고 나머지 부분에 대해 에너지적으로 패널티를 부과함으로써 제약 조합 최적화의 실현 가능성과 해의 품질을 크게 향상시키는 하이브리드 양자 알고리즘인 분할 제약 QAOA(PC-QAOA)를 소개하며, 이는 얕은 깊이에서 기존 페널티 기반 QAOA 보다 우수한 성능을 보입니다.

핵심

거대한 혼란스러운 미로를 통과하여 보물상자에 도달하는 최상의 경로를 찾으려 한다고 상상해 보세요. 양자 컴퓨팅 세계에서는 이'미로'가조합 최적화라는 복잡한 수학 문제이고, '보물'은 완벽한 해답입니다.

오랫동안 양자 컴퓨터는 제약 조건 (constraints) 이라는 엄격한 규칙 때문에 이러한 미로를 헤매는 데 어려움을 겪어 왔습니다. 예를 들어, "5 개 이상의 물품만 운반할 수 있다"거나"정확히 3 개의 도시를 방문해야 한다"는 규칙이 있습니다.

구식 방법: "무거운 배낭" 접근법

이전까지의 주요 전략은 양자 컴퓨터에납으로 가득 찬 무거운 배낭(벌점) 을 지우는 것과 같았습니다.

• 작동 원리: 컴퓨터가 규칙을 위반하는 경로 (예: 6 개의 물품을 운반) 를 시도하면 배낭이 더 무거워져 그 경로가'비싸거나'혹은'고통스러운'것처럼 느껴지게 됩니다.
• 문제점: 컴퓨터는 무거운 벌점이 결국 합법적인 경로로 이끌기를 바라며, 모든 막다른 길과 불법 경로를 포함한 미로 전체를 헤매야 했습니다. 이는 느리고 비효율적이며, 종종 잘못된 지역에 갇히곤 했습니다.

신식 방법: PC-QAOA("스마트 가이드"접근법)

이 논문의 저자들은PC-QAOA(Partitioned-Constraint QAOA) 라는 새로운 방법을 소개합니다. 모든 규칙에 대해 무거운 벌점만 사용하는 대신, 규칙을 두 그룹으로 나누어 다르게 처리합니다.

1. "구조적"규칙: 올바른 문 만들기

일부 규칙은 올바른 문을 만들기만 하면 이해하고 따르기 쉽습니다.

• 유추: "10 명 중 정확히 3 명을 선택해야 한다"는 규칙을 생각해 보세요. 컴퓨터가 10 명을 모두 선택한 후 4 명을 선택하면 벌점을 주는 대신, 저자들은정확히 3 명 그룹에게만 열리는 특수한 문을 만듭니다.
• 작동 원리: 그들은**가젯 (Gadgets)**이라고 불리는 특수한 양자 회로를 사용하여 컴퓨터의 초기 상태를 준비합니다. 이는 미로 탐색을 유효 해답의 방 밖의 광야가 아니라, 방 안쪽에서 시작하는 것과 같습니다.
• 마법: 규칙들이 서로 간섭하지 않는 경우 (예: 서로 다른 사람들을 대상으로 하는"3 명 선택"과"2 가지 색상 선택") , 이러한 특수한 문들을 나란히 짓고 한 번에 모두 열 수 있습니다. 이를병렬 준비라고 합니다.

2. "벌점"규칙: 남은 벌점

일부 규칙은 복잡하거나 다른 규칙과 겹칩니다 (예: "3 명 선택"과"같은그룹에서 2 명 선택"). 이러한 규칙들을 위한 단일 문을 쉽게 만들 수 없습니다.

• 유추: 이러한 까다로운 규칙들에 대해서는 여전히무거운 배낭(벌점) 을 사용합니다. 하지만 컴퓨터가 이미"구조적"방 안에 있기 때문에, 남은 몇 가지 규칙에 대한 벌점만 지우면 됩니다. 배낭이 훨씬 가벼워졌으므로 컴퓨터는 더 빠르고 똑똑하게 움직입니다.

비밀 무기:"변분 제약 가젯"(VCGs)

완벽한 문을 만들기에는 규칙이 너무 기이한 경우가 있을까요?

• 해결책: 저자들은변분 제약 가젯 (Variational Constraint Gadgets, VCGs)을 만들었습니다. 이를훈련용 바퀴나예행 연습으로 생각하세요.
• 작동 원리: 큰 문제를 풀기 전에, 오프라인에서 작고 재사용 가능한 양자 회로를 훈련시킵니다. 이 회로는 그 특정 기이한 규칙에 대한"완벽한 문"을 어떻게 근사할지 학습합니다. 일단 훈련되면, 이 가젯은 다양한 문제에 대해 반복적으로 재사용되어 시간과 에너지를 절약할 수 있습니다.

그들이 발견한 것

이 팀은 이 방법을 백과다섯 가지 수학 문제 (예: 배낭 채우기 또는 작업 일정 조정) 에 대해 테스트했습니다.

• 더 나은 결과: "스마트 가이드"접근법 (PC-QAOA) 은"무거운 배낭"접근법보다 훨씬 더 자주 유효한 해답을 찾았습니다.
• 더 높은 품질: 해답을 찾았을 때, 그것이 가능한최고의해답일 가능성이 더 높았습니다.
• 적은 노력: 좋은 결과를 얻기 위해 필요한 단계 (더 얕은"회로 깊이") 가 적었습니다. 양자 컴퓨팅에서 단계가 적다는 것은 노이즈로 인한 컴퓨터의 실수 가능성이 적다는 것을 의미합니다.
• 자원 절약: 구조적 규칙을 위해 추가적인"여유"변수 (추가 수학 도우미) 를 추가할 필요가 없었기 때문에, 더 적은 양자 비트 (큐비트) 와 더 적은 복잡한 2-큐비트 게이트를 사용했습니다.

결론

이 논문은 오늘날 세계의 모든 문제를 해결한다고 주장하지 않습니다. 대신, 쉬운 규칙을 위한 특수한 문을 짓고 어려운 규칙에는 벌점을 사용하는두 가지 전략을 혼합함으로써 양자 컴퓨터가 복잡한 미로를 훨씬 더 효율적으로 탐색할 수 있음을 보여줍니다. 이는 현재 우리가 가진 잡음과 불완전함을 가진 양자 컴퓨터를 위해 양자 최적화를 실용화하는 한 걸음입니다.

기술 요약

기술 요약: 분할 제약 QAOA (PC-QAOA)

문제 제기
제약 조합 최적화 문제 (COPs) 는 양자 알고리즘, 특히 양자 근사 최적화 알고리즘 (QAOA) 에 있어 여전히 중요한 도전 과제로 남아 있습니다. 제약을 처리하는 표준적인 접근법은 비용 해밀토니안에 페널티 항을 추가하여 제약 문제를 비제약 2 차 비제약 이진 최적화 (QUBO) 문제로 변환하는 것입니다. PenaltyQAOA 로 알려진 이 방법은 몇 가지 어려움을 초래합니다: 종종 보조 슬랙 변수가 필요하며, 결과적인 QUBO 의 밀도를 증가시키고, 페널티 계수의 신중한 튜닝을 요구합니다. 큰 페널티는 에너지 지형을 왜곡하여 목적 함수 개선에 대한 민감도를 억제하거나 매우 진동하는 최적화 지형을 유발하는 가파른 장벽을 생성할 수 있습니다. 반면, 문제 특화 믹서와 상태 준비를 통해 탐색을 실현 가능 부분 공간으로 국한시키는 완전 구조적 접근법 (QAOA+ 또는 Grover-Mixer QAOA 등) 은 종종 복잡하고 문제 특화적인 회로 설계를 필요로 하며, 이는 준비하기 어렵고 barren plateaus(황량한 대륙) 나 제한된 연결성으로 고통받을 수 있습니다.

방법론: PC-QAOA 프레임워크
저자들은 PenaltyQAOA 와 완전 구조적 강제 사이의 중간을 이루는 하이브리드 프레임워크인 분할 제약 QAOA(PC-QAOA) 를 소개합니다. 핵심 아이디어는 제약 집합 $C$를 두 개의 서로소 부분 집합으로 분할하는 것입니다:

1. 구조적 제약 ($C_{str}$): 실현 가능성을 보존하는 상태 준비 및 믹싱 연산자를 통해 강제됩니다.
2. 페널티 제약 ($C_{pen}$): 비용 해밀토니안의 에너지 페널티 항을 통해 강제됩니다.

알고리즘은 다음과 같이 진행됩니다:

• 제약 분할: 탐욕적 2-pass 알고리즘은 효율적인 상태 준비를 허용하고 이전에 선택된 구조적 제약과 불연속적인 지지를 갖는 경우 해당 제약을 $C_{str}$에 할당합니다. 나머지 제약은 $C_{pen}$에 할당됩니다.
• 구조적 강제: $C_{str}$에 속하는 제약의 경우, 알고리즘은 실현 가능한 할당들의 중첩인 초기 상태 $|F_{str}\rangle$를 준비합니다.
  • 특정 계열 (카디널리티, 할당, 유량 보존) 의 경우, 정확한 회로 (예: Dicke-상태 준비) 가 사용됩니다.
  • 정확한 구성이 부재한 일반적인 저지지 제약의 경우, 저자들은 **변분 제약 가젯 (VCGs)**을 도입합니다. 이들은 단일 제약의 실현 가능 집합에 대한 균일 중첩을 근사하도록 다각도 QAOA 절차를 사용하여 오프라인에서 훈련된 매개변수화 양자 회로입니다.
• 믹싱: 믹싱 연산자는 $C_{str}$로 정의된 실현 가능 부분 공간을 보존하도록 구성됩니다. 정확한 가젯의 경우, 특정 믹서 (예: 카디널리티용 XY-믹서, VCG 용 Grover 믹서) 가 사용됩니다. 구조적 가젯으로 커버되지 않은 큐비트는 표준 X-믹서를 사용합니다.
• 에너지적 강제: 비용 해밀토니안에는 원래 목적 함수와 $C_{pen}$의 잔여 제약에 대한 페널티 항만 포함됩니다. 탐색이 $F_{str}$로 제한되므로, 축소된 실현 가능 공간에서의 목적 함수 범위가 전체 이진 공간에서의 범위보다 일반적으로 작기 때문에 필요한 페널티 계수는 더 작을 수 있습니다.

주요 기여

1. 하이브리드 제약 처리: 이 논문은 복잡한 제약이나 중첩되는 제약에 대한 페널티를 유지하면서 초기 상태와 동역학에 제약 구조를 선택적으로 인코딩함으로써 회로 복잡성과 탐색 공간 감소를 균형 있게 조절하는 새로운 프레임워크를 제안합니다.
2. 변분 제약 가젯 (VCGs): 저자들은 임의의 저지지 제약에 대한 근사적 실현 가능 상태 준비를 구성하는 방법을 소개합니다. 이러한 가젯은 제약 특화 해밀토니안을 최소화하도록 오프라인에서 훈련되며 문제 인스턴스 간에 재사용될 수 있어, 정확한 구성이 불가능할 때 유연한 대체 수단을 제공합니다.
3. 조성에 대한 이론적 보장: 이 논문은 (명제 IV.1) 쌍별 불연속 지지를 갖는 제약 가젯들이 간섭 없이 정확하게 조립될 수 있음을 입증하여, 병렬로 결합된 실현 가능 중첩을 준비할 수 있음을 보여줍니다. Corollary IV.2 는 결합된 실현 가능 확률에서의 오차 누적은 개별 가젯 오차의 합으로 제한됨을 보여주어, 근사적 가젯을 사용하더라도 높은 실현 가능성을 보장합니다.
4. 유량 보존 구성: 변수 집합 간 동일한 해밍 무게를 강제하기 위해 상관된 Dicke-상태 준비를 활용하는 유량 제약에 대한 새로운 정확한 회로 구성이 제시됩니다.

결과
저자들은 7 가지 제약 계열 (카디널리티, 할당, 유량 보존, 배낭, 2 차 배낭 포함) 에 걸친 413 개의 완료된 인스턴스를 $n \in \{3, \dots, 8\}$의 문제 크기로 평가했습니다.

• 실현 가능성 및 해의 질: PC-QAOA 는 PenaltyQAOA 를 크게 능가했습니다. 얕은 깊이 ($p=1$) 에서 PC-QAOA 는 평균 실현 가능 근사 비율 ($AR_{feas}$) 을 0.588 로 달성한 반면 PenaltyQAOA 는 0.219 였습니다. $p=5$에서 이 격차는 0.783 대 0.305 로 확대되었습니다.
• 실현 가능성 확률: PC-QAOA 는 실현 가능한 해를 샘플링할 높은 확률을 유지했습니다 ($p=1$에서 $P(feas) \approx 0.912$). 반면 PenaltyQAOA 는 현저히 저하되었습니다 ($p=1$에서 $P(feas) \approx 0.420$).
• 최적 해 확률: PC-QAOA 는 $p=1$에서 PenaltyQAOA 대비 최적 해를 샘플링할 확률 ($P(opt)$) 에서 215% 의 상대적 개선을 보였습니다.
• 자원 효율성: PC-QAOA 는 더 적은 수의 큐비트 (구조적 제약에 대한 슬랙 변수 없음) 와 더 적은 2-큐비트 게이트를 필요로 했습니다. $p=1$에서 PenaltyQAOA 보다 1.35 배 적은 2-큐비트 게이트가 필요했으며, $p=5$에서는 이 이점이 1.45 배로 커졌습니다.
• VCG 성능: 훈련된 VCG 들은 $P_{Fk} = 1$의 실현 가능 확률과 평균 0.9186 의 정규화 실현 가능 엔트로피 ($S_{norm}$) 를 달성하여, 실현 가능 부분 공간의 거의 균일한 커버리지를 나타냈습니다.

의의 및 주장
이 논문은 PC-QAOA 가 양자 최적화에서 부분 구조적 강제의 가치를 입증한다고 주장합니다. 초기 상태와 동역학에 제약 구조를 선택적으로 인코딩함으로써, 이 방법은 순수 페널티 기반 접근법보다 얕은 회로 깊이에서 실현 가능해와 최적 해를 측정할 확률을 크게 향상시킵니다. 저자들은 이 접근법이 단기 양자 하드웨어에 대한 실용적인 절충안을 제공하며, 큰 페널티 계수와 보조 슬랙 변수에 대한 의존성을 줄이고 완전히 문제 특화적인 믹서 설계의 복잡성을 완화한다고 주장합니다. 이 연구는 제약 구조를 선택적으로 인코딩하는 것이 특히 제약이 불연속적이고 구조적으로 강제 가능한 부분 집합으로 분할될 수 있는 문제에 대해 확장 가능한 제약 양자 최적화를 위한 유망한 방향임을 시사합니다. 저자들은 그 효과성이 유용한 분할의 가용성에 달려 있으며, 향후 작업은 더 많은 제약을 구조적 강제에 적합하게 만들기 위해 제약 지지 크기를 줄이기 위한 고전적 전처리 (예: 커버 부등식) 를 포함할 수 있다고 지적합니다.