Can Quantum Machines Do It All?
What keeps SAT out of BQP?
Dan Boneh is an expert on cryptography, especially the use of advanced number theory, such as the Weil pairing. He is famous for his seminal work on identity based encryption with Matt Franklin, which uses the Weil pairing.
Today I want to recall an old result Dan and I proved years ago and mix in a new result.
When Peter Shor announced in 1994 his instantly famous result that there is a quantum factoring algorithm that runs in polynomial time, many of us were amazed. We quickly read his paper, tried to understand why it worked, and followed the proofs step-by-step. It was—is still—a beautiful result.
Yet there was something about the result that troubled me. Perhaps no one else was troubled, but I did not really understand why the theorem was true. Yes I could follow the steps, yes I could explain the result to my students, but I did not really understand it.
I have discussed this phenomenon before: proofs are not just a mechanical means to move a statement from the conjecture pile to the proved pile. No, proofs are much more—they need to convey why the result is really true. They need to not seem magical, which Peter’s proof seemed to me. Proofs need to explain what is really happening.
Now I will say that Scott Aaronson’s well-noted explanation does this for the central idea, but back then Dan and I had no Scott to guide us. So we did something else.
In order to understand what was going on, Dan and I decided the best way would be to try and generalize Peter’s theorem. This is a standard method in mathematics: one way to really see what is happening is to generalize a theorem. Doing this can often shed new light on why the original theorem is true, and also can be interesting in its own right.
I could give countless examples of this method, it is used so often in math. Here is an example from number theory that is later explained better—I believe—by a classic result from group theory. Consider Fermat’s Little Theorem:
If is a prime and is an integer not divisible by , then
There are many proofs of this fundamental theorem. See our friends at Wikipedia here for several proofs: They have proofs based on: counting necklaces, using modular arithmetic, using the binomial theorem, and using dynamical systems.
Each proof gives a different insight into why must be prime, why cannot divide , and why the theorem is true.
The proof that I personally feel best explains what is happening is the one based on Lagrange’s Theorem:
Theorem: In any finite group, the order of an element divides the order of the group.
As an aside Joseph Lagrange did not prove his theorem, but only discussed special cases in 1771. It was finally proved by Pietro Abbati and published in 1803. The proof of Fermat’s Little Theorem now follows since when is prime, the set of numbers
form a group under multiplication modulo .
Hidden Linear Functions
Dan and I began to look at what we called the hidden linear problem. A function from has period provided
for all . We say that is m-to-one provided at most integers in the set map to the same value in . Note, if is one-to-one, then it is m-to-one with .
Let be a function from the integers to some arbitrary set . Say that f has hidden linear structure over provided there are integers and some function of period so that
for all integers . Further we say that is m-to-one provided is.
Our conjecture, which eventually became a theorem is:
Suppose that is a function that has a hidden linear structure over which is at most m-to-one. Assume the conditions:
- Let , so that and are at most polynomial in .
- Let be the smallest prime divisor of , so that .
For such a function , in quantum polynomial time in we can recover the values of modulo from an oracle for .
Note that the added conditions are critical. If the function were constant then there would be no way to reconstruct the ‘s: there must be some limit on how much it collapses. The second condition makes the values of the ‘s make sense modulo .
Look at our paper for details. The above theorem is strong enough to prove both factoring and discrete logarithm are in polynomial quantum time. This already indicated that we had made some progress. In Shor’s paper he uses different but similar arguments to handle factoring and the discrete logarithm. I personally thought that our proof helped me have a greater understanding of Shor’s brilliant work.
By the way, proving this theorem was hard. We used the same type of quantum algorithm that Peter did. But the fact that was not one-to-one created serious difficulties for us. Sometimes relaxing from a constant to `polynomial’ is a walk in the park, but not this time… I recall many times that one of us wanted to give up, but eventually we found the key trick. In the one-to-one case—the case that occurs in Peter’s theorems—there is an exponential sum that must be estimated. This sum is quite easy to handle. However, in the poly-to-one case the sum that arose was much harder to bound. We finally found a trick: when trying to bound a sum, change the sum. More on this another time.
Quantum Detection of Periods
Dan and I could also prove the following theorem:
Suppose that has period , and no smaller period. Also let be m-to-one. Add the conditions:
- Let , so that and are at most polynomial in .
- Let be the smallest prime divisor of , so that .
For such a function , in quantum polynomial time in we can recover the the period .
In Shor’s paper this theorem is essentially proved with : the so called bijective case. Obviously our result is a modest generalization to the case where the function can fail to be one-to-one, but a value in the range can only have a polynomial number of pre-images. Since then there have been much better improvements to the period solving problem. The current best results can recover the period provided the function has small auto-correlation—see this for details. Indeed for quantum algorithms that only use as an oracle, the current results are essentially best possible.
There is another reason that there may be no quantum algorithm for solving the general period finding problem. That is, given a small circuit—not an oracle—for the function , find its period. The reason is that the following is a theorem:
Theorem: The following two problems are equivalent via a random reduction:
- Finding an assignment to a instance.
- Finding the period of a Boolean valued function given by a small circuit.
Note, the lower bounds of quantum complexity theory are mostly based on a black box argument—they assume that only oracle access is available to the function whose period you want. There is no way known to show that they apply when the function is given by a circuit. This follows since if one could guess the period.
This will be an example of “evolving” a theorem from a trivial beginning to more-meaningful forms. At issue first are: how small is `small’ and what is the time on the reduction? Then the main issue will become, how close are the resulting cases of period-finding to ones that quantum algorithms can handle?
First we prove a version where `small’ means polynomial, the reduction is deterministic polynomial time, and the cases of periodicity involved are trivial. Namely, given an instance formula for , let be the circuit that on input an assignment outputs . If is not satisfiable then the function computed by is identically zero and so has period . If is true on the all- assignment then we say yes. Else, is satisfiable, so but for some other , so does not have period . It may not have any period, which is what makes this trivial. But we certainly know has period .
Now we want always to have a period, in the case where . This can be done by a simple padding trick. Let us use some number of variables defining a value , and define the circuit by . Then the function always has a period dividing —the question is whether that period is or something larger.
Thus finding the period of a periodic function given by poly-size circuits is -hard. Of course this is far from bijective—it is just 0-1 valued. If we could make bijective on this period, at least when the formula is satisfiable, then we would put into . How close can we come?
We start by arranging that when , with high probability at least one we run across has a period of some prime order , where finding for this is enough to say . Take the above circuit ; we wish to see if it has an input so that . We can assume that is unique, if it exists by using the famous result of Leslie Valiant and Vijay Vazirani.
A further simple random argument shows that we can also assume that the solution is a prime number. Here’s why: Consider flipping each input bit of independently: since the proportion of primes up to is order-of , this will map the to a prime number with reasonable probability, and we only need that our test succeeds on it once. In summary we can assume that is either unsatisfiable or has some prime as the unique solution.
Now let be the function
where is over all prime divisors of . Then it is easy to see the following: If is unsatisfiable, then is identically and has period . If there is a unique prime so that , then has period . Therefore we have reduced solving to period finding—where we can restrict attention to positive cases where the period has prime length and the function is except for a on the period start.
There is a small point, really a BIG point: the function does not have a poly-size circuit. In order to compute it we must factor into it prime factors and then check each one, , to see it makes . However, factoring, currently, has algorithms that run in time roughly order-of for . Thus will have circuits of this order of sub-exponential size, where the circuits themselves are also succinct. So long as `small’ means size for some known , we are OK.
With that point on hold, we can finally try to work on the period structure we have achieved. For arguments where , we would like to provide values in , or at least provide different values. Not knowing in advance may be a problem, but possibly inside the details of reducing to factoring in the previous paragraph, we may be able to assume that is known.
Here is where we pause and say we’ve at least posed a non-trivial research idea. We may work on it tomorrow and find it doesn’t go any further. We might not put it in a paper yet. But in a blog at least we can see how many ideas get their birth and first steps, where hard theorems successfully raised in the past may give some fostering.
Is in ? This is the motivating question.
What other ideas for creating and modifying periods might be relevant?