I was wondering if there is a complexity class for problems that can be solved efficiently by a quantum computer such that it always gives the right answer? For example the Deutsch-Josza algorithm never fails. Another way of asking would be: is there a class (call it Q) such that Q is to P what BQP is to BPP?

I guess classically the question also makes sense: is there a class for problems that can be solved efficiently by a computer with access to randomness and never making an error? (I suspect this is simply equal to P?)


Yes, it's called EQP (exact quantum polynomial) and is listed in the complexity zoo:

The same as BQP, except that the quantum algorithm must return the correct answer with probability 1, and run in polynomial time with probability 1. Unlike bounded-error quantum computing, there is no theory of universal QTMs for exact quantum computing models. In the original definition in [BV97], each language in EQP is computed by a single QTM, equivalently to a uniform family of quantum circuits with a finite gate set K whose amplitudes can be computed in polynomial time. See EQP_K. However, some results require an infinite gate set. The official definition here is that the gate set should be finite.

| cite | improve this answer | |
  • $\begingroup$ Thanks! Do you know the answer to the second part of my question as well? I could not find a EPP (exact probabilistic polynomial time) class or similar in the complexity zoo. $\endgroup$ – Sebastian Aug 7 '18 at 20:03
  • $\begingroup$ @Sebastian Isn't that just P? If the computer never makes an error, then all random values must work, so just use 000.... as the "random string" and you have something in P. $\endgroup$ – Craig Gidney Aug 7 '18 at 21:03
  • $\begingroup$ Yes, of course! I knew there was some obvious reason I overlooked that proves the classes are equal... $\endgroup$ – Sebastian Aug 7 '18 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.