More Quantum Chocolate Boxes
Unwrapping the layers between classical and quantum?
Daniel Simon discovered the first quantum algorithm that yielded an oracle separation of from an exponential-time analogue of . Even more, his algorithm was the direct inspiration for Peter Shor’s factoring algorithm, which roughly speaking replaced Simon’s use of the Hadamard transform with the quantum Fourier transform. Apologies to Christopher Marlowe, Shor’s algorithm was the one with “the phase that launched a thousand scrips” (scrips meaning papers, funding, you name it).
Today we wish to revisit the question of solving Simon’s problem by a classical algorithm. We also ask whether the classical algorithms are being given a fair counterpart to the following principle, which the quantum algorithms take for granted:
Given an invertible function, there is a unitary matrix that implements the function as a permutation matrix, and moreover: the matrix is efficiently constructible, in a way that is realizable by a physical system.
Let’s call this the quantum black box assumption (QBB). Without it there is no Deutsch(-Jozsa) or Simon or Grover algorithm, and in the details, no Shor algorithm either (compare discussion here). Without it there are no quantum algorithms for anything interesting, since it is a central assumption required by all them. It is justified by polynomial-time universality theorems for quantum circuits, but is it really innocuous? And since the matrix computes the function at any algebraic input, should not the representation for the classical algorithms do the same?
Ironically, Simon himself is not sanguine on the prospects of quantum computers. He works on Windows security at Microsoft, and was among the many builders of the Transport Layer Security (TLS) protocol. In March 2009 he contributed comments noted here, including this statement:
Basically, there is one thing that quantum computers [are known to do] better than classical computers. Because this one thing happens to lead to polynomial-time algorithms for integer factoring and discrete log, quantum computers have been bandied about as an incredible new computing technology, but the truth is that this one thing is really very limited in scope, and in a decade and a half, nobody’s found another significant application for it.
Moreover, there are lots of (admittedly informal) reasons for believing that quantum computers can’t really do anything interesting beyond this one thing.
Simon would add, following the title of his own blog, “I could be wrong.” We could be wrong likewise, but let’s first look at Simon’s problem.
Simon’s Distinguishing Problem
We describe Simon’s problem with the same chocolate-box metaphor we recently used here. Again we are trying to identify a Boolean function , except this time maps into itself, i.e., the output is an -bit string not just 0 or 1. Again we are told that is a special function that belongs to a limited number of “boxes.” Here we have one box for every “hidden” string :
As usual means bitwise exclusive-or. When is the all-zero vector, the condition holds iff is 1-to-1, and so box includes all that are bijectively onto . The other boxes, however, comprise functions that are exactly 2-to-1 in a particular periodic way.
The input to Simon’s problem is an oracle for an unknown member of one of the boxes. The first goal is to distinguish the case from being in one of the other boxes. The full goal is to tell which box, i.e., to compute with high probability. Simon’s beautiful result is that this can be done by a polynomial time quantum algorithm.
As in our previous post, is given as an operator on qubits, such that on input padded with -many 0’s, outputs the pair . The point of necessity is that this computation is 1-to-1 even when itself is 2-to-1.
The key to understanding a quantum algorithm is to look at the vectors and unitary operators. All in this case are from real Hilbert spaces, or if you prefer finite dimensional Euclidean spaces. We will use capital letters for our vectors, and script letters for our matrices. We also avoid subscripts and use the simple notion to denote the coordinate of the vector . If you like we are viewing vectors as functions.
The Hadamard matrix is denoted by where is always . We also use
to denote the row and column of the matrix . Note, the important fact that
where is the boolean inner product of and . If is a vector, then is defined by
Simon’s Quantum Algorithm
The first key insight is that we can use a quantum algorithm to efficiently construct a vector so that
when and is zero otherwise. The is just the concatenation of the numbers and . Essentially we are using two Hilbert spaces that we put together by a tensor product. Note: this is where the QBB assumption is invoked—without this assumption the algorithm cannot even get started—since where is a -qubit state prepared as the equal superposition of basis states in the first qubits, all with zeroes in the second qubits.
Then we can apply the matrix to and yield the vector . The key is that
This is what is meant by applying the Hadamard only to the coordinate.
We need to analyze what the amplitude is of the coordinates . There are two cases.
In this case is one-to-one. Let see what is then. As the sum runs over values the only time is non-zero is when . This only happens once, and therefore
Thus any measurement of will yield an -part that is simply a random uniform number in the range to . After a number of these samples it will be clear that there is no . Put another way, viewing the samples as binary vectors rather than numbers, after samples we expect to have independent vectors.
In this case is two-to-one. Let see what is in this case—it is much more interesting. If has no pre-image under , then . If it has a pre-image it also has a pre-image . In this case
This is either or depending on whether or not . This gives an equation on over the boolean finite field. That is, the sample gives a random in the perpendicular subspace to . After a similar number of samples we have equations by which to solve for and solve the problem.
Quantum Versus Classical Settings
All discussions of Simon’s algorithm immediately point out that there is no classical algorithm that can solve the problem without an exponential number of calls to the black box for . This is easy to prove and is unassailable—it is correct. Case closed: quantum is more powerful than classical.
Well of course that is not quite true. If the black box for were presented by a circuit of polynomial size, then the argument that a polynomial amount of classical computing is inadequate would require the assumption that . So the claim that quantum is stronger than classical can be true if the conventional wisdom is true, but who knows?
We suggest that the proper comparison may involve granting the classical setting a multi-linear extension of to use as the black box. This is not restricted to Boolean queries, but can be evaluated on points like that strike us as analogous to Hadamard-transformed states given to . One rub is that if is an unsatisfiable Boolean formula, and comes out to be the all-zero function, recognizing this fact is -hard. If seems too much to assume, compared to the QBB, we are reminded of a common story where one child makes hands like a tank approaching another child, and the second child swoops a hand down like a missile to blow up the tank.
Child 1: “Where did you get that missile?”
Child 2: “Well, where did you get that tank?”
The Classical Black Box Assumption
To make our assumption concrete, we settle on this extension of a Boolean function to a mapping from to :
That is, is the product of factors for and for . For instance, when and ,
The effect is that over Boolean arguments , is zero except when , so that for all Boolean .
Of course for other arguments , can be a sum of exponentially many terms, and it is not evident that can be regarded as easily-given as is. Indeed that is the point. But let’s make the assumption clear:
Given a function with a polynomial size Boolean circuit, there is an arithmetic circuit that is also polynomial in size and computes .
This assertion itself does not force , though obtaining the arithmetic circuit might do so. We will call this assumption the classical black box assumption (CBB). It seems unlikely to be true, but we cannot rule it out immediately. We can also compare with the “Arithmetic Checkability” axiom of this paper by Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova.
And for a companion question, is the QBB assumption really true in prospect? Why is it fair to have a quantum linear operator that can be applied to other quantum states besides the 0-1 basis states, and not be able to do so with a classical multi-linear extension? Or is this where the first power of quantum over classical resides?
Using CBB for Simon’s Problem
Can we use the CBB assumption to create a classical algorithm for Simon’s problem? We would like to report that the answer is yes, but we leave it open. It seems likely to be true, yet we cannot prove it. Still we find the question interesting in its own right, and in shedding new light on QBB.
The goal now is to show that evaluating at the right values will yield information about the structure of , just as Simon’s algorithm uses QBB to get information about . Here is just a note on how to start, and some difficulties that we hope you can help us resolve. When , the “schematic terms” all give value . It follows that whenever is 1-to-1,
When is 2-to-1, it is possible that . If it doesn’t, then we instantly deduce . Whether it does depends completely on the range of , not on the value of . When , this happens exactly when the range of is , or when it is .
Our approach now is to ask, what happens on arguments whose entries are or , perhaps chosen at random? For such we have
where means the number of places where and agree in the sense that and , or and . This is the same as the Hamming weight of using the bitwise complement of , and it may help that .
Whenever is 2-to-1, is a sum over pairs with of binomials
The question is finally whether we can exploit divisibility properties of these related sums of two powers of to tell this apart from the case where is 1-to-1. In the latter case, for a rule that chooses or randomly, it seems by symmetry that we need only analyze this for being the identity function on . One can try arguments with entries with or , and/or other definitions of .
One can also try to imitate the quantum proof further, working with linear extensions of on bits, so that the “line” between and , which equals , has constant value in the last coordinates. The idea would be to generate random values with each randomly chosen as above, and distinguish the 1-to-1 and 2-to-1-with-period- cases according to whether they span or only dimensions. Does this work?
There are two technical open problems. Is the CBB assumption wrong? Can one prove that there is an so that must have large complexity? Also assuming the above version of CBB, or any reasonable version, can we prove that there is a classical algorithm that solves Simon’s problem?
Our point is that if the classical-vs.-quantum difference persists with our extension of Simon’s problem, it must reside either in the CBB, or in the problem itself under more powerful conditions. Is this a helpful layering of the issues?
[fixed opening sentence on nature/priority of Simon’s oracle separation][added reference to this discussion][improved exposition of algorithm]