I’m waiting for Scott’s “speedo quantum mechanics.”

]]>As I explained it in the Zoo page, there are at least two rigorous but inequivalent definitions of EQP. Some papers may implicitly use other definitions as well. Again, clarifying these definitions, and determining if they serve a good purpose, is more important than finding algorithms and oracle separations.

You certainly shouldn’t study EQP before you study some other objects in quantum complexity theory.

]]>Does this mean that EQP is not worth studying? From what I can gather from Greg’s comments, it seems that it’s not well-defined. Is this correct?

]]>I am also added my own medical concerns for PhP, and if I may, rephrasing the ones that Scott had. The “holographic principle” should be downplayed because it is not established physics, even though it is very reasonable conjectured physics.

]]>What Mosca and Zalka actually claim is an EQP algorithm for QFT and discrete logarithm with a known modulus. I think that they do not and cannot use Bernstein and Vazirani’s definition. As best I can tell, if the modulus p is part of the input, then they have a classical computer that (a) delivers a polynomial-time algorithm to generate the angles of some unitary gates, and (b) builds a quantum circuit.

Bernstein and Vazirani define EQP using a quantum Turing machine instead. It means, in effect, that an algorithm can only have one fixed gate set. There is no simple way to reconcile that with what Mosca and Zalka do. QFT_p cannot be in EQP in the Bernstein-Vazirani definition, because the field of definition of the unitary matrix entries grows with p.

Then, too, there probabily is no exact quantum universal TM in the Bernstein-Vazirani definition — they argue universality in the context of BQTIME rather than EQTIME. If you allow a classical computer to describe any quantum circuit, then of course that can be universal, but only for a cheap reason.

Another question is why the gate matrix entries have to be computable in P, rather than EQP (whatever that is in the end).

Another remark is that the distinction between BQP and EQP is not tenable in the context of fault tolerant quantum computation.

In my view, EQP is a tiger with goat’s feet and a serpent tail, and some suspicious sutures. The Zoo should warn visitors away from it. This story has been a big distraction for a lot of people.

]]>Mike Mosca and Christof Zalka showed in quant-ph/0301093 that factoring is in EQP, for some definition of EQP.

I hereby license you to make up any definition of EQP you want that leaves their result valid.

]]>Yes, I know the statement that the probabilities in EQP should be exactly zero or one. My question is, what is the gate set of an EQP circuit, and how would a generating Turing machine describe the circuits?

]]>Yes, indeed. If it had been mentioned in the zoo, I wouldn’t have even bothered asking the silly question!

Thanks for adding it. In fact, it can be added to the EQP section as well (the stronger result: there exists an oracle relative to which EQP is not in P/poly – this is the result that I had asked about). Also, there exists an oracle relative to which EQP is not contained in P^NP – that can be added as well. That result is due to Pruim and Green (appeared in IPL).

]]>Sure. First amplify, then hardwire a random string that works for all inputs of size n (as in the proof that BPP is in P/poly), then hardwire the // advice corresponding to that string.

]]>