A semi-definite programming formulation of the device-dependent guessing probability

이 논문은 완전히 특성화된 준비-측정 양자 설정에서 고유한 무작위성과 공격자의 추측 확률을 정밀하게 추정하기 위한 준정부호 계획법 정식화를 도입하며, 이를 통해 정확한 인증 가능한 무작위성을 결정할 수 있는 능력과 얽힘이 공격자의 예측력을 엄격하게 증가시킨다는 사실을 입증한다.

핵심

당신이 모자에서 토끼를 꺼내는 마술 공연을 하고 있다고 상상해 보세요. 양자 세계에서 이 "토끼"는 아주 작은 입자를 측정하여 생성된 무작위 숫자입니다. 보안 전문가들의 큰 질문은 이것입니다: 이 토끼는 얼마나 진정으로 무작위적인가? 교활한 마술사(적대자인 '이브')가 모자나 토끼를 조작하여, 일이 벌어지기도 전에 결과가 무엇인지 정확히 알 수 있도록 설계했을까요?

이 논문은 이러한 질문에 답하기 위해, "준비 및 측정(prepare-and-measure)" 설정이라 불리는 가장 단순한 종류의 양자 마술 트릭에 대해 적용할 수 있는 새롭고 강력한 수학적 도구를 소개합니다.

다음은 이 논문의 연구 결과를 쉬운 비유를 사용하여 정리한 내용입니다:

1. 문제점: "블랙박스"의 미스터리

현실 세계에서 우리의 양자 장치(모자와 토끼)는 완벽하지 않습니다. 마치 잡음이 섞인 라디오처럼 노이즈가 존재합니다.

• 설정: 앨리스(정직한 사용자)는 특정 양자 상태(토끼)를 준비하고 이를 측정하는(토끼를 꺼내는) 장치를 가지고 있습니다. 그녀는 장치가 수행해야 할 동작을 알고 있습니다.
• 위협: 이브(해커)는 앨리스보다 더 많은 것을 알고 있을 수 있습니다. 그녀는 비밀스러운 "컨닝 페이퍼"를 가지고 있거나, 장치와 숨겨진 연결 고리를 가져서 결과를 예측할 수 있습니다.
• 난이도: 지금까지 이 장치가 얼마나 무작위적인지 정확히 계산하는 것은 계속해서 모양이 변하는 미로를 푸는 것과 같았습니다. 특히 장치에 노이즈가 있을 때, 일반적이고 쉬운 방법이 없었습니다.

2. 해결책: "마법의 계산기" (반정부호 계획법, Semidefinite Programming)

저자들은 **반정부호 계획법(SDP)**이라는 새로운 수학적 레시피를 만들었습니다.

• 비유: 안개 낀 산맥에서 가장 높은 지점을 찾는다고 상상해 보세요. 이전에는 길을 헤매며 올라가야 했고, 실제 정상이 아닌 작은 골짜기에 갇혀 그곳이 정상이라고 착각할 수도 있었습니다. 새로운 SDP 방식은 산맥 전체를 한눈에 볼 수 있는 드론과 같아서, 정확한 최고 정점이 어디인지 즉시 알려줍니다.
• 역할: 이 방법은 무질서하고 노이즈가 섞인 양자 장치의 현실을 깔끔하고 해결 가능한 수학 문제로 변환합니다. 이를 통해 과학자들은 단순히 "최선의 추측"인 상한선을 구하는 것이 아니라, 이브로부터 안전함이 보장되는 정확한 무작위성을 계산할 수 있습니다.

3. 발견한 내용 (세 가지 테스트)

저자들은 자신들의 새로운 계산기가 어떻게 작동하는지 확인하기 위해 세 가지 시나리오에서 테스트를 진행했습니다.

• 테스트 A: 노이즈가 섞인 거울
  그들은 토끼와 모자 모두에 "정적"(탈분극 노이즈)이 덮여 있는 시나리오를 살펴보았습니다.

  • 결과: 그들의 계산기는 이 설정의 무작위성에 대한 기존의 수학적 추측이 실제로 완벽했다는 것을 확인했습니다. 즉, 기존의 추측이 절대적인 한계치였음을 증명했습니다.

• 테스트 B: 누출되는 검출기
  그들은 검출기(토끼를 꺼내는 손)가 가끔 게으르거나 효율이 떨어지는 설정을 살펴보았습니다.

  • 결과: 기존 방식들은 "누출"이 매우 단순한 방식으로 일어난다고 가정했습니다. 하지만 새로운 계산기는 만약 이브가 더 복잡한 방식의 "누출"을 이용할 만큼 영리하다면, 기존 방식이 생각했던 것보다 결과를 더 잘 맞출 수 있다는 것을 보여주었습니다. 이는 기존의 추정치가 안전성을 너무 낙관적으로(과하게 높게) 평가했음을 의미합니다.

• 테스트 C: 다중 결과 트릭
  그들은 장치가 여러 가지 결과(예를 들어 토끼, 비둘기, 혹은 비둘기 알을 꺼내는 것)를 만들어낼 수 있는 트릭을 살펴보았습니다.

  • 결과: 기존 이론은 측정 장치를 완전히 신뢰한다면 무한한 무작위성을 생성할 수 있다고 주장했습니다. 그러나 새로운 계산기는 만약 이브가 측정 장치와 비밀스러운 연결 고리를 가질 수 있다면, 결과값이 3개 또는 4개를 넘어가는 순간 그 "무한한 무작위성"이 사라진다는 것을 보여주었습니다. 즉, 장치가 완벽하게 격리되어 있다고 가정함으로써 발생한 안전의 환상이었습니다.

4. 거대한 놀라움: 얽힘(Entanglement)은 초능력이다

가장 흥계로운 발견은 얽힘(입자 사이의 기묘한 연결)에 관한 것입니다.

• 기존의 가정: 많은 보안 모델은 상태를 준비하는 장치와 측정하는 장치가 분리되어 있으며, 오직 "고전적" 정보(예: 전화 통화)만을 공유한다고 가정합니다.
• 새로운 발견: 저자들은 준비 장치와 측정 장치가 얽혀 있다면(양자적 마법으로 연결되어 있다면), 이브가 결과를 맞출 확률이 엄격하게 증가한다는 것을 증명했습니다.
• 비유: 두 명의 스파이가 비밀 코드를 맞히려고 한다고 상상해 보세요. 만약 그들이 단순히 전화로 대화한다면(고전적 상관관계), 90%의 확률로 맞힐 수 있습니다. 하지만 만약 그들이 텔레파시 연결을 공유한다면(얽힘), 91%의 확률로 맞힐 수 있습니다. 그 미세한 1%의 차이가 고도의 보안이 요구되는 상황에서는 매우 중요합니다. 이것은 양자적 연결이 해커에게 불공정한 이점을 주는 것을 보여준 가장 단순한 사례입니다.

요약

이 논문은 양자 무작위성을 측정하기 위한 더 나은, 더 정직한 자를 제공합니다. 이는 다음을 보여줍니다:

1. 우리는 이제 단순한 양자 난수 생성기의 안전성을 정확하게 계산할 수 있습니다.
2. 기존의 방식들은 장치가 실제보다 더 단순하거나 더 격리되어 있다고 가정함으로써 안전성을 과대평가하는 경우가 많았습니다.
3. 만약 장치들이 양자적 연결(얽힘)을 공유한다면, 해커의 권한이 높아집니다. 따라서 우리는 이러한 장치를 만들 때 훨씬 더 주의를 기울여야 합니다.

저자들은 다른 사람들이 자신의 양자 장치를 테스트하는 데 사용할 수 있도록 "계산기" 코드를 공개했습니다.

기술 요약

기술 요약: 장치 의존적 추측 확률의 준정부호 계획법(Semidefinite Programming) 정식화

문제 정의
양자 역학에서, 관측량의 고유 상태(eigenstate)가 아닌 상태를 측정할 때 발생하는 본질적 무작위성은 양자 난수 생성기(QRNG)를 위한 근본적인 자원이다. 가장 단순한 QRNG 시나리오는 완전히 특성화된(장치 의존적) 준비-측정(prepare-and-measure, PM) 설정—즉, 알려진 상태 $\rho_S$가 알려진 양의 연산자 값 측정(POVM) $\{M^a_S\}$에 의해 측정되는 경우—을 포함하지만, 인증 가능한 무작위성의 정확한 양을 정량화하는 것은 여전히 어려운 과제이다.

무작위성의 표준 운영 지표는 조건부 최소 엔트로피(conditional min-entropy) $H_{\min}(A|E)$이며, 이는 적대자(Eve)가 양자 측면 정보(side information)를 가졌을 때 측정 결과값을 맞출 수 있는 최대 확률($P_{\text{guess}}$)으로부터 유도된다. 장치 의존적 시나리오에서, Eve는 시스템과 측정의 딜레이션(dilation)에 관련된 모든 부가 시스템의 결합 상태에 대한 퍼ification(purification)을 보유한다고 가정한다. 선행 연구 [4]에서 언급되었듯이, 이 추측 확률을 계산하는 것은 측정의 모든 가능한 나이마크 딜레이션(Naimark dilation)과 Eve가 장치와 공유할 수 있는 모든 가능한 상관관계에 대한 비볼록 최적화(non-convex optimization) 문제를 포함한다. 기존에는 이 비볼록 문제를 정확하게 해결할 수 있는 일반적인 계산 절차가 존재하지 않았으며, 이로 인해 연구자들은 종종 상한선(upper bounds)에 의존하거나 제한적인 가정(예: 준비 장치와 측정 장치 사이의 얽힘이 없다고 가정함)을 사용해야만 했다.

방법론
저자들은 장치 의존적 추측 확률이 준정부호 계획법(SDP)으로 재정식화될 수 있음을 증명함으로써 이러한 계산적 공백을 해결한다.

1. 최적화의 재구성: 저자들은 $P_{\text{guess}}$의 정의를 시스템-보조 공간(system-ancilla space) 상의 투영 측정(PVM) $\{\Pi^a_{SM}\}$과 Eve의 측정 결과에 대한 최대화 문제로 시작한다. Eve의 결과에 따라 조건화된 하부 정규화 상태(subnormalized states)를 도입함으로써, 이 문제는 비가환 다항식(non-commutative polynomials)을 포함하는 형태로 재구성된다.
2. SDP 구축: [5, 13]의 기법을 활용하여, 저자들은 시스템 힐베르트 공간의 직교 기저에 대한 블록 형태(block form)로 투영 측정 $\{\Pi^a_{SM}\}$을 표현한다. 이를 통해 일반화된 모멘트 행렬(moment matrices) $\Gamma_e$를 정의할 수 있다.
3. 선형 제약 조건: 목적 함수와 물리적 제약 조건(알려진 상태 $\rho_S$, 알려진 POVM $\{M^a_S\}$, 그리고 투영성 및 완비성(projectivity/completeness)의 성질과의 호환성)은 모멘트 행렬의 계수들에 대한 선형 함수로 표현된다.
4. 완비성: 저자들은 이 SDP 완화(relaxation)가 단순히 상한선을 제공하는 것이 아니라, 추측 확률에 대한 완전한 특성화를 제공함을 증명한다(정리 1). 즉, SDP의 모든 가용 해(feasible solution)는 원래의 비볼록 문제에 해당하는 유효한 물리적 해에 대응하며, 따라서 SDP가 정확한 최대 추측 확률을 도출함을 보장한다.

주요 결과 및 응용
논문은 이 방법의 성능을 벤치마킹하고 기존에 상한선만을 알고 있었던 지점에서 정확한 무작위성 값을 결정하기 위해 세 가지 특정 시나리오에 이 SDP 정식화를 적용한다:

1. 탈분극된 상태 및 측정(Depolarized State and Measurement): 저자들은 큐비트 상태와 측정이 모두 탈분극 노이즈의 영향을 받는 설정을 분석한다. SDP 결과는 [6]에서 유도된 해석적 하한선(analytic lower bound)과 일치하며, 이는 해당 해석적 하한선이 타이트(tight)하며 SDP가 정확한 인증 가능 무작위성을 올바르게 식별함을 확인시켜 준다.
2. 탈분극된 상태와 비효율적 검출기(Depolarized State and Inefficient Detector): 양자 컴퓨터를 위해 제안된 Berta와 Brandão [7]의 체계를 재검토하면서, 저자들은 고정된 특정 딜레이션을 사용하여 추정된 무작위성([7]에서 수행된 방식)을 자신들의 SDP가 제공하는 무제한 최적화와 비교한다. 그들은 딜레이션을 고정하는 것이 내재적 무작위성을 약간 과대평가하게 만든다는 것을 발견하였으며, 이는 모든 가능한 딜레이션에 대해 최적화하는 것의 필요성을 입증한다.
3. 미특성화 상태와 등각 측정(Uncharacterized State with Equiangular Measurements): 저자들은 상태는 미특성화되어 있으나 측정은 신뢰할 수 있는 등각 $k$-결과 POVM인 소스-장치-독립적(source-device-independent) 체계 [8]를 조사한다. [8]에서는 측정이 신뢰된다는 가정하에 $k > 3$일 때 무제한의 무작위성을 추출할 수 있다고 주장했으나, 저자들은 만약 Eve가 측정 장치와 상관관을 가질 수 있다면(즉, 측정이 완전히 신뢰되지 않는다면) $k=4$일 때 인증 가능한 무작위성이 사라짐을 보여준다. 이는 측정 신뢰 가정의 결정적인 영향을 강조한다.

얽힘과 예측력(Entanglement and Predictive Power)
이 논문의 중요한 이론적 기여는 상태 준비 장치와 측정 장치 사이의 얽힘이 Eve의 예측력을 엄격하게 증가시킨다는 점을 입증한 것이다.

• 저자들은 임의의 상관관계(얽힘 포함)를 허용하는 추측 확률 $P_{\text{guess}}$와 시스템 및 측정 레지스터 사이의 분리 가능한 상태(separable states)로 제한된 $P^{\text{sep}}_{\text{guess}}$를 비교한다.
• 특정 큐비트 상태와 이진 측정을 사용하여, 저자들은 $P_{\text{guess}} > P^{\text{sep}}_{\text{guess}}$임을 보여준다.
• 이 결과는 준비 장치와 측정 장치 사이에 얽힘이 없다고 가정하는 것(일부 프레임워크에서의 흔한 단순화)이, 단일 큐비트와 이진 측정이라는 가장 기초적인 시나리오에서도 생성된 무작위성을 과대평가하게 만든다는 것을 의미한다.

의의 및 주장
이 논문은 비볼록 최적화 휴리스틱이나 장치 간 상관관계에 대한 제한적인 가정에 의존하지 않고, 장치 의존적 PM 설정에서 내재적 무작위성을 추정할 수 있는 최초의 일반적이고 계산 친화적인 방법을 제공한다고 주장한다.

• 인증(Certification): SDP를 통해 상한선만을 알 수 있었던 시나리오에서 인증 가능한 무작위성을 정확하게 결정할 수 있다.
• 근본적 통찰: 본 연구는 준비 및 측정 장치 사이의 얽힘 보조(entanglement assistance)가 적대자의 결과 예측 능력을 강화하는 자원임을 입증하며, 이는 단순한 이진 측정 시나리오에서도 관찰 가능한 결과이다.
• 실용적 유용성: 이 방법은 노이즈의 영향을 받는 실제 양자 장치에서 무작위성을 인증하기 위한 일반적인 도구 역할을 하며, 가장 단순한 형태의 장치 의존적 QRNG를 위한 엄격한 레시피를 제공한다.

저자들은 이 정식화가 양자 측면 정보가 존재하는 상황에서의 무작위성 생성에 대한 이해를 진전시키며, 향-미래의 무작위성 인증 프로토콜을 위한 견고한 프레임워크를 제공한다고 결론짓는다.