Quantum Chocolate Boxes
What kind of knowledge helps us peek inside black boxes?
David Deutsch is one of the fathers of quantum computation alongside Richard Feynman. Deutsch is a Fellow of the Royal Society of London, and is attached to the Centre for Quantum Computation at Oxford University.
Today we want to step back from quantum physics and focus on some quantum algorithms as situations involving ordinary queries, such as in the game “Twenty Questions.”
Deutsch formulated the quantum Turing machine (QTM) model in 1985, seven years after completing his doctorate in mathematical physics at Oxford. Ken was an onlooker as professors there turned aside Deutsch’s initial thoughts that a QTM could violate the Church-Turing Thesis, and Ken queried what all the fuss was about. Of course Peter Shor’s evidence for violating the polynomial-time Church-Turing thesis has decisively answered that query.
Besides developing the QTM, Deutsch devised the first algorithmic situations involving simple Boolean logic that illustrated extra powers of quantum computation. These were extended by Richard Jozsa and Daniel Simon and others, before Shor’s breakthrough on factoring. Ken and I are trying to understand these algorithms in a new way.
Like physicist Brian Greene whom we’ve recently cited, Deutsch is an author of a popular science book with title beginning The Fabric of… Deutsch’s book is The Fabric of Reality. Greene’s is The Fabric of the Cosmos, but Reality appears in its subtitle. The books have little in common—the closest overlap in Ken’s opinion is that both support the Many-Worlds Interpretation, which yields the ensemble of worlds on which Deutsch’s mathematical analysis is predicated. The math involves the statistics of how much information is needed to distinguish between possible worlds.
Queries and Chocolate Boxes
The famous tag line from the movie “Forrest Gump” is
Mama always said life was like a box of chocolates. You never know what you’re going to get.
Mama isn’t letting you read the index to the chocolates on the inside lid, and may not even let you look inside to see their shapes. However, if you can ask queries about what’s in the box and get useful answers, you can at least narrow your range of expectation.
Indeed, suppose Mama has two boxes.
Can you find a query that will enable you to decide between them? If you know in advance that one has pralines and the other does not, the query “Are you a praline?” will separate the boxes—chocolates in one will all answer “yes” and the other box, “no.” If you are fortunate enough to have access to a myriad of boxes, finding the right queries to narrow them down is itself a challenge.
Some underlying principles are familiar from the game “Twenty Questions.” If you have possibilities, then it is axiomatic that for every strategy that asks at most yes/no queries, there is at least one input that the algorithm will fail to distinguish. This follows from information theory, because the answers to the queries provide no more than bits of information.
A similar situation happens with matrices , when queries are made by giving argument vectors and requesting the answer . If you are trying to identify an unknown matrix , then you will generally need at least such queries. Each query gives you at most one dimension. With queries you can always succeed by presenting the standard basis vectors with the in the -th place, as the values give you all the entries of .
The question is: When can we do better? Deutsch’s insight was to isolate situations where quantum computations can obtain information with speed that appears surprising when the situation is approached with classical reasoning. The issue of speed is highlighted by Shor’s theorem, but we also wish to understand it without the “quantum magic” as an issue of how to frame queries. Note that by Holevo’s Theorem, quantum computers cannot actually cheat the above information-theoretic principles. What is the simplest explanation of what is going on?
The original Deutsch algorithm operates on a one-bit boolean function:
The goal is to tell whether the function is a constant or not, by asking only one query for a value of . There are one-bit Boolean functions, and two boxes we are trying to separate:
- One box, Box C for “Constant,” has the constant functions and defined by:
- The other box, Box B for “Balanced,” has the identity function and the NOT function :
Let us think of the value as saying whether is a light or dark chocolate, and the value as saying praline or fruit filling. Thus we have:
- Box C has a light praline and a dark fruit-filled chocolate.
- Box B has a dark praline and a light fruit-filled chocolate.
If we query the value , we are asking, are you light or dark? Both boxes have a chocolate that can answer “light” and one that can answer “dark,” so this query does not separate them. The same lack faces . It seems that to learn which box is in, we need to ask two questions. How can we do it with one?
We can apply an idea that has been important in computational complexity: (multi-)linear extensions of Boolean functions over various fields. Here the extensions are clear:
Now ask for the value ? All four chocolates give different answers, so given one answer by an unknown chocolate, you can tell which it is. In particular, the answers or tell you Box C, while or tells you Box B. If we only cared about distinguishing the boxes, we could query instead.
In a sense what we have done is asked a linear combination of the two possible queries, here . By linearity the result is the same linear combination of the answers of any individual function , so .
For a digression, you might wonder if you can still separate the two boxes when the chocolates in each box are allowed to give a fixed linear combination of their answers. For instance, suppose the chocolates in Box C and Box B elect to do the following linear combinations, which happen to have the same coefficients:
Then and are both the constant function with value for any . That is, mushing together a light praline and a dark fruit-filled gives the same result as a dark praline together with a light fruit-filled. No possible query can separate these two cases.
Does Deutsch’s Algorithm Do More?
Now Deutsch’s quantum algorithm uses a different linear extension—let’s see how different it is. The Boolean values and are represented by qubit values and . These in turn are formally two-dimensional standard-basis vectors
over the complex field . Now the relevant linear extensions of the four Boolean functions are the following matrices:
The analogue of the argument which worked last time is . We have the same distinctions as before:
In quantum, however, we have one more requirement—the computation must be reversible. This is violated above because the matrices and for the constant functions are not invertible. The standard remedy is to replace the original function by the two-dimensional function . Here on Boolean values is XOR (exclusive-or), while on arbitrary complex values we can put .
Thus Deutsch’s algorithm is technically about distinguishing the resulting functions from . We get these matrices:
Strangely, under this representation not has become the identity matrix, and all four are now permutation matrices. What does is interchange the first two co-ordinates, the latter two, and swaps both. Thus we can distinguish the four matrices by their values on a query like by seeing where the minus signs end up.
The quantum algorithm needs the query argument to be a unit vector, so is used. The state is easy to prepare by a few Hadamard transforms. To distinguish whether an unknown answer comes from in Box C or in Box B, we need only tell whether the minus signs in are in positions of the same or different parity. This can be done by a Hadamard transform on (part of) followed by a measurement. The details here are essentially similar.
Is there really more here than the linear extension idea?
The Deutsch-Jozsa Extension
Here the chocolates are multi-variable Boolean functions . Box C still has just the constant functions and , but Box B has every function on that is balanced, meaning that of the values are , and are .
If one is limited to queries for Boolean arguments then queries might still not be enough to tell Box C from Box B. The queries might all be answered , and yet could still be balanced. This was the point that Richard Jozsa added to Deutsch’s original observation, while one quantum query still suffices.
We can, however, simply see this in linear extensions. Give the argument , normalizing by dividing by or or whatever factor is desired. By linearity, the extension of every balanced Boolean function will give the same value strictly between and . This separates the boxes with one query.
The quantum version of this, however, involves vectors of -many qubits. The above encoding transforms them into ordinary vectors of exponentially many bits, , or with the reversibility trick. This puts extra heft into our main query: is exponential-sized notation the best explanation of what Nature is doing with a polynomial amount of effort?
Later we will illustrate with some other quantum algorithms, such as Simon’s algorithm, in which the goal is to separate the boxes of functions
over all , where is bitwise exclusive-or. When we have the box of all 1-to-1 functions, while the other boxes have functions that are 2-to-1 in a particular periodic manner. When is unknown this may require something like the Hadamard transform where even with our classical standpoint. Of course Simon’s algorithm was an inspiration for Shor, so this may isolate a critical difference.
How many quantum algorithms can be more-simply “explained” using more-compact linear or multi-linear algebra representations? Where do we hit a true boundary in the reach of polynomial-time classical methods?