In Plain Words
쉽게 풀면
양자컴퓨터만 통과할 수 있는 시험(양자성 증명)이 존재한다고 해서 반드시 "풀기 어려운 계산 문제가 있다"는 뜻은 아닐 수 있습니다. 이 연구는 모든 NP 문제가 다항시간에 풀리는 P=NP 세계에서도 양자 우위가 여전히 나타날 수 있음을 오라클 구성으로 증명합니다. 결과적으로, 양자 우위를 발판 삼아 암호 체계를 세우려는 시도에 근본적인 장벽이 존재함을 시사합니다.
Abstract
한국어 초록
(1) 문제: 양자성 증명(proof of quantumness)과 (양자 검증자) 망각적 상태 준비(oblivious state preparation)라는 양자 계산·암호 원시함수가 복잡도 클래스 분리를 필연적으로 함의하는지 묻는다. (2) 방법: 고전 오라클과 유니터리 오라클을 각각 구성하여 오라클 분리를 확립한다. (3) 결과: 첫째, 이고 인 동시에 에 대해 평균적으로 어려운 양자성 증명이 존재하는 고전 오라클이 존재한다. 둘째, 이면서 양자 검증자 망각적 상태 준비가 존재하는 유니터리 오라클이 존재한다. (4) 의의: 양자성 증명은 상대화 증명 방식으로는 고전·양자 암호학 구축에 활용될 수 없으며, 양자 연산·고전 통신 무의식 전송(oblivious transfer)도 양자 후(post-quantum) 일방향 함수 구축에 상대화 증명으로 사용될 수 없음을 직접 함의한다.
Expert Notes
전문가 노트
연구 배경 및 위치
양자성 증명은 고전 다항시간 알고리즘이 통과할 수 없지만 양자 다항시간 알고리즘은 통과할 수 있는 인터랙티브 프로토콜로, 계산 기반 양자 우위의 조작적 증거로 활발히 연구되어 왔다. 기존 문헌에서는 양자성 증명의 존재가 일방향 함수(OWF)나 복잡도 분리를 함의하는지가 열린 문제로 남아 있었다.
핵심 결과
결과 1 (고전 오라클): 이고 이면서, 에 속하는 언어가 에 대해 평균 어려운 양자성 증명이 공존하는 오라클이 존재한다. 이는 비결정론적 계산의 용이성이 양자 우위를 소거하지 못함을 보인다.
결과 2 (유니터리 오라클): —양자 증인이 고전 증인보다 추가적 힘을 갖지 않는 세계—에서도 양자 검증자 망각적 상태 준비가 존재하는 유니터리 오라클이 존재한다.
핵심 가정·한계
오라클 분리는 본질적으로 상대화(relativizing) 기법의 범주에서만 유효하다. 대수화(algebrization), 자연 증명(natural proofs) 등 비상대화 기법에 의한 함의 가능성은 배제되지 않는다. 또한 이는 특정 오라클 세계에서의 존재 증명이지, 실제 복잡도 세계에 대한 무조건적 결론이 아님에 주의해야 한다.
후속 함의 및 열린 문제
이 결과는 양자성 증명에서 출발해 OWF·양자 후 암호 기반으로 이어지는 환원(reduction)에 상대화 장벽이 존재함을 확립하며, 양자 암호 원시함수 계층 구조 연구에 중요한 제약을 제공한다. 비상대화 환원의 존재 여부, 그리고 망각적 상태 준비와 OWF의 관계가 향후 핵심 과제로 남는다.
Glossary
핵심 용어
Source
원문 출처
원문 초록 (영문) 보기
We consider the complexity implications of proofs of quantumness and (quantum verifier) oblivious state preparation. We show that both of these objects can coexist with the easiness of nondeterministic computation. That is, we give evidence that proofs of quantumness can exist when $\mathsf{P} = \mathsf{NP}$ and that (quantum verifier) oblivious state preparation can exist when $\mathsf{BQP} = \mathsf{QCMA}$. In particular, we give a classical oracle relative to which (1) $\mathsf{P}^\mathcal{O} = \mathsf{NP}^\mathcal{O}$ (2) $\mathsf{BQP}^\mathcal{O} = \mathsf{PSPACE}^\mathcal{O}$ (3) Proofs of quantumness exist. In particular, there exists a language in $\mathsf{IP}^\mathcal{O} \subseteq \mathsf{BQP}^\mathcal{O}$ which is hard on average against $\mathsf{P}^\mathcal{O}/poly$. We give a unitary oracle such that (1) $\mathsf{BQP}^\mathcal{O} = \mathsf{QCMA}^\mathcal{O}$ (2) Quantum verifier oblivious state preparation exists. These oracle separations directly imply a number of related consequences. For example, our first result implies that proofs of quantumness cannot be used to construct classical or quantum cryptography with a relativizing proof. Our second result implies that quantum computation/classical communication oblivious transfer cannot be used to construct post-quantum one-way functions with a relativizing proof.
