Shallow quantum circuit for generating extremely low-entangled approximate state designs

기술 요약: 극도로 낮은 얽힘을 가진 근사 상태 설계를 생성하기 위한 얕은 양자 회로

문제 정의
무작위 양자 상태는 양자 정보 과학의 근본적인 도구로서, 얽힘, 열화(thermalization), 그리고 카오스적 역학을 이해하는 데 활용됩니다. 또한 이들은 암호학, 장치 벤치마킹, 그리고 섀도 토모그래피(shadow tomography)에서도 중요한 역할을 합니다. 그러나 진정한 하르 무작위 상태(Haar-random states)를 생성하려면 큐비트 수($n$)에 대해 지수적인 깊이의 양자 회로가 필요하며, 이는 근미래의 장치들에는 불가능한 작업입니다. 결과적으로, 분야는 주로 근사 상태 $t$-설계(Haar 분포의 첫 $t$ 모멘트를 모사하는 것) 및 **의사 무작위 상태(pseudorandom states)**에 의존하고 있습니다.

기존의 근사 상태 $t$-설계 구축 방식의 주요 한계는 자원 비용입니다. 층상 무작위 회로나 카오스적 역학에 기반한 대부분의 알려진 방법들은 볼륨 법칙 얽힘(시스템 크기 $n$에 비례하여 선형적으로 스케일링)과 높은 "매직(magic)" 및 결맞음(coherence)을 생성합니다. 최근 의사 무작위 상태에 관한 연구는 낮은 얽힘($\omega(\log n)$)이 가능하다는 것을 보여주었으나, 근사 상태 $t$-설계의 얽힘 특성은 아직 탐구되지 않았습니다. 본 연구에서 다루는 핵심적인 미해결 과제는, 근사 상태 $t$-설계가 시스템 크기에 따라 스케일링되지 않는 극도로 낮은 얽힘, 매직, 그리고 결맞음을 가질 수 있는지, 그리고 만약 그렇다면 보조 큐비트(ancilla qubits) 없이 효율적인 얕은 양자 회로를 통해 구현 가능한지 여부입니다.

방법론
저자들은 특정 매핑이 사용될 경우 $k$-큐비트 상태 설계를 $n$-큐비트 시스템으로 확장하면서도 설계 특성과 얽힘 구조를 보존할 수 있다는 직관을 바탕으로 새로운 구성을 제안합니다.

1. 무작위 단사 사상(Random Injective Maps)을 통한 차원 확장:
   핵심적인 이론적 통찰은 **보조정리 1(Lemma 1)**로, $k$-큐비트 $\epsilon$-근사 상태 $t$-설계( $n-k$개의 0이 포함된 부분 공간에 임베딩됨)에 무작위 유니터리 연산자 $U_p$를 적용하면 $n$-큐비트 $\epsilon'$-근사 상태 $t$-설계가 된다는 점을 확립하는 것입니다. 연산자 $U_p$는 $[2^k]$에서 $[2^n]$으로의 $t$-독립 무작위 단사 사상(t-wise independent random injective map) $p$에 의해 정의됩니다. 결정적으로, $U_p$는 계산 기저(computational basis)에서의 중첩 수를 보존하기 때문에, 결과적으로 생성된 $n$-큐비트 상태의 얽힘, 매직, 결맞음은 전체 크기 $n$이 아니라 부분 시스템 크기 $k$에 의해 결정됩니다.

2. 이론적 하한(Theoretical Lower Bounds):
   저자들은 **정리 2(Theorem 2)**를 통해, $\epsilon$-근사 상태 $t$-설계를 형성하는 모든 앙상블은 최소 $\Omega(\log(t/\epsilon))$의 평균 얽힘, 매질, 결맞음을 가져야 함을 증명합니다. 이는 필요한 자원이 시스템 크기 $n$이 아니라 설계 파라미터인 $t$와 $\epsilon$에 의해 근본적으로 제한됨을 입증합니다.

3. 얕은 회로 구현:
   이 구성을 물리적으로 구현하기 위해, 저자들은 무작위 단사 사상 $U_p$를 얕은 양자 회로로 구현하는 명시적인 알고리즘(알고리즘 1 및 2)을 개발합니다.

   • 메커니즘: 이 회로는 병렬 CNOT 게이트를 사용하여 $k$-큐비트 부분 시스템을 나머지 시스템으로 복사한 다음, 무작위 다중 제어 X (MCX) 게이트를 사용하여 비트를 무작위화합니다.
   • 깊이(Depth): 보조 큐비트가 없는 경우 회로 깊이는 $O(t[\log t]^3 \log n \log(1/\epsilon))$이며, 보조 큐비트가 있는 경우 깊이는 $\tilde{O}(t[\log t]^2 \log n \log(1/\epsilon))$로 개선됩니다.
   • 효율성: 이 깊이는 보조 큐비트 없이 상태 설계를 생성하는 기존의 방법(예: $O(n)$ 깊이가 필요한 국소 무작위 회로)보다 현저히 얕습니다.

4. 섀도 토모그래피에의 적용:
   저자들은 이 구성을 **클래식 섀도 토모그래피(classical shadow tomography)**에 적용합니다. 무작위 유니터리 $U$가 $k$-큐비트 유니터리 3-설계와 얕은 무작위 단사 사상 $U_p$로 구성된 측정 앙상블을 사용하여 섀도 추정기(shadow estimator)를 구축합니다.

   • 핵심 특징: 결과적인 추정기는 오직 두 개의 계산 기저 상태 사이의 중첩만을 포함합니다 ($k=1$인 경우).
   • 이점: 이는 클래식 후처리 비용을 획기적으로 줄여줍니다. 고차 스테빌라이저 랭크(high-stabilizer-rank) 관측량의 평가가 계산적으로 비용이 많이 들 수 있는 무작위 클리포드 회로 기반의 추정기와 달리, 이 방법은 관측량의 특성에 따라 상수 또는 로그 샘플 복잡도를 가지는 효율적인 관측량 평가를 가능하게 합니다.

주요 결과

• 자원 포화(Resource Saturation): 구축된 앙상블은 얽힘, 매직, 결맞음에 대해 이론적 하한인 $\Theta(\log(t/\epsilon))$를 달성합니다. 고정된 $t$와 $\epsilon$에 대해, 이러한 자원은 총 큐비트 수 $n$에 대해 $O(1)$입니다.
• 회로 효율성: 제안된 얕은 회로는 보조 큐비트 없이 상태 설계를 생성하는 가장 효율적인 방법이며, 회로 깊이는 $n$에 대해 선형 또는 다항식이 아닌 로그 스케일링을 따릅니다.
• 상태 인증(State Certification): 저자들은 거의 모든 $n$-큐비트 순수 상태가 $O(1/\epsilon^2)$의 측정과 $O(\log(n/\epsilon))$-깊이의 회로를 사용하여 인증(충실도 추정)될 수 있음을 입증하였으며, 이는 $O(n^2)$ 측정이 필요했던 이전 방법들에 비해 상당한 개선입니다.
• 클래식 섀도 효율성: 새로운 섀도 추정기는 특히 낮은 랭크의 관측량이나 반집중된 고유상태(anti-concentrated eigenstates)를 가진 관측량에 대해 클래식 오버헤드를 줄여 양자 상태를 인증할 수 있게 합니다.

의의 및 주장
본 논문은 자원 비용(얽힘, 매직, 결맞음)을 시스템 크기와 분리함으로써 효율적인 무작위 양자 상태 생성의 새로운 방향을 제시한다고 주장합니다. 저자들은 자신들의 연구가 다음과 같은 성과를 거두었다고 밝힙니다:

1. 미해결 과제 해결: 근사 상태 $t$-설계가 비확장적(non-extensive) 자원을 가질 수 있음을 증명함으로써, 설계 맥락에서 높은 얽힘이 무작위와 유사한 동작을 위해 반드시 필요하다는 가설에 도전하고 이를 해결했습니다.
2. 근미래 응용 가능성 지원: 얕은 깊이와 낮은 얽힘은 이 상태들을 근미래 양자 장치, 특히 전방향 연결성(all-to-all connectivity)을 가진 장치(예: 중성 원자 양자 컴퓨터)에서 구현 가능하게 만듭니다.
3. 클래식 시뮬레이션 개선: 얽힘과 섀도 추정기의 복잡성을 줄임으로써, 이 방법은 양자 실험의 더 효율적인 클래식 시뮬레이션 및 후처리를 위한 경로를 제공하며, 더 적은 샘플과 낮은 계산 비용으로 양자 상태 인증 및 벤치마킹 작업을 용이하게 합니다.

저자들은 낮은 얽힘을 가진 의사 무작위 상태가 존재하지만, 이들이 특정 설계 맥락에서 모든 시스템 크기에 대해 평균 충실도를 정확하게 근사하는 방식에서 근사 상태 설계와는 다르다는 점을 강조하며, 본인들의 구성이 갖는 독특한 유용성을 부각했습니다.