EQP is the class of problems solvable deterministically using a quantum computer in polynomial time - that seems to me to be a good analogue to P, whereas BQP is the quantum analogue of BPP.
It doesn't seem like much is known about EQP! Just like BPP is not known to be contained in NP, is it known whether EQP \subseteq BQP \subseteq QMA? Is there a corresponding "Derandomization" of BQP into EQP?
What about the relationship of EQP and P?
Hi Henry,
One reason why EQP isn't studied more is that it's not even uniquely defined! In particular, which complexity class you get might depend on the specific quantum gates you assume are available. (For BQP, by contrast, the Solovay-Kitaev Theorem assures us that any universal set of quantum gates can approximate any other universal set to within exponentially small error.)
Still, you could forge ahead, fix a particular universal set of gates (say, Hadamard and Toffoli), and study the resulting class EQP.
In that case, it's not hard to construct an oracle relative to which BQP (and even BPP) are not contained in EQP -- for example, just take the MAJORITY function with a promised (1/3,2/3) gap in the Hamming weight. (You can prove that's not in EQP using the polynomial method.) Nor is it hard to construct an oracle relative to which EQP is not contained in BPP (Bernstein and Vazirani's Recursive Fourier Sampling problem, for example).
Outside the oracle world, the main result about EQP I know of is due to Mosca (don't have the reference offhand), who showed that, if you're careful to define EQP with a large enough set of gates, then it contains FACTORING (i.e., Shor's algorithm can be made zero-error). This gives pretty good evidence that EQP (suitably defined) is not contained in BPP.
I would guess that EQP ≠ BQP in the unrelativized world, but I don't have any evidence for that (and of course, it's possible that EQP equals BQP under some definitions but doesn't under others).
Scott gives the good answer that at the technical level, EQP is not uniquely defined. However, there are deeper issues of interpreting quantum complexity classes, and deciding which ones are contrived and which ones are natural.
To a computer scientist who first learns finite quantum mechanics, it may look like BQP is to BPP as EQP is to P. That was indeed the motivation for defining EQP. However, the analogy treats quantumness and randomness and separate generalizations of deterministic computation, and this isn't really true. A better viewpoint is that quantumness is a strengthened form of randomness. So the question "BQP is to BPP as (blank) is to P" is like the question "motorcycling is to bicycling as (blank) is to walking". It's a strange question.
The question "BQP is to EQP as BPP is to (blank)" is actually less strange, and my answer would not be P. Rather, you could define "EPP" to be the class of problems where, if the true answer is yes, the algorithm accepts with probability exactly 2/3; if the true answer is no, the algorithm accepts with probability exactly 1/3. This might not be a perfect analogy either, but it does show you how EQP is a contrived combination of probability and exactitude. If you use binary gates, then this definition of EPP is empty! The precise behavior of EPP is depends on algebraic coincidences. In order to have a viable definition (never mind natural), you should either change the probabilities to 1/4 and 3/4 (say), or you should use ternary circuits.
However, it dawned on me once that non-uniform EQP, or EQPn.u.,, is a well-defined complexity class. Because, in the non-uniform setting, you can allow all gates on two qubits. EQPn.u., is not necessarily a natural complexity class, but it isn't particularly less natural than non-uniformity itself. Similarly to a non-uniform classical circuit, you can show that a non-uniform quantum circuit of exponential size can express any unitary operator. A more robust interpretation of Mosca's and Zalka's theorem is that factoring is in EQPn.u.. It is also an interesting question to compare EQPn.u. to BQP/qpoly, and I don't know the answer.
Per Ricky Demer's remark, ZQP as defined in the Complexity Zoo is another EQP-like class that has the same shortcomings. However, I penciled into the Zoo a more interesting operational equivalent of ZPP that I called ZBQP. It's not a great name, but ZQP is already taken. My definition of ZBQP is that a quantum computer produces a certificate for either yes or no that can be checked by a deterministic verifier in polynomial time. And, the quantum computer succeeds in its task in polynomial time with high probability. If you use a classical randomness-enhanced computer instead of a quantum computer, you get the class ZPP. For example, any factoring-related decision question, such as whether a number is square-free, is in ZBQP, and this fact neither implies nor is implied by Mosca-Zalka.
