Factoring Is In BQP
Further discussions of the proof that factoring is in BQP
Scott Aaronson is a, if not the, world expert on quantum computation. He writes, as you all know, one of the best blogs on quantum and many more things.
Today I and Ken want to make a short summary on the last discussion: is factoring really in . Yes it is. But I want to explain some more of the issues behind the discussion.
Here is Scott’s comment I received late last night—I have fixed some minor things to make it typeset in LaTeX.
Scott’s comment can be redacted to its gist as follows:
“[You feel that as a matter of pedagogy, expositions of Shor's proof should directly show] that some decision problem related to factoring has polynomial-size quantum circuits, rather than giving poly-size circuits for the factoring search problem and then appealing to well-known closure properties of (as shown, for example, in the BBBV paper) to get that the decision version is also in I strongly disagree I think a fairer standard is that something is `proved’ when the gaps are small enough that any expert (or enterprising student), working in good faith, can fill them without difficulty. And that standard is more than met by Shor’s algorithm, as evidenced (for example) by the thread above.”
Why We Made The Post
I am not for being pedantic nor for excessive formalism. I have written papers arguing against that for years—see my paper on social processes, with Rich DeMillo and Alan Perlis. The reason for the post was to make a couple of points: (I) that factoring is in is a very important theorem; (II) as such it should have a proof that is on the web and available to all. The “A” answer that no one made was: “here is a url to the proof in X’s textbook/paper/wiki etc.” The answer that we got is: “yes the simple argument that is sometimes made is not the real one, but here is the correct one.”
I think that there is a big difference between being pedantic and simply wanting to see a sketch of what is arguably one of the landmark results in theory. I do agree the comments together have answered the issue, but I would humbly suggest that someone write down a short sketch of the proof so all can see it. Scott is the expert of experts in quantum computing, and I meant no disrespect to Scott or anyone else. I just wanted to see how this fundamental result is proved. So yes it is true. I hope you agree that having a good pointer for this critical result is not being pedantic.
We meant no disrespect to Scott or any of the experts in quantum computing, and we are grateful that several including Michael Nielsen, co-author of the signature quantum-computing textbook, provided answers. We do agree the comments together have answered the issue, and we will summarize the most important points here. However, I humbly suggest that it be reflected in prominent current materials so that memory in the field is kept fresh rather than going back 15–17 years (not “moves”) as my introduction had alluded.
We perceived gaps in both directions of the standard polynomial equivalence between search problems and decision problems. Going from decision to search, the issue was, can we decide whether without using Shor to calculate the prime factors of in a way that overtly requires measuring many qubits? The answer is yes, and the idea was given with some examples in comments by Nielsen beginning here. We summarize as follows:
Think first of a classical algorithm that uses Shor’s factoring algorithm as an oracle. runs and in the end produces one output bit as its answer. Computations by submit queries and receive multiple bits from the oracle. We may regard these bits as having come directly from a large-scale measurement. The point is that we can now transform itself into a quantum algorithm that keeps those bits in superposition, without measuring. The output bit of then becomes a quantum bit in . This is all we need to measure, so meets the formal definition of a algorithm that we were targeting. This works seamlessly because the classical body of can be coded with reversible gates that apply equally well in the quantum circuit for because everything is linear. This also proves that .
In brief, the point is that if all you desire is a 1-bit answer, then the “Principle of Deferred Measurement” extends to say that one can avoid the postponed measurements altogether, except for one bit.
The other direction, reducing search to decision, still holds more than pedagogic interest for us.
A Mathematical Problem?
Before all the answers, I had started to think about the following question: Suppose that I had a quantum computer that could just execute the quantum part of Shor’s algorithm. But for some physical limitation at the last step I could only measure and therefore get one bit of information. Can a classical algorithm use just this quantum subroutine to still find the factors? More precisely, at the end there is a large register that Shor’s algorithm measures all of the bits. Suppose now you can choose which bit to measure, but only that one. Can you still use this subroutine to factor?
The reason I thought it might be interesting is this: perhaps it is easier to build such a device, perhaps not. In any event trying to factor with this limited subroutine strikes me as an interesting challenge. Since Shor’s algorithm puts different random values in the register each time it is run, it is not obvious to me that this can be made to work.
Note the plural on proofs. A proof does much more than check off that something is true. This holds whether the proof is barely outlined, sketched, or even stated in quite precise detail. Proofs do more than prove.
Michael Atiyah, a winner of the Fields Medal in 1966, has made a number of interesting comments on the role of proof. One of his great results is the so called Atiyah-Singer Index Theorem. Atiyah says:
I think it is said that Gauss had ten different proofs for the law of quadratic reciprocity. Any good theorem should have several proofs, the more the better. For two reasons: usually, different proofs have different strengths and weaknesses, and they generalize in different directions; they are not just repetitions of each other. And that is certainly the case with the proofs that we came up with. There are different reasons for the proofs, they have different histories and backgrounds. Some of them are good for this application, some are good for that application. They all shed light on the area. If you cannot look at a problem from different directions, it is probably not very interesting; the more perspectives, the better!
We agree. We believe that the fact that factoring is in is super important, and deserves to have as many different proofs as possible.
We guess the first open problem today is “was it pedantic to ask for a full proof that factoring is in ?”
But to ask another: In what sampling situations where we compute a predicate of strings output by a black-box random generator , can we still compute whp. in time given only one (selected) bit of each answer ?