Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

다음은 "양자 교대 방향 승수법을 이용한 반정부호 계획법(Quantum Alternating Direction Method of Multipliers for Semidefinite Programming)" 논문의 상세 기술 요약입니다.

문제 정의

반정부호 계획법(Semidefinite Programming, SDP)은 제어 이론, 통계학, 머신러닝, 금융, 양자 정보 분야에서 응용되는 근본적인 볼록 최적화 문제이다. 그러나 대규모 SDP 인스턴스를 해결하는 것은 고전적 알고리즘에게 여전히 계산적으로 까다로운 과제이다. 주요 병목 현상은 각 반복 단계에서 선형 시스템을 풀고 고유값 분해(특히 양의 준정부호 锥(cone)로의 투영)를 수행하는 데 드는 높은 비용이다. QMWU(Quantum Matrix Multiplicative Weights Updates) 및 QIPM(Quantum Interior Point Methods)과 같은 양자 알고리즘이 이러한 문제를 해결하기 위해 제안되었으나, 이들은 종종 차원 의존성, 희소성 파라미터 또는 정확도 요구 사항 사이의 트레이드오프에 직면한다.

방법론

저자들은 가장 비용이 많이 드는 서브루틴에 대한 양자 가속을 활용하면서도 고전적 1차 방법의 견고함을 유지하도록 설계된 하이브리드 양자-고전 알고리즘인 **양자 교대 방향 승수법(QADMM)**을 제안한다.

1. 부정확한(Inexact) ADMM 프레임워크:
이 접근 방식의 핵심은 SDP에 맞게 조정된 부정확한 ADMM 프레임워크이다. 표준 ADMM과 달리, 이 프레임워크는 양자 서브루틴에 의해 도입되는 오차를 명시적으로 허용한다.

• 쌍대 변수 업데이트: 쌍대 변수 $y$에 대한 업데이트는 선형 시스템 $(AA^*)y = \dots$를 푸는 과정을 포함한다. 양자 설정에서 이는 양자 선형 솔버(QLS)를 사용하여 해결된다.
• 원 변수 업데이트: 원 변수 $S$와 $X$에 대한 업데이트는 양의 준정부호(PSD) 锥로의 투영을 포함한다. 고전적으로 이는 고유값 분해를 필요로 한다. QADMM은 이를 **다항 근사 연산자(polynomial proximal operator)**로 대체한다.
• 오차 허용: 이 프레임워크는 블록 인코딩 근사, 양자 특이값 변환(QSVT), 그리고 양자 상태 토모그래피로부터 발생하는 부정확성을 설명하기 위해 오차 항($\Delta \tilde{y}, \Delta \tilde{S}, \Delta \tilde{X}$ 등)을 도입한다. 저자들은 이 부정확한 스킴의 평균 반복값(averaged iterates)이 여전히 $\epsilon$-최적해로 수렴함을 증명한다.

2. 다항 근사 연산자 및 QSVT:
투영 단계에서의 고유값 분해 비용을 피하기 위해, 저자들은 투영 연산자 $\text{Proj}_{S_+}(x) = \max(0, x)$를 근사하는 다항 함수 $g(x)$를 설계한다.

• 근사 이론을 사용하여, 저자들은 오차 $\epsilon$ 내에서 ReLU 함수를 근사하는 차수 $d = O(1/\epsilon)$의 단조 증가 다항식 $g$를 구성한다.
• 이 다항식은 블록 인코딩 모델 하의 **양자 특이값 변환(QSVT)**을 사용하여 양자 컴퓨터에서 구현된다.
• 이들의 수렴 분석에 필요한 변분 구조를 보장하기 위해, $S$의 "가상" 장벽 함수(virtual barrier function) $h(S)$가 구축되며, 이의 근사 연산자는 이 다항식 변환에 대응한다.

3. 알고리즘 흐름:
알고리즘은 다음과 같이 반복적으로 진행된다:

1. $y$-업데이트: 선형 사상을 고전적으로 계산하고, 양자 상태를 준비하며, QLS를 사용하여 선형 시스템을 푼다.
2. $V$-업데이트: 유니터리의 선형 결합(LCU)을 사용하여 중간 변수 $V = C - A^*(y) - \gamma X$를 계산한다.
3. $S$-업데이트: $V$에 대해 다항식 스펙트럼 변환(PSD 투영을 근사함)을 QSVT를 통해 적용한 후, 고전적 행렬을 재구성하기 위해 토모그래피를 수행한다.
4. $X$-업데이트: $S$-업데이트와 유사하게, 쌍대 변수 $X$를 업데이트하기 위해 다항식 변환을 적용한다.
5. 고전적 후처리: 타당성을 보장하기 위해 재구성된 행렬들을 유계 집합(프로베니우스 노름 제약 조건)으로 투영한다.

주요 기여

1. 견고한 부정확한 ADMM 프레임워크: 본 논문은 고전적 ADMM 수렴 이론과 실제 양자 계산 사이의 이론적 가교를 구축한다. 저자들은 서브문제 해결 및 쌍대 업데이트에 양자 노이즈와 근사 한계에 의한 오차가 포함되더라도, 평균 반복값이 $\epsilon$-최적해로 수렴함을 증명한다.
2. SDP를 위한 다항 근사 매핑: 저자들은 ADMM에서 고유값 분해를 다항식 고유값 변환으로 대체하는 새로운 방법을 도입한다. 이를 통해 QSVT를 사용하여 효율적으로 반정부호 锥 제약을 처리함으로써, 고전적인 스펙트럼 투영의 $O(n^3)$ 또는 $O(n^4)$ 비용을 피할 수 있다.
3. 복잡도 분석 및 비교: 본 논문은 QADMM가 클래식 ADMM 및 기존 양자 솔버(QMWU, QIPM)와 비교하여 유리한 차원 의존성을 달성함을 보여주는 엄밀한 복잡도 분석을 제공한다.

결과 및 복잡도
저자들은 목적 함수 값과 타당성 잔차에 대해 절대 정확도 $\epsilon_{abs}$를 달성하는 데 필요한 총 계산 복잡도를 도출한다.

• 반복 복잡도: 알고리즘은 $K = O\left(\frac{R_X^2 + R_S^2}{\epsilon_{abs}}\right)$ 번의 반복을 필요로 하며, 여기서 $R_X$와 $R_S$는 최적 원 변수 및 쌍대 변수의 프로베니우스 노름 상한이다.
• 총 복잡도:
  • 고전적 연산: $O\left((s_A + n^2)\frac{R_X^2 + R_S^2}{\epsilon_{abs}}\right)$, 여기서 $s_A$는 제약 행렬의 비제로(non-zero) 엔트리 수이다.
  • 양자 게이트 복잡도: $\tilde{O}\left( \left[ m\kappa_A^2(1+R_y)^2 + n^2(\kappa_A^2(1+R_y) + R_X) \right] \frac{(R_X + R_S)^3}{\epsilon_{abs}^3} \right)$.
  • 여기서 $\kappa_A$는 $AA^*$의 조건수이며, $R_y$는 쌍대 변수 노름의 상한이다.

비교:

• 고전적 ADMM 대비: QADMM는 (각 반복 단계에서 고유값 분해 및 행렬 곱셈과 관련된 $O(n^6)$ 또는 $O(n^4)$ 인자들을 피함으로써) 차원 $n$에 대해 더 나은 의존성을 제공한다.
• QIPM 대비: QADMM는 뉴턴 시스템의 높은 조건수($\kappa_{newt}$) 의존성을 피하며, 정확도 의존성에 있어 다른 트레이드오프를 제공한다.
• QMWU 대비: QADMM는 QMWU와 유사한 차원 의존성을 가지지만, 정확도 파라미터 $\epsilon_{abs}$에 대한 낮은 차수의 의존성(일부 영역에서 세제곱 vs 더 높은 거듭제곱)을 가지며, 특히 $\|X^*\|_F$가 $\text{Tr}(X^*)$보다 훨씬 작은 경우(예: 대각 SDP 임베딩)에 매우 유리하다.

의의 및 주장
본 논문은 QADMM가 대규모 SDP를 해결하기 위해 차원에 대해 유리한 스케일링을 제공하며, 고전적 솔버가 고유값 분해 비용으로 인해 어려움을 겪는 문제들에 유망한 후보임을 주장한다.

저자들은 자신들의 접근 방식이 다음을 강조한다:

• 양자 가속 통합: 가장 계산 집약적인 부분들을 가속화하기 위해 QSVT와 QLS를 성공적으로 활용한다.
• 수렴 보장 유지: 부정확한 프레임워크를 개발함으로써, 양자 오차가 최적해로의 수렴을 방해하지 않도록 보장한다.
• 특정 가정에 의존: 알고리즘은 데이터 접근을 위한 다항 크기의 QRAM과 입력 행렬의 블록 인코딩이 가능함을 가정한다. 저자들은 이것이 강력한 가정임을 인정하며, 향-후 연구에서는 이 요구 사항을 완화하는 데 집중할 것이라고 언급한다.

결론적으로, 이 알고리즘은 QRAM 가정에 의해 제한되지만, 대규모 볼록 최적화, 특히 양자 컴퓨팅을 적용하는 데 있어 중요한 진전을 나타내며, 특정 차원 및 정확도 영역에서 고전적 1차 방법 및 다른 양자 SDP 솔버에 대한 실행 가능한 대안을 제시한다.