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?
Best Answer
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).