Physics – Quantum Physics
Scientific paper
2006-07-28
Quant. Inf. Comp. 9:513-532, 2009
Physics
Quantum Physics
18 pages; final version
Scientific paper
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 S, then L in 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 Goldreich and Krawczyk (1990). 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 BQP would imply an impossibly-good quantum search algorithm.
Jain Rahul
Kolla Alexandra
Midrijanis Gatis
Reichardt Ben W.
No associations
LandOfFree
On parallel composition of zero-knowledge proofs with black-box quantum simulators does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On parallel composition of zero-knowledge proofs with black-box quantum simulators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On parallel composition of zero-knowledge proofs with black-box quantum simulators will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-251047