Algebraic Reduction to Improve an Optimally Bounded Quantum State Preparation Algorithm

기술 요약: 최적의 경계가 설정된 양자 상태 준비 알고리즘의 대수적 축소를 통한 개선

문제 정의
양자 상태 준비(QSP)는 선형 시스템 솔버, 해밀토니안 시뮬레이션, 양자 화학, 머신러닝을 포함한 수많은 양자 알고리즘에 필수적인 기본 서브루틴이다. 주요 과제는 원하는 타겟 상태 $|\psi\rangle = \sum c_i |i\rangle$로 초기 상태 $|0\rangle^{\otimes n}$을 매핑하는 유니터리 연산자 $U$의 회로 복잡도(깊이, 게이트 수, CNOT 수)를 최소화하는 것이다. Sun 등이 제안한 알고리즘(SUN)은 (보조 큐비트를 사용하여 깊이를 줄이는) 점근적 시공간 트레이드오프(space-time trade-off) 측면에서 최적으로 경계가 설정되어 있는 것으로 알려져 있으나, 그 구현은 각 균일 제어 게이트(Uniformly Controlled Gate, UCG)에 대해 세 개의 $\Lambda$-유형 연산자를 사용하는 분해 과정을 포함한다. 본 논문은 특히 보조 큐비트의 수 $m$이 $2^n \leq m \leq 2^n/n$을 만족하는 파라메트릭 범위에서, SUN 알고리즘의 회로 깊이와 게이트 수를 더 효율적인 대수적 분해를 통해 줄일 수 있는 기회를 다룬다.

방법론
저자들은 유니터리 연산자의 더 단순한 대수적 분해를 도입하는 새로운 QSP 알고리즘인 OSUN을 제안한다. 핵심적인 방법론적 변화는 원하는 상태의 준비를 두 개의 별개 유니터리 블록으로 분리하는 것이다:

1. 실수부 ($U_{mod}$): 타겟 상태 계수의 실수 절대값(진폭)을 준비하는 유니터리.
2. 복소부 ($D_{ph}$): 필요한 복소 위상을 적용하는 대각 유니터리.

전통적인 SUN 프레임워크에서는 사다리 구조 내의 각 UCG가 세 개의 $\Lambda$-유형 연산자(실수 및 복소 성분에 대한 대각 위상 이동을 각각 처리)로 분해된다. 제안된 OSUN 알고리즘은 $U_{mod}$가 오직 실수 진폭의 준비만을 필요로 한다는 점을 활용한다. 이 블록의 UCG를 $R_y$-블록 대각 행렬로 제한하고 특정 게이트 집합 변경($R_y(\gamma) \equiv SH \cdot R_z(\gamma) \cdot HS^\dagger$)을 활용함으로써, 저자들은 각 $U_{mod}$ 내의 UCG가 세 개의 $\Lambda$-유형 연산자 대신 단 하나의 $\Lambda$-유형 연산자로 구현될 수 있음을 입증한다. 복소 위상 정보는 이후 단일한 최대 차원 $\Lambda$ 연산자를 통해 회로의 마지막 단계에서 적용된다.

이 분해는 이전 SUN 구현에서 확립된 5단계 푸리에 공간 합산 방식을 사용하면서도, 보조 레지스터에 대한 연산을 병렬화할 수 있게 하며, 동시에 각 레벨당 $\Lambda$ 생성자의 수를 줄여준다.

주요 기여
본 논문은 다음과 같은 여섯 가지 구체적인 기여를 기술한다:

1. SUN의 최적화: Sun 등의 [40, 정리 1]에서 정의된 최적의 시공간 트레이드오프의 첫 번째 범위 전체에서 depth와 게이트 수를 개선하는 새로운 QSP 알고리즘.
2. 대수적 분해: 실수부와 복소부를 분리함으로써 각 UCG가 단일 $\Lambda$-유형 생성자로 구현될 수 있음을 보여주는 유도 과정, 이를 통해 게이트 레벨당 개수를 3개에서 1개로 감소시킴.
3. 더 정밀한 점근적 경계: 지정된 파라메트릭 범위 내에서 시공간 트레이드오프에 대한 더 정밀한 점근적 최적 경계에 대한 공식적 분석.
4. 구현: GitHub에 공개된 PennyLane 라이브러리를 이용한 OSUN 알고리즘의 전체 구현.
5. 광범한 검증: 밀집 및 희소 상태, 무작위 계수(실수 양수, 실수 음수, 복소수), 그리고 물리적으로 유의미한 상태(Bell, GHZ, W, Dicke)를 포함하여 최대 10개의 큐비트에 대해 University of Parma의 HPC 시스템에서 실행된 종합적인 테스트 배터리.
6. 비교 분석: Möttönen 등의 알고리즘(보조 큐비트가 없는 표준 QSP) 및 원본 SUN 구현과 직접적인 성능 비교를 수행하여 depth, 총 게이트 수, CNOT 수 및 게이트 유형을 평가함.

결과
시뮬레이션 결과는 OSUN 알고리즘이 원본 SUN 구현에 비해 회로 깊이를 체계적으로 감소시킨다는 것을 보여준다.

• 복잡도 분석: 이론적 분석은 점근적 복잡도 클래스는 여전히 $O(n^2 + 2^n/m)$을 유지하지만, 지배적인 항들의 계수(prefactor)가 크게 감소함을 확인시켜 준다. 구체적으로, 선형-로그 항($n \log m$)은 3배의 개선을 보이며, 지수 항($2^n/m$)은 2배의 개선을 보인다.
• 시뮬레이션 지표: 복소 계수를 가진 무작위 상태에 대해, OSUN은 6개 큐비트부터부터 원본 SUN 및 Möttönen의 알고리즘보다 얕은 깊이를 보여준다. 깊이의 성장 곡선은 원본 버전보다 더 매끄럽다.
• 게이트 수: OSUN은 깊이를 줄이지만, 총 게이트 수와 CNOT 수는 Möttönen의 알고리즘에 비해 감소를 보이지 않는다. 그러나 저자들은 게이트 집합 구성의 변화를 언급한다. Möttönen의 방식은 CNOT와 회전을 사용하지만, OSUN은 CNO T와 위상 이동(대각 연산자)을 활용한다.
• 충실도(Fidelity): 알고리즘은 테스트된 모든 상태 유형과 큐비트 수(2~10)에 대해 높은 충실도(1에 근접)와 낮은 트레이스 거리(trace distance)를 유지한다.

의의 및 주장
본 논문은 제안된 대수적 축소가 근본적인 점근적 복잡도 클래스를 변경하지 않으면서도 최첨단인 SUN 알고리즘에 대한 실질적인 개선을 제공한다고 주장한다. 깊이와 게이트 수의 상수 계수를 줄임으로써, OSUN은 보조 큐비트가 가용한 영역($m \geq 2^n$)에서 상태 준비를 위한 더 효율적인 회로를 제공한다. 저자들은 이 최적화가 최적 트레이드오프의 전체 첫 번째 파라메트릭 범위에 적용됨을 명시한다. 또한, 향후 연구를 통해 보조 레지스터가 지수적으로 증가하는 다른 도메인의 지점들로 이러한 이점을 확장할 수 있을 것이라고 제안한다. 결론적으로, OSUN이 깊이를 개선하기는 하지만, 실제 하드웨어에서의 큐비트 연결성 문제와 결함 허용(fault-tolerant) 맥락에서 이 회로들을 Clifford+T 게이트 집합으로 변환하는 작업에 대한 향후 조사가 필요함을 밝힌다. 본 연구는 일반적인 QSP 문제를 모든 하드웨어 제약 조건에 대해 해결한다고 주장하는 것이 아니라, 기존의 보조 큐비트 전략을 사용하는 SUN 프레임워크에 대한 구체적이고 검증된 개선책을 제시하는 것이다.