기술 요약: One for All: 하드 제약 조건이 있는 조합 최적화 문제를 위한 범용 양자 코닉 프로그래밍 프레임워크

1. 문제 정의

본 논문은 특히 잡음이 있는 중간 규모 양자(NISQ) 시대에, 양자 하드웨어에서 **NP-완전 제약 조건 조합 최적화 문제(CCOPs)**를 해결하는 과제를 다룹다.

QAOA(Quantum Approximate Optimisation Algorithm)와 같은 기존의 변분 양자 알고리즘(VQAs)은 하드 제약 문제가 적용될 때 세 가지 주요 장애물에 직면한다:

1. 제약 조건 처리: 제약 조건을 엄격하게 준수하는 매개변수화된 양자 회로(PQC)를 설계하는 것은 매우 까ৰ론하며, 종종 문제 특화적인 "믹서(mixer)" 및 초기 상태 엔지니어링을 요구한다.
2. 최적화의 어려움: VQA의 고전적 매개변수 최적화 루프는 원래의 문제만큼이나 어려울 수 있으며, 비볼록(non-convex) 지형으로 인해 고통받는다.
3. 배런 플래토(Barren Plateaus): 많은 VQA는 기울기 소실(vanishing gradients) 현상을 겪으며, 이로 인해 큐비트 수가 증가함에 따라 국소 최적해(local optima)에 도달하는 것조차 어려워진다.

최근 제안된 양자 코닉 프로그래밍(QCP)과 같은 방식은 작업을 일반화된 고유값 문제(GEP)로 매핑함으로써 배런 플래토를 완화하고 최적화를 단순화하는 데 성공했지만, 소프트 제약 페널티(정교한 하이퍼파라미터 튜닝이 필요함)를 사용하거나 복잡한 실행 가능성 보존 믹서를 사용하지 않고는 **하드 제약(hard constraints)**을 처리할 수 있는 메커니즘이 부족했다.

2. 방법론

저자들은 QCP를 임의의 하드 제약 문제가 있는 문제로 일반화하는 통합 양자-고전 프레임워크인 One for All을 제안한다. 이 방법론은 다음 구성 요소들에 의존한다:

A. 선형 결합 유니터리(LCU)를 통한 매개변수화된 안사츠(Ansatz)

본 프레임워크는 유니터리 진화 대신, 선형 결합 유니터리(LCU)를 통해 구축된 비유니터리 안사츠 클래스를 사용한다.

• 안사츠: 상태는 $|\psi\rangle = \frac{M_\alpha |\iota\rangle}{\|M_\alpha |\iota\rangle\|}$로 정의된다. 여기서 $M_\alpha = \sum_{j=1}^\ell \alpha_j U_j$이며, $\{U_j\}$는 탐색 유니터리, $|\iota\rangle$는 초기 상태, $\alpha \in \mathbb{C}^\ell$는 복소수 계수이다.
• 실행 가능성 강제: 불가능한 상태를 목적 함수에서 페널티를 주는 소프트 제약 접근 방식과 달리, 이 프레임워크는 매개변수 최적화 과정에서 직접 하드 제약을 강제한다. 즉, 결과 상태가 불가능한 부분 공간 $S^\perp$와 직교하도록 요구한다.

B. 샘플 행렬 및 측정 프로토콜

양자 문제를 고전적 최적화 작업으로 변환하기 위해, 저자들은 초기 상태와 탐색 유니터리로부터 유도된 세 가지 샘플 행렬($F, G, H$)을 정의한다:

• $F$: 정규화($\langle \psi | M_\alpha^\dagger M_\alpha | \psi \rangle$)를 인코딩한다.
• $G$: 실행 가능성($\langle \psi | M_\alpha^\dagger (1-P_S) M_\alpha | \psi \rangle$, 여기서 $P_S$는 실행 가능한 부분 공간으로 투영하는 연산자)을 인코딩한다.
• $H$: 목적 함수($\langle \psi | M_\alpha^\dagger C M_\alpha | \psi \rangle$)를 인코딩한다.

측정의 핵심 혁신: 본 논문은 목적 해밀토니안 $C$나 양자 실행 가능성 오라클을 QPU에 구현할 필요가 없는 특수한 측정 프로토콜을 상세히 설명한다.

1. 보조 큐비트에 의해 제어되는 LCU 연산을 사용하여 $(U_j \pm U_k)|\iota\rangle$와 같은 상태의 중첩을 준비한다.
2. 계산 기저(computational basis)에서 비트 문자열을 측정한다.
3. 샘플링된 비트 문자열에 고전적 목적 함수 $c(b)$와 고전적 실행 가능성 오라클 $d(b)$를 적용하여 행렬 엔트리를 추정한다.

C. 일반화된 고유값 문제(GEP)로의 환원

핵심적인 이론적 기여는 이중 제약 이차 최적화 문제(minimising $H$ subject to $F=1$ and $G=0$)를 **일반화된 고유값 문제(GEP)**로 엄격하게 환원하는 것이다.

• 저자들은 최소한의 가정(생성된 상태들의 선형 독립성) 하에서, 제약된 최적화가 변환된 쌍의 행렬에 대한 최소 일반 고유값을 찾는 것과 동등함을 증명한다.
• 이 변환은 퇴화(degenerate) 사례에 대한 이전 유도 과정의 공백을 메우며, 문제가 전형적인 VQA의 NP-어려운 매개변수 최적화를 피하고 고전 CPU에서 효율적으로 해결 가능한 상태를 유지하도록 보장한다.

D. 노이즈에 대한 강건성

본 프레임워크는 노이즈로 인해 초기 상태가 혼합 상태(밀도 연산자)가 되더라도 유효함을 보여준다. 저자들은 결과적인 반정부호 계획법(SDP)의 최적해가 랭크-1 행렬에서 달성됨을 증명하며, 이는 최적해가 여전히 보조 레지스터에 대한 순수 상태 업데이트로 표현되고 구현될 수 있어 LCU 구현의 효율성을 보존함을 의미한다.

3. 주요 기여

1. QCP의 일반화: 본 논문은 소프트 제약을 사용하지 않고 임의의 하드 제약이 있는 조합 최적화 문제로 양자 코닉 프로그래밍을 확장한다.
2. 통합 프레임워크: 고전적 목적 함수와 실행 가능성 오라클에 의해서만 알고리즘 구축이 결정되는 "즉시 사용 가능한(out-of-the-box)" 접근 방식을 제공하여, 문제 특화적인 믹서 설계(QAOA의 주요 병목 현상)의 필요성을 제거한다.
3. 엄격한 GEP 유도: 저자들은 이중 제약 매개변수 최적화를 GEP로 환원하는 수학적으로 엄격한 증명을 제공하여, 퇴화 사례 및 강한 쌍대성(strong duality)에 관한 기존 문헌의 공백과 오류를 바로잡는다.
4. 하드웨어 효율적 프로토콜: 복잡한 해밀토니안이나 오라클을 양자 장치에 구현하는 대신, 샘플링된 비트 문자열의 고전적 사후 처리에 의존하는 측정 프로토콜을 도입한다.
5. 노이즈 탄력성: 생성된 서브콘(subcone) 내에서 최적해가 노이즈(혼합 상태)의 영향 아래에서도 포착될 수 있음을 입증하는 증명을 제공한다.

4. 결과

저자들은 10개의 강력하게 상관된 Pisinger 배낭 문제(n=16 아이템)에 대한 개념 증명(proof-of-concept) 수치 시뮬레이션을 제시한다.

• 성능: 이 방법은 고전적 그리디(greedy) 베이스라인을 성공적으로 개선했다. 그리디 솔루션이 약했던 사례에서, 양자 최적화기는 근사 비율(approximation ratio)이 최대 0.98에 달하는 실행 가능한 중첩으로 수렴하였으며, 그리디 솔루션 대비 최대 0.09의 이득을 얻었다.
• 메커니즘: 이러한 이득은 단일 채널 고전 업데이트가 실현할 수 없는 아이템 교환의 결맞는 중첩(coherent superpositions)을 통해 달성되었다.
• 구현 확률: LCU 단계를 구현할 확률은 웜 스타트(warm-start) 값($2^{-16}$)의 6배 이내로 유지되어, 이 영역에서 지수적으로 소멸하는 성공 확률 문제를 겪지 않음을 보여주었다.
• 수렴: 근사 비율은 그리디 값을 밑돌지 않았으며, 구성 요소들에 걸쳐 가중치가 분산됨에 따라 구현 확률은 완만하게 감소했다.

5. 의의 및 주장

본 논문은 짧거나 중간 정도의 결맞는 시간(coherence time)을 가진 양자 장치에서 임의의 제약이 있는 조합 최적화 문제를 해결하기 위한 통합 프레임워크를 구축한다고 주장한다.

• 배런 플래토 완화: 비유니터리 매개변수 게이트를 활용하고 최적화를 GEP로 매핑함으로써, 본 프레임워크는 배런 플래토를 방지하고 NP-어려운 매개변수 최적화를 피하는 유리한 특성을 상속받는다.
• QAOA와의 개념적 독립성: QAOA에서 영감을 받았으나 개념적으로는 독립적이다. 일반화된 QAOA(특화된 믹서가 필요한)에서 상실되었던 "즉시 사용 가능한" 적용 가능성을 고전적 목적 함수와 실행 가능성 오라클을 최적화 루프에 직접 통합함으로써 복구한다.
• 확장성: 이 접근 방식은 원거리 장치(far-term devices)에 적용 가능하도록 설계되었으며, 적절한 서브루틴을 CPU로 외주화할 수 있고, 임의의 제약이 있는 문제에 대해서도 유효하다.

저자들은 현재의 연구가 이론적 토대와 시뮬레이션을 통한 개념 증명을 제공하지만, 프레임워크의 성능을 완전히 측정하기 위해서는 더 큰 규모의 문제(예: 외판원 문제)에 대한 추가적인 이론적 강화와 광범위한 수치 실험이 필요하다고 결론짓는다.