⚛️ quantum physics

On Certified Randomness from Fourier Sampling or Random Circuit Sampling

이 논문은 양자 푸리에 샘플링(Quantum Fourier Sampling)을 활용하여 계산 복잡도 가설에 의존하지 않고 양자 랜덤 오라클 모델(QROM)에서 블랙박스 보안을 보장하는 공개 검증 가능한 인증된 무작위성(Certified Randomness) 프로토콜을 제안합니다.

원저자: Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn, Avishay Tal

게시일 2026-02-11

📖 2 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn, Avishay Tal

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

1. 배경: "가짜 주사위"를 잡아라! (Certified Randomness)

상상해 보세요. 당신은 아주 큰 규모의 복권 추첨을 진행하려고 합니다. 그런데 추첨 기계(양자 컴퓨터)를 만든 회사가 사실은 자기들 마음대로 숫자가 나오도록 기계를 조작했을지도 모른다는 의심이 듭니다.

보통은 기계를 믿어야 하지만, 이 논문은 **"기계가 어떤 원리로 작동하든 상관없이, 결과물만 보고도 이 숫자가 진짜 무작위인지 아닌지를 누구나 확인할 수 있는 방법"**을 제안합니다. 이것을 전문 용어로 **'인증된 무작위성(Certified Randomness)'**이라고 합니다.

2. 핵심 아이디어: "소음 속의 패턴 찾기" (Fourier Sampling)

이 논문은 양자 컴퓨터가 내놓는 결과물을 **'복잡한 음악 소리'**에 비유할 수 있습니다.

진짜 무작위(정상적인 양자 상태): 수만 명의 사람이 동시에 각자 다른 노래를 부르는 것처럼, 소리가 아주 불규칙하고 복잡합니다. 특정 음이 유독 크게 들리지 않고 전체적으로 '화이트 노이즈(백색 소음)'처럼 들려야 합니다.
조작된 상태(가짜 무작위): 누군가 숫자를 조작했다면, 아무리 복잡하게 숨기려 해도 아주 미세하게 특정 음(패턴)이 반복되거나 유독 크게 들리는 구간이 생기기 마련입니다.

연구진은 **'푸리에 샘플링(Fourier Sampling)'**이라는 수학적 도구를 사용합니다. 이것은 마치 복잡한 소음 속에서 **"특정 주파수의 음이 얼마나 크게 들리는지"**를 분석하는 필터와 같습니다. 만약 양자 컴퓨터가 내놓은 숫자들이 이 필터를 통과했을 때, "어? 특정 음이 너무 자주 들리는데?"라고 판단되면 그 숫자는 가짜(조작된 것)라고 판정하는 것이죠.

3. 이 논문의 놀라운 점 (두 가지 성과)

첫 번째: "수학적 증명서" 만들기 (Theorem 1)

연구진은 양자 컴퓨터가 내놓은 결과물이 특정 통계적 기준(무거운 계수, Heavy Coefficients)을 통과한다면, 그 숫자는 최소한 이만큼의 '진짜 무작위성(Entropy)'을 가지고 있다는 것을 수학적으로 증명했습니다.

비유하자면, 복권 번호를 뽑았는데 그 번호들이 "통계적으로 아주 불규칙한 패턴을 완벽하게 따르고 있음"을 보여주는 **'수학적 보증서'**를 발행할 수 있게 된 것입니다.

두 번째: "천재적인 도둑"도 못 속이는 법 (LLQSV Conjecture)

기존의 이론들은 "아무리 똑똑한 해커(양자 알고리즘)라도 이 패턴을 찾아내기는 어려울 것이다"라는 **'추측'**에 의존했습니다. 하지만 이 논문의 저자들은 이 추측이 맞다는 강력한 증거를 제시했습니다.

그들은 **'SquaredForrelation'**이라는 아주 까다로운 문제를 만들어냈습니다. 이것은 마치 **"아무리 눈썰미가 좋은 도둑이라도, 수조 개의 모래알 중에서 아주 미세하게 색깔이 다른 모래알 몇 개를 찾아내는 것은 불가능하다"**는 것을 수학적으로 보여준 것과 같습니다. 즉, 조작을 시도하는 양자 컴퓨터가 아무리 똑똑해도 우리가 만든 검증 시스템을 속이기는 거의 불가능하다는 것을 증명한 것입니다.

4. 요약하자면?

이 논문은 **"양자 컴퓨터라는 아주 강력한 도구가 내놓는 결과물이 진짜인지 가짜인지, 복잡한 수학적 필터를 통해 누구나 검증할 수 있는 안전한 방법"**을 설계한 것입니다.

이 기술이 완성되면, 미래에 양자 컴퓨터를 이용한 공정한 복권, 해킹 불가능한 암호 키 생성, 공정한 암호화폐 채굴 등이 가능해지는 든든한 기초가 됩니다.

[기술 요약] Fourier Sampling 또는 Random Circuit Sampling을 이용한 인증된 무작위성 연구

1. 연구 배경 및 문제 정의 (Problem)

**인증된 무작위성(Certified Randomness)**이란, 장치(device)를 신뢰할 수 없는 상황에서도 생성된 숫자가 실제로 무작위적임을 수학적으로 증명할 수 있는 능력을 의미합니다. 이는 공정한 복권, 암호 키 생성, 작업 증명(Proof of Work) 등에 응용될 수 있습니다.

최근 Scott Aaronson은 무작위 회로 샘플링(Random Circuit Sampling, RCS) 실험을 통해 단일 장치로도 공개적으로 검증 가능한 인증된 무작위성을 생성할 수 있다는 프로토콜을 제안했습니다. 그러나 이 프로토콜의 보안성은 **LLQSV(Long List Quantum Supremacy Verification)**라는 매우 강력하고 비표준적인 복잡도 이론적 가설에 의존하고 있어, 그 타당성에 대한 검증이 필요했습니다.

본 논문은 Aaronson의 제안을 확장하여, 양자 랜덤 오라클 모델(QROM) 환경에서 **Fourier Sampling(푸리에 샘플링)**을 이용해 계산적 가설 없이도 블랙박스 보안성을 갖는 인증된 무작위성 프로토콜을 구축하고, Aaronson의 가설을 뒷받침하는 복잡도 이론적 증거를 제시하는 것을 목표로 합니다.

2. 연구 방법론 (Methodology)

연구진은 크게 두 가지 접근 방식을 사용합니다.

QROM 기반의 Fourier Sampling 연구: 무작위 함수 $f$ 에 대한 블랙박스 접근 권한이 주어졌을 때, $f$ 의 푸리에 스펙트럼에서 샘플을 추출하는 문제를 다룹니다. 이를 통해 특정 통계적 테스트(FHOG: Fourier Heavy Output Generation)를 통과하는 장치가 높은 **최소 엔트로피(min-entropy)**를 생성함을 증명합니다.
복잡도 이론적 증거 제시 (Black-box LLQSV): Aaronson의 LLQSV 가설을 블랙박스 버전으로 변환하여, 무작위 회로 대신 무작위 불리언 함수(Boolean function)를 사용합니다. 이를 통해 이 문제가 BQP(양자 다항 시간) 및 PH(다항 계층) 범주를 벗어남을 증명하기 위해 SquaredForrelation이라는 새로운 문제를 도입하고, Raz와 Tal의 BQP vs PH 오라클 분리 기법을 확장하여 분석합니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

① 인증된 무작위성 프로토콜 구축 (Theorem 1)

결과: Fourier Sampling을 이용해 단일 라운드, 공개 검증 가능한 인증된 무작위성 프로토콜을 설계했습니다.
특징: 기존의 Yamakawa-Zhandry 프로토콜과 달리 계산적 가설(Aaronson-Ambainis 가설 등)에 의존하지 않습니다. 다만, 검증 과정에서 지수 시간(exponential-time)의 클래식 계산이 필요하다는 트레이드오프가 있습니다.
엔트로피 보장: 효율적인 양자 알고리즘이 FHOG 테스트를 통과하면서 동시에 낮은 엔트로피를 생성하는 것은 불가능함을 증명하여, 생성된 무작위성의 질을 보장했습니다.

② Aaronson의 LLQSV 가설에 대한 블랙박스 증거 (Theorem 4)

결과: 블랙박스 LLQSV 문제가 BQP 및 PH에 속하지 않음을 증명했습니다.
SquaredForrelation 문제: 기존의 Forrelation 문제보다 약화된 형태인 SquaredForrelation 문제를 정의하고, 이 문제가 BQP에는 속하지만 PH에는 속하지 않음을 보여줌으로써 강력한 오라클 분리를 달성했습니다. 이는 Aaronson의 가설이 타당할 가능성이 매우 높음을 시사합니다.

③ 하이브리드 및 재무작위화(Derandomization) 기법

상수 엔트로피(constant min-entropy) 보장 문제를 선형 엔트로피(linear min-entropy) 문제로 전환하기 위해 새로운 재무작위화 논증을 도입했습니다. 이는 양자 알고리즘의 출력을 클래식한 거부 샘플링(rejection sampling)을 통해 추출하여 알고리즘을 거의 결정론적으로 만드는 기법입니다.

4. 연구의 의의 (Significance)

이론적 토대 마련: Aaronson이 제안한 RCS 기반 무작위성 생성 프로토콜의 보안성을 뒷받침하는 강력한 복잡도 이론적 근거를 제공했습니다.
실용적 가능성 제시: Fourier Sampling은 양자 우위(Quantum Advantage) 실험의 유력한 후보입니다. 본 연구는 이러한 실험이 단순한 성능 과시를 넘어, 실제 암호학적 무작위성 생성 도구로 사용될 수 있는 이론적 경로를 열었습니다.
복잡도 이론의 발전: BQP와 PH 사이의 새로운 오라클 분리(SquaredForrelation)를 제시함으로써 양자 계산 복잡도 이론 분야에 학술적 기여를 했습니다.

요약하자면, 본 논문은 양자 푸리에 샘플링이 인증된 무작위성을 생성할 수 있음을 수학적으로 증명하고, 이를 뒷받침하는 복잡도 이론적 가설들이 블랙박스 모델에서 타당함을 입증함으로써 차세대 양자 기술의 실용적 응용 가능성을 높인 연구입니다.