Paper 2020/1391

Interactive Proofs for Quantum Black-Box Computations

Jiang Zhang, Yu Yu, Dengguo Feng, Shuqin Fan, Zhenfeng Zhang, and Kang Yang

Abstract

In this paper, we initiate the study of interactive proofs for the promise problem $\mathsf{QBBC}$ (i.e., quantum black-box computations), which consists of a quantum device $\mathcal{D}(|x\rangle |y\rangle) =|x\rangle D_x(|y\rangle)$ acting on $(n+m)$ qubits for some self-joint unitary $D_x$ (i.e., $D_x(D_x(|y\rangle)) = |y\rangle$), a classical device $\mathcal{R}_F$ deciding the input-output relation of some unknown function $F:\{0,1\}^n \rightarrow \{0,1\}^m$, and two reals $0< b < a \leq 1$. Let $p(\mathcal{D},x) = \| |x,F(x)\rangle \langle x,F(x)| \mathcal{D}(|x\rangle |0^m\rangle)\|^2$ be the probability of obtaining $(x,F(x))$ as a result of a standard measurement of the $(n+m)$-qubit state returned by $\mathcal{D}$ on input $|x\rangle |0^m\rangle$. The task of the problem $\mathsf{QBBC}(\mathcal{D},\mathcal{R}_F,a,b)$ is to distinguish between two cases for all $x\in \{0,1\}^n$: \\ $\bullet$ YES Instance: $p(\mathcal{D},x) \geq a$; $\bullet$ NO Instance: $p(\mathcal{D},x) \leq b$. First, we show that for any constant $15/16< a \leq 1$, the problem $\mathsf{QBBC}(\mathcal{D},\mathcal{R}_F,a,b)$ has an efficient two-round interactive proof $(\mathcal{P}^{\mathcal{D}},\mathcal{V}^{\mathcal{R}_F})$ which basically allows a verifier $\mathcal{V}$, given a classical black-box device $\mathcal{R}_F$, to efficiently verify if the prover $\mathcal{P}$ has a quantum black-box device $\mathcal{D}$ (correctly) computing $F$. This proof system achieves completeness $\frac{1 + a}{2}$ and soundness error $\frac{31}{32} + \frac{\epsilon}{2} + \mathsf{negl}(n)$ for any constant $\max(0,b-\frac{15}{16})<\epsilon<a - \frac{15}{16}$, given that the verifier $\mathcal{V}$ has some (limited) quantum capabilities. In terms of query complexities, the prover $\mathcal{P}^\mathcal{D}$ will make at most two quantum queries to $\mathcal{D}$, while the verifier $\mathcal{V}^{\mathcal{R}_F}$ only makes a single classical query to $\mathcal{R}_F$. This result is based on an information versus disturbance lemma, which may be of independent interest. Second, under the learning with errors (LWE) assumption in (Regev 2005), we show that the problem $\mathsf{QBBC}(\mathcal{D},\mathcal{R}_F,a,b)$ can even have an efficient interactive proof $(\mathcal{P}^{\mathcal{D}},\mathcal{V}^{\mathcal{R}_F})$ with a fully classical verifier $\mathcal{V}$ that does not have any quantum capability. This proof system achieves completeness $\frac{1 + a}{2}-\mathsf{negl}(n)$ and soundness error $\frac{1+b}{2} + \mathsf{negl}(n)$, and thus applies to any $\mathsf{QBBC}(\mathcal{D},\mathcal{R}_F,a,b)$ with constants $0< b<a \leq 1$. Moreover, this proof system has the same query complexities as above. This result is based on the techniques introduced in (Brakerski et al. 2018) and (Mahadev 2018). As an application, we show that the problem of distinguishing the random oracle model (ROM) and the quantum random oracle model (QROM) in cryptography can be naturally seen as a $\mathsf{QBBC}$ problem. By applying the above result, we immediately obtain a separation between ROM and QROM under the standard LWE assumption.

Note: This is a major update of https://eprint.iacr.org/2019/1101 with new results.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Quantum ComputationInteractive ProofsROMQROMSeparations
Contact author(s)
jiangzhang09 @ gmail com
yuyu @ yuyu hk
feng @ tca iscas ac cn
shuqinfan78 @ 163 com
zfzhang @ tca iscas ac cn
yangk @ sklc org
History
2020-11-19: last of 3 revisions
2020-11-10: received
See all versions
Short URL
https://ia.cr/2020/1391
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1391,
      author = {Jiang Zhang and Yu Yu and Dengguo Feng and Shuqin Fan and Zhenfeng Zhang and Kang Yang},
      title = {Interactive Proofs for Quantum Black-Box Computations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1391},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1391}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.