양자 컴퓨터를 위한 초고속 도서관을 구축한다고 상상해 보세요. 이 도서관에서는 고유한 주소(예: 전화번호나 화학식)를 기반으로 특정 정보 조각을 찾아야 합니다. 양자 세계에서는 이를 QROM(Quantum Read-Only Memory, 양자 읽기 전용 메모리)이라고 부릅니다. 이는 거의 모든 양자 알고리즘의 '주력'으로, 데이터 로딩이라는 중책을 수행합니다.

그러나 지난 7 년 동안 이 도서관을 구축하는 데는 'Toffoli 게이트'라는 측면에서 엄청난 비용이 들었습니다. Toffoli 게이트를 도서관을 짓기 위해 필요한 복잡하고 에너지를 많이 소모하는 벽돌로 생각하세요. 필요한 벽돌이 많을수록 컴퓨터를 실행하는 것이 더 어렵고 비싸집니다.

여기서 Xanadu 의 Danial Motlagh 와 Matthew Pocrnic 저자들은 이 도서관을 구축하는 비용을 절반으로 줄이는 방법을 찾아냈습니다.

구식 방법: "스왑" 춤

이전에는 이 데이터를 로드하는 가장 효율적인 방법 (약간 지저분할 수 있는 빌린 도구와 같은 '더러운' 큐비트를 사용하는 경우) 은 SelectSwap이라는 과정을 포함했습니다.

100 개의 잠긴 상자 (데이터) 가 줄지어 있고, 하나의 깨끗하고 빈 상자 (출력) 가 있다고 상상해 보세요. 어떤 상자를 열어야 하는지 알려주는 마법 열쇠 (주소) 가 있습니다.

구식 방법: 올바른 항목을 깨끗한 상자에 넣기 위해서는 다음을 수행해야 했습니다:
1. 지저분한 상자와 깨끗한 상자를 서로 바꾸기.
2. 항목 복사.
3. 지저분한 상자를 원래 위치로 다시 바꾸기.
4. 모든 항목에 대해 이 춤을 반복하기.

이 "스왑 춤"은 매우 효율적이었지만, 로드하려는 항목 하나당 여전히 두 개의 복잡한 움직임 (벽돌) 이 필요했습니다.

첫 번째 돌파구: "복사" 단축키

저자들은 "스왑 춤"이 불필요하다는 것을 깨달았습니다. 상자를 오가며 서로 바꾸는 대신, 항목을 직접 복사할 수 있습니다.

새로운 방법: 그들은 "SelectSwap"을 "SelectCopy" 기법으로 대체했습니다.
- 지저분한 상자와 깨끗한 상자를 서로 바꾸는 대신, 주소에 따라 지저분한 상자의 내용을 깨끗한 상자로 직접 복사했습니다.
- 결과: 이로써 복사 과정에 필요한 복잡한 벽돌의 수가 즉시 절반으로 줄었습니다. 방을 청소하기 위해 가구를 옮길 필요가 없다는 것을 깨닫고 표면을 직접 닦는 것과 같습니다.

두 번째 돌파구: "패킷" 전략

첫 번째 수정이 훌륭했지만, 저자들은 특히 "지저분한" 빌린 도구 (더러운 큐비트) 의 공급이 많지 않을 때 더 나은 결과를 얻을 수 있는 방법을 발견했습니다.

1,000 개의 패키지를 실은 거대한 트럭을 싣는다고 상상해 보세요.

구식 방법: 하나씩 또는 작은 그룹으로 적재하여 많은 왕복 이동이 필요했습니다.
새로운 전략: 그들은 데이터를 일련의 작은 패킷으로 처리할 수 있음을 깨달았습니다. 1,000 개 항목 목록 전체를 한 번에 적재하는 대신, 더 작은 덩어리 (예: 한 번에 10 개) 로 나누어 순차적으로 적재했습니다.

이를 통해 그들은 필요한 "복잡한 벽돌"의 수학을 변경했습니다.

이전에는 항목당 약 2 개의 벽돌이 필요했습니다.
이 새로운 "패킷" 전략을 사용하면 항목당 약 1 개의 벽돌로 비용이 줄어듭니다 (구체적으로는 $1 + 1/b$ 개의 벽돌이며, 여기서 $b$ 는 데이터 크기입니다).

큰 그림: 비용 절감

"SelectCopy" 단축키와 "패킷" 전략을 결합함으로써 저자들은 다음과 같은 엄청난 개선을 이루었습니다:

비용 절감: 실용적인 시나리오에서 데이터를 로드하는 데 필요한 비싼 "벽돌"(Toffoli 게이트) 의 수가 약 50% 감소했습니다.
최고 성능 달성: 그들은 "더러운"(지저분한) 큐비트가 이전에는 두 배의 자원을 사용하지 않고는 불가능하다고 생각되었던 "깨끗한"(완벽한) 큐비트만큼 잘 수행되도록 만들었습니다.

왜 이것이 중요한가

양자 컴퓨팅 세계에서는 모든 "벽돌"(Toffoli 게이트) 이 중요합니다. 이러한 게이트는 시스템에서 가장 어렵고 오류가 발생하기 쉬운 부분입니다. 데이터를 로드하는 데 필요한 벽돌 수를 절반으로 줄임으로써, 이 새로운 방법은 양자 알고리즘을 훨씬 더 효율적으로 만들고 실제 양자 컴퓨터에서 실행하기 쉽게 만듭니다.

저자들은 새로운 유형의 컴퓨터를 발명한 것이 아니라, 데이터 로딩을 조직하는 훨씬 더 지능적인 방법을 찾아내어 어색하고 비싼 과정을 간소화되고 효율적인 것으로 바꾸었을 뿐입니다.

기술 요약: QROM 비용 절감

문제 정의

양자 판독 전용 메모리 (QROM) 는 결함 허용 양자 알고리즘의 기본 서브루틴으로, 고전 데이터를 중첩 상태로 일관성 있게 로드하는 기능을 제공합니다. 이는 해밀토니안 시뮬레이션, 상태 준비, 유니터리 합성, 그리고 미분 및 선형 방정식에 대한 양수 솔버와 같은 응용 분야에서 알고리즘 오버헤드의 주요 원인입니다.

QROM 의 핵심 작업은 다음 변환을 구현하는 것입니다:
$\sum_{x=0}^{N-1} \psi_x |x\rangle|0\rangle \to \sum_{x=0}^{N-1} \psi_x |x\rangle|f(x)\rangle$
여기서 $N$ 은 데이터 항목의 수, $b$ 는 각 항목의 비트 길이, 그리고 $f(x)$ 는 사전 계산된 고전 함수입니다.

역사적으로 QROM 의 비-클리포드 비용 (특히 Toffoli 게이트 수) 은 병목 현상이었습니다. 1 차 반복을 사용한 초기 방법들은 비용을 $N$ 까지 줄였으나, 보조 큐비트를 활용한 "SelectSwap" 기법의 도입으로 추가적인 최적화가 가능해졌습니다. 본 연구 이전의 최첨단 기술인 Berry 등 연구팀의 방법은 $b(\lambda-1)$ 개의 "더티 (불순)" 보조 큐비트를 사용하여 다음과 같은 Toffoli 비용을 달성했습니다:
$2\frac{N}{\lambda} + 4b(\lambda-1)$
여기서 $\lambda$ 는 보조 큐비트 수와 Toffoli 수 사이의 트레이드오프를 결정하는 매개변수입니다. 이 구조는 더티 보조 큐비트의 사용으로 인해 지배적인 $N/\lambda$ 항에 2 배의 곱셈 인자가 부과되었으며, 이는 7 년 이상 지속된 한계였습니다.

방법론

저자들은 실용적인 영역에서 구현 비용을 효과적으로 절반으로 줄이는 새로운 QROM 구조를 제안합니다. 방법론은 두 가지 주요 단계로 진행됩니다:

1. SelectSwap 에서 SelectCopy 로

첫 번째 최적화는 "SelectSwap" 아키텍처를 "SelectCopy" 아키텍처로 대체합니다.

기존 접근법 (SelectSwap): 더티 보조 큐비트를 사용하여 데이터를 로드할 때, 알고리즘은 주소 상태 $|r\rangle$ 에 기반하여 $r$ 번째 더티 레지스터와 0 번째 레지스터를 스왑하고, 0 번째 레지스터를 클린 레지스터로 복사한 후 다시 스왑합니다. 이 시퀀스는 여러 개의 멀티플렉스된 스왑과 CNOT 게이트를 필요로 합니다.
새로운 접근법 (SelectCopy): 저자들은 스왑, 복사, 다시 스왑하는 시퀀스가 수학적으로 $|r\rangle$ $∣ r ⟩$ 에 기반하여 $r$ $r$ 번째 레지스터를 클린 레지스터로 직접 멀티플렉스 복사하는 것과 동등하다는 점을 발견했습니다.
- 이 직접 복사 연산은 스왑 기반 접근법과 비교하여 멀티플렉스 연산의 Toffoli 비용을 절반으로 줄입니다.
- 또한, 로드 전략을 수정하여 $f(q, 0)$ 을 직접 클린 레지스터에 로드하고 $f(q, r) \oplus f(q, 0)$ 을 더티 레지스터에 로드 ( $r > 0$ ) 함으로써, 저자들은 더티 보조 큐비트 요구량을 $b\lambda$ 에서 $b(\lambda-1)$ 로 줄이면서 상수 항을 추가로 정제했습니다.
- 결과 비용: $2\frac{N}{\lambda} + 2b(\lambda-1) + 2\lambda - 6$ .

2. 순차적 비트 패킷 (매개변수 최적화)

두 번째 최적화는 $N/\lambda$ 항이 지배적인 큐비트 제약 영역을 다룹니다. 저자들은 단일 $b$ -비트 QROM 을 $b/\alpha$ 비트씩 로드하는 $\alpha$ 개의 순차적 QROM 으로 취급하는 방법을 도입했습니다.

순차적 언로딩: $m$ 개의 QROM 적용을 체이닝함으로써, $j$ 번째 적용의 언로드 단계를 $(j+1)$ 번째 적용의 로드 단계와 결합할 수 있습니다. 이는 전체 로드/언로드 사이클의 수를 줄입니다.
비용 절감: $m$ 개의 순차적 QROM 의 경우, $N/\lambda$ 항의 선행 인자는 $2m$ 가 아닌 $(m+1)$ 이 됩니다.
단일 QROM 에의 적용: 저자들은 $b$ -비트 QROM 을 크기 $b/\alpha$ 인 $\alpha$ 개의 순차적 QROM 으로 취급합니다. 이를 통해 "SelectCopy" 깊이는 $\lambda$ 에서 $\alpha\lambda$ 로 증가할 수 있습니다.
매개변수 계열: 이는 조정 가능한 매개변수 $\alpha$ 에 의존하는 비용 함수를 산출합니다:
$\left(1 + \frac{1}{\alpha}\right)\frac{N}{\lambda} + \left(b + \frac{b}{\alpha}\right)(\alpha\lambda - 1) + (\alpha + 1)(\alpha\lambda - 3)$
$\alpha$ 를 1 에서 $b$ 까지 변화시킴으로써, 지배적인 $N/\lambda$ 항의 선행 인자는 2 에서 $(1 + 1/b)$ 까지 보간될 수 있습니다.

주요 결과

최적 영역: $N \gg b^2\lambda^2$ 이고 사용 가능한 더티 큐비트 수가 제한된 극한에서, $\alpha = b$ (한 번에 한 비트씩 순차적으로 로드) 로 설정하는 것이 최적입니다.
비용 절감: 이러한 조건 하에서 총 Toffoli 비용은 대략 다음과 같이 감소합니다:
$\left(1 + \frac{1}{b}\right)\frac{N}{\lambda}$
성능 향상: 이는 이전 최첨단 기술 ( $2N/\lambda$ ) 에 비해 약 50% 의 비용 절감을 의미합니다.
클린 큐비트 동등성: 이 더티 큐비트 구조의 성능은 실용적인 $b$ 값에 대해 클린 큐비트 QROM(일반적으로 선행 인자 1 을 달성함) 과 효과적으로 일치합니다.
일반화: 이 논문은 특정 큐비트 가용성과 문제 크기 제약에 따라 표준 SelectCopy 방법의 비용과 완전한 순차적 방법의 비용 사이를 보간할 수 있는 매개변수 계열의 방법들을 제공합니다.

중요성과 주장

이 논문은 5 년 반 이상 QROM 서브루틴에 이루어진 첫 번째 주요 개선 사항을 제공한다고 주장합니다. 그 중요성은 다음과 같습니다:

오버헤드 감소: QROM 은 대부분의 실용적 양자 응용 분야 (예: 화학, 선형 시스템) 에서 알고리즘 오버헤드의 대부분을 차지하므로, 그 비용을 절반으로 줄이는 것은 전 분야에 걸쳐 상당한 자원 절감으로 직접 이어집니다.
실용성: 이러한 개선 사항은 "더티" 보조 큐비트를 사용하여 달성되었으며, 이는 "클린 (순수)" 보조 큐비트보다 결함 허용 아키텍처에서 구현하기가 더 쉽습니다. 또한 일반적으로 클린 큐비트와 관련된 효율성 향상을 희생하지 않습니다.
유연성: 솔루션의 매개변수적 특성으로 인해 알고리즘 설계자는 매개변수 $\alpha$ 를 조정하여 특정 하드웨어 제약 (큐비트 예산 대 게이트 깊이) 에 대해 최적화할 수 있습니다.

저자들은 현재 구조가 매개변수가 2 의 거듭제곱이라고 가정하지만, 향후 연구는 $2^k$ 제약에 맞지 않는 경우 사용 가능한 더티 큐비트 예산을 완전히 활용하기 위해 정수 나눗셈 기법을 통합할 수 있으며, 이는 특정 영역에서 추가적인 감소를 제공할 수 있다고 언급합니다. 제안된 구조는 PennyLane 라이브러리에 구현되었습니다.

Halving the cost of QROM