http://swrc.ontoware.org/ontology#TechnicalReport
Classical verification of quantum computing with trusted center
en
京都大学基礎物理学研究所
NTTコミュニケーション科学基礎研究所
森前 智行
竹内 勇貴
The classical channel remote state preparation (ccRSP) is an important two-party primitive in quantum cryptography. Alice (classical polynomial-time) and Bob (quantum polynomial-time) exchange polynomial rounds of classical messages, and Bob finally gets random single-qubit states while Alice finally gets classical descriptions of the states. In [T. Morimae, arXiv:2003.10712], an information-theoretically-sound non-interactive protocol for the verification of quantum computing was proposed. The verifier of the protocol is classical, but the trusted center is assumed that sends random single-qubit states to the prover and their classical descriptions to the verifier. If the trusted center can be replaced with a ccRSP protocol while keeping the information-theoretical soundness, an information-theoretically-sound classical verification of quantum computing is possible, which solves the long-standing open problem. In this paper, we show that it is not the case unless BQP is contained in MA. We also consider a general verification protocol where the verifier or the trusted center first sends quantum states to the prover, and then the prover and the verifier exchange a constant round of classical messages. We show that the first quantum message transmission cannot be replaced with a ccRSP protocol while keeping the information-theoretical soundness unless BQP is contained in AM. Furthermore, we also study the verification with the computational soundness. We show that if a ccRSP protocol satisfies a certain condition even against any quantum polynomial-time malicious prover, the replacement of the trusted center with the ccRSP protocol realizes a computationally-sound classical verification of quantum computing. The condition is weaker than the verifiability of the ccRSP. At this moment, however, there is no known ccRSP protocol that satisfies the condition. If a simple construction of such a ccRSP protocol is found, the combination of it with the trusted center verification model provides another simpler and modular proof of the Mahadev's result. We finally show that the trusted center model and its variant with the ccRSP have extractors for low-energy states. For details, see [T. Morimae and Y. Takeuchi, arXiv:2008.05033]
The classical channel remote state preparation (ccRSP) is an important two-party primitive in quantum cryptography. Alice (classical polynomial-time) and Bob (quantum polynomial-time) exchange polynomial rounds of classical messages, and Bob finally gets random single-qubit states while Alice finally gets classical descriptions of the states. In [T. Morimae, arXiv:2003.10712], an information-theoretically-sound non-interactive protocol for the verification of quantum computing was proposed. The verifier of the protocol is classical, but the trusted center is assumed that sends random single-qubit states to the prover and their classical descriptions to the verifier. If the trusted center can be replaced with a ccRSP protocol while keeping the information-theoretical soundness, an information-theoretically-sound classical verification of quantum computing is possible, which solves the long-standing open problem. In this paper, we show that it is not the case unless BQP is contained in MA. We also consider a general verification protocol where the verifier or the trusted center first sends quantum states to the prover, and then the prover and the verifier exchange a constant round of classical messages. We show that the first quantum message transmission cannot be replaced with a ccRSP protocol while keeping the information-theoretical soundness unless BQP is contained in AM. Furthermore, we also study the verification with the computational soundness. We show that if a ccRSP protocol satisfies a certain condition even against any quantum polynomial-time malicious prover, the replacement of the trusted center with the ccRSP protocol realizes a computationally-sound classical verification of quantum computing. The condition is weaker than the verifiability of the ccRSP. At this moment, however, there is no known ccRSP protocol that satisfies the condition. If a simple construction of such a ccRSP protocol is found, the combination of it with the trusted center verification model provides another simpler and modular proof of the Mahadev's result. We finally show that the trusted center model and its variant with the ccRSP have extractors for low-energy states. For details, see [T. Morimae and Y. Takeuchi, arXiv:2008.05033]
AA12894105
研究報告量子ソフトウェア（QS）
2020-QS-1
8
1-6
2020-10-09
2435-6492