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:

Theorem:
If \({p}\) is a prime and \({a}\) is an integer not divisible by \({p}\), then

$$a^{p-1} \equiv 1 \bmod p.$$

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 \({p}\) must be prime, why \({p}\) cannot divide \({a}\), 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 \({p}\) is prime, the set of numbers

$$\{ 1,2,3,\dots,p-1\}$$

form a group under multiplication modulo \({p}\).

Hidden Linear Functions

Dan and I began to look at what we called the hidden linear problem. A function from \({h: \mathbb{Z} \rightarrow S}\) has period \({q}\) provided

$$h(x + q) = h(x)$$

for all \({x}\). We say that \({h}\) is m-to-one provided at most \({m}\) integers in the set \({0,1,2,\dots,q-1}\) map to the same value in \({S}\). Note, if \({h}\) is one-to-one, then it is m-to-one with \({m=1}\).

Let \({f(x_{1},\dots,x_{k})}\) be a function from the integers \({\mathbb{Z}^{k}}\) to some arbitrary set \({S}\). Say that f has hidden linear structure over \({q}\) provided there are integers and some function \({h}\) of period \({q}\) so that

$$f(x_{1},\dots,x_{k}) = h(x_{1} + \alpha_{2}x_{2} + \cdots + \alpha_{k}x_{k})$$

for all integers \({x_{1},\dots,x_{k}}\). Further we say that \({f}\) is m-to-one provided \({h}\) is.

Our conjecture, which eventually became a theorem is:

Theorem:
Suppose that \({f(x_{1},\dots,x_{k})}\) is a function that has a hidden linear structure over \({q}\) which is at most m-to-one. Assume the conditions:

  1. Let \({n = \log q}\), so that \({m}\) and \({k}\) are at most polynomial in \({n}\).
  2. Let \({p}\) be the smallest prime divisor of \({q}\), so that \({m<p}\).

For such a function \({f}\), in quantum polynomial time in \({n}\) we can recover the values of \({\alpha_{2},\dots,\alpha_{k}}\) modulo \({q}\) from an oracle for \({f}\).

Note that the added conditions are critical. If the function \({h}\) were constant then there would be no way to reconstruct the \({\alpha}\)‘s: there must be some limit on how much it collapses. The second condition makes the values of the \({\alpha}\)‘s make sense modulo \({q}\).

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 \({h}\) 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:

Theorem:
Suppose that \({h:\mathbb{Z} \rightarrow S}\) has period \({q}\), and no smaller period. Also let \({h}\) be m-to-one. Add the conditions:

  1. Let \({n = \log q}\), so that \({m}\) and \({k}\) are at most polynomial in \({n}\).
  2. Let \({p}\) be the smallest prime divisor of \({q}\), so that \({m<p}\).

For such a function \({h}\), in quantum polynomial time in \({n}\) we can recover the the period \({q}\).

In Shor’s paper this theorem is essentially proved with \({m=1}\): 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 \({h}\) has small auto-correlation—see this for details. Indeed for quantum algorithms that only use \({h}\) as an oracle, the current results are essentially best possible.

SAT

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 \({h}\), find its period. The reason is that the following is a theorem:

Theorem: The following two problems are equivalent via a random reduction:

  1. Finding an assignment to a \({\mathsf{SAT}}\) instance.
  2. 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 \({h}\) is given by a circuit. This follows since if \({\mathsf{P} = \mathsf{NP}}\) 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 \({\phi}\) for \({\mathsf{SAT}}\), let \({C}\) be the circuit that on input an assignment \({x}\) outputs \({\phi(x)}\). If \({\phi}\) is not satisfiable then the function \({h}\) computed by \({C}\) is identically zero and so has period \({1}\). If \({\phi}\) is true on the all-\({0}\) assignment then we say yes. Else, \({\phi}\) is satisfiable, so \({h(0^n) = 0}\) but \({h(x) = 1}\) for some other \({x}\), so \({h}\) does not have period \({1}\). It may not have any period, which is what makes this trivial. But we certainly know \({\phi \notin \mathsf{SAT} \iff h}\) has period \({1}\).

Amplifying Periods

Now we want \({h}\) always to have a period, in the case where \({\phi \in \mathsf{SAT}}\). This can be done by a simple padding trick. Let us use some number \({n' > n}\) of variables defining a value \({y}\), and define the circuit \({C'}\) by \({C'(y) = C(y \bmod{2^n})}\). Then the function \({h}\) always has a period dividing \({2^n}\)—the question is whether that period is \({1}\) or something larger.

Thus finding the period of a periodic function \({h}\) given by poly-size circuits is \({\mathsf{NP}}\)-hard. Of course this \({h}\) is far from bijective—it is just 0-1 valued. If we could make \({h}\) bijective on this period, at least when the formula is satisfiable, then we would put \({\mathsf{SAT}}\) into \({\mathsf{BQP}}\). How close can we come?

We start by arranging that when \({\phi \in \mathsf{SAT}}\), with high probability at least one \({h}\) we run across has a period of some prime order \({q}\), where finding \({q}\) for this \({h}\) is enough to say \({\phi \in \mathsf{SAT}}\). Take the above circuit \({C}\); we wish to see if it has an input \({x}\) so that \({C(x)=1}\). We can assume that \({x}\) 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 \({x}\) is a prime number. Here’s why: Consider flipping each input bit of \({C}\) independently: since the proportion of primes up to \({2^n}\) is order-of \({1/n}\), this will map the \({x}\) to a prime number with reasonable probability, and we only need that our test succeeds on it once. In summary we can assume that \({C(x)}\) is either unsatisfiable or has some prime \({q}\) as the unique solution.

Now let \({h(x)}\) be the function

$$\bigvee_{p | x} C(p),$$

where \({p}\) is over all prime divisors of \({x}\). Then it is easy to see the following: If \({C(x)}\) is unsatisfiable, then \({h}\) is identically \({0}\) and has period \({1}\). If there is a unique prime \({q}\) so that \({C(q)=1}\), then \({h}\) has period \({q}\). Therefore we have reduced solving \({\mathsf{SAT}}\) to period finding—where we can restrict attention to positive cases where the period has prime length and the function is \({0}\) except for a \({1}\) on the period start.

There is a small point, really a BIG point: the function \({h(x)}\) does not have a poly-size circuit. In order to compute it we must factor \({x}\) into it prime factors and then check each one, \({p}\), to see it makes \({C(p)=1}\). However, factoring, currently, has algorithms that run in time roughly order-of \({\exp(n^\epsilon)}\) for \({\epsilon = 1/3}\). Thus \({h}\) will have circuits of this order of sub-exponential size, where the circuits themselves are also succinct. So long as `small’ means size \({\exp(n^\epsilon)}\) for some known \({\epsilon}\), we are OK.


With that point on hold, we can finally try to work on the period structure we have achieved. For arguments \({w}\) where \({h(w) = 0}\), we would like to provide values in \({\{0,2,\dots,q-1\}}\), or at least provide \({w}\) different values. Not knowing \({q}\) 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 \({q}\) 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.

Open Problems

Is \({\mathsf{SAT}}\) in \({\mathsf{BQP}}\)? This is the motivating question.

What other ideas for creating and modifying periods might be relevant?