A competitive NISQ and qubit-efficient solver for the LABS problem

기술 요약: LABS 문제에 대한 경쟁력 있는 NISQ 및 큐비트 효율적 솔버

문제 정의
저자기상관 이진 수열(Low Autocorrelation Binary Sequences, LABS) 문제는 공학, 통신 및 통계 물리학 분야에 응용되는 잘 알려진 NP-난해(NP-hard) 조합 최적화 과제입니다. 정수 $N$이 주어졌을 때, 목표는 부수 로브 에너지(sidelobe energy) $E(x)$를 최소화하는 이진 수열 $x \in \{-1, +1\}^N$를 찾는 것입니다. 여기서 $E(x)$는 $\ell > 0$에 대한 제곱 자기상관 $C_\ell(x)$의 합으로 정의됩니다. 동등하게, 목표는 메리트 팩터(merit factor) $F(x) = N^2 / 2E(x)$를 최대화하는 것입니다. 이 문제는 수많은 국소 최솟값(local minima)과 고립된 전역 최솟값(global minima)을 가진 "골프 코스(golf course)" 형태의 최적화 지형을 특징으로 합니다. $N \le 66$인 경우 정확한 해를 찾을 수 있지만, 더 큰 $N$에 대해 최적 또는 고품질의 근사 해를 찾는 것은 고전적인 브루트 포스(brute-force) 방법으로는 불가능하며, 멤메틱 타부 서치(Memetic Tabu Search)와 같은 최첨단 휴리스틱조차 상당한 스케일링 문제를 겪게 됩니다.

방법론: 파울리 상관 인코딩 (Pauli Correlation Encoding, PCE)
저자들은 큐비트 효율적인 변분 양자 솔버를 제안하며, 이는 PCE 프레임워크를 기반으로 합니다. 하나의 큐비트당 하나의 이진 변수를 요구하는 표준 인코딩과 달리, PCE는 $N$개의 이진 변수를 $N = \text{poly}(n)$ 관계를 만족하는 $n$개의 큐비트로 압축합니다(즉, $n \ll N$).

• 인코딩: 이진 변수 $x_i$는 $n$-큐비트 파울리 문자열 $\Pi = \{\Pi_i\}_{i \in [N]}$의 기댓값 부호로 인코딩됩니다:
  $$x_i := \text{sgn}(\langle \Pi_i \rangle)$$
  여기서 $\langle \Pi_i \rangle = \langle \Psi | \Pi_i | \Psi \rangle$입니다.
• 최적화: 양자 상태 $|\Psi\rangle$는 매개변수화된 브릭워크(brickwork) 회로에 의해 생성됩니다. 매개변수는 비선형 손실 함수 $L$을 최소화하기 위해 고전적으로 최적화됩니다. 경사 하강법(gradient-based optimization)을 용이하게 하기 위해, 이진 변수는 쌍곡 탄젠트 함수를 사용하여 완화됩니다: $\tilde{x}_i = \tanh(\alpha \langle \Pi_i \rangle)$. 손실 함수에는 상관 계수가 소멸하는 것을 방지하기 위한 정규화 항이 포함됩니다.
• 파울리 집합 선택: 연구에서는 $\Pi$를 위한 두 가지 구별된 집합을 평가합니다:
  1. $\Pi(C)$: 무작위로 선택된, 상호 가환(mutually commuting)하는 파울리 연산자 집합.
  2. $\Pi(NC)$: 상호 비가환(mutually non-commuting)하는 파울리 연산자의 수를 최대화하도록 설계된 집합. 저자들은 비가환성이 상호 무의사 측정(mutually unbiased measurements)을 유도하여 인코딩된 변수의 표현력과 독립성을 높일 것이라고 가설을 세웠습니다.

주요 기여 및 결과

1. 수치 시뮬레이션 ($N \le 45$):

   • 저자들은 $n=4$ 큐비트와 회로 깊이 15 레이어(2-큐비트 게이트 30개, 매개변수 150개)를 사용하여 PCE 솔버를 시뮬레이션했습니다.
   • $\Pi(NC)$ 변형이 가환 변형보다 일관되게 우수한 성능을 보였습니다.
   • 스케일링 분석: 정확한 해를 찾는 데 필요한 비용 함수 평가 횟수인 TTS(Time-to-Solution)를 QAOA 및 멤메틱 타부 서치와 벤치마킹했습니다.
     • PCE 스케일링: 짝수 인스턴스의 경우 $O(1.330^N)$, 홀수 인스턴스의 경우 $O(1.326^N)$.
     • 비교: 이 스케일링은 QAOA의 스케일링인 $O(1.46^N)$보다 개선되었으며, 최첨단 타부 서치의 스크일링인 $O(1.34^N)$ (짝수 인스턴스) 및 $O(1.409^N)$ (홀수 인스턴스)보다 약간 더 우수합니다.
   • 결과는 테스트된 범위 내에서 PCE가 고전적 베이스라인에 대해 멱법칙(power-law) 이점을 가짐을 나타냅니다.

2. 실험적 입증 (IonQ Forte):

   • 저자들은 현재 양자 하드웨어에서 입증된 가장 큰 크기인 $N=120$ 인스턴스에 대해 IonQ의 Forte 양자 프로세서를 사용하여 개념 증명(proof-of-principle)을 수행했습니다.
   • 실험을 위해 특정 하드웨어 친화적인 $k$-체 상관 계수($k=2$) 세트를 사용했으며, 이는 단 세 번의 측정 설정만을 필요로 했습니다.
   • 노이즈 탄력성: 연구 결과, 샷 노이즈(shot noise)는 미미한 영향(수천 번의 샷만 필요)을 미쳤으나, 하드웨어 노이즈는 최종 해의 품질을 크게 저하시키는 것으로 나타났습니다. 그러나 훈련 과정 자체는 견고하게 유지되었으며, 이는 근미래 배포를 위해 오차 완화(error mitigation)나 더 높은 압축률이 핵심임을 시사합니다.

의의 및 주장
본 논문은 PCE 기반 솔버가 다음 두 가지 경로에 대해 유망한 접근 방식임을 주장합니다:

1. 양자 영감을 받은 고전적 휴리스틱: 클래식하게 시뮬레이션될 때에도, PCE 프레임워크는 LABS와 같은 어려운 문제에 대해 선도적인 고전적 휴리스틱에 비해 경쟁력 있거나 우월한 스케일링을 제공하며, 강력한 양자 영감 알고리즘으로서 기능합니다.
2. NISQ 자원 감소: $N$개의 변수를 폴리노미얼(polynomial)하게 작은 수의 큐비트($n$)로 인코딩함으로써, PCE는 근미래 장치의 큐비트 요구 사항을 획기적으로 줄여줍니다. 저자들은 $n=8$ 큐비트로 이론적으로 정확한 해가 알려진 $N=66$까지의 인스턴스를 다룰 수 있으며, $n \le 20$이면 고전적 휴리스틱으로 해결 가능한 가장 큰 인스턴스들에 도전할 수 있다고 언급했습니다.

저자들은 "양자 우위(quantum advantage)"에 대해 신중한 입장을 유지합니다. 그들은 전체 양자 상태 벡터를 클래식하게 시뮬레이션하는 오버헤드가 진정한 양자 실행 시간 이점이 드러나는 교차점을 늦춘다는 점을 인정합니다. 또한, 이 방법이 강력한 성능을 보여주지만 현재로서는 성능 보장이 부족하다는 점도 명시합니다. 그럼에도 불구하고, 적은 샷 예산으로 $N=120$ 인스턴스를 해결할 수 있는 능력과 노이즈 탄력성에 대한 관찰은 실제 양자 알고리즘의 자원 요구 사항을 줄이는 도구로서 PCE의 잠재력을 강조합니다.