🔢 mathematics

Frozen-Tree Sampling Refutes Quantum Advantage of Random Circuit Sampling

이 논문은 선형 시간 내에 통계적으로 구별 불가능한 샘플을 생성하는 효율적인 클래식 "프로즌 트리(frozen-tree)" 알고리즘을 제안함으로써 무작위 회로 샘플링에서의 양자 우위 전제를 반박하며, 진정한 계산적 난해함은 밑바탕이 되는 디리클레 분포로부터 샘플링하는 것이 아니라 특정 회로 실현을 식별하는 데 있다고 주장한다.

원저자: Sangchul Oh

게시일 2026-07-07

📖 4 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Sangchul Oh

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

큰 그림: "양자 마법"에 대한 도전

높은 판돈이 걸린 "패턴 맞추기" 게임을 상상해 보세요. 과학자들은 양자 컴퓨터가 일반 컴퓨터는 절대 할 수 없는 일을 할 수 있다고 주장해 왔습니다. 즉, 매우 복잡한 특정 유형의 무작위 0과 1의 문자열(디지털 동전 던지기 시퀀스와 같은 것)을 생성할 수 있다는 것입니다. 이 작업은 **무작위 회로 샘플링(Random Circuit Sampling, RCS)**이라고 불리며, 양자 컴퓨터가 기존 컴퓨터보다 우월하다는 것을 증명하는 주요 근거로 사용되어 왔습니다.

이 논문의 저자인 오상철(Sangchul Oh)은 이렇게 말합니다. "잠깐만요. 이걸 하는 데 양자 컴퓨터가 필요하지 않습니다. 저는 일반 노트북으로도 할 수 있고, 심지어 더 빠르게 할 수 있습니다."

핵심 아이디어: "얼어붙은 나무 (Frozen Tree)"

저자가 이 일을 어떻게 수행하는지 이해하기 위해, 거대하고 마법 같은 나무라는 비유를 사용해 보겠습니다.

양자의 주장: 양자 컴퓨터가 무작위 회로를 실행하면, 하나의 "가능성의 숲"을 만들어냅니다. 당신이 답을 요청할 때마다, 컴퓨터는 이 숲속의 어떤 경로를 선택하게 됩니다. 사람들의 주장은 이 숲이 너무 혼란스럽고 뒤엉켜 있어서, 기존 컴퓨터(당신의 노트북 같은)는 이 숲의 규칙을 파악하여 동일한 경로를 선택할 수 없다는 것입니다.
저자의 발견: 저자는 이 "혼란스러운 숲"이 사실 숨겨진 완벽한 구조를 가지고 있다는 것을 발견했습니다. 그것은 바로 이진 트리(binary tree, 모든 가지가 두 개로 갈라지는 나무) 형태입니다.
- 맨 위(뿌리)에서 나무는 갈라집니다.
- 다음 단계에서 그 가지들은 다시 갈라집니다.
- 이 과정은 맨 아래 잎사귀(최종적인 0과 1을 나타냄)에 도달할 때까지 계속됩니다.

비결은 **"조건부 척도 불변성(Conditional Scale Invariance)"**이라는 규칙입니다. 쉬운 말로 설명하자면, 이 나무는 **자기 유사성(self-similar)**을 가지고 있다는 뜻입니다. 나무의 맨 꼭대기에서 갈라지는 방식은 중간 지점에서 갈라지는 방식과 통계적으로 동일하며, 잎사귀 직전에서 갈라지는 방식과도 동일합니다. 이는 프랙탈과 같습니다. 전체 패턴이 모든 작은 조각 안에 반복되는 구조입니다.

"얼어붙은(Frozen)" 기술

여기서 영리한 부분이 나옵니다. 저자는 이 양자 나무를 시뮬레이션하기 위해 전체를 한꺼번에 계산할 필요가 없다는 것을 깨달았습니다. 그저 나무를 따라 걸어가면서 구축하기만 하면 됩니다.

걷기: 나무의 꼭대기에서 잎사귀를 향해 걸어간다고 상상해 보세요. 길의 갈림길에 도착할 때마다 당신은 결정해야 합니다. "왼쪽(0)으로 갈 것인가, 오른쪽(1)으로 갈 것인가?"
"얼어붙은" 순간: 실제 양자 실험에서는 이러한 결정이 양자 기계에 의해 내려집니다. 저자의 고전적 방법에서는, 당신이 처음으로 갈림길에 도착했을 때, 분할 비율(왼쪽과 오른쪽 중 어디로 갈 확률이 높은지)을 결정하기 위해 특별한 동전을 던집니다.
- 결정적인 점: 그 동전을 던져 특정 갈림길의 비율을 결정하고 나면, 당신은 그것을 "얼려(freeze)" 버립니다. 즉, 그 값을 기록해 둡니다.
- 만약 당신(혹은 다른 누군가)이 나중에 동일한 갈림길을 다시 방문하게 된다면, 다시 동전을 던지는 대신, 이전에 기록해 둔 동일한 얼어붙은 비율을 사용합니다.

나무가 이런 방식으로 "얼어붙어" 있기 때문에, 저자는 이 무작위 문자열을 믿을 수 없을 정도로 빠르게 생성할 수 있습니다. 논문에 따르면 이 작업은 O(n) 시간이 걸립니다. 즉, 비트 수가 두 배가 되면 작업량도 두 배가 될 뿐입니다. 이는 선형적이며 효율적입니다.

"통계적 쌍둥이" 논증

이 논문은 결과에 대해 매우 강력한 주장을 펼칩니다.

양자의 결과: 양자 컴퓨터는 특정 무작위 회로를 기반으로 한 숫자 목록을 생성합니다.
고전적 결과: "얼어붙은 나무" 알고리즘은 나무 구조를 기반으로 한 숫자 목록을 생성합니다.

저자는 수학적으로 **두 목록이 정확히 동일한 통계적 가족(디리클레 분포, Dirichlet distribution)**에서 나왔음을 증명합니다.

이것은 마치 두 명의 제빵사가 초콜릿 칩 쿠키를 만드는 것과 같습니다.

제빵사 A (양자)는 비밀스럽고 혼란스러운 오븐을 사용합니다.
제빵사 B (고전)는 정밀하게 설계된 얼어붙은 틀을 사용합니다.

논문의 주장은 만약 눈을 가린 심판에게 제빵사 A의 쿠키와 제빵사 B의 쿠키를 건네준다면, 심판은 둘 사이의 차이를 구별할 수 없다는 것입니다. 쿠키(데이터)는 통계적으로 동일합니다.

이것이 왜 중요한가 (논문에 따르면)

현재 과학자들은 이렇게 말합니다. "보라! 양자 컴퓨터가 기존 컴퓨터는 만들 수 없는 기이하고 복잡한 패턴을 만들어냈다. 그러므로 양자 컴퓨터가 이기고 있는 것이다."

저자는 이렇게 반박합니다. "그건 사실이 아닙니다. 우리는 방금 고전 컴퓨터가 '얼어붙은 나무' 방법을 사용하여 그와 똑같은 패턴을 즉시 만들어낼 수 있다는 것을 보여주었습니다."

만약 고전 컴퓨터가 그와 똑같은 패턴을 완벽하게 흉내 낼 수 있다면, 이 특정 테스트에 대한 "양자 우위(Quantum Advantage, 양자 컴퓨터가 기존 컴퓨터가 할 수 없는 일을 한다는 개념)"는 사라지게 됩니다.

"노이즈(Noise)" 요인

실제 양자 컴퓨터는 지저지고 실수를 합니다(노이즈). 이 논문은 "얼어붙은 나무" 방법이 이러한 실수들까지도 쉽게 흉내 낼 수 있음을 보여줍니다. 양자 컴퓨터가 "탈분극 노이즈(depolarizing noise, 무작위 정적)"를 겪든, "진폭 감쇠(amplitude damping, 에너지 손실)"를 겪든, 혹은 "판독 오류(readout errors, 결과 오독)"를 범하든, 고전적인 "얼어붙은 나무"는 이러한 오류들을 완벽하게 시뮬레이션할 수 있습니다.

논문은 결론적으로, 오직 최종 숫자 목록(샘플)만을 바탕으로 한 테스트로는 양자 컴퓨터가 특별한 일을 하고 있다는 것을 증명할 수 없다고 말합니다. "어려움"은 무작위성 자체에 있는 것이 아니라, 양자 컴퓨터가 어떤 특정한 나무를 구축했는지 알아내는 데 있습니다. 하지만 통계적 결과가 동일하기 때문에, 해당 벤치마크는 실패한 것이 됩니다.

한 문장 요약

이 논문은 무작위 양자 회로의 "마법"이 사실은 나무를 따라 내려가며 결정을 "얼려" 버리는 방식으로 고전 컴퓨터가 완벽하고 즉각적으로 복제할 수 있는 숨겨진 자기 유사성 나무 구조일 뿐이며, 따라서 현재의 양자 우위 테스트들은 결함이 있다고 주장합니다.

기술 요약: 프로즌 트리 샘플러(Frozen-Tree Sampler), 무작위 회로 샘플링의 양자 우위론을 반박하다

문제 제기
무작위 회로 샘플링(Random Circuit Sampling, RCS)은 현재 양자 우위를 입증하기 위한 주요 벤치마크로 간주되고 있다. 이는 무작위 회로에 의해 생성된 하어-무작위(Haar-random) 양자 상태로부터 비트 문자열(bitstring)을 추출하는 작업이다. 지배적인 가정은 무작위 양자 상태가 고도로 얽혀 있고 활용 가능한 패턴이 없기 때문에 이 작업이 클래식하게 다루기 어렵다는 것이다. 이러한 상태는 지수적 출력 분포, 선형 교차 엔트로피 벤치마크(XEB) 점수, 헤비 출력 생성(heavy output generation), 그리고 반-집중(anti-concentration)과 같은 통계적 특성을 보인다. 본 논문은 이러한 통계적 특성이 양자 우위의 증거라는 전제에 이의를 제기하며, RCS의 난해함이 실제로는 확률 분포 자체를 샘플링하는 것의 어려움이 아니라 특정 회로의 구현(circuit realization)을 식별하는 것의 어려움과 혼동되어 있다고 주장한다.

방법론: 프로즌 트리 샘플러(The Frozen-Tree Sampler)
저자들은 하어-무작위 양자 상태의 **정확한 조건부 척도 불변성(exact conditional scale invariance)**을 활용하는 클래식 알고리즘인 프로즌 트리 샘플러를 제안한다. 핵심적인 이론적 통찰은 무작위 $n$ -큐비트 상태에서 비트 문자열 $x$ 를 찾을 확률 $p(x) = |\langle x|\psi\rangle|^2$ 가 이진 트리 워크(binary tree walk)로 표현될 수 있다는 점이다.

트리 표현: 결합 확률은 조건부 확률의 곱으로 연쇄 법칙(chain rule)을 통해 분해된다:
$p(x) = \prod_{k=1}^n R_{x_{<k}}^{1-x_k} (1 - R_{x_{<k}})^{x_k}$
여기서 $x_{<k}$ 는 첫 $k-1$ 개 비트의 접두사(prefix)이다. 각 노드 $u$ 에서의 "분기 비율(branch ratios)" $R_u$ 는 다음과 같은 베타 분포(Beta distribution)에서 추출된 독립적인 무작위 변수이다:
$R_u \sim \text{Beta}(K, K), \quad \text{단, } K = 2^{n-|u|-1}.$
이 구조는 디리클레 분포(Dirichlet distribution)의 집합 성질(aggregation property)과 무작위 상태의 조건부 척도 불변성으로부터 기인한다.
샘플링 알고리즘: 샘플러는 루트에서 리프까지 무작위 워크(random walk)를 수행한다( $n$ 단계).
- 지연 생성(Lazy Generation): 모든 $2^n - 1$ 개의 분기 비율을 미리 계산하는 대신, 알고리즘은 필요할 때마다 이를 생성한다. 노드 $u$ 가 처음 방문될 때, 비율 $R_u$ 를 $\text{Beta}(K, K)$ 에서 추출하여 "동결(frozen)"한다(즉, 저장하거나 노드 식별자를 키로 하는 의사 난수 함수를 통해 결정론적으로 재생성한다).
- 효율성: 알고리즘은 $O(n)$ 시간 내에 하나의 비트 문자열을 생성한다. $M$ 개의 샘플에 대해 총 실행 시간은 $O(Mn)$이다.
- 노이즈 모델링: 이 프레임워크는 트리 구조나 최종 비트 문자열에 아핀 변환(affine transformations) 또는 혼란 행렬(confusion matrices)을 적용함으로써 노이즈 채널(전역 탈분극, 진폭 감쇠, 판독 오류)을 자연스럽게 통합하며, $O(n)$ 의 비용을 유지한다.

주요 결과

통계적 동일성: 저자들은 프로즌 트리 샘플러의 출력 확률 $p_F(x)$ 와 무작위 양자 회로의 출력 확률 $p_C(x)$ 가 $(N-1)$ -심플렉스( $N=2^n$ ) 상의 동일한 평평한 디리클레 분포의 독립적인 실현임을 증명한다. 결과적으로 $p_F(x) \stackrel{d}{=} p_C(x)$ 이다.
구별 불가능성: 두 분포는 통계적으로 동일하기 때문에, 샘플링된 비트 문자열만을 대상으로 하는 어떠한 통계적 테스트(XEB, 헤비 출력 생성, 반-집중 테스트 등)도 클래식 프로즌 트리 샘플러와 양자 무작위 회로를 구별할 수 없다.
성능: 이 샘플러는 표준 GPU에서 $n=1000$ 큐비트에 대해 $10^7$ 개의 샘플을 단 몇 초 만에 생성한다. 이는 구글의 시카모어(Sycamore) 프로세서가 $n=53$ 에서 약 $10^6$ 개의 샘플을 수집하는 데 약 200초가 소요된 것과 대조적이다.
노이즈 재현: 프로즌 트리 샘플러는 진폭 감쇠에 의한 통계적 왜곡(예: 지수적 피크와 꼬리 거동의 억제)을 유한한 샘플에 대한 경험적 추정 없이도 정확하게 재현한다.

의의 및 주장
본 논문은 RCS의 양자 우위가 정밀한 검토를 견디지 못한다고 주장한다.

RCS의 "난해함"은 샘플링 과정 자체(클래식하게 $O(n)$ 으로 효율적임)가 아니라, 회로에서 그 진폭으로 가는 특정 매핑(mapping)에 존재한다.
프로즌 트리 샘플러가 모든 표준 검증 지표(지수 분포, XEB 등)를 클래식하고 효율적으로 재현하므로, 이러한 지표들은 양자 우위의 독립적인 증거로 기능할 수 없다.
저자들은 현재 검증 방식으로서의 RCS가 단독 벤치마크로서 타당하지 않다고 결론짓는다. 또한, 잔여 우위는 효율적인 클래식 샘플러를 허용하는 "허르비츠-프로즌-트리 회로(Hurwitz–frozen-tree circuit)"에 관한 동료 연구에서 다루어진 회로 특유의 구현(circuit-specific realization)에 존재할 수 있음을 언급한다.