Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
I remember Greg Kuperberg starting a discussion about EQP as a comment of the following post in Scott's blog: scottaaronson.com/blog/?p=96 . There you can also find the reference to the paper by Mosca and Zalka and Greg's comment to their result. –  Alessandro Cosentino Oct 9 '10 at 13:46
add comment

2 Answers

up vote 10 down vote accepted

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

share|improve this answer
Something similar that is uniquely defined is ZQP, the set of languages in NP intersect coNP such that (classical) proofs can be found by a BQP machine. –  Ricky Demer Oct 1 '10 at 23:44
Why on earth would you take just Hadamard and Toffoli? Clearly it is most natural to just choose all unitary operators acting on k or fewer qubits, for any fixed k > 2 you prefer. –  Vivek Shende Oct 2 '10 at 1:42
Thanks, Scott, for your answer! However, what did you mean by the MAJORITY function with the promised (1/3,2/3) gap? Computing this function is not in EQP relative to an oracle? If you know of the reference, that would be wonderful! –  Henry Yuen Oct 2 '10 at 5:29
Henry: I meant MAJORITY on N=2^n bits, with the promise that the Hamming weight of the oracle string is either less than N/3 or more than 2N/3. Certainly that oracle problem is in BPP (just sample a constant number of bits and output their majority). On the other hand, I claim that it's not in EQP. As I mentioned, the proof is that the polynomial representing the acceptance probability would necessarily have degree Omega(n). –  Scott Aaronson Oct 2 '10 at 19:45
@Scott: Why not allow arbitrary unitaries? Then we no longer have EQP $\subseteq$ BQP, but EQP $\subseteq$ BQP/poly, but I'd much rather have a non-uniform complexity class than a non-robust complexity class. –  Peter Shor Oct 9 '10 at 14:52
show 2 more comments

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.

share|improve this answer
. . . as riding a Segway is to walking? –  Tracy Hall Oct 9 '10 at 18:46
Yes, there you go, EQP is the Segway of complexity classes. :-) –  Greg Kuperberg Oct 9 '10 at 19:07
Here's a test of whether EQP$_\mathrm{n.u.}$ is truly a robust class. For any theory of anyons $A$ (see topological quantum computing), you can define a complexity class EQP$_A$ for that theory (the set of problems which can be solved deterministically by creating, braiding and fusing those anyons). Is EQP$_A$ $\subseteq$ EQP$_\mathrm{n.u.}$ for all theories of anyons? –  Peter Shor Oct 10 '10 at 12:25
Fusion is a kind of measurement, so I'm not sure what you mean at the rigorous level. Let me modify this question a little bit. (And I see that you suggested EQP$_{n.u.}$ in your comment above.) Suppose that you have an anyonic theory with all k-particle unitaries for some k, including unitaries that can be assembled from fusion and unfusion, and fusion is an allowed post-measurement. Then I think that you get exactly the same EQP$_{n.u.}$ for every non-abelian anyonic theory. –  Greg Kuperberg Oct 10 '10 at 12:39
I'm confused by what you mean by an anyonic theory with all $k$-particle unitaries. And wouldn't some anyonic theories be less powerful than EQP$_{\mathrm{n.u.}}$, because even some non-abelian anyons are polynomial-time computable. I suspect that both of these questions have the same answer, but I don't see what it means to add arbitrary $k$-particle unitaries to a given theory of anyons. –  Peter Shor Oct 10 '10 at 22:55
show 2 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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