Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems

기술 요약: 근대칭 최적화 문제에 대한 얕은 QAOA의 결함 허용 비용

문제 정의
Montanaro와 Zhou [1]는 깊이 1의 양자 근사 최적화 알고리즘(QAOA) 회로가 특정 근대칭 제약 충족 문제(CSP)의 심어진 해(planted solution)를 상수 확률 $\Omega(1)$로 찾을 수 있음을 입증했다. 반면, 이러한 문제들의 명시적 구현체들은 강력한 고전 솔버들에 대해 외견상 지수적인 실행 시간 스케일링을 보인다. 이는 경험적인 지수적 가속을 시사하지만, 초기 결함 허용 양자 컴퓨터에서 이러한 회로를 구현하기 위한 자원 요구 사항은 불분명하다. 이 문제들의 비용 해밀토니안은 $\Theta(n^\ell)$ 개의 절(clause)을 포함하며 ($\ell \ge 5$), 이는 표준 Clifford+$T$ 합성법을 사용하여 컴파일할 때 비-클리포드(non-Clifford) 게이트 수가 $\tilde{O}(n^\ell)$로 스케일링됨을 의미한다. 이러한 스케일링은 관련 문제 규모를 근미래의 결함 허용 하드웨어의 도달 범위를 벗어나게 만든다.

방법론
저자들은 이러한 근대칭 인스턴스에 적용되는 깊이 1 QAOA 회로의 결함 허용 자원 비용을 분석하며, 특히 위상 분리층(phase-separator layer)의 합성에 집중한다. 분석은 다음 세 가지 주요 단계를 거친다:

1. 위상 매칭 및 각도 스케일링: 저자들은 상수 성공 확률을 위해 필요한 위상 매칭 조건을 재검토한다. 심어진 해에 대해 변수 치환에 대칭적인 비용 함수의 경우, 지배적인 해밍 껍질(Hamming shells)의 건설적 간섭을 보장하기 위해 위상 분리 각도 $\gamma$는 $\gamma = \Theta(n^{1-\ell})$로 스케일링되어야 한다.
2. 작은 각도 합성: $\gamma$가 시스템 크기에 따라 줄어든다는 점을 활용하여, 저자들은 작은 각도 Clifford+$T$ 회전 합성 기법(특히 Bothe 등 [9]의 방식)을 적용한다. 이들은 작은 각도 회전이 높은 확률로 항등 함수(identity)로 근사되고, 오직 적은 비율의 회전만이 비-클리포드 합성을 필요로 하는 준확률(quasi-probability) 및 확률 혼합 정식화를 활용한다.
3. 명시적 절 컴파일 및 누출 분석: 저자들은 값 오라클 모델(비용 $C(x)$만을 쿼리하는 모델)에서 회로 컴파일에 필요한 명시적 절 목록 모델로 전환한다. 이들은 명시적 절 목록으로부터 유도된 비용 함수의 푸리에 계수를 분석하여, 컴파일 과정이 의도치 않게 해를 드러내는지 확인한다.
4. 기만적 인스턴스 구축: 명시적 구조를 이용하는 고전적 공격에 대한 견고성을 테스트하기 위해, 저자들은 "심어지지 않은(unplanted)" 근대칭 인스턴스를 구축한다. 이 인스턴스들은 지수적으로 큰 최적 해밍 껍질 내에 NP-난해(NP-hard) 부분 문제를 포함하며, 국소 탐색 알고리즘을 함정에 빠뜨리도록 설계된 비용 랜드스케이프를 갖는다.

주요 기여 및 결과

• 이차 비-클리포드 스케일링: 주요 결과는 이러한 인스턴스에 대한 깊이 1 QAOA의 비-클리포드 비용이 절의 국부성 $\ell$ 및 희소화율에 관계없이 $\tilde{O}(n^2)$로 감소한다는 것이다. 이러한 감소는 전체 위상 질량($m\gamma$, 여기서 $m$은 절의 개수)이 $n$에 선형적으로 스케일링되고, 작은 각도 합성 비용이 이 위상 질량의 제곱에 의존하기 때문에 발생한다. 결과적으로, 기존에 $\tilde{O}(n^\ell)$ 스케일링으로 인해 불가능하다고 여겨졌던 문제 규모들이 초기 결함 허용 장치에서도 실행 가능해진다 (그림 2 참조).
• 심어진 계열에서의 고전적 누출: Ref. [1]에서 연구된 심어진 계열의 경우, 저자들은 컴파일에 필요한 명시적 절 목록이 심어진 해를 노출한다는 것을 보여준다. 위상 매칭 조건($F'(1/2) \neq 0$)은 비용 함수의 1차 푸리에 계수(국소 장)의 부호를 결정한다. 이 부호들은 절 목록에 대한 단순한 선형 시간 고전 스캔을 통해 심어진 해 $s$를 직접적으로 드러낸다. 따라서 QAOA가 상수 확률로 성공하더라도, 명시적 구현은 문제를 고전적으로 사소하게(trivial) 만든다.
• 심어지지 않은 인스턴스의 존재: 저자들은 작은 각도 영역과 $\tilde{O}(n^2)$ 비용 스케일링이 심어진 해의 존재 여부에 의존하지 않음을 입증한다. 저자들은 심어진 해가 없는 근대칭 인스턴스를 다음과 같이 구축한다:
  • 전역 최적해가 지수적으로 큰 해밍 껍질 내에 존재한다.
  • 해당 껍질 내에서 정확한 최적해를 찾는 것은 NP-난해이다.
  • 비용 랜드스케이프는 "기만적"이며, 높은 에너지 장벽에 의해 분리된 하위 최적 섹터에 국소 탐색 및 일반 목적 MaxSAT 솔버를 가둔다.
  • 작은 각도에서의 깊이 1 QAOA는 최적 껍질에 출력을 집중시키며 동일한 $\tilde{O}(n^2)$ 비-클리포드 비용을 갖는다.
  • 이러한 심어지지 않은 경우, 1차 계수들은 균일하며 해를 드러내지 않는다. 이는 특정 대칭 구조를 이용하지 않는 고전 알고리즘에 대한 난해성을 보존한다.

의의
본 논문은 근대칭 문제에 대한 낮은 깊이의 QAOA가 이전에 가정되었던 것보다 훨씬 낮은 결함 허용 자원, 즉 $\tilde{O}(n^\ell)$가 아닌 $\tilde{ODE}(n^2)$의 비-클리포드 게이트를 사용하여 실현될 수 있음을 확립한다. 이는 이러한 얕은 작은 각도 회로들이 초기 결함 허용 하드웨어의 현실적인 목표가 될 수 있음을 의미한다.

그러나 저자들은 중요한 트레이드오프를 조심스럽게 언급한다: 작은 각도 합성을 가능하게 하는 메커니즘(결맞는 국소 장)이 동시에 심어진 시나리오에서 해를 고전적 공격에 노출시킨다는 점이다. 이 연구의 의의는 얕은 QAOA가 최적화를 위한 자원 효율적인 경로를 제공하는 영역을 식별하는 동시에, 이러한 효율성을 가능하게 하는 특정 구조적 특성이 양날의 검이 될 수 있음을 밝히는 데 있다. 저자들은 핵심적인 미결 과제가 이 "저렴한" 작은 각도 영역을 더 깊은 회로나 해가 저차 고전 공격으로부터 숨겨진 다른 문제 구조로 확장하여, 결함 허용 측면에서 저렴하면서도 고전적으로 저항력이 있는 진정한 양자 우위를 달야낼 수 있는지 여부라고 결론짓는다.