Impossibility of Succinct Quantum Proofs for Collision-Freeness

Details Impossibility of Succinct Quantum Proofs for Collision-Freeness Impossibility of Succinct Quantum Proofs for Collision-Freeness

2011-01-02

arxiv.org/abs/1101.0403v1

Physics

Quantum Physics

9 pages

Scientific paper

We show that any quantum algorithm to decide whether a function f:[n]->[n] is a permutation or far from a permutation must make Omega(n^{1/3}/w) queries to f, even if the algorithm is given a w-qubit quantum witness in support of f being a permutation. This implies that there exists an oracle A such that SZK^A is not contained in QMA^A, answering an eight-year-old open question of the author. Indeed, we show that relative to some oracle, SZK is not in the counting class A0PP defined by Vyalyi. The proof is a fairly simple extension of the quantum lower bound for the collision problem.

Affiliated with

Also associated with

No associations

Rating

Impossibility of Succinct Quantum Proofs for Collision-Freeness 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 Impossibility of Succinct Quantum Proofs for Collision-Freeness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Impossibility of Succinct Quantum Proofs for Collision-Freeness will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-134027