Long story short, I share your beliefs (on quantum computers at least). I was just being a little pedantic

]]>The comments in your letter seem reasonable, and when aimed at a general audience, I understand a certain amount of brevity.

The tag line on you blog, however, “Quantum computers cannot solve NP-complete problems in polynomial time”, is a much stronger statement, and one I can’t see how you can be justified.

I am a physicist, and I know how hand wavy you think we, as a group, are, and I do not mean to annoy you with this comment. It’s just intended to point out something you have expressed a little stronger than you may have intended.

]]>All right, you can even say it rigorously this way:

Conjecture: BQP does not equal BPPFACTOR.

I am sure that this conjecture is true, that there are tons of problems in the set difference. I don’t even see a reason to expect other period-finding problems there such as discrete logarithm. Maybe a better conjecture is:

Conjecture: BQP does not equal BPPAHSP.

where “AHSP” means the abelian hidden subgroup problem as solved by the Simon-Shor-Kitaev algorithm. Even here Hallgren’s algorithm is a frustrating potential counterexample, because it is basically AHSP for a locally compact group (the real numbers) rather than a discrete group. Well, you could define AHSP to include Hallgren’s cases.

At this point it is good to wonder about the oracle protocol between BPP and AHSP. Of course it is fashionable to make the oracle a “promise oracle”, but a much better definition is to make it a fuzzy oracle that that returns randomized output. The oracle is handed an arbitrary subroutine that computes a putative hiding function, and then the AHSP oracle uses the known quantum algorithms to return an answer which is unhindered by promises but may be a fuzzy probability distribution.

You can see that the problem with this is that as long as you keep finding quantum problems that do have reasonable classical instances, you keep having to expand the oracle to make a conjecture that does not look stacked. A more sly observation is that most (or all?) convincing algorithms in BQP are in FH, i.e., they use only finitely many layers of non-permutation gates. I do not know if this is true of all of the wonderful Moore-Rockmore-Russell non-commutative Fourier transforms, but then, I also do not know important classical uses of those transforms. So you could ask this:

Conjecture: BQP does not equal BPPFH.

Again, you should let the FH oracle have fuzzy output.

I think that this conjecture is also extremely likely. Maybe the other regulars here can weigh in with reasons.

The computational power of BQP is well beyond the ability to factor.

(Actually, one interesting item in my marathon e-mail discussion/debate with Greg was the role of “verbal” rather than formal/mathematical formulations of conjectures in mathematics/physics.)

Cheshire Cat asked for evidence. A strong evidence, in my opinion, is that factoring requires only log-depth polynomial size quantum circuits (along with a classical computer). This was proved by Cleve and Watrous. The insight from Boolean circuit-complexity suggests that it is unlikely that log depth gives you full power. There are other reasons to believe 7.

]]>I think Scott means that AM, MA, and BPP have non-promise P-complete problems if they turn out to be equal to NP, NP, and P. Your point is that they have BPP-complete promise problems. Or in my conventions, the fuzzy-valued versions of AM and MA have pP-complete problems.

Note that the fuzzy version of MA is very easy to define. You have a pP-style stochastic Turing machine, to which Merlin supplies the certificate that maximizes the acceptance probability. That’s all that you have to say. You can, after that, apply the bounded-error operator “B” to make boolean-valued MA. AM has a similar definition, except of course that Merlin is a map from challenge strings to certificates.

]]>Currently, the only semantic classes for which we have a proof or positive evidence of complete problems โ IP, AM, MA, BPP, PostBQP, etc. โ are the ones for which we have a proof or evidence that they coincide with a syntactic class. For other semantic classes โ TFNP, SZK, BQP โ itโs hard to imagine what syntactic class they could coincide with.

I don’t follow this. What is the difference between complete problems for BQP (approximating the Jones polynomial at a root of unity) and complete problems for AM, MA, BPP? All of these are going to be promise problems, because they’re randomized classes [correct me if I’m wrong]. And I believe we have reasonable promise problems for all of these.

Of course, IP is defined as a randomized class, and it turns out to have determinstic complete problems. But this is (again) part of the miracle of IP=PSPACE.

]]>Well, the point is that existing proofs of completeness of problems is essentially syntactic.

]]>