Certified Optimal Measurement Reduction over Quantum Context Landscapes

기술 요약: 양자 컨텍스트 지형(Quantum Context Landscapes)에 대한 인증된 최적 측정 감소

문제 정의
근사 근접 양자 장치(near-term quantum devices)에서 양자 해밀토니안 $\langle H \rangle$의 기댓값을 추정하려면, $H$를 측정 가능한 파편(contexts)으로 분해하고 분산을 최소화하기 위해 측정 샷(shots)을 할당해야 한다. QWC(Qubit-Wise Commuting) 그룹화부터 클래식 섀도우(classical shadows) 및 페르미온 파편에 이르는 기존 전략들은 특정 선언된 측정 모델에 대한 엄격한 하한선 없이 측정 스케줄을 생성하는 경우가 많다. 결과적으로, 관찰된 개선이 고정된 지형 내에서의 더 나은 지점에서 기인한 것인지, 지형의 확장(새로운 컨텍스트) 때문인지, 아니면 기존 프레임워크 내에서 계수 분할(coefficient splitting)이 최적화되지 않았기 때문인지 구분하기 어렵다. 본 논문은 다음과 같은 질문에 답하는 "인증서(certificate)"의 필요성을 다룬다: 선언된 측정 컨텍스트 집합과 공분산 모델 내에서, 최소한으로 불가피한 샷 비용은 얼마이며, 주어진 스케줄은 이 최적값에 얼마나 근접해 있는가?

방법론
저자들은 측정 감소 문제를 두 개의 구별된 최적화 계층, 즉 연속적인 내부 계층과 비볼록(non-convex) 외부 계층으로 나누는 프레임워크를 제안한다.

1. 내부 계층 (볼록 최적화): 고정된 측정 컨텍스트 사전 $\mathcal{D} = \{(V_\ell, c_\ell)\}$ 및 선언된 공분산 모델 $\Gamma_\ell$에 대하여, 최적의 선형 층화 추정량(linear stratified estimator, $H$를 파편 $F_\ell \in V_\ell$로 분해하고 샷 $N_\ell$을 할당)을 찾는 문제는 **이차 원뿔 계획법(Second-Order Cone Program, SOCP)**으로 정식화된다.

   • 목표는 재구성 제약 조건 $\sum F_\ell = H$를 만족하면서 주요 샷 상수 $\Phi = \min \sum \sqrt{c_\ell} \|F_\ell\|_\rho$를 최소화하는 것이다.
   • 이 정식화는 모든 계수 분할의 자유도(중첩 분할 및 상태 인지 공분산 사용 포함)를 단일 볼록 게이지(convex gauge)로 통합한다.

2. 쌍대 인증서 (Dual Certificates): SOCP는 하한 증거(lower-bound witness) $L$을 제공하는 코닉 쌍대(conic dual)를 갖는다.

   • 원형(primal) 솔루션은 특정 스케줄의 비용을 나타내는 상한($U$)을 제공한다.
   • 쌍대 실행 가능 벡터 $y$는 동일한 사전 위에서 어떤 편향되지 않은 선형 층화 추정량도 $L$보다 낮은 비용을 달랄 수 없음을 인증한다.
   • 간극 $U/L$은 기계적으로 확인 가능한 최적성 인증서가 된다. 만약 $U=L$이면, 해당 스케줄은 선언된 지형에 대해 전역적으로 최적이다.

3. 외부 계층 (조합 탐색): 사전(dictionary) 자체의 설계(어떤 컨텍스트를 포함할지 선택하는 것)와 공분산 모델의 보정은 비볼록 문제이다. 저자들은 다음을 수행하기 위해 RANGE(인공 벌 군집과 유전 알고리즘을 혼합한 강건한 적응형 자연 모방 글로벌 옵티마이저)를 사용한다:

   • 최적의 부분 사전(sub-dictionaries) 탐색 (압축).
   • 열 생성(column generation): 쌍대 증거를 "가격 책정 오라클(pricing oracle)"로 사용하여 쌍대 제약 조건을 위반하는(즉, 비용을 확실히 낮출 수 있는) 누락된 컨텍스트를 식별함.
   • 파일럿 데이터를 사용하여 공분산 반경 모델을 보정함.

4. 강건성 (Robustness): 공분산 모델(예: 파일럿 측정 또는 프록시 상태로부터의 데이터)의 불확실성을 처리하기 위해, 프레임워크는 공분산 행렬에 대한 동시 신뢰 구간(샌드위치)을 구축한다. 이는 실제 상태 $\rho$를 알지 못해도 높은 확률로 성립하는 데이터 기반 강건한 인증서($L_{rob} \le \Phi \le U_{rob}$)를 생성한다.

주요 기여

1. 고전적 계보를 가진 정확한 최적해: 본 논문은 임의의 유한 사전에 대한 최소 주요 샷 상수가 SOCP의 값임을 입증한다. 이는 다중 응답 $c$-최적 실험 설계의 양자 컨텍스트 특화 버전이며, 계수 분할 설계 공간의 전역 볼록 폐포(global convex closure)를 제공한다.
2. 독립적으로 검증 가능한 인증서: 기존 연구들이 스케줄과 추정된 분산을 보고하는 것과 달리, 이 프레임워크는 쌍대 증거를 내보낸다. 검증자는 옵티마이저를 신뢰하지 않고도 실행 가능성 잔차(feasibility residuals)를 수정하고 경계값을 재계산할 수 있어, 보고된 간극이 보수적이고 유효함을 보장한다.
3. 공분산 불확실성 하에서의 유효성: 정리 4는 파일럿 데이터를 사용하여 고신뢰도 강건 인증서를 제공함으로써, 오라클 기반 인증서를 데이터 기반 인증서로 업그레이드한다.
4. 열 생성을 통한 사전 인증: 쌍대 증거는 가격 책정 오라클 역할을 한다. 누락된 컨텍스트가 쌍대 제약 조건을 위반하면 해당 컨텍스트를 사전에 추가한다. 이를 통해 프레임워크는 초기 해결된 지형보다 더 큰 지형에 대해 최적성을 인증하거나, 지형을 확장해야 하는 시점을 식별할 수 있다.
5. 등급 판정 도구: 인증서는 세 가지 영역을 구분한다: 자신의 지형 내에서 이미 최적인 휴리스틱, "게이지 자유도"(최적화되지 않은 분할)를 남겨둔 휴리스틱, 그리고 근본적으로 부적절하여 확장이 필요한 지형.

수치 결과
프레임워크는 합성 지형, 분자 해밀토니안($\text{H}_2$, $\text{LiH}$, $\text{BeH}_2$, $\text{H}_2\text{O}$), 그리고 29~35 큐비트 규모의 생산 단계 f-원소 해밀토니안($\text{CeO}$, $\text{NdO}$, $\text{UO}_2^+$ 등)을 통해 검증되었다.

• 최적성 간극: $\text{H}_2$와 같은 작은 시스템에서는 표준 전략(예: 정렬 삽입)이 정확히 최적임이 밝혀졌다. 그러나 $\text{H}_2\text{O}$와 같은 더 큰 시스템에서는 표준 전략이 자신의 설정 내에서 2.1~7.7배의 샷 비용을 최적화하지 못한 채 남겨두는 것으로 나타났다.
• 사전 압축: 글로벌 탐색을 사용하여, 저자들은 사전 크기를 줄이면서도 인증된 샷 비용을 단 0.22.1%만 증가시키며 분자 컨텍스트 사전을 **4.36.1배** 압축했다. 이는 사전 크기와 비용 사이의 날카로운 "무릎(knee)" 지점을 드러냈다.
• 얽힘 설정의 영향: 완전히 가환하는(fully commuting, FC) 컨텍스트(얽힌 설정)를 추가하면 분자 시스템의 인증된 최적값이 25~56% 낮아졌다. 생산 단계 f-원소 해밀토니안의 경우, 이러한 지형 확장은 QWC 전용 사전에 비해 **31~70%**의 샷을 절감했다.
• 압축 vs 샘플링: 본 연구는 블록 인코딩 노름(simulation cost)을 줄이기 위해 설계된 압축 기술이 반드시 샘플링 비용을 줄이지는 않는다는 것을 보여주었다. 예를 들어, 대칭 이동(symmetry shifts)은 블록 인코딩 노름을 크게 줄였으나 인증된 측정 상수에 미치는 영향은 미미했던 반면, 큐비트 테이퍼링(qubit tapering)은 샷 수를 크게 줄였다.
• 생산 규모: 프레임워크는 약 $2 \times 10^4$개의 항과 약 $10^4$개의 컨텍스트(약 $2 \times 10^6$개의 코른 변수)를 가진 해밀토니안에 대해 단일 CPU 노드에서 8~15분 만에 인증서를 성공적으로 생성했으며, 인증된 간극은 $10^{-1}\%$ 미만이었다.

의의 및 주장
본 논문은 측정 감소 주장에 대한 공통 표준을 확립한다고 주장한다. 비볼록 설계 선택(사전 선택)을 볼록 핵심(최적 할당)과 분리함으로써, 이 프레임워크는 전역 탐색이 진정한 조합론적 문제에 집중되도록 하고, 동시에 볼록 최적화가 증명 가능한 보장을 제공하도록 보장한다.

저자들은 이 프레임워크가 기존 휴리스틱(예: ShadowGrouping 또는 minimum clique cover)을 대체하는 것이 아니라, 그 위에 인증 계층을 제공하는 것임을 강조한다. 일단 휴리스틱이 사전이나 스케줄을 제안하면, 코닉 프로그램이 남은 자유도를 최적화하고, 쌍대 증거가 결과가 이론적 한계에 얼마나 근접했는지 인증한다. 논문은 결론적으로 측정 감소를 "기하학 + 최적화"로 보아야 한다고 명시한다. 여기서 지형의 기하학은 허용된 컨텍스트에 의해 정의되며, 인증서는 진행 상황을 평가하는 데 필요한 엄격한 경계값을 제공한다.

저자들은 제한 사항을 명시적으로 언급한다: 인증서는 선언된 공분산 모델에 조건부이며(잘못된 공분산은 잘못된 것에 대한 엄격한 진술을 낳음), 보장은 선언된 지형에 상대적이다(모든 스테빌라이저 컨텍스트에 대한 정확한 가격 책정은 여전히 어려운 조합론적 문제임). 이 프레임워크는 알려진 타겟을 위한 층화된 무편향 추정량을 위해 설계되었으며, 적응형 또는 정보 완전 프로토콜을 위한 것은 아니지만, 그러한 프로토콜에 의해 유도된 추정량을 등급 매길 수는 있다.