기술적 요약: 의사 무작위 유니터리(pseudorandom unitaries)의 구별성 임계값(Distinctness threshold)

문제 정의

본 논문은 양자 정보 이론의 두 가지 형태의 의사 무작위성, 즉 통계적 의사 무작위성(유니터리 디자인에 의해 구현됨)과 계산적 의사 무작위성(의사 무작위 유니터리 또는 PRU에 의해 포착됨) 사이의 개념적 및 기술적 간극을 다룬다. 기존의 PRU 구축 방식(예: PFC 패밀리)은 통계적 무작위화 도구(구체적으로 유니터리 2-디자인)를 고전적 암호학적 프리미티브와 결합하는 것에 의존하고 있으나, 이러한 통계적 성분의 근본적인 필요성은 여전히 불분명하다. 높은 통계적 무작위성을 제공하는 유니터리 디자인이 Haar-무작위 유니터리와의 계산적 구별 가능성을 달성하기 위해 엄격히 요구되는지, 아니면 더 약한 통계적 특성만으로도 충분한지는 미해결 과제로 남아 있다. 또한, 쿼리 레지스터가 쌍으로 구별되는 라벨을 생성하는 데 사용되는 기술적 도구인 "구별되는 부분 공간(distinct subspace)"과 기저 앙상블 속성 사이의 관계에 대한 명확한 설명이 필요하다.

방법론

저자들은 **구별성(distinctness)**이라 명명된 특정 속성을 분리하여 분석한다. 저자들은 어떤 앙상블이 $t$개의 쿼리 레지스터에 대해 효율적으로 준비 가능한 임의의 입력 상태에 대해, 계산 기저(computational basis)에서 충돌(비구별 라벨)을 측정할 확률이 $\delta$ 이하일 때 $\delta$-구별하다고 정의한다.

방법론은 다음 단계들을 통해 진행된다:

1. 운용적 특성화: 저자들은 표준적인 안티집중성(anticoncentration)을 일반화하여, 최대 얽힘 상태를 포함한 임의의 이분 상태(bipartite inputs)에 대해서도 충돌 억제를 요구하는 **얽힘 안티집중성(Entangled Anticoncentration, EAC)**을 도입한다. 저자들은 다항식 개수의 쿼리($t = \text{poly}(n)$) 영역에서 $\delta$-구별성과 $\delta$-EAC가 동치임을 증명한다.
2. 필요성 증명: 저자들은 구별성이 모든 PRU의 필요 조건임을 입증한다. 만로 앙상블이 구별성을 갖추지 못하면, 단순한 구별자(distinguisher)가 높은 확률로 충돌을 감지하여 해당 앙상블을 Haar-무작위 유니터리와 구별해낼 수 있다.
3. 반례 구축: 디자인의 충분성을 테스트하기 위해, 저자들은 구별성은 만족하지만 유니터리조차 되지 않거나 심지어 상태 1-디자인(state 1-design)도 되지 않는 명시적인 앙상블들을 구축한다. 구체적으로 HF 앙상블(Hadamard 변환 후 무작위 복소 위상 유니터리 적용)과 단일 레이어 클리포드(single-layer Clifford) 앙상블을 분석한다.
4. 자원 분석: 구별성과 EAC 사이의 동치성을 사용하여, 구별성에 필요한 양자 자원(imaginarity 및 coherence)에 대한 하한을 도출하며, 이러한 하한이 완전한 의사 무작위성이 달성되기 전부터 적용됨을 보여준다.
5. 입력 의존적 분석: 실수 값 유니터리가 구별성을 만족할 수 있는 조건을 조사한다. Bell 중첩(Bell overlap) 메트릭(unnormalized Bell 상태와의 trace overlap)을 정의함으로써, 실수 값 성질에 대한 장애가 사라지는 입력 상태의 클래스를 식별한다.
6. 가설에 대한 제약: JLS 가설(교대 위상 및 Hadamard 레이어)에 구별성 프레임워크를 적용하여, 보안성을 유지하기 위해 요구되는 함수 공역(codomain)의 크기를 분석한다.

주요 기여 및 결과

1. 필요충분조건으로서의 구별성

본 논문은 구별성이 통계적 무작위성과 계산적 의사 무작위성을 연결하는 근본적인 중간 속성임을 확립한다.

• 필요성: 모든 PRU 앙상블은 모든 효율적으로 준비 가능한 입력 상태에 대해 $\text{negl}(n)$-구별되어야 한다.
• 동치성: 다항식 쿼리 영역에서, 구별성은 얽힘 안티집중성(EAC)과 동치이다.
• 충분성: PFC 프레임워크에서, 유니터리 2-디자인 레이어를 임의의 $\text{negl}(n)$-구별되는 앙상블로 대체하더라도 보안이 유지되는 PRU를 얻을 수 있다.

2. 디자인 없는 구별성

저자들은 높은 구별성을 가지면서도 디자인의 통계적 속성은 결여된 앙상블들을 구축한다:

• HF 앙상블: $n$-큐비트 Hadamard 변환($H$)과 4-wise 독립적인 삼진 함수를 가진 무작위 복소 위상 유니터리($F$)로 구성된 앙상블은 $O(t^2/N)$-구별함을 보인다. 결정적으로, 이 앙상블은 상태 1-디자인이 아니며(단일 복사본에 대해 최대 혼합 상태조차 근사하지 못함), 그럼에도 불구하고 기존 PFC 구축에서 사용된 유니터리 2-디자인과 동일한 구별성 하한을 달성한다.
• 단일 레이어 클리포드: 독립적인 무작위 단일 큐비트 클리포드 게이트의 단일 레이어는 $\text{negl}(n)$-구별됨을 보인다. 이를 통해 기존 구축의 $\log(n)$-깊이 글로벌 유니터리 2-디자인을 깊이 1의 레이어로 대체할 수 있게 되어, 통계적 무작위화 단계의 회로 깊이를 크게 줄일 수 있다.

3. 양자 자원 하한

구별성을 EAC와 연결함으로써, 본 논문은 PRU에 대한 자원 하한을 회복하고 강화한다:

• Imaginarity: 모든 $\delta$-구별되는 앙상블은 최소 $1-\delta$ 이상의 기대 imaginarity를 가져야 한다. 이는 완전히 실수 값인 유니터리 앙상블은 임의의 입력에 대해 구별될 수 없음을 의미한다.
• Coherence: 모든 $\delta$-구별되는 앙상블은 최소 $\ln(1/\delta)$ 이상의 기대 coherence를 가져야 한다.
  이러한 하한은 구별성 수준에서 발생하며, 이는 이러한 자원들이 앙상블이 완전한 의사 무작위성을 달성하기 훨씬 전부터 필요함을 시사한다.

4. Bell 중첩을 통한 실수 값 PRU

본 논문은 장애가 입력 의존적임을 보여줌으로써 실수 값 PRU에 대한 문제를 해결한다:

• Bell 중 중첩 조건: 실수 값 구별성의 불가능성은 특히 정준 최대 얽힘 Bell 상태와 큰 중첩을 갖는 입력에 의해 목격된다.
• 제한된 보안성: 저자들은 제한된 Bell 중첩을 갖는 입력 상태에 대해 보안이 보장되는 실수 값 PRU(실수 클리포드 군과 이진 위상 연산자 사용)를 구축한다. 이 클래스에는 다음이 포함된다:
  • 모든 양의 부분 전치(PPT) 상태.
  • Choi 상태를 포함한 특정 음의 부분 전치(NPT) 상태.
  • Schmidt number(또는 Schmidt rank)가 최대 $N/n^{\omega(1)}$인 모든 상태.
    이 결과는 곱 상태(product states)에 대한 실수 PRU에 관한 열린 질문을 해결하며, 유니터리 디자인과 직교 디자인 사이의 동치성을 PPT 장벽 너머로 확장한다.

5. JLS 가설에 대한 제약

본 논문은 무작위 위상 및 Hadamard 레이어가 교대로 나타나는 형태가 PRU를 형성한다는 가설을 분석한다.

• 공역 크기 제약: 만약 무작위 위상 함수가 $\log K \le n - \omega(\log n)$인 공역 $K$로 매핑된다면(즉, 공역이 도메인보다 초다항식적으로 작다면), 결과물인 앙상블은 PRU가 될 수 없음을 증명한다.
• 구별자: Bell 상태 기반의 구별자가 이러한 앙상블을 Haar-무작위성과 구별해낼 수 있다. 이는 위상 알파벳이 작은 경우의 더 넓고 약한 버전의 JLS 가설을 배제하지만, 전체 알파벳($K=N$)을 사용하는 원래의 가설을 반박하는 것은 아니다.

의의

본 논문은 구별성이 통계적 양자 의사 무작위성과 계산적 의사 무작위성을 가르는 "임계값" 역할을 한다고 주장한다. 그 의의는 다음과 같다:

1. PRU 구축의 명확화: 유니터리 디자인이라는 무거운 통계적 기구가 계산적 보안을 위해 반드시 필요한 것은 아니며, 훨씬 약한 속성인 구별성만으로도 충분함을 보여준다.
2. 구조적 단순화: 더 낮은 회로 깊이(무작위화 레이어의 깊이 1)와 더 단순한 구성 요소(예: 제한된 입력에 대한 실수 값 연산자)를 가진 PRU를 구축할 수 있게 한다.
3. 운용적 특성화: 후보 PRU 구축을 배제하기 위한 명확한 운용적 테스트(얽힌 입력에 대한 충돌 억제)를 제공하여, 의사 무작위성에 대한 "불가능성(no-go)" 테스트를 제시한다.
4. 자원 요구사항의 정교화: 자원 제약(imaginarity, coherence)이 디자인을 사용하는 특정 증명 기법의 부산물이 아니라, PRU에 필수적인 구별성 속성 자체에 묶여 있음을 명확히 한다.

저자들은 구별성을 더 넓은 양자 의사 무작위성 이론의 모듈형 구성 요소로 위치시키며, 향-연구가 강력한 디자인 가정에 의존하기보다 특정 작업을 위해 요구되는 최소한의 운용적 속성을 식별하는 데 집중해야 함을 제안한다.