Is Factoring Really In BQP? Really?
Is the factoring problem in the complexity class BQP?
Peter Shor is the author of the paper on quantum computing—the paper that helped create an entire new research agenda. It was not the first paper on quantum computing, it certainly is not the last paper on quantum computing, but it probably is the most exciting one. Peter won the Nevanlinna Prize in 1998, among many other well deserved awards for this seminal work. The paper is known as the one that shows factoring is in
Today I have an embarrassingly simple question:
Is factoring in ?
This is one of those discussions that perhaps will show how wrong I can be. I try to get things right, but we are all human. Take a look at this Sunday New York Times’ chess column to see examples of chess blindness: one example is Magnus Carlsen, the top rated player in the world, making a “colossal blunder” that basically lost a Knight in one move. In my case the blunder may even be in a position where I made the right move 17 moves ago. Then I was involved with Umesh Vazirani and Ethan Bernstein over measurement and precision issues in their famous seminal paper on quantum Turing machine complexity, which formally defined . Perhaps my question today is just silly, but I am going to press forward anyway. Even if I am wrong, perhaps this will yield a nice intuitive answer to the other way of putting my question:
Is there a simple way of reducing search problems to decision problems in quantum computations, especially those that involve sampling?
Ken Regan and I have discussed this issue quite a bit and the comments to follow are joint. If this turns out to be just wrong or not even wrong, then I am probably the one to blame the most—if it’s a good question then thanks go to Ken.
If you know the quantum complexity class , then you can skip ahead. But we thought it is important to be sure we all are together. Recall is the counterpart of —does that help? The complexity class is the set of languages that are accepted by a probabilistic machine that runs in polynomial time. Further when the machine accepts it does so with probability at least , and when it rejects it also does so with probability at least . The consequence of forcing accept/reject to be bounded away from is that this makes the class of languages “nice.” Note if a language is in , then it is possible to determine if a string is in to high probability: just run the machine repeatedly with different random bits and take the majority answer.
The class is the same except that now the probabilistic machine is replaced by a polynomial time quantum one. The machine also must have the property: accept/reject is always with probability at least . This again is the reason for the bounded in the name.
Let’s turn to factoring, one of our favorite problems.
What Shor Proved
Shor showed that there is a polynomial time quantum computation that can find a factor of a number. It succeeds with a reasonable probability, and can be repeated, if needed, to find all the factors of the number.
This is a brilliant result, a wonderful result, a game changing result.
What Shor Did Not Prove
Peter’s paper does not directly prove that factoring is in . Yet everyone knows that factoring is now in . Right? The claim is everywhere: it’s on wiki pages, quantum sites, in lecture notes, and elsewhere. But we do not understand the proof—actually one of us, guess who, thinks there is a problems with the “proofs.”
Let’s look at the issue more carefully.
The factoring problem is about decomposing an integer into its prime factors. Thus given as the input, a factoring algorithm must output a list of primes
so that . Note if we insist that the list is ordered, then the answer is unique, since the integers have unique factorization. Technically this is a function: given an input it returns unique output. Thus if denotes the factoring function, some examples are:
Since factoring is a function we cannot say that it is in a complexity class—that makes no sense. It a type error like trying to take the square root of a character string: languages give only one bit and the factoring function returns many bits. This has nothing to do with the power of the complexity class, it is a straight consequence of their definition. Thus it is meaningless to say that is in or even in .
Shor’s paper itself speaks of only once, and only as a function class, but of course it is a language class. Thus we need to speak of factoring as a decision problem.
How To Encode Factoring As A Language
There are, as you probably know, many ways to encode a function into a language. This is, therefore, what people mean when they say “factoring is in .” Sounds easy—we just have to create a language that encodes and then show that the language is in . Some sites define the following language as their encoding of factoring. The language is:
Is this a reasonable language to encode factoring? It must satisfy, we claim, two properties:
- Given an there must be a polynomial time algorithm that computes if allowed access to as an oracle.
- Given an there must be a polynomial time algorithm that determines whether or not is in if allowed access to .
What these conditions really say is “the language captures factoring, but no more.”
The statement (1) is easily seen to be true: use binary search to find in polynomial time a factor of . Divide by this factor, and then continue until all the factors are found. Finally sort them and output the value of . Perfect—so far so good. The statement (2) is also easy to check.
Here is a proof that is in . It is from a site on quantum computing—we know you can probably find it, but we thought we would not name it directly.
The decision problem for factoring is in : given and , is there a non-trivial factor of n smaller than ? This is easily seen to be equivalent to having a polynomial-time quantum algorithm to find a non-trivial factor of any composite number , with probability of outputting such a factor of at least . Shor’s efficient quantum algorithm for factoring can be used to find factors in this way, and so it follows that the decision problem for factoring is in .
Color us confused, since we, especially one of us, does not follow this argument.
Let’s consider the argument carefully with replaced by polynomial time. In this case the argument is rock solid. Suppose that there is the new super factoring algorithm that given finds all its factors. Then here is the proof that factoring is in :
- Let be the input.
- Run the polynomial time algorithm and factor .
- Check if any .
- If yes, then output accept; otherwise, output reject.
This proves that factoring is in provided there is a polynomial time factoring algorithm. Rock solid. No problem, if the algorithms are classic.
If the factoring algorithm is Shor’s, then we do not see why this will be in . There are several reasons that we are confused, but the main one is simple: A quantum algorithm makes one measurement and gets one bit. The above algorithm uses Shor as a subroutine, and his algorithm makes a measurement of many qubits. This seems to be a problem. It says to us that the proof is not correct, that it does not prove that factoring as a language is in .
What Is Going On?
Now we hasten to mention that the aspect of Shor’s algorithm needing to measure many bits is the basis of Leonid Levin’s critique. This has been viewed as an issue of whether the quantum states created in Shor’s algorithm are really physically feasible, see Scott Aaronson here. We have a more facile query: what if you can only measure one qubit and must then start over?
Here is an abstract description of the problem we see that does not mention quantum. Suppose in the functional (i.e., search-problem) case we have a “black box” that when we press a button at time gives us a random function value . This is a “multi-valued function,” really a sampling procedure. We also have an efficient deterministic procedure such that with high probability over a sufficient number of samples, gives us the correct answer. Shor’s algorithm can be viewed this way, and so far that’s fine.
Now, however, suppose that in place of we have a black-box that gives only one bit according to a language representation of the multi-valued function. Thus instead of getting , we get only one bit pertaining to . The problem is that if we press the button again at time , we may get a bit that pertains to some other value that is not the same as . If we could guarantee that repeated taps on would stay focused on then we could apply search-to-decision and recover the function value . Our problem in a nutshell is that we do not see how Shor’s algorithm carries over to this setting.
We are confused. The whole idea of quantum computing, the whole reason it is more powerful, the whole source of excitement is due to new rules. Old simple tricks from classic computing do not work anymore. You cannot erase—computations must be reversible—is one good example.
We think there are three possible situations:
- We are completely wrong. The proof is correct and we are just confused. Quite possible—would not be the first time.
- We are right, but. The above “proof” is the one written down in many places, but all quantum experts are aware of how to fix it. The real proof is so trivial that no one has ever bothered to write it down. Again quite possible. But we would then suggest that it might be nice to write down a correct proof—no?
- We are right. There really is a missing argument here. Possible?
What references seem to be telling us is that the answer is deep within closure properties of rather than on the surface. But even here, the details cannot be found in the Wikipedia article on —rather the article on (a different class that equals ) proves such properties for and alludes that the proofs for are similar. Can we make this clearer?
Is factoring really in ? We believe that it is, and we believe that there is a proper proof of this fact. But we do not think the “proof” that is out there is correct. It would be great if we have simply overlooked a well-known proof. If you know one please tell us—somehow we think if this is the case we will be told.