Is there a complexity class “BQP without error”?

Question

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?)

Answer 1

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.