Asymptotically Optimal Depth Fermionic Permutation on 2D Grid Quantum Architecture without Ancillas

본 논문은 보조 큐비트, 중간 회로 측정, 고전 피드포워드를 요구하지 않으면서도 이론적 $\Omega(\sqrt{N})$ 깊이 하한을 달성하는 2D 그리드 양자 아키텍처를 위한 점근적으로 최적의 페르미온 순열 프로토콜을 소개하며, 주요 페르미온 인코딩 간의 효율적인 변환을 가능하게 하고 초기 오류 허용 시뮬레이션에서 상당한 성능 향상을 입증합니다.

핵심

페르미온(아원자 입자의 한 종류)을 위한 거대한 댄스 파티를 조직하려고 상상해 보세요. 양자 세계에서는 이 입자들이 매우 엄격한 규칙을 따릅니다: 그들은 이웃과 같은 상태에 있는 것을 싫어하며, 만약 그들의 위치를 바꾸면 파티 전체의 "분위기"가 변합니다 (수학적으로는 부호가 반전됩니다).

이를 양자 컴퓨터에서 시뮬레이션하려면 이 입자들을 작은 프로세서 (큐비트) 의 격자 위를 이동시켜야 합니다. 문제는 컴퓨터의 격자가 옆집으로만 걸을 수 있는 도시 블록과 같다는 점입니다. 하지만 페르미온의 규칙은 그들이 도시 전체에 걸쳐 있는 사람들과 상호작용해야 함을 요구합니다.

이 논문이 달성한 바를 간단히 요약하면 다음과 같습니다:

1. 문제: "긴 도보" 병목 현상

과거에 2 차원 격자 (체스판과 같은) 위에서 이 입자들을 이동시키기 위해 과학자들은 "뱀" 패턴을 사용해야 했습니다. 긴 복도 한쪽 끝에서 다른 쪽 끝으로 사람들의 줄을 이동시키려는데, 오직 바로 옆 사람에게만 메시지를 전달할 수 있다고 상상해 보세요.

• 옛 방법: 100 명의 사람이 있다면, "메시지" (또는 입자) 가 반대편에 도달하기 위해 100 개의 집을 지나가야 할 수도 있습니다. 이는 느립니다. 소요 시간은 입자의 수 ($N$) 에 비례하여 선형적으로 증가했습니다.
• 2 차원의 이점: 격자가 정사각형 (도시와 같음) 이기 때문에, 가로지르는 거리는 실제로 훨씬 더 짧습니다 ($N$의 제곱근). 하지만 이전 방법들은 이 이점을 활용하기에는 너무 둔감했습니다; 그들은 여전히 길고 구불구불한 줄을 따라 걷고 있었습니다.

2. 해결책: 3 단계 셔플

저자들은 정사각형 격자에 완벽하게 들어맞는 새로운 입자 셔플 방식을 고안했습니다. 마치 도시 계획가가 교통 흐름을 재설계하는 것과 같습니다. 그들은 "행 - 열 - 행" 전략을 사용합니다:

1. 행 셔플: 모든 사람을 자신의 행 내에서 오른쪽 차선으로 이동시킵니다.
2. 열 이동: 모든 사람을 올바른 행으로 위나 아래로 이동시킵니다.
3. 행 셔플: 모든 사람을 해당 행 내의 최종 위치로 이동시킵니다.

이 방식은 격자의 모양을 효율적으로 활용하기 때문에 훨씬 더 빠릅니다. 100 걸음을 걷는 대신 100 개의 입자에 대해 약 10 걸음만 걸으면 됩니다.

3. 비밀 무기: "마법의 유령" ($\Gamma$ 연산자)

여기가 까다로운 부분입니다. 입자를 격자를 따라 수직으로 (위와 아래로) 이동시킬 때, "뱀" 순서가 깨집니다. 양자 물리학에서 순서를 깨뜨리면 수학을 올바르게 유지하기 위해 특별한 "보정" (위상 반전) 이 필요합니다.

• 옛 해결책: 이전 방법들은 이 오류를 수정하기 위해 격자 위를 돌아다니는 "유령" 입자들 ( 안실라라고 함) 을 사용했습니다. 이는 추가적인 공간과 시간을 소모했습니다.
• 새로운 해결책: 저자들은 유령 도우미 없이 이 보정을 수행하는 방법을 찾았습니다. 그들은 지휘자처럼 작용하는 특별한 "마법" ( $\Gamma$이라는 수학적 연산자) 을 고안했습니다.
  • 지휘자가 지휘봉을 휘두른다고 상상해 보세요. 지휘봉이 휘두러질 때, 그것은 한 번에 전체 행의 "분위기"를 즉시 수정합니다.
  • 그들은 추가 도우미 없이 기존 댄서들 (큐비트) 만을 사용하여 이 지휘자를 만드는 방법을 알아냈습니다. 또한 지휘자의 움직임을 최적화하여 이전보다 시간이 덜 걸리도록 했습니다 (약 38% 단축).

4. 결과: 가능한 가장 빠른 셔플

이 논문은 그들의 방법이 점근적으로 최적임을 증명합니다.

• 그 의미: 무한한 추가 도우미, 텔레포트, 또는 초고속 고전 컴퓨터를 사용하더라도 2 차원 격자에서 이 셔플을 더 빠르게 수행하는 것은 불가능합니다. 그들은 이론적 속도 한계에 도달했습니다.
• 이득: 100 개의 입자로 구성된 시스템의 경우, 그들의 방법은 이전 방법들보다 훨씬 빠르며 더 적은 "시공간" (사용된 컴퓨터 성능과 시간의 측정치) 을 사용합니다.
• 다용도성: 그들은 또한 이 속도를 페르미온에 대해 이야기하는 양자 컴퓨터가 사용하는 세 가지 다른 "언어" (인코딩) 로 변환하는 방법도 보여주어 전체 시스템의 유연성을 높였습니다.

5. 현실 세계 테스트

그들은 두 가지 특정 양자 시뮬레이션에서 이를 테스트했습니다:

1. 페르미온 푸리에 변환: 양자 파동을 분석하기 위한 표준 도구.
2. SYK 모델: 혼돈적인 양자 시스템 (심지어 블랙홀까지) 을 연구하는 데 사용되는 복잡한 모델.

두 경우 모두 시스템이 충분히 커지면 (약 100 개의 입자), 그들의 새로운 방법이 명백한 승자가 되어 이전 방법들보다 훨씬 높은 정확도 (신뢰도) 와 낮은 오류율을 제공했습니다.

요약 비유

당신이 도시의 격자 모양 집들에서 거대한 파티를 조직한다고 상상해 보세요.

• 옛 방법: 집 1 번에서 집 100 번까지 메시지를 전달하려면 문간에서 문간으로 걸어가야 했고, 레시피가 섞이지 않도록 하기 위해 메신저 팀 (안실라) 이 필요했습니다. 이는 영원히 걸렸습니다.
• 새로운 방법: 당신은 집들을 행과 열로 조직합니다. 모든 사람에게 행으로 이동하라고 하고, 그 다음 열로 이동하라고 하고, 마지막으로 좌석으로 이동하라고 합니다. 당신은 추가 메신저 없이 모든 혼란을 즉시 수정하는 특별한 "마법 휘슬" ( $\Gamma$ 연산자) 을 사용합니다.
• 결과: 파티는 절대적으로 최소 시간 내에 조직되며, 파티에 이미 있는 사람들만 사용되고, 음식은 완벽하게 신선하게 도착합니다.

이 논문은 그 "마법 휘슬"과 양자 컴퓨터를 위한 가장 효율적인 교통 계획의 청사진을 제공하여, 화학과 물리학의 복잡한 시뮬레이션을 훨씬 더 실현 가능하게 만듭니다.

기술 요약

기술 요약: 애너실라 없이 2 차원 그리드 양자 아키텍처에서 점근적으로 최적인 깊이의 페르미온 순열

1. 문제 제기

큐비트 하드웨어에서 상호작용하는 페르미온 시스템을 시뮬레이션하는 것은 국소 큐비트 연산자와 페르미온 생성 및 소멸 연산자의 비국소적 반교환 관계 사이의 근본적인 불일치로 인해 방해받습니다. 이로 인해 페르미온 - 큐비트 매핑 (예: Jordan–Wigner, Bravyi–Kitaev, 또는 Parity 인코딩) 과 상호작용하는 모드를 인접한 큐비트로 라우팅하기 위한 동적 페르미온 순열이 필요합니다.

2 차원 최근접 이웃 (NN) 그리드 아키텍처에서 기존 라우팅 프로토콜은 상당한 오버헤드에 직면합니다.

• 1 차원 접근법: 1 차원 정렬 네트워크 (예: 홀수 - 짝수 전치) 를 2 차원 그리드에 단순하게 컴파일하면 $O(N)$ 의 깊이와 $O(N^2)$ 의 게이트 수가 발생하여 그리드의 두 번째 차원을 활용하지 못합니다.
• 전체 - 전체 (All-to-All) 적응: 전체 - 전체 또는 재구성 가능한 아키텍처에서 $O(\log N)$ 또는 $O(\log^2 N)$ 깊이를 달성한 최근 프로토콜들은 배열을 횡단하는 데 $\Theta(\sqrt{N})$ 시간이 소요되기 때문에 2 차원 그리드에서는 $O(\sqrt{N} \text{ polylog } N)$ 으로 저하됩니다.
• 하한: $O(N)$ 개의 애너실라, 회로 중간 측정, 그리고 고전 피드포워드를 허용하는 국소 연산 및 고전 통신 (LOCC) 모델에서도 유효한 2 차원 그리드 라우팅에 대한 이론적 하한 $\Omega(\sqrt{N})$ 이 존재합니다.

핵심적인 과제는 애너실라, 측정, 또는 피드포워드에 의존하지 않고 2 차원 NN 하드웨어에서 이 $\Omega(\sqrt{N})$ 하한을 달성하는 것입니다. 이러한 요소들은 초기 오류 정정 regime 에서 자원 집약적이고 오류가 발생하기 쉽습니다.

2. 방법론

저자들은 2 차원 그리드 아키텍처에 특화된 페르미온 순열 프로토콜을 제안하며, 이는 고전적 라우팅 분해와 위상 보정을 위한 애너실라 없는 유니터리 연산자로 구성됩니다.

A. Hall 의 행 - 열 - 행 (RCR) 분해

모드를 1 차원 체인으로 선형화하고 1 차원 회로를 컴파일하는 대신, 이 프로토콜은 Hall 의 결혼 정리에 기반한 고전적 분해를 활용합니다. $L \times L$ 그리드 ($N=L^2$) 위의 임의의 순열 $\pi$ 는 세 단계로 분해됩니다.

1. 행 A: 소스 행 내의 순열.
2. 열: 목적지 행으로 항목을 이동시키기 위한 열 내의 순열.
3. 행 B: 최종 열로 이동하기 위한 목적지 행 내의 순열.

표준 "뱀" (boustrophedon) Jordan–Wigner (JW) 순서 하에서, 수평 이웃은 JW-인접하므로 행 단계는 자연스럽게 국소적입니다. 그러나 열 단계는 JW-비인접한 수직 이웃을 포함하므로, 표준 하드웨어 FSWAP 게이트가 제공하지 않는 패리티 문자열 보정이 필요합니다.

B. $\Gamma$ 연산자 (위상 다항식 보정)

애너실라 없이 수직 스왑의 비국소성을 해결하기 위해, 저자들은 대각 유니터리 연산자 $\Gamma$ 를 구성합니다.

• 기능: $\Gamma$ 는 (패리티 문자열을 무시하는) "벌거벗은" 수직 FSWAP 을 (필요한 위상 보정을 포함하는) "완전한" 페르미온 SWAP 으로 변환합니다. 구체적으로, $\Gamma \cdot B_{j,k} \cdot \Gamma = F_{j,k}$이며, 여기서 $B$ 는 벌거벗은 스왑이고 $F$ 는 완전한 페르미온 스왑입니다.
• 구현: 저자들은 $\Gamma$ 를 위상 다항식 렌즈를 사용하여 재구성합니다. 그들은 요구되는 위상 함수 $f(s)$ 를 2 차원 그리드 기하학에 부합하는 국소 단항식으로 분해합니다.
  • 대수적 재구성: 위상 다항식은 $f_D$(동일 행 및 인접 교차 행 항) 와 $f_B$(열 패리티 기저 항) 로 분할됩니다. 이는 모든 단항식이 그리드의 작고 기하학적으로 국소적인 부분집합 내의 큐비트들을 포함하도록 하여, 이전 연구 [21] 에서 사용된 이동 애너실라의 필요성을 제거합니다.
  • 파이프라인 융합: 회로는 여러 대수적 조각을 행당 단일 "스위프"로 융합하도록 스케줄링됩니다. 접두사 합 CNOT 캐스케이드 뒤에 상호작용 게이트를 배치함으로써, 이 프로토콜은 $\Gamma$ 적용당 $8L$ 의 깊이를 달성하며, 이는 이전 애너실라 기반 구성의 $13L$ 깊이보다 약 38% 감소한 것입니다.

C. 전체 프로토콜

완전한 알고리즘 (알고리즘 1) 은 5 단계 파이프라인으로 실행됩니다.

1. 행 A 정렬 실행 (국소 FSWAP 사용).
2. $\Gamma$ 적용.
3. 열 정렬 실행 (벌거벗은 수직 FSWAP 사용).
4. $\Gamma$ 적용 ($\Gamma = \Gamma^\dagger$ 이므로).
5. 행 B 정렬 실행.

$\Gamma$ 연산자들은 열 정렬을 샌드위치하여 벌거벗은 스왑의 전체 시퀀스를 유효한 페르미온 순열로 변환합니다.

D. BK 및 Parity 인코딩으로의 확장

이 프로토콜은 기저 변환을 통해 Bravyi–Kitaev (BK) 및 Parity 인코딩으로 확장됩니다. 큐비트를 힐베르트 공간 채우기 곡선을 따라 매핑함으로써, 저자들은 인코딩 간 변환을 위한 트리 회전 CNOT 레이어가 2 차원 그리드에서 $O(\sqrt{N})$ 깊이로 라우팅될 수 있음을 보여줍니다. 이는 세 가지 주요 인코딩 모두에 대해 점근적 최적성을 유지합니다.

3. 주요 기여

• 애너실라 없는 점근적으로 최적의 깊이: 이 논문은 2 차원 NN 그리드에서 깊이 $22\sqrt{N} + O(1)$ 및 $O(N\sqrt{N})$ 최근접 이웃 얽힘 게이트를 가지며, 영개의 애너실라, 회로 중간 측정, 또는 고전 피드포워드를 요구하는 페르미온 순열 알고리즘을 제시합니다. 이는 엄격히 더 많은 자원을 가진 프로토콜에 대해서도 $\Omega(\sqrt{N})$ 하한과 일치합니다.
• 애너실라 없는 $\Gamma$ 구성: 이전 2 차원 페르미온 라우팅 방법 [21] 이 요구했던 $\Theta(\sqrt{N})$ 이동 애너실라를 제거하는 새로운 위상 다항식 기반 최적화로, $\Gamma$ 깊이의 상수 계수를 약 38% 감소시켰습니다.
• 인코딩 중립성: 힐베르트 곡선 레이아웃을 사용하여 2 차원 그리드에서 JW, BK, Parity 인코딩 간 변환을 위한 $O(\sqrt{N})$ 깊이 방식을 통해, 최적 순열 결과를 세 가지 인코딩 모두로 확장했습니다.
• 실용적 성능: 수치적 벤치마크는 시스템 크기 $N \gtrsim 100$ 에서 CNOT 깊이, 시공간 부피, 그리고 추정된 충실도 측면에서 기존 기준 (1 차원 FSWAP 네트워크 및 애너실라 기반 2 차원 방법) 보다 일관되게 우수한 성능을 보여줍니다.

4. 결과 및 평가

저자들은 독립적인 페르미온 순열, 2 차원 페르미온 고속 푸리에 변환 (FFFT), 그리고 희소 Sachdev–Ye–Kitaev (SYK) 모델의 Trotter 시뮬레이션이라는 세 가지 작업 부하에 대해 프로토콜을 평가했습니다.

• 확장성: $N \ge 100$ 에 대해 제안된 방법의 $O(\sqrt{N})$ 확장성은 1 차원 기준의 $O(N)$ 확장성보다 2 차적인 개선을 제공합니다.
• 깊이 감소: $N \approx 900$ 에서 제안된 방법은 최상의 2 차원 애너실라 기반 기준 대비 약 50%, 1 차원 기준 대비 약 60% 의 깊이 감소를 달성합니다.
• 충실도: 잡음 시뮬레이션 (탈분극 잡음) 에서 제안된 방법은 $N \gtrsim 100$ 에 대해 경쟁자보다 높은 충실도를 유지합니다. 예를 들어, 2 큐비트 오류율이 $10^{-5}$ 일 때, 이 방법은 $N \approx 900$ 까지 충실도 $>0.5$ 를 유지하는 반면, 1 차원 기준은 $N \approx 400$ 에서 이 임계값 아래로 떨어집니다.
• 자원 효율성: 애너실라를 제거함으로써 시공간 부피가 크게 감소합니다 (예: $N=900$ 에서 애너실라 기반 방법보다 약 1.7 배 낮음).

5. 중요성 및 주장

이 논문은 2 차원 하드웨어에서 페르미온 시뮬레이션을 위한 이론적 하한과 실제 컴파일 사이의 격차를 해소했다고 주장합니다. 애너실라 없이 $\Omega(\sqrt{N})$ 하한을 달성함으로써, 이 프로토콜은 강력한 LOCC 모델에 대해서도 최적입니다.

저자들은 이 작업이 초기 오류 정정 regime에서 특히 관련성이 높음을 강조합니다. 이 regime 에서는 자원 제약 (큐비트 수, 오류율) 으로 인해 애너실라 제거와 상수 계수 감소가 중요합니다. 이 방법은 페르미온 시스템 (예: Fermi–Hubbard, SYK 모델) 과 변환 (FFFT) 의 더 효율적인 시뮬레이션을 가능하게 하여, 근미래 하드웨어에서 이러한 알고리즘에 필요한 논리적 예산을 직접 축소합니다.

논문은 두 가지 열린 질문을 언급하며 결론을 맺습니다. 2 차원 그리드에서 곱 보존 3 진 트리 인코딩의 전체 클래스로 $O(\sqrt{N})$ 한계가 확장되는지 여부, 그리고 $\Gamma$ 연산자의 상수 계수가 공동 스케줄 최적화를 통해 더 감소될 수 있는지 여부입니다.