Genuine certifiable randomness from a black-box

이 논문은 기존 방식의 가정 없이 블랙박스 환경에서도 결정론적 적대자가 실패할 수밖에 없는 진정한 무작위성을 단일 입자 상태 측정을 통해 증명하고 시연한 연구입니다.

핵심

1. 문제의 핵심: "진짜 주사위"를 어떻게 믿을 수 있을까?

상상해 보세요. 누군가 당신에게 "이건 진짜 무작위로 나온 숫자야"라고 말하며 주사위를 굴려줍니다. 하지만 그 사람이 속임수를 썼을 수도 있죠? 미리 정해진 숫자 순서 (예: 1, 2, 3, 4...) 를 외워서 굴린 것일 수도 있습니다.

• 기존의 방식: 보통 우리는 상대방이 "양자 컴퓨터"를 썼는지, "벨 부등식"을 위반했는지 등을 확인하기 위해 상대방의 내부 상태를 감시하거나 복잡한 물리적 장치를 요구합니다. 하지만 이는 상대방이 "검은 상자"일 때 (내부를 볼 수 없을 때) 불가능합니다.
• 이 논문의 목표: 상대방의 내부 workings(작동 원리) 를 전혀 몰라도, 오직 결과물만 보고 "이건 진짜 무작위야"라고 100% 증명하는 방법을 찾았습니다.

2. 핵심 아이디어: "미지의 편지"와 "예측 불가능한 답"

이 논문은 복잡한 계산을 요구하는 대신, **"예측"**이라는 게임을 제안합니다.

🎁 비유: "미지의 편지" 게임

1. **심판 (Verifier)**이 "무작위성"을 담고 있는 **양자 상태 (기하학적 모양의 편지)**를 작성합니다. 이 편지에는 'θ(세타)'라는 비밀 숫자가 숨겨져 있습니다.
2. 심판은 이 편지를 **상대방 (Prover)**에게 보냅니다. 상대방은 편지의 내용을 알 수 없습니다.
3. 상대방은 이 편지를 보고 "비밀 숫자가 뭐였나요?"라고 **추측 (예측)**해야 합니다.

여기서 중요한 규칙이 하나 있습니다:

• 상대방이 편지를 열어서 읽지 않고 (측정하지 않고) 추측한다면, 그 답은 항상 중간값이나 임의의 고정된 숫자가 될 수밖에 없습니다. (예: "아마 1.5 일 거예요"라고 항상 말함).
• 하지만 상대방이 편지를 열어서 읽으면 (양자 측정) 양자역학의 법칙 (보른 규칙) 에 따라 진짜 무작위적인 숫자가 나옵니다.

3. 왜 이것이 '진짜' 무작위성 증명인가?

이 게임의 핵심은 **"오차 (실수)"**를 측정하는 것입니다.

• 상대방이 속임수 (결정론적) 를 썼다면: 편지를 읽지 않고 미리 정해진 답을 내놓을 것입니다. 이때 심판이 정한 '비밀 숫자'와 상대방의 '추측' 사이의 거리는 통계적으로 **특정 한계 (0.5)**보다 작아질 수 없습니다. (예: 항상 1.5 라고 말하면, 실제 숫자가 0 이든 1 이든 평균 오차는 커집니다.)
• 상대방이 진짜 양자 측정을 했다면: 양자역학의 특성상 편지를 읽는 순간 숫자가 무작위로 결정됩니다. 이 무작위성을 이용해 만든 답은 통계적으로 오차가 훨씬 더 작아집니다.

결론: 상대방이 "오차"를 줄여 성공적으로 답을 맞췄다면, 그 사람은 편지를 열어서 읽었을 수밖에 없습니다. 그리고 양자 편지를 읽는다는 것은 진짜 무작위성을 생성했다는 뜻입니다.

4. 실험: 다이아몬드 속의 작은 나침반

저자는 이 이론을 실제로 증명하기 위해 실험을 했습니다.

• 도구: 다이아몬드 안에 있는 질소 - 공공 (NV) 센터라는 아주 작은 원자 하나를 사용했습니다. 이는 마치 아주 작은 자석 (나침반) 과 같습니다.
• 과정:
  1. 심판이 마이크로파를 쏘아 이 나침반의 방향을 특정 각도로 설정합니다 (이게 '비밀 편지'입니다).
  2. 상대방은 나침반을 측정합니다.
  3. 상대방이 측정한 결과 (0 또는 1) 를 바탕으로 각도를 추측합니다.
• 결과: 수천 번의 실험을 반복했을 때, 상대방이 양자 측정을 했을 때의 오차는 결정론적 (속임수) 인 방법보다 훨씬 작았습니다. 이는 상대방이 진짜 무작위성을 생성했음을 99.9999% 확신하게 증명했습니다.

5. 이 연구가 중요한 이유 (세 가지 질문)

이 논문은 기존에 제기되던 세 가지 의문에 명확한 답을 줍니다.

1. 검은 상자 (Black-box) 가 가능할까?
   • 답: 네, 가능합니다. 상대방의 내부 장비를 확인하지 않아도, 오직 결과물의 통계적 오차만으로도 진위를 가릴 수 있습니다.
2. 얽힘 (Entanglement) 이 필요할까?
   • 답: 아닙니다. 기존 방식은 두 개의 입자가 얽혀 있어야 했지만, 이 방법은 단 하나의 입자만으로도 가능합니다. 훨씬 저렴하고 간단합니다.
3. 처음에 무작위 숫자가 필요할까?
   • 답: 아닙니다. 기존 방식은 "진짜 무작위 숫자"를 먼저 만들어서 상대방에게 주어야 했지만, 이 방법은 심판이 아무 숫자나 (심지어 고정된 숫자) 정해서 보내도 상대방이 진짜 무작위성을 증명할 수 있습니다.

요약

이 논문은 **"양자역학의 불확실성"**을 이용해, **"상대방이 속임수를 쓰지 않고 진짜 무작위성을 냈는지"**를 증명하는 새로운 게임을 고안했습니다.

마치 **"상대방이 미지의 편지를 읽었는지, 아니면 그냥 추측만 했는지"**를 편지의 내용 (오차) 만으로 완벽하게 가려내는 것과 같습니다. 이는 향후 암호학, 보안, 그리고 양자 컴퓨팅 분야에서 신뢰할 수 있는 '진짜 무작위성'을 만들어내는 획기적인 기술이 될 것입니다.

기술 요약

1. 문제 제기 (Problem Statement)

• 배경: 양자역학의 본질적 특성인 측정 결과의 무작위성은 무작위성 인증 (Randomness Certification) 의 핵심 자원으로 활용되어 왔습니다. 그러나 기존의 인증 프로토콜들은 대부분 '블랙박스 (Black-box)' 설정이 아니었습니다.
• 기존 접근법의 한계:
  • 벨 부등식 위반 (BCR): 두 개의 분리된 프로버가 통신하지 않음을 검증해야 하며, 이는 물리적 위치 감시와 같은 추가적인 가정을 요구합니다.
  • 회로 샘플링 (CSR): 양자 컴퓨터의 계산 복잡도 가정에 의존하며, 프로버가 특정 계산 능력을 갖지 않는다는 것을 검증해야 합니다.
  • 핵심 문제: 기존 방식들은 프로버의 내부 상태나 계산 능력을 검증해야 하므로, "검증자가 프로버를 블랙박스 (내부를 알 수 없는 상자) 로 간주하고도 무작위성을 증명할 수 있는가?"라는 질문에 답하지 못했습니다. 또한, 초기 무작위 시드 (seed) 가 필요한 경우가 많아 진정한 무작위성 생성 (Generation) 이 아닌 확장 (Expansion) 에 그치는 경우가 많았습니다.
• 목표: 프로버의 물리적 상태, 계산 능력, 또는 내부 작동 원리에 대한 어떤 가정도 하지 않고 (완전한 블랙박스), 오직 측정 데이터만으로 프로버가 진정한 무작위성을 생성했음을 수학적으로 증명하는 프로토콜 개발.

2. 방법론 (Methodology)

저자는 양자 추정 기반 무작위성 (Estimation Certified Randomness, ECR) 이라는 새로운 프로토콜을 제안합니다. 이는 계산 복잡도 이론이 아닌 통계적 파라미터 추정 (Statistical Parameter Estimation) 의 틀을 차용합니다.

• 핵심 아이디어:
  • 검증자 (Verifier) 는 매개변수 $\theta$에 의존하는 단일 양자 상태 $|\theta\rangle$를 생성하여 프로버 (Prover) 에게 보냅니다.
  • 프로버는 이 상태를 측정하여 $\theta$의 값을 추정 ($\hat{\theta}$) 해야 합니다.
  • 가정 1 (No hidden information): 프로버는 검증자가 보낸 양자 상태 $|\theta\rangle$ 외에는 $\theta$에 대한 어떤 정보도 가지고 있지 않습니다.
• 수학적 도구:
  • 반대극 거리 (Antipodal Metric): 유클리드 거리가 아닌, 원 위의 호 길이 (arc length) 를 기반으로 한 반대극 거리 $d^\circ[\theta, \hat{\theta}] = |\sin[\pi(\theta - \hat{\theta})/2]|$를 사용합니다. 이는 양자 위상의 대칭성을 반영합니다.
  • 반대극 확률 분포 (Antipodal Probability Distribution): $\pi^\circ[\theta] = \pi^\circ[(\theta+1) \mod 2]$를 만족하는 분포를 사용하여, 결정론적 알고리즘이 $\theta$를 알지 못한다면 특정 오차 한계를 넘을 수 없음을 보장합니다.
• 프로토콜 흐름:
  1. 검증자가 $\theta$를 선택하고 이를 양자 상태 $|\theta\rangle$로 인코딩하여 프로버에게 전송.
  2. 프로버는 $|\theta\rangle$를 측정하여 1 비트 추정치 $\hat{\theta}$를 반환.
  3. 검증자는 수신된 $\hat{\theta}$와 실제 $\theta$ 간의 평균 제곱 오차 (MSE) 를 계산.

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

이 논문은 다음과 같은 이론적 정리를 증명하고 실험적으로 검증했습니다.

• 정리 1: 측정 부재 한계 (No-measurement bound)
  • 프로버가 $|\theta\rangle$를 측정하지 않고 (즉, 결정론적 함수만 사용), $\theta$에 대한 사전 정보가 없다면, 추정치 $\hat{\theta}$의 기대 평균 제곱 오차 (EMSE) 는 **$1/2$**보다 작을 수 없습니다.
  • 이는 계산 복잡도 (P vs NP 등) 와 무관하며, 프로버가 어떤 강력한 컴퓨터를 사용하더라도 측정 없이는 이 한계를 넘을 수 없음을 의미합니다.
• 정리 2: 양자 측정 한계 (Quantum measurement bound)
  • 프로버가 $|\theta\rangle$를 측정할 경우, 최적의 측정 (예: X-기저 측정) 과 통계 처리를 통해 EMSE 를 **$1/4$**까지 낮출 수 있습니다.
  • 이는 측정 없이는 도달할 수 없는 영역으로, 검증자가 데이터가 무작위 측정에서 비롯되었음을 통계적으로 확신할 수 있는 근거가 됩니다.
• 실험적 증명:
  • 시스템: 다이아몬드 내의 단일 질소 - 공극 (NV) 중심의 스핀 상태를 사용.
  • 과정: 검증자가 마이크로파 펄스를 이용해 특정 위상 $\theta$를 가진 양자 상태를 준비하고, 프로버가 이를 측정하여 결과를 반환.
  • 결과: 고신뢰도 측정 시, 120 회 정도의 반복으로 5 시그마 (5-sigma) 신뢰수준에서 데이터가 무작위임을 확인했습니다. 반면, 결정론적 전략 (측정 없이) 은 이론적 한계인 1/2 에 수렴하며 무작위성을 통과하지 못했습니다.

4. 의의 및 중요성 (Significance)

• 진정한 블랙박스 인증의 실현: 프로버의 내부 구조, 계산 능력, 또는 통신 제한에 대한 가정을 전혀 하지 않고도 무작위성을 인증할 수 있는 최초의 프로토콜입니다.
• 초기 무작위성 불필요: 기존 프로토콜들이 초기 무작위 시드를 필요로 했던 것과 달리, 이 방식은 검증자가 결정론적으로 $\theta$를 선택해도 (Assumption 1 하에서) 프로버가 이를 알 수 없으므로 진정한 무작위성 생성 (True Randomness Generation) 이 가능합니다.
• 얽힘 (Entanglement) 불필요: 기존의 벨 부등식 기반 인증이 얽힘 상태를 요구하는 반면, 이 프로토콜은 단일 입자 (Single particle) 만으로 작동하여 구현 비용과 복잡도를 획기적으로 낮췄습니다.
• 컴퓨팅 이론에 대한 함의:
  • 이 결과는 "결정론적 튜링 기계가 양자 랜덤화된 튜링 기계와 동일한 오차 수준으로 문제를 해결할 수 없다"는 것을 보여줍니다. 이는 계산 이론의 관점에서 Church-Turing 테제에 대한 새로운 도전을 제기하며, P vs NP 문제 해결을 위한 새로운 접근법 (대각선 논법 없이 MSE 를 이용한 경계 설정) 을 시사합니다.
  • 양자 파라미터 추정의 새로운 하한 (Lower bound) 을 제시하여, 기존 크라메르 - 라오 (Cramér-Rao) 하한보다 더 강력하고 단일 측정에서도 성립하는 한계를 증명했습니다.

요약

이 논문은 통계적 추정 이론과 양자역학의 Born 규칙을 결합하여, 프로버가 블랙박스 상태에서도 측정 없이 무작위성을 모방할 수 없음을 수학적으로 증명하고 실험적으로 검증했습니다. 이는 암호학, 양자 정보, 그리고 계산 복잡도 이론 분야에서 획기적인 진전을 의미하며, 외부의 신뢰할 수 없는 장치로부터도 검증 가능한 진정한 무작위성 생성이 가능함을 보여줍니다.