Quantum Counting in the Rydberg Blockade

기술 요약: 리드베리 차단(Rydberg Blockade)에서의 양자 카운팅

문제 정의
불리언 만족 가능성 문제(SAT)와 같은 조합론적 문제의 해의 개수를 세는 것은 인공지능, 네트워크 신뢰성, 통계 물리학에서 매우 중요한 과제이다. 그러나 어려운 인스턴스에 대한 정확한 카운팅은 계산 복잡도 클래스 #P에 속하며, 이는 고전 컴퓨터로는 다루기 힘든 것으로 알려져 있다. 샘플링을 통한 근사 카운팅은 실행 가능한 대안이지만, 해를 거의 균일하게 샘플링할 수 있는 능력이 필요하다. 고전적인 샘플링 기반 방식은 효율적으로 균일성을 달빙하는 데 어려움을 겪는 경우가 많다. 또한, 그로버 반복(Grover iterations)에 기반한 기존의 양자 접근 방식들은 변수의 개수에 따라 지수적으로 증가하는 회로 깊이를 요구하므로, 현재의 노이즈가 있는 중간 규모 양자(NISQ) 프로세서에서는 접근이 불가능하다.

방법론: RydCount
저자들은 중성 원자 양자 컴퓨터(NAQC)에 네이티브하게 설계된 샘플링 기반 근사 카운팅 알고리즘인 RydCount를 제안한다. 이 알고리즘은 평면 2-만족 가능성(2-satisfiability, 2SAT) 공식을 대상으로 한다.

1. 물리적 인코딩: 알고리즘은 광학 트랩(optical tweezers)에 갇힌 원자 레지스터에 불리언 변수를 매핑한다. 2SAT 제약 조건은 리드베리 차단(Ridberg blockade)을 통해 강제된다. 구체적으로, 시스템은 인접한 리드베리 상태의 원자들이 동시에 여기되는 것이 에너지적으로 금지되는 리드베리 해밀토니안 하에서 진화한다. 이 물리적 제약은 모노톤 2SAT 공식 $\phi_G(x) = \bigwedge_{(i,j) \in E} (\neg x_i \lor \neg x_j)$를 자연스럽게 인코딩하며, 저에너지 부분 공간은 공식의 해 공간에 해당한다.
2. 샘플링 프로토콜: 핵심 서브루틴인 RydSamp는 초기 계산 기저 상태(일반적으로 $|0\rangle^{\otimes n}$)를 준비하고, 무작위 진화 시간 $t \in [t_{min}, t_{max}]$ 동안 정적 레이저 펄스를 통해 "퀜치(quench)"를 가한 후, 결과 상태를 계산 기저에서 측정하는 과정을 포함한다.
3. 피드포워드(FF) 메커니즘: 샘플링 균일성을 개선하기 위해 알고리즘은 피드포워드 프로토콜을 사용한다. 측정된 비트스트링이 유효한 해인 경우, 이를 다음 반복의 초기 상태로 다시 입력한다. 이론적 분석에 따르면, 일반적인 초기 상태에 대해 리드베리 해밀토니안의 카오스적 역학은 접근 가능한 힐베르트 공간 전체로 상태 진폭을 확산시키며, 충분한 수의 FF 단계($k$)를 거친 후에는 해 집합에 대해 거의 균일한 분포를 생성한다.
4. 자기 감소 카운팅(Self-Reduction Counting): 알고리즘은 Jerrum-Valiant-Vazirani(JVV) 프레임워크를 따른다. 수집된 샘플을 바탕으로 변수를 최대 우도 상태로 반복적으로 고정함으로써 문제의 크기를 줄여나간다. 최종 추정치는 이러한 관측된 확률들의 역수의 곱이다.

주요 기여 및 결과

• 이론적 타당성: 저자들은 리드베리 차단 표현이 JVV 카운팅에 필요한 자기 감소성을 보존함을 입증한다. 완벽한 차단과 장거리 상호작용 꼬리(long-range interaction tails)로 인해 리드베리 해밀토니안이 완벽하게 균일한 분포를 생성하지는 못하지만, $n \approx 10^4$개의 변수를 가진 인스턴스에 대해 다항식 횟수의 FF 단계를 사용하여 "거의 균일한" 샘플링($n\eta \lesssim 1$)을 달성함을 보여준다.

• 고전 시뮬레이션:

  • 1D 및 2D 그리드: 1차원 체인 및 2차원 삼각형 그리드에 대한 시뮬레이션 결과, 샘플 수가 증가함에 따라 추정된 카운트가 정확한 카운트 값의 상수 배 이내로 수렴함을 보여준다.
  • 편향 분석: 저자들은 차세대 이웃 상호작용(next-nearest neighbor interactions)으로 인해 발생하는 2D 및 펑쳐드(punctured) 그리드의 체계적 편향을 식별하였다. 이는 해밍 가중치(Hamming weight)가 높은 상태를 페널티를 주어, 변수가 상태 $|1\rangle$에 있을 확률을 과소평가하게 만들며, 결과적으로 총 카운트를 체계적으로 과대평가하게 만든다. 따라서 이 알고리즘은 이러한 시나리오에서 정확한 추정치보다는 효과적인 상한선(upper bound) 역할을 수행한다.
  • 펑쳐드 그리드: 낮은 홀 밀도(hole density)를 가진 무작위 "펑쳐드" 2D 그리드에 대해, 알고리즘은 정확한 카운트의 1.1배 이내로 수렴한다. 저자들은 GANAK과 같은 고전 솔버가 이러한 인스턴스에 대해 지수적 실행 시간 스케일링을 보인다는 점을 언급하며, 이는 이 그래프 앙상블 내에 고전적으로 어려운 #2SAT 인스턴스가 존재함을 시사하지만, RydCount가 런타임 측면에서 더 빠르거나 우월하다고 주장하는 것은 아니다.

• 실험적 시연: 저자들은 Pasqal의 Orion Alpha NAQC에서 단순화된 하이브리드 변형 RydCount를 구현하였다. 선택적 원자 주소 지정 기능의 부재라는 하드웨어적 한계로 인해, 전체 반복적 자기 감소를 수행할 수는 없었다. 대신 다음과 같이 수행하였다:

  1. 바닥 상태로부터 단일 단계($k=1$) 샘플링을 수행하였다.
  2. 그래프 분리자(separator)를 사전 선택하여 81개 변수의 문제를 두 개의 작은 하위 문제로 분해하였다.
  3. 하위 문제들을 고전적으로 해결하고, 분리자로부터 얻은 양자 유도 곱셈 인자와 결합하였다.
  4. 두 가지 데시메이션 경로($x_c=0$ 또는 $1$로 변수 고정)를 평가하여 상한과 하한을 설정하였다.

  실험 결과: 81개 변수의 평면 그리드 인스턴스에 대해, 순수 하드웨어 샷은 정확한 카운트의 상수 배 5($x_c=1$ 경로) 및 1.01($x_c=0$ 경로) 이내의 추정치를 제공하였다. 유효한 해 비트스트링만을 사후 선택(post-selecting)했을 때, $x_c=0$ 경로는 1.25 미만의 배수 이내로 개선되었다. 두 경로는 정확한 카운트를 성공적으로 경계 지었다.

의의 및 전망
본 논문은 RydCount가 NISQ 장치에서 근사 카운팅을 위한 실행 가능한 근사 접근 방식임을 주장한다. 이 연구의 의의는 다음과 같다:

1. 네이티브 구현: 게이트 기반 양자 알고리즘에 필요한 깊은 회로를 피하기 위해, 제약 조건을 강제하는 데 있어 NAQC의 자연스러운 물리 현상(리드베리 차단)을 활용한다.
2. 확장성: 이 프로토콜은 현재의 비-어닐링 양자 프로세서에게 도전적인 문제 크기($n=81$)에서도 작동하며, 특정 그래프 앙상블에 대해 최첨단 고전 솔버의 한계에 접근한다.
3. 미래 잠재력: 저자들은 현재 클락 속도가 낮지만(< 10 Hz), 100 Hz로의 향후 개선과 수천 개의 원자를 가두고 선택적 주소 지정(이미 학계 실험실에서 입증됨)을 구현할 수 있는 능력이 결합된다면, RydCount가 #P-hard 문제를 위한 고전적 방법의 경쟁력 있는 대안이 될 수 있다고 언급한다. 원자 체인을 사용하여 평면 3-정규 이분 그래프(planar 3-regular bipartite graphs)를 인코딩하는 방식은 이 방법이 #P-complete 인스턴스로 확장될 수 있음을 시사한다.

저자들은 현재의 실험적 시연이 단순화된 하이브리드 변형임을 인정하며, 정확한 추정치가 아닌 경계값만을 얻기 위해서는 장거리 상호작용에 의한 체계적 편향을 완화(예: 더 나은 차단 강도 또는 주소 지정 능력)해야 한다는 점을 명시하며 겸허한 태도를 유지하고 있다.