History

Please fill in your query. A complete syntax description you will find on the General Help page.
On parallel composition of zero-knowledge proofs with black-box quantum simulators. (English)
Quantum Inf. Comput. 9, No. 5-6, 513-532 (2009).
Summary: Let $L$ be a language decided by a constant-round quantum Arthur-Merlin (QAM) protocol with negligible soundness error and all but possibly the last message being classical. We prove that if this protocol is zero knowledge with a black-box, quantum simulator ${\cal S}$, then $L\in \text{BQP}$. Our result also applies to any language having a three-round quantum interactive proof (QIP), with all but possibly the last message being classical, with negligible soundness error and a black-box quantum simulator. These results in particular make it unlikely that certain protocols can be composed in parallel in order to reduce soundness error, while maintaining zero knowledge with a black-box quantum simulator. They generalize analogous classical results of {\it O. Goldreich} and {\it H. Krawczyk} [in: Automata, languages and programming, Proc. 17th Int. Colloq., Warwick/GB 1990, Lect. Notes Comput. Sci. 443, 268‒282 (1990; Zbl 0766.68033)]. Our proof goes via a reduction to quantum black-box search. We show that the existence of a black-box quantum simulator for such protocols when $L\notin \text{BQP}$ would imply an impossibly-good quantum search algorithm.