Quantum Circuits for the Metropolis-Hastings Algorithm

본 논문은 고전적 제안-수용 논리를 직접 따름으로써 가역 연산의 높은 큐비트 오버헤드를 회피하는 메트로폴리스-헤이스팅스 알고리즘을 위한 자원 효율적인 세게디 양자 보행 구성을 제시하여, 마르코프 연쇄 몬테카를로 시뮬레이션을 위한 실용적인 엔드투엔드 2 차 속도 향상을 가능하게 한다.

핵심

거대한 어두운 방에 가구가 가득 차 있다고 상상해 보세요. 가장 편안한 장소를 찾고자 합니다. 당신은 한 번에 방 전체를 볼 수 없으므로 다음과 같은 전략을 사용합니다: 무작위로 한 걸음을 내딛고, 새로운 장소가 더 나은지 확인한 후, 그곳에 머무를지 아니면 원래 위치로 돌아갈지 결정합니다. 이것이 메트로폴리스-헤이스팅스 (MH) 알고리즘의 본질입니다. 이는 복잡한 확률 지형을 탐색하는 데 사용되는 고전적인 컴퓨터 방법입니다. 안개 낀 산맥을 헤매는 등산객과 같아서, 새로운 봉우리로의 이동 확률을 알려주는 지도에 기반하여 걸음을 옮기는 것과 같습니다.

수십 년간 과학자들은 양자 컴퓨터가 이 등산객이 훨씬 더 빠르게, 구체적으로 최적의 장소를 찾는 데 필요한 '걸음' 수 기준으로 두 배 빠르게 움직일 수 있기를 희망해 왔습니다. 이 속도 향상은 세게디 양자화 (Szegedy's quantization) 라는 수학적 트릭에서 비롯됩니다. 이는 등산객의 무작위 보행을 '양자 보행'으로 변환하여 등산객이 여러 경로를 동시에 탐색할 수 있게 합니다.

그러나 기존 양자 방식에는 큰 문제가 있습니다. 양자 등산객을 작동시키기 위해 컴퓨터는 등산객이 걷는 동안 엄청난 양의 복잡한 수학 계산을 수행해야 합니다. 이는 등산객이 한 걸음을 내딛기 전에 모든 가능한 미래 걸음에 대한 정확한 확률을 계산하도록 요구하는 것과 같습니다. 이를 양자 컴퓨터에서 수행하려면 이러한 계산을 저장하기 위해 방대한 수의 추가 '도움' 비트 (큐비트) 가 필요합니다. 현재 우리는 매우 적은 수의 도움 비트만 사용할 수 있는 양자 컴퓨터 시대에 살고 있으므로, 이 방법은 너무 무거워 감당하기 어렵습니다.

이 논문의 해결책: '기억' 트릭

이 논문의 저자인 바티스트 클로드와 그의 팀은 무거운 계산을 우회하는 교묘한 방법을 발견했습니다. 모든 이동의 확률을 계산하려 시도하는 대신, 그들은 게임의 규칙을 약간 변경했습니다.

표준 MH 알고리즘을 생각해 보세요. 이는 이동을 제안하고, 만약 거절되면 그 생각을 잊어버리고 제자리에 머무는 게임과 같습니다. 문제는 양자 세계에서는 '잊어버리는' 행위가 번거롭다는 점입니다. '잊어버리는' 행위를 쉽게 되돌릴 수 없습니다.

저자들의 해결책은 등산객에게 기억을 부여하는 것입니다.

• 설정: 등산객의 현재 위치만 추적하는 대신, 양자 컴퓨터는 쌍으로 된 위치를 추적합니다. 즉, 등산객이 현재 있는 곳과 방금 왔던 곳 (또는 이동하려 시도했던 곳) 입니다.
• 논리:
  • 새로운 장소가 수용되면, 등산객은 그곳으로 이동하고 기억은 이전 장소를 보여주도록 업데이트됩니다.
  • 새로운 장소가 거절되면, 등산객은 제자리에 머무르지만 기억은 거절된 장소를 유지합니다.
• 마법: 거절된 장소를 기억에 남겨두면, 과정은 결코 진정으로 '잊어버리는' 일이 없습니다. 모든 걸음이 되돌릴 수 있게 됩니다 (항상 이전 상태로 돌아갈 수 있음). 이 되돌림 가능성은 양자 컴퓨터가 즉흥적인 복잡한 산술 계산 없이 보행을 실행할 수 있게 해주는 열쇠입니다.

결과: 더 가볍고 빠른 양자 보행

즉흥적인 복잡한 확률을 계산할 필요가 없기 때문에, 그들의 새로운 양자 회로는 놀라울 정도로 가볍습니다.

• 기존 방식: 문제의 복잡도에 따라 증가하는 수의 도움 비트 (큐비트) 가 필요했습니다. 이는 걷는 마일마다 새로운 배낭이 필요한 것과 같습니다.
• 새로운 방식: 문제의 복잡도와 관계없이 고정된 소수의 도움 비트 (단 세 개의 추가 큐비트) 만 사용합니다. 이는 어떤 여정이든 들어맞는 작고 효율적인 배낭을 가진 것과 같습니다.

그들이 증명한 것

저자들은 단순히 더 가벼운 회로를 구축한 것이 아니라, 그것이 이론상 최선의 속도로 여전히 작동함을 증명했습니다.

1. 속도: 그들은 그들의 양자 보행이 약속된 '이차 속도 향상'을 여전히 달성함을 보였습니다. 고전적 등산객이 최적의 장소를 찾는 데 100 걸음이 필요하다면, 그들의 양자 등산객은 약 10 걸음만 필요합니다.
2. 정확도: 그들은 '기억' 트릭이 결과를 왜곡하지 않음을 증명했습니다. 등산객은 여전히 고전적 등산객이 하던 대로 올바른 비율로 방을 탐색하며, 훨씬 더 빠르게 올바른 장소를 찾습니다.
3. 현실 세계 테스트: 그들은 메트로폴리스 조정 랑주뱅 알고리즘 (MALA) 이라는 특정 유형의 문제에서 이를 테스트했습니다. 이는 분자 역학 (분자의 움직임 시뮬레이션) 과 기계 학습에서 널리 사용됩니다. 그들은 27 개의 큐비트를 가진 양자 컴퓨터에서 이를 성공적으로 시뮬레이션하여, 이론이 예측한 대로 '양자 간격' (속도 측정치) 이 실제로 제곱됨을 확인했습니다.

요약

이 논문은 양자 컴퓨터에서 메트로폴리스 - 헤이스팅스 알고리즘을 실행하는 새로운 효율적인 방법을 제시합니다. 거절된 이동에 대한 간단한 '기억'을 알고리즘에 부여함으로써, 저자들은 일반적으로 양자 시뮬레이션을 지연시키는 무겁고 복잡한 계산의 필요성을 제거했습니다. 이는 오늘날 이용 가능한 제한된 양자 컴퓨터에서 이러한 강력한 샘플링 알고리즘을 실행할 수 있게 하여, 막대한 양의 추가 하드웨어 없이도 더 빠른 신약 개발 시뮬레이션과 더 나은 기계 학습 모델을 위한 길을 마련합니다.

기술 요약

기술 요약: 메트로폴리스-헤이스팅스 알고리즘을 위한 양자 회로

문제 제기
마르코프 연쇄 몬테카를로 (MCMC) 방법, 특히 메트로폴리스 - 헤이스팅스 (MH) 알고리즘은 분자 역학부터 기계 학습에 이르기까지 다양한 분야에서 확률 분포로부터 표본을 추출하는 데 필수적입니다. 이러한 알고리즘의 효율성은 혼합 시간에 의해 결정되며, 이는 근본적인 마르코프 연쇄의 스펙트럼 갭에 반비례하여 스케일링됩니다. 세게디 (Szegedy) 의 양자화 프레임워크는 가역적 마르코프 연쇄를 이차적으로 더 큰 스펙트럼 갭을 가진 양자 보행으로 매핑함으로써 이론적인 이차적 속도 향상을 제공합니다.

그러나 MH 알고리즘에 대한 세게디의 양자 보행을 구현하는 것은 상당한 실용적 장애물을 안고 있습니다. 일반적인 구현은 전이 확률 (특히 거절 확률을 나타내는 마르코프 커널의 대각 성분) 의 일관된 계산을 요구합니다. 이는 큐비트 레지스터에 대한 복잡한 가역 산술을 필요로 하여, 계산의 복잡도에 비례하여 증가하는 큐비트 오버헤드를 초래합니다. 논리 큐비트가 희소한 근미래의 결함 허용 양자 컴퓨팅 맥락에서 이러한 오버헤드는 금지적입니다. furthermore, 기존 방법들은 종종 MH 알고리즘이 본질적으로 갖지 않는 특정 대칭성이나 군 구조에 의존합니다.

방법론
저자들은 전이 확률의 일관된 계산을 완전히 피하는 MH 알고리즘의 양자 단계 연산자에 대한 새로운 구성을 제안합니다. 그들의 방법론의 핵심은 확장된 상태 공간에서의 MH 과정을 재형식화하는 것입니다.

1. 엣지 공간의 이중 커널: 상태 공간 $S$에서 작동하는 대신, 저자들은 방향성 엣지 공간 $S^2$(상태 쌍 $(x, y)$) 에 대한 이중 마르코프 커널을 정의합니다. 이 프레임워크에서 상태 $(x, y)$는 '꼬리' $x$와 '머리' $y$를 나타냅니다.

   • 제안: 제안 단계 $T$는 꼬리 $x$를 고정하면서 새로운 머리 $z$를 생성하여 $(x, y) \to (x, z)$로 전이합니다.
   • 수용/거절: 수용 단계 $A$는 엣지에 작용합니다. 수용되면 엣지는 $(z, x)$로 뒤집히고, 거절되면 엣지는 $(x, z)$로 유지됩니다.
   • 가역성: 결정적으로, 이 형식화는 거절된 제안을 머리에 저장함으로써 거절 단계를 가역적으로 만듭니다. 이를 통해 전체 과정을 '샘플 망각'이나 비가역적 연산 없이 유니터리 역학으로 인코딩할 수 있습니다.

2. 오라클을 통한 양자 단계 연산자: 이 구성은 두 가지 양자 오라클에 의존합니다.

   • $O_T$: 제안된 이동의 중첩을 준비하는 제안 오라클.
   • $O_A$: 수용 행렬 $A$에 기반하여 엣지의 확률적 뒤집기를 수행하는 수용 오라클.
     저자들은 이중 커널 $P = TA$의 양자 단계 연산자와 그 시간 역행$P^\star = AT$가$O_T$와$O_A$에 대한 일정한 횟수의 호출을 사용하여 구성될 수 있음을 증명합니다.

3. 에르미트화 및 큐비트화: 이중 커널 $P$는 일반적으로 비가역적이므로, 저자들은 에르미트화 절차를 사용합니다. 그들은 $P$와 $P^\star$의 인코딩을 가역적 팽창의 판별자 (discriminant) 에 대한 대칭적 투영 유니터리 인코딩 (SPUE) 으로 결합합니다. 이를 통해 큐비트화된 보행 스펙트럼 정리를 적용할 수 있습니다.

4. 샘플링 절차: 결과적으로 생성된 큐비트화된 보행 연산자 $W$는 원래 MH 연쇄의 정상 분포에 해당하는 인코딩 범위 내에서 고유한 1-고유벡터를 갖습니다. 양자 위상 추정을 사용하여 이 고유벡터로 투영한 후 오라클을 역계산 (uncomputing) 함으로써 목표 분포 $\pi$로부터의 표본을 추출할 수 있습니다.

주요 기여

• 산술 없는 가역 논리: 이 논문은 전이 확률이나 거절률의 일관된 계산을 요구하지 않는 MH 커널의 세게디 양자화를 제시합니다. 이는 오직 제안 및 수용 오라클에만 의존합니다.
• 일정한 큐비트 오버헤드: 이 구성은 수용 확률 계산의 복잡성과 관계없이 고정된 수량의 보조 큐비트 (주요 구성의 경우 3 개, 대안적인 제어 -SWAP 접근법의 경우 1 개) 만 필요합니다. 이는 이전 방법들에서 보조 큐비트 수가 산술의 정밀도나 복잡도에 비례하여 증가했던 점과 대조됩니다.
• 이차적 속도 향상 유지: 저자들은 결과적으로 생성된 큐비트화된 보행의 스펙트럼 갭이 고전적 MH 연쇄의 스펙트럼 갭 $\delta$에 대해 $\Omega(\sqrt{\delta})$임을 증명하여 이론적인 이차적 속도 향상을 유지함을 보여줍니다.
• 이중 커널 형식화: 엣지 공간 $S^2$에 대한 이중 커널의 도입은 MH의 비가역적 거절 단계를 가역적으로 만들어 유니터리 인코딩을 용이하게 하는 메커니즘을 제공합니다.

결과

• 이론적 경계: 저자들은 구성된 보행 연산자의 각 갭이 $\Omega(\sqrt{\delta})$임을 증명합니다. 그들은 가역적 팽창 $PP^\star$의 스펙트럼 갭이 일반적인 수용 행렬의 경우 적어도 $\delta/2$이거나 (글로버 선택의 경우 $\delta$와 같음) 이차적 증폭이 성립함을 보장합니다.
• 자원 효율성: 논문의 표 I 은 논리 큐비트 요구 사항을 비교합니다. 제안된 방법은 주요 구성의 경우 $4m + 3$개의 큐비트 (여기서 $m = \lceil \log_2 n \rceil$는 상태 공간의 비트 수) 를 필요로 하며, 대안적인 방법은 $2m + 1$개를 필요로 합니다. 이는 이전 접근법들 (예: Childs 등 requiring $5pd + du$개의 큐비트) 보다 훨씬 낮습니다.
• 수치적 검증: 저자들은 두 우물 퍼텐셜에 적용된 메트로폴리스 - 조정 랑주뱅 알고리즘 (MALA) 에 대한 오픈소스 구현과 수치 시뮬레이션을 제공합니다. 27 개의 큐비트 (상태 레지스터당 6 비트) 를 사용하여 구현된 보행 연산자가 고전적 과정보다 이차적으로 큰 스펙트럼 갭을 보이며 이론적 경계와 일치함을 확인했습니다.

의의
이 논문은 행렬 요소나 전이 확률의 일간된 계산을 피하는 유일한 MH 커널의 세게디 양자화라고 주장합니다. 가역적 산술에 필요한 큐비트 수를 최소화 (일정 수로 감소) 함으로써, 이 연구는 MH 양자 보행이 금지적인 알고리즘적 오버헤드 없이 구현될 수 있음을 시사합니다. 이는 수용 단계가 복잡한 분자 역학 및 기계 학습 응용 분야에서 근미래의 결함 허용 양자 컴퓨터를 위한 MCMC 시뮬레이션의 이차적 속도 향상을 더 접근 가능하게 만듭니다. 저자들은 이를 마르코프 연쇄 몬테카를로 알고리즘의 완전한 이차적 양자 속도 향상을 향한 점진적인 단계로 위치시키며, 작은 인스턴스들이 수치적으로 분석될 수 있고 이 방법이 원자 수에 대한 선형 큐비트 스케일링을 통해 현실적인 시스템으로 확장 가능함을 보여줍니다.