Quantum Approximation Complexity of Classical Optimization Problems

제목: 고전 최적화 문제의 양자 근사 복잡도
저자: Stuart Hadfield

문제 정의

본 논문은 양자 최적화 알고리즘에 대한 엄격한 최악의 경우(worst-case) 성능 보장이 부족하다는 점을 다룬다. 많은 양자 방법들(예: QAOA, DQI)이 특정 인스턴스에서 높은 점수를 보여주거나 기대값(디코딩된 평균)에 대한 경계치를 제공하지만, 유계 오차(bounded error)를 가진 특정 근사비를 모든 입력에 대해 보장하는 균일한 알고리즘은 결여되어 있는 경우가 많다. 본 연구는 양자 계산이 요청된 정확도를 달ic하기 위해 필요한 시간이나 해결 품질의 측면에서, 무작위적 고전 알고리즘보다 엄격하게 개선될 수 있는지 결정하기 위해 고전적 근사 복잡도 클래스(APX, PTAS, FPTAS)의 양자 유사체를 공식적으로 정의하고자 한다.

방법론

저자는 NPO(NP Optimization) 문제를 유계 오차 양자 알고리즘을 포함하도록 확장한다.

1. 양자 클래스의 정의: 본 논문은 BQ-APX, BQ-PTAS, BQ-FPTAS를 정의한다. 이 클래스들에 속하기 위해서는 모든 입력에 대해, 최소 $2/3$의 확률로 주장된 근사비를 달성하는 실행 가능한 고전적 해를 반환하는 균일한 양자 알고리즘이 필요하다. 결정적으로, 실행 시간에는 파라미터 선택, 상태 준비, 측정, 디코딩 및 반복 단계가 모두 포함된다. 솔루션의 점수는 고전적으로 효율적으로 계산 가능해야 한다.
2. 디코딩된 평균에서 출력으로의 전이: 논문의 Lemma 6과 Corollary 7은 디코딩된 해의 기대 점수와 유계 오차를 가진 고전적 출력 보장 사이의 관계를 확립하는 핵심 기술적 도구이다. 이를 통해 기대값 기반 분석(양자 문헌에서 흔히 사용됨)을 엄격한 출력 보장이 요구되는 클래스 멤버십으로 변환할 수 있다.
3. 조건부 분리: 본 논문은 표준적인 복잡도 가정(예: $NP \not\subseteq BQP$ 및 $Factor \notin FBPP$) 하에서 양자 클래스와 고전 클래스 간의 엄격한 포함 관계를 보여주기 위해 특정 문제들을 구성한다. 이러한 구성은 "탐색 패딩(search padding)"과 암호학적 난해성에 의존한다.

주요 기여 및 결과

1. 양자 근사 클래스의 공식적 계층 구조
본 논문은 $NP \not\subseteq BQP$라는 가정하에 양자 근사 클래스에 대한 엄격한 계층 구조를 확립한다:
$$BQ\text{-}FPTAS \subsetneq BQ\text{-}PTAS \subsetneq BQ\text{-}APX$$
이 계층 구조는 다음과 같은 고전적 문제들에 의해 입증된다:

• Max-E3SAT: 결정론적 상수 비율 근사(APX에 속함)를 가지지만, 양자 PTAS는 존재하지 않는다.
• Planar Vertex Cover: 결정론적 PTAS를 가지지만, 양자 FPTAS는 존재하지 않는다.
  이러한 결과들은 양자 클래스들이 서로 구별됨을 보여주지만, 이 특정 문제들에 대해 양자 클래스와 무작위적 고전 클래스를 분리하지는 못한다.

2. 인증된 최대 차수 (Certified Maximum Order, CMO): 강력한 양자-고전 분리
본 논문은 $N$에 대한 원소의 곱셈 차수(multiplicative order)를 차수의 소인수 분해에 의해 인증하는 인증된 최대 차수(CMO) 문제를 도입한다.

• 양자 결과: 유계 오차 양자 알고리즘은 인수분해와 주기 찾기를 사용하여 다항 시간 내에 정확한 최적값(카마이클 함수 $\lambda(N)$)을 찾을 수 있다. 따라서 $CMO \in BQ\text{-}FPTAS$이다.
• 고전적 장벽: 다항식 인자 근사비조차 보장하는 임의의 무작위 다항 시간 알고리즘이 CMO에 대해 존재한다면, 이는 무작위 다항 시간 인수분해 알고리즘을 의미하게 된다.
• 결론: $Factor \notin FBPP$라고 가정할 때, $CMO \in BQ\text{-}FPTAS \setminus R\text{-}POLY\text{-}APX$이다. 이는 양자 알고리즘은 정확한 해를 제공하는 반면, 무작위 고전 알고리즘은 다항식 인자 근사조차 달성할 수 없음을 보여주는 조건부 분리를 확립한다.

3. 이산 로그 피팅 (Discrete-Logarithm Fitting, DLog-Fit): 임계치 분리
본 논문은 이산 로그를 기반으로 샘플에 대한 레이블을 예측하는 문제인 DLog-Fit을 정의한다.

• 고전적 기준선: 결정론적 알고리즘은 $1/2$-근사(다수 레이블 예측)를 달성한다.
• 양자 우위: 양자 알고리즘은 완벽한 피팅(정확한 최적값)을 찾을 수 있다.
• 고전적 장벽: 무작위 고전 알고리즘이 $1/2$ 비율보다 고정된 개선을 이루는 것은 세이프 프라임(safe-prime) 부서군에서의 이산 로그 문제를 푸는 것과 같다.
• 결론: 세이프 프라임 이산 로그가 $FBPP$에 속하지 않는다는 가정하에, $DLog\text{-}Fit \in R\text{-}APX \cap BQ\text{-}FPTAS \setminus R\text{-}PTAS$이다. 이는 $1/2$ 근사 임계치에서의 격차를 보여준다.

4. 일반 탐색 패딩 (Theorem 8)
본 논문은 효율적으로 검증 가능한 증인이 존재하는 모든 탐색 문제가 $1/2$ 근사 임계치를 가진 NPO 문제로 변환될 수 있음을 보여주는 일반적인 구성을 제공한다. 만약 양자 솔버는 존재하지만 무작위 고전 솔버는 존재하지 않는 양자 솔버가 있다면, 결과적인 최적화 문제는 BQ\text{-}FPTAS}에 속하지만 R\text{-}PTAS} 밖의 영역에 놓이게 된다.

5. 기존 양자 방법론 분석
본 논문은 기존 알고리즘들에 이 정의들을 적용한다:

• QAOA: 3-정규 MaxCut에 대한 고정 깊이 QAOA에 대해, 본 논문은 디코딩된 평균 전이를 사용하여 반복이 유계 오차 출력 보장(예: 최적값의 $2/3$ 초과)을 생성할 수 있음을 보여줌으로써, 이 특정 그래프 패밀리를 $BQ\text{-}APX$에 위치시킨다.
• 디코딩된 양자 간섭계 (DQI): 본 논문은 DQI가 특정 패밀리(예: folded OPI)에서 개선된 기대 점수를 보여주지만, 명시적 입력 시간 모델에서 분리를 확립하려면 무작위 고전 알고리즘이 동일한 비율을 달성할 수 없음을 증명해야 하며, 이는 여전히 미해결 과제로 남아있음을 언급한다.

의의 및 주장

본 논문은 유계 오차 양자 근사 클래스에 대한 최초의 엄격한 정의를 제공하고, 명시적인 복잡도 가정 하에 양자 계산이 무작위 고전 계산에 비해 최악의 경우 근사 보장을 엄격하게 개선할 수 있음을 증명했다고 주장한다.

• 제한된 범위: 저자는 MaxCut 또는 MaxSAT와 같은 일반적이고 제한 없는 문제들에 대해서는 최악의 경우 출력 비율에 대한 양자-고전 격차가 여전히 **열려 있는 문제(open problem)**임을 명시적으로 밝힌다. 확립된 분리들은 특정, 종종 암호학적인 문제 구성(CMO, DLog-Fit)이나 제한된 그래프 패밀리에 의존한다.
• 이론적 프레임워크: 본 연구는 휴리스틱 양자 성능(종종 기대값으로 측정됨)과 엄격한 복잡도 이론(유계 오차 출력 보장) 사이의 간극을 메운다. 이는 균일성과 실행 시간 제한 없이 높은 벤치마크 점수만으로는 근사 클래스 멤버십을 확립할 수 없음을 명확히 한다.
• 향 향후 방향: 본 논문은 표준적인 문제들(예: 제한 없는 MaxCut)에 대해 고전적 난해도 임계치보다 나은 비율을 보장하는 균일한 양자 알고리즘을 찾는 것이 이 분야의 핵심적인 미해결 과제임을 식별한다.