Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

기술 요약: 양자 샘플링에 대한 타이트한 쿼리 하한 및 인증된 무작위성 적용

문제 정의
무작위 회로 샘플링(Random circuit sampling) 실험은 양자 컴퓨팅 우위를 입증하는 주요 방법이며, 일반적으로 선형 교차 엔트로피 벤치마크(XEB)를 사용하여 검증됩니다. XEB 점수는 장치의 출력이 이상적인 분포 $p$와 얼마나 잘 일치하는지를 계산하기 위해 반환된 문자열 $z$에 대한 $N p(z)$의 평균을 측정하며, 여기서 $N=2^n$입니다. 높은 점수는 양자 우위를 시사하지만, 장치가 반드시 $p$로부터 샘플링했거나 그 출력이 무작위임을 본질적으로 보증하지는 않습니다. 장치는 가장 가능성이 높은 문자열을 결정론적으로 출력함으로써 높은 점수를 얻을 수 있으며(이 경우 공격자가 이를 알고 있을 수 있음), 이는 인증된 무작위성을 생성하는 데 실패하게 됩니다.

본 논문은 양자 쿼리 모델에서 두 가지 근본적인 질문을 다룹니다:

1. 점수 한계: 효율적인 양자 장치는 이상적인 점수에 비해 얼마나 높은 점수를 얻을 수 있는가? 즉, 효율적인 장치가 이상적인 점수를 상수만큼 초과할 수 있는가?
2. 무작위성 인증: 만약 장치가 이상적인 점수에 근접한 점수를 달성한다면, 그 출력은 (장치와 얽혀 있고 사후에 오라클(회로 또는 함수)을 학습한 적대자(Eve)에 대해서도) 얼마나 많은 평활 최소 엔트로피(smooth min-entropy, 인증된 무작위성)를 포함하고 있는가?

방법론
저자들은 회로가 알려진 앙상블에서 추출된 오라클로 대체되는 쿼리 모델에서 작업합니다. 저자들은 두 가지 특정 앙상블을 분석합니다:

• 푸리에 샘플링(Fourier Sampling): 오라클은 균일하게 무작위인 함수 $f: \{0,1\}^n \to \{\pm 1\}$입니다. 정직한 샘플러(honest sampler)는 약 3의 점수를 기록합니다.
• 하르-무작위 상태(Haar-Random States): 오라클은 (정준 상태 준비 오라클 또는 하르-무작위 유니터리 접근을 통해 접근 가능한) 균일하게 무작위인 단위 벡터 $|\phi\rangle$를 숨깁니다. 정직한 샘플러는 약 2의 점수를 기록합니다.

핵심 방법론은 장치의 상태가 "정직한" 상태(단일 쿼리를 수행하는 상태)로부터 벗어난 정도를 정량화하는 진전 척도(progress measure) $\lambda$를 정의하는 것입니다. 분석은 다음의 3단계 프레임워크를 따릅니다:

1. 점수 경계: 기대 점수 $B(A)$는 진전 척도에 의해 제한됩니다: $B(A) \leq \text{Ideal Score} + O(\lambda + \lambda^2)$.
2. 성장 경계: 각 쿼리가 $\lambda$를 $O(\sqrt{(t+1)/N})$만큼만 증가시킨다는 것을 보여줍니다(여기서 $t$는 이전 쿼리 횟수). 결과적으로, $q$번의 쿼리 후 $\lambda = O(q^{3/2}/\sqrt{N})$가 됩니다.
3. 무작위성 추출: 점수가 이상적인 점수에 근접한(작은 결핍 $\delta$를 가진) 장치의 경우, 점수 경계에 대한 증명을 정교화하여 장치의 출력 브랜치가 특정 보조 벡터들과 가깝다는 것을 보여줍니다. 이 벡터들은 장치에만 작용하는 연산자에 의해 생성되며, 그 노름(norm)은 $\text{poly}(q)\sqrt{p(z)}$에 의해 제한됩니다. 이러한 구조는 Eve가 오라클을 알더라도 출력을 추측하는 능력이 제한됨을 의미합니다.

주요 기여 및 결과

1. 이상적 점수를 초과하기 위한 타이트한 하한
본 논문은 효율적인 양자 장치에 대해 이상적인 점수가 "치렐슨슨 경계(Tsirelson bound)" 역할을 한다는 것을 확립합니다.

• 쿼리 복잡도: 이상적인 점수를 상수 $\epsilon$만큼 초과하기 위해, 양자 알고리즘은 $\Omega(N^{1/3})$의 쿼리가 필요합니다.
  • 푸리에 샘플링의 경우, 기대 점수 $3 + \epsilon$을 얻으려면 $q \geq \Omega(N^{1/3})$가 필요합니다.
  • 하르-무작위 상태의 경우, 기대 점수 $2 + \epsilon$을 얻으려면 $q \geq \Omega(N^{1/3})$가 필요합니다.
• 상한: 저자들은 "스퀘어링 알고리즘(squaring algorithm, 충돌 찾기 알고리즘의 변형)"을 사용하여 이상적인 점수를 상수만큼 초과하는 데 $O(N^{1/3})$ 쿼리가 충분함을 확인했습니다. 이 알고리즘은 $m \approx N^{1/3}$개의 이상적인 샘플을 저장하고 진폭 증폭(amplitude amplification)을 사용하여 출력을 이상적인 분포의 제곱인 $p(z)^2$ 쪽으로 편향시킵니다.
• 타이트함(Tightness): 이러한 경계는 타이트합니다. 정직한 샘플러(1 쿼리)와 이상적인 점수를 유의미하게 초과할 수 있는 능력 사이의 간극은 정확히 $N^{1/3}$ 임계값에 의해 특징지어집니다.

2. 이상적 점수에서의 인증된 무작위성
본 논문은 다항식 개의 쿼리를 수행하고 점수가 이상적인 점수와 $o(1)$ 차이 내에 있는 장치가 거의 최대의 무작위성을 가진 출력을 생성함을 증명합니다.

• 최소 엔트로피: 푸리에 샘플링과 하르-무작위 상태(정준 오라클을 통한) 모두에 대해, 출력 $Z$는 평활 최소 엔트로피 $H_{\min}^\eta(Z | RE) \geq n - O(\log n)$를 가집니다 (여기서 $R$은 오라클, $E$는 Eve의 레지스터입니다).
• 적대적 모델: 이는 Eve가 장치와 얽혀 있고 장치가 $Z$를 출력한 후 오라클의 전체 기술(함수 $f$ 또는 벡터 $\phi$)을 학습하더라도 성립합니다.
• 매개변수: 평활 매개변수 $\eta$는 $O(\sqrt{\delta} + q^{3/4}N^{-1/4})$로 스케일링됩니다. 결핍 $\delta$가 무시할 만하고 $q$가 $n$에 대한 다항식인 경우, 평활화는 무시할 수 있는 수준이며 $n - O(\log n)$ 비트의 무작위성을 인증합니다.
• 최적성: $O(\log n)$ 손실은 거의 최적임이 밝혀졌습니다. 저자들은 이상적인 점수에 근접한 점수를 달성하면서도 출력을 크기가 $N/q^2$인 알려진 집합으로 제한하여, 최소 엔트로피를 $n - 2\log q$로 제한하는 장치를 진폭 증폭을 사용하여 구성합니다.

3. 추가 결과

• 충돌 분포(Collision Distribution): 본 논문은 충돌 분포($p(z)^2$에 비례)를 샘플링하는 쿼리 복잡도가 $\Theta(N^{1/3})$임을 보여줍니다.
• 양자 헤더 곱(Quantum Hadamard Products): 두 상태의 양자 헤더 곱을 준비하기 위한 코히런트 버전의 스퀘어링 알고리즘이 제시됩니다. 이 알고리즘은 균일한 진폭 크기를 가진 두 상태의 양자 헤더 곱을 준비하며, 표준 진폭 증폭에 필요한 $\sqrt{N}$ 쿼리보다 개선된 $O(N^{1/3})$ 쿼리를 사용하여 트레이스 거리(trace distance) 오차 $O(N^{-1/6})$를 달성합니다.

의의 및 주장
본 논문은 양자 샘플링 작업에 대해 무조건적인 정보 이론적 보장을 제공하며, "양자 우위 치렐슨슨 부등식(quantum supremacy Tsirelson inequality)"에 대한 열린 질문을 해결한다고 주장합니다.

• CHSH와의 유사성: 이 결과는 CHSH 게임과 직접적인 평행 구조를 가집니다. 치렐슨슨의 경계($\cos^2(\pi/8)$)가 양자 전략의 승률을 제한하고 그 경계에서 무작위성을 인증하는 것과 마찬가지로, 이상적인 XEB 점수는 효율적인 양자 샘플러의 성능을 제한하고 점수가 이상적 점수에 근접할 때 무작위성을 인증합니다.
• 무조건적 보안: 계산적 어려움에 대한 가정이나 적대자의 지식(예: 전체 오라클을 배우지 못함)에 의존했던 이전의 결과들과 달리, 본 연구는 오라클을 학습하고 임의의 얽힘을 보유한 강력한 적대자에 대해서도 무조건적인 경계를 제공합니다.
• 한계: 저자들은 자신들의 결과가 오라클 모델에 적용된다는 점을 언급합니다. 실제 환경의 장치들(예: [AAB+19])의 경우, 현재 점수는 이상적인 값(예: 2)에서 상당히 떨어져 있습니다(예: 1.002). 따라서 실험적 설정에서 인증된 무작위성에 대한 현재의 보증은 다른 더 약한 가정(예: [AH23])에 의존하고 있습니다. 또한, 하르-무작위 상태의 경우, 결과는 전체 유니터리 접근이 아닌 정준 상태 준비 오라클을 필요로 합니다. 이는 적대자가 전체 하르-무작위 유니터리를 학습할 경우 출력과 유니터리의 열(column) 사이의 상관관계를 파악할 수 있기 때문입니다.

요약하자면, 본 논문은 효율적인 양자 샘플링의 한계를 엄격하게 정의하며, 이상적인 점수가 효율적인 장치에 대한 어려운 장벽임을 입증하는 동시에, 이 장벽에 접근하는 것이 강력한 양자 적대자에 대해서도 거의 모든 가능한 무작위성을 인증한다는 것을 증명합니다.