14
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Oct 9, 2010 at 13:46

2 Answers 2

16
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – user5810
    Oct 1, 2010 at 23:44
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 2, 2010 at 1:42
  • 1
    $\begingroup$ 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). $\endgroup$ Oct 2, 2010 at 19:45
  • 1
    $\begingroup$ @Vivek, It doesn't matter which fixed $k$ you choose, since (say) any 3-qubit gate can be decomposed exactly into $C$ 2-qubit gates for some fixed constant $C$. ($C$ can be computed exactly, but I'm too lazy to look up the answer -- or do the computation -- right now.) This, in fact, is a very good reason to choose this model of computation. You could also define EQP relative to topological quantum computation with some fixed set of anyons. I don't know if EQP with arbitrary 2-qubit gates contains all anyonic models of EQP. If it does, then this is good evidence that EQP is a robust class. $\endgroup$
    – Peter Shor
    Oct 9, 2010 at 14:47
  • 3
    $\begingroup$ @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. $\endgroup$
    – Peter Shor
    Oct 9, 2010 at 14:52
5
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ . . . as riding a Segway is to walking? $\endgroup$
    – Tracy Hall
    Oct 9, 2010 at 18:46
  • 2
    $\begingroup$ Yes, there you go, EQP is the Segway of complexity classes. :-) $\endgroup$ Oct 9, 2010 at 19:07
  • $\begingroup$ 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? $\endgroup$
    – Peter Shor
    Oct 10, 2010 at 12:25
  • $\begingroup$ 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. $\endgroup$ Oct 10, 2010 at 12:39
  • $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Oct 10, 2010 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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