Arts & crafts: Strong random unitaries and geometric locality

본 논문은 $D$차원 격자에서 강력한 근사 유니터리 $k$-디자인과 의사난수 유니터리를 생성하기 위한 두 가지 구성을 제시하며, 두 번째 방법은 보조 큐비트 없이 증명적으로 최적의 깊이를 달성합니다.

핵심

완벽하고 완전히 예측 불가능한 케이크를 굽으려 한다고 상상해 보세요. 양자 컴퓨터의 세계에서는 이 "완벽한 케이크"를 **하어-무작위 유니타리 (Haar-random unitary)**라고 부릅니다. 이는 카드 덱을 섞어 순서가 진정으로 무작위가 될 때까지 섞는 것과 마찬가지로, 모든 가능한 결과가 동등하게 발생할 확률을 보장하는 수학적 레시피입니다.

그러나 이 완벽한 케이크를 굽는 것은 실제 양자 컴퓨터에서는 불가능합니다. 케이크의 크기에 따라 지수적으로 증가하는 시간과 에너지가 필요하기 때문입니다. 즉, 겨우 몇십 가지 재료로 케이크를 만들려면 우주의 에너지가 필요할 것입니다.

그래서 과학자들은 질문합니다: 누군가가 그것을 먹으려 시도할 때 완벽하게 무작위처럼 보이지만, 실제로는 훨씬 빠르게 만들 수 있는 "충분히 좋은" 케이크를 구울 수 있을까요?

이 논문은 **격자형 구조 (많은 실제 양자 칩에서 사용되는 2 차원 또는 3 차원 격자와 같은)**로 구축된 양자 컴퓨터에 대해 "예"라고 답합니다. 여기서는 간단한 비유를 사용하여 그들의 해결책을 설명합니다.

문제: "빛원뿔 (Lightcone)" 제약

양자 컴퓨터를 사람들이 즉각적인 이웃과만 대화할 수 있는 도시라고 상상해 보세요. 전체 도시의 인구를 섞어 무작위 순서를 만들려면, 모든 사람을 중앙으로 순간이동시킬 수 없습니다. 대신 이웃에서 이웃으로 메시지를 전달해야 합니다.

도시가 긴 줄 (1 차원) 이라면, 한쪽 끝에서 다른 쪽 끝까지 메시지가 전달되는 데 오랜 시간이 걸립니다. 이를 **빛원뿔 한계 (lightcone limit)**라고 합니다. 논문은 크기가 $n$인 격자의 경우, 무작위성을 섞을 수 있는 가장 빠른 속도는 격자의 "반지름" (대략 $n$의 $D$제곱근, 여기서 $D$는 차원 수) 에 비례한다고 지적합니다.

이전 연구는 모든 사람이 서로 즉시 대화할 수 있는 "전체 연결 (all-to-all)" 도시와 1 차원 줄에 대해서는 이 문제를 해결했지만, 중간 영역인 **다차원 격자 (초전도 양자 칩에서 사용되는 2 차원 격자와 같은)**는 미스터리로 남아 있었습니다.

해결책: 케이크를 섞는 두 가지 방법

저자들은 격자에서 이러한 "강력한 무작위성" 회로를 생성하기 위한 두 가지 다른 레시피를 제시합니다.

레시피 1: "접착" 방법 (마스터 건축가)

이것은 거대한 모자이크를 만드는 것과 같습니다. 전체를 한 번에 만들 수 없으므로 작은 완벽한 타일을 만들어 그들을 붙여 합칩니다.

1. 작은 타일: 먼저 격자의 작은 영역에서 완벽하게 무작위인 작은 "타일" (강력한 2-디자인) 을 만드는 방법을 알아냈습니다.
2. 접착제: 이 작은 무작위 타일들을 거대한 무작위 모자이크로 결합할 수 있는 특별한 수학적 "접착제" (접착 보조정리, gluing lemma) 를 사용합니다.
3. 결과: 이러한 타일을 신중하게 배열함으로써, 이론적 속도 한계 (빛원뿔) 에 부합하는 시간 내에 $D$차원 격자에서 거대하고 강력한 무작위 회로를 구축할 수 있음을 증명했습니다.

주요 특징: 이 방법은 최적입니다. 시간이나 추가 재료 (보조 큐비트) 를 낭비하지 않습니다. 이 특정 유형의 무작위성을 만드는 가장 효율적인 방법입니다.

레시피 2: "라우팅" 방법 (교통 통제관)

집의 다른 방에 놓인 재료를 섞어야 하는 레시피가 있다고 상상해 보세요. 복도가 하나뿐인 집 (제한된 연결성) 에서는 재료를 섞는 그릇으로 직접 운반해야 합니다.

1. 문제: 가장 좋은 무작위 레시피는 모든 방이 서로 연결된 집 (전체 연결) 을 위해 설계되었습니다.
2. 해결책: 저자들은 라우팅 전략을 사용했습니다. 이는 사람들이 효율적으로 자리를 바꾸도록 집 안을 걷는 방법을 정확히 지시하는 교통 통제관과 같습니다.
3. 결과: 그들은 "전체 연결" 무작위 레시피를 가져와 큐비트들이 서로 상호작용할 수 있도록 인접하게 이동시키는 "걷기 지시" (순열) 레이어를 추가했습니다.

주요 특징: 이 방법은 총 큐비트 수에 관해서는 첫 번째 방법보다 약간 느리지만 매우 유연합니다. "무작위성" 매개변수 (예: 케이크를 확인하는 횟수) 에 대한 더 나은 제어를 허용하며, 필요시 속도를 높이기 위해 추가 "도움" 큐비트를 사용할 수 있습니다.

"강력한" 디자인이란 무엇인가?

논문은 **"강력한 (Strong)"**이라는 단어에 강조를 둡니다.

• 약한 무작위성: 마술사가 카드 덱을 섞는다고 상상해 보세요. 만약 상단 카드만 본다면 무작위처럼 보입니다. 하지만 상단 카드를 본 후 덱을 뒤집어 하단 카드를 보면, "약한" 섞기에서는 패턴이 드러날 수 있습니다.
• 강력한 무작위성: "강력한" 디자인은 마술사가 덱을 너무 완벽하게 섞어서, 상단 카드를 보고 덱을 뒤집어 하단을 본 후 섞기를 역으로 시도해 보더라도 여전히 완전히 무작위처럼 보이는 것과 같습니다.

저자들의 구성은 "강력한" 것으로, 적대자가 양자 컴퓨터를 역으로 사용하거나 여러 각도에서 과정을 관찰하더라도 무작위성이 유지됨을 의미합니다.

결론

이 논문은 격자로 배치된 양자 컴퓨터 (오늘날 대부분의 실제 양자 칩이 구축된 방식) 에 대해서는 물리 법칙이 허용하는 속도로 강력한 무작위 프로세스를 생성할 수 있음을 증명합니다.

그들은 다음을 통해 이를 달성했습니다:

1. 작은 무작위 블록을 효율적으로 접착하는 것.
2. 완전히 연결된 시스템을 모방하기 위해 격자 주위를 큐비트를 **라우팅 (이동)**하는 것.

이는 엔지니어들이 특정 하드웨어에서 이러한 무작위 회로를 얼마나 빠르게 실행할 수 있는지 정확히 알려주기 때문에 큰 진전입니다. 이는 양자 컴퓨터가 시간이나 자원을 낭비하지 않고 벤치마킹, 암호화, 복잡한 물리 시뮬레이션과 같은 작업을 수행할 수 있음을 보장합니다.

기술 요약

기술적 요약: 강력한 랜덤 유니터리와 기하학적 국소성

문제 제기
본 논문은 기하학적으로 국소적인 연결성, 구체적으로 $D$차원 격자를 갖는 양자 시스템에서 강력한 근사 유니터리 $k$-디자인과 **강력한 의사난수 유니터리 (PRU)**를 구성하는 문제를 다룬다. Haar-랜덤 유니터리는 무작위성을 위한 이상적인 모델이지만, 계산적으로 다루기 어렵다. 디자인으로 알려진 효율적인 근사들은 양자 머신러닝, 다체 물리학, 암호학의 응용에 필수적이다.

약한 디자인 (유니터리 $U$만 쿼리하는 적대자에 대해 안전함) 과 강력한 디자인 ($U$, 그 역 $U^\dagger$, 전치 $U^T$, 그리고 켤레 $\bar{U}$를 쿼리하는 적대자에 대해 안전함) 사이에는 중요한 구분이 존재한다. 많은 양자 알고리즘과 물리적 과정이 정방향 및 역방향 진화를 포함하므로 강력한 디자인이 필요하다.

이전 연구는 **전체 연결 (all-to-all)**의 경우 깊이 $O(\log n)$에서, 1 차원 체인의 경우 $\Omega(n)$에서 강력한 디자인을 구성할 수 있음을 확립했다. 그러나 $D$차원 격자 ($D > 1$) 와 같은 중간 연결성에 대한 최적의 깊이는 여전히 미해결 문제였다. 본 논문은 $n$개의 큐비트를 갖는 $D$차원 격자에 특히 초점을 맞추어, 이러한 일반적인 연결성에서 강력한 디자인과 PRU 를 형성하는 데 필요한 회로 깊이를 규명하는 것을 목표로 한다.

방법론
저자들은 $D$차원 격자에서 이러한 디자인을 구성하기 위해 두 가지 다른 접근법을 사용한다:

1. 글루링 (Gluing) 과 데카르트 곱을 통한 직접 구성:

   • 강력한 글루링 보조정리: 저자들은 Schuster 등 [SML+25] 의 강력한 글루링 보조정리를 기반으로 하여, 강력한 2-디자인 사이에 끼워져 있을 경우 더 작은 강력한 유니터리 디자인들을 더 큰 디자인으로 결합할 수 있음을 활용한다.
   • 데카르트 곱 구조: $D$차원 격자가 1 차원 선 그래프들의 데카르트 곱임을 인식하여, 저자들은 "파울리 믹싱" 프로토콜을 반복적으로 적용함으로써 강력한 2-디자인을 구성한다. 이는 격자의 행과 열에 작용하는 유니터리들의 교차 레이어를 포함한다.
   • 약한 디자인 통합: 결과 앙상블이 강력한 디자인이 되도록 하기 위해, 구성된 2-디자인 (특정 쿼리 조합에 대해 안전함) 은 [SHH25] 의 알려진 약한 상대오차 2-디자인과 결합된다.
   • 재귀적 합성: 강력한 2-디자인을 구성 요소로 사용하여, 저자들은 보조 큐비트 없이 강력한 $k$-디자인을 구성하기 위해 글루링 보조정리를 재귀적으로 적용한다.

2. 라우팅 기반 구성:

   • 라우팅 이론: 두 번째 접근법은 그래프 라우팅 이론의 결과를 활용한다. 국소 격자에서 비국소 상호작용을 구현하는 작업은 " Pebbles"(큐비트) 을 특정 목적지로 치환해야 하는 라우팅 문제로 매핑된다.
   • SWAP 네트워크: 저자들은 큐비트를 국소적으로 상호작용할 수 있는 위치로 치환하는 데 필요한 깊이를 결정하기 위해 데카르트 곱 그래프의 라우팅 수에 대한 경계 (특히 [BA91] 의 정리 23) 를 활용한다.
   • 컴파일: 기존 전체 연결 강력한 디자인 구성 ([SML+25] 에서 제공됨) 은 무작위 게이트 레이어와 라우팅 레이어 (SWAP 네트워크) 를 교차 배치하여 격자에 컴파일된다. 이 접근법은 $k$와 $\epsilon$에 대한 스케일링을 개선하기 위해 보조 큐비트를 사용할 수 있게 한다.

주요 기여 및 결과

• 최적 깊이 강력한 $k$-디자인 (정리 1/22):
  저자들은 임의의 상수 차원 $D$에 대해, $D$차원 격자에서 깊이 $d$로 강력한 $\epsilon$-근사 유니터리 $k$-디자인을 구성할 수 있음을 증명한다:
  $$d = O\left(n^{1/D} + k \log^7(k) \log(nk/\epsilon)\right)$$
  이 구성은 보조 큐비트가 필요하지 않다. $n^{1/D}$ 항은 $D$차원에서의 정보 전파에 대한 자연스러운 광원 (lightcone) 하한과 일치하여, $n$에 대한 최적성을 확립한다.

• 최적 깊이 강력한 PRU (정리 2/27):
  LWE(Learning With Errors) 문제의 부분 지수적 난이도를 가정할 때, 저자들은 $D$차원 격자에서 깊이 $d$로 강력한 PRU 를 구성한다:
  $$d = \Theta(n^{1/D})$$
  이 또한 보조 큐비트가 필요하지 않으며, 광원 논증에 의해 제공된 하한과 일치한다.

• 라우팅 기반 준최적 디자인 (정리 4/Corollary 26):
  전체 연결 디자인에 라우팅 프로토콜을 적용함으로써, 저자들은 보조 큐비트의 비용으로 $k$와 $\epsilon$에 대한 개선된 스케일링을 가진 대안적 구성을 제공한다:

  1. $\tilde{O}(nk)$개의 보조 큐비트를 사용하여 깊이 $O((nk)^{1/D} \text{polylog}(n,k) \log \log(1/\epsilon))$.
  2. $\tilde{O}(n)$개의 보조 큐비트를 사용하여 깊이 $O(n^{1/D} k \text{polylog}(n) \log \log(k/\epsilon))$.

• 데카르트 곱으로의 일반화:
  이 기법들은 단순한 격자를 넘어 더 작은 그래프들의 데카르트 곱인 임의의 연결성 그래프로 확장됨이 입증되었다.

의의 및 주장
본 논문은 중간 연결성에서 강력한 디자인의 깊이 스케일링에 관한 미해결 문제를 해결했다고 주장한다. 주요 의의는 $D$차원 격자에서 강력한 디자인과 PRU 가 광원에 의해 부과된 근본적인 물리적 한계와 일치하는 최적의 깊이 스케일링 ($\Theta(n^{1/D})$) 으로 구성될 수 있음을 입증하는 데 있다.

저자들은 라우팅 기반 접근법이 $k$와 $\epsilon$에 대해 더 나은 스케일링을 제공하지만, 직접 구성은 보조 큐비트 없이 $n$에서 최적성을 달성한다는 점에서 중요하다고 지적한다. 이는 단기간 양자 하드웨어에 있어 중요한 제약 조건이다. 이 연구는 이론적 전체 연결 모델과 초전도 큐비트, 실리콘 양자 점과 같은 실제 양자 장치에서 발견되는 기하학적으로 국소적인 아키텍처 사이의 간극을 메운다. 본 논문은 이러한 기법을 육각 격자와 같은 비데카르트 연결성으로 확장하는 것은 여전히 미해결 문제라고 명시적으로 밝히고 있다.