Bounds on the Power of Constant-Depth Quantum Circuits

Physics – Quantum Physics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

We show that if a language is recognized within certain error bounds by constant-depth quantum circuits over a finite family of gates, then it is computable in (classical) polynomial time. In particular, our results imply EQNC^0 is contained in P, where EQNC^0 is the constant-depth analog of the class EQP. On the other hand, we adapt and extend ideas of Terhal and DiVincenzo (quant-ph/0205133) to show that, for any family F of quantum gates including Hadamard and CNOT gates, computing the acceptance probabilities of depth-five circuits over F is just as hard as computing these probabilities for circuits over F. In particular, this implies that NQNC^0 = NQACC = NQP = coC=P where NQNC^0 is the constant-depth analog of the class NQP. This essentially refutes a conjecture of Green et al. that NQACC is contained in TC^0 (quant-ph/0106017).

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Bounds on the Power of Constant-Depth Quantum Circuits 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 Bounds on the Power of Constant-Depth Quantum Circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds on the Power of Constant-Depth Quantum Circuits will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-717762

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.