Classically Spoofing System Linear Cross Entropy Score Benchmarking

기술 요약: 서브리니어 깊이 회로에 대한 클래식 스푸핑 시스템 선형 교차 엔트로피 점수 벤치마킹

문제 정의
최근의 "양자 우위(quantum supremacy)" 주장은 주로 양자 장치가 클래식 컴퓨터로는 다루기 힘든 작업(예: 무작위 회로 샘플링)을 수행하는지 검증하기 위해 선형 교차 엔트로피 벤치마킹(Linear XEB) 지표에 의존해 왔습니다. 선형 XEB를 클래식하게 스푸핑하는 것의 이론적 난도는 교차 엔트로피 양자 임계값(XQUATH) 가설에 근거합니다. 그러나 최근 연구는 서브리니어 깊이(sublinear-depth) 회로에 대해 XQUATH가 성립하지 않음을 입증하였으며, 이는 무작위 샘플링(RCS)의 견고한 벤치마크로서 선형 XEB의 신뢰성을 약화시켰습니다.

이에 대응하여, 최소 양자 특이값 변환(mQSVT) 회로를 사용하는 양자 해밀토니안 시뮬레이션 실험을 위한 변형된 벤치마크인 시스템 선형 교차 엔트로피 점수(sXES)가 제안되었습니다. 표준 무작위 회로 샘플링(RCS)과 달리, mQSVT 회로는 동일한 유니터리 $U$와 그 켤레 복소수 $U^\dagger$의 여러 복사본을 포함하는 독특한 구조를 가집니다. 이러한 구조적 차이는 시스템 선형 교차 엔트로피 양자 임계값 가정(sXQUATH)을 이끌어냈으며, 이는 어떤 다항 시간 클래식 알고리즘도 mQSVT 회로의 출력 확률을 자명한 균등 근사(uniform approximation)보다 유의미하게 낮은 평균 제곱 오차(MSE)로 근사할 수 없다는 가설을 담고 있습니다. sXQUATH와 XQUATH 사이의 공식적인 관계는 이전에는 불분명했으며, 기존의 스푸핑 기법들이 sXQUATH를 반박하기 위해 적응될 수 있는지에 대한 의문을 남겨두었습니다.

방법론
저자들은 mQSVT 회로의 출력 확률 분포에 대한 효율적인 클래식 근사를 구축하기 위해 파울리 경로(Pauli path) 알고리즘을 사용합니다. 이 접근 방식의 핵심은 모든 레이어에서 정규화된 파울리 행렬을 사용하여 회로의 밀도 행렬을 전개하는 것입니다.

주요 기술 단계는 다음과 같습니다:

1. 파울리 경로 전개: 출력 확률 $p(U, x)$는 파울리 경로 $s$에 대응하는 푸리에 계수의 합으로 표현됩니다. $d$개의 블록을 가진 mQSVＴ 회로의 경우, 파울리 경로는 $U$와 $U^\dagger$를 통과하는 하위 경로들의 시퀀스입니다.
2. 직교성 문제 극복: 표준 RCS에서 "직교성 성질"은 서로 다른 경로들에 대한 푸리에 계수의 곱의 기댓값이 0임을 보장합니다. mQSVT 회로에서는 동일한 무작위 유니터리 $U$가 여러 번 등장하기 때문에(구체적으로 $d$ 블록 회로에서 $2d$번) 이 성질이 실패합니다. 결과적으로, 분석에는 이전의 RCS 스푸핑 결과에서 사용된 2차 모멘트가 아닌, 하이어 차수의 모멘트(구체적으로 4차 모멘트)의 활용이 필요합니다.
3. 바인가텐 계산법(Weingarten Calculus): 동일한 유니터리의 여러 복사본을 포함하는 곱의 기댓값을 평가하기 위해, 저자들은 바인가텐 계산법을 활용합니다. 이를 통해 하어 무작위(Haar-random) 유니터리 모멘트를 바인가텐 함수와 치환 연산자로 표현할 수 있습니다.
4. 특정 경로 구축: 저자들은 첫 번째 레이어에서 첫 번째 큐비트와 그에 결합된 파트너에 비항등 파울리($Z \otimes Z$)로 시작하여, 이후 레이어에서는 항등 파울리를 따르는 효율적으로 계산 가능한 특정 파울리 경로 $r$을 정의합니다. 이들은 클래식 근사 $q(U, x) = 2^{-n} + F(U, r, x)$를 구축하며, 여기서 $F(U, r, x)$는 경로 $r$에 대한 푸리에 계수입니다.

주요 기여 및 결과
본 논문은 sXQUATH의 실패와 sXES의 스푸핑 가능성을 입증하는 두 가지 주요 정리를 제시합니다.

1. sXQUATH의 반박 (정리 1): 저자들은 서브리니어 깊이($d_U = o(n)$)를 가진 단일 블록($d=1$) mQSVT 회로에 대해, 구축된 클래식 알고리즘 $q(U, x)$가 자명한 근사($2^{-n}$)보다 유의미하게 낮은 평균 제곱 오차(MSE)를 달성함을 증证明합니다. 구체적으로, $sXQ$(자명한 근사와 제안된 알고리즘 간의 MSE 차이)가 $\Omega(2^{-3n})$으로 스케일링됨을 보여줍니다. 이는 클래식 알고리즘이 가설이 허용하는 것보다 더 잘 출력 확률을 근사할 수 있음을 입증함으로써 sXQUATH 가설을 직접적으로 반박합니다.

2. sXES 벤치마크 스푸핑 (정리 2): 저자들은 동일한 알고리즘이 노이즈가 있는 mQSVT 회로에 대한 sXES 벤치마크를 스푸핑할 수 있음을 보여줍니다. 특정 임계값 이상의 데폴라라이징 노이즈(depolarizing noise)에 의해 오염된 회로에 대해, 클래식 알고리즘이 노이즈가 있는 양자 회로와 유사한 sXES 점수를 생성함을 입증합니다. 스푸핑된 sXES는 $2^{-n}(\sum_{x \neq 0^n} \mathbb{E}_U[p(U, x)] + c d_U)$로 제한되며, 이는 해당 영역에서 벤치마크가 노이즈가 있는 양자 실험과 클래식 시뮬레이션을 구분할 수 없음을 나타냅니다.

의의
본 논문은 RCS에서의 선형 XEB 스푸핑에 관한 Aharonov 등의 연구(2023)를 확장하는 결과를 제시한다고 주장합니다. sXES 역시 파울리 경로 알고리즘을 통한 효율적인 클래식 스푸핑에 취약하다는 것을 보여줌으로써, 저자들은 다음과 같이 결론짓습니다:

• sXES의 복잡도 이론적 기초(sXQUATH)는 특히 서브리니어 깊이 회로에서 취약합니다.
• mQSVT 회로의 구조적 차이가 현재의 최첨단 클래식 시뮬레이션 기법으로부터 충분한 보호를 제공하지 못합니다.
• RCS 또는 해밀토니안 시뮬레이션에 기반한 미래의 양자 우위 주장에는, 파울리 경로 알고리즘 및 유사한 방법들에 의한 스푸핑을 배제할 수 있는 더 강력한 복잡도 이론적 보증을 갖춘 새로운 벤치마킹 작업이 필요합니다.

이 연구는 새로운 실험 프로토콜이나 향후 응용 분야를 제안하는 것이 아니라, 이론적인 경고를 전달하는 역할을 하며, 양자 이점(quantum advantage)을 입증하려는 노력에 있어 더욱 견고한 검증 방법의 필요성을 강조합니다.