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 ${2^{20} + 1}$ possibilities, then it is axiomatic that for every strategy that asks at most ${20}$ 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 ${20}$ bits of information.

A similar situation happens with matrices ${A}$, when queries are made by giving argument vectors ${x}$ and requesting the answer ${Ax}$. If you are trying to identify an unknown ${20 \times 20}$ matrix ${A}$, then you will generally need at least ${20}$ such queries. Each query gives you at most one dimension. With ${20}$ queries you can always succeed by presenting the standard basis vectors ${x_i = (0,0,\dots,0,1,0,\dots,0)}$ with the ${1}$ in the ${i}$-th place, as the values ${A x_i}$ give you all the entries of ${A}$.

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 Problem

The original Deutsch algorithm operates on a one-bit boolean function:

$\displaystyle f: \{0,1\} \rightarrow \{0,1\}.$

The goal is to tell whether the function is a constant or not, by asking only one query for a value of ${f}$. There are ${4}$ one-bit Boolean functions, and two boxes we are trying to separate:

• One box, Box C for “Constant,” has the constant functions ${f_0}$ and ${f_1}$ defined by:

$\displaystyle f_0(0) = 0, f_0(1) = 0; \qquad f_1(0) = 1, f_1(1) = 1;$

• The other box, Box B for “Balanced,” has the identity function ${f_I}$ and the NOT function ${f_N}$:

$\displaystyle f_I(0) = 0, f_I(1) = 1; \qquad f_N(0) = 1, f_N(1) = 0;$

Let us think of the value ${f(0)}$ as saying whether ${f}$ is a light or dark chocolate, and the value ${f(1)}$ 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 ${f(0)}$, 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 ${f(1)}$. It seems that to learn which box ${f}$ is in, we need to ask two questions. How can we do it with one?

## Linear Extensions

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:

$\displaystyle f_0(x) = 0; \qquad f_1(x) = 1; \qquad f_I(x) = x; \qquad f_N(x) = 1-x .$

Now ask for the value ${f(1/4) = }$? All four chocolates give different answers, so given one answer by an unknown chocolate, you can tell which it is. In particular, the answers ${0}$ or ${1}$ tell you Box C, while ${1/4}$ or ${3/4}$ tells you Box B. If we only cared about distinguishing the boxes, we could query ${f(1/2)}$ instead.

In a sense what we have done is asked a linear combination of the two possible queries, here ${a = (3/4)0 + (1/4)1 = 1/4}$. By linearity the result is the same linear combination of the answers of any individual function ${f}$, so ${f(a) = (3/4)f(0) + (1/4)f(1)}$.

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:

$\displaystyle f_C(x) = \frac{1}{2}f_0(x) + \frac{1}{2}f_1(x); \qquad f_B(x) = \frac{1}{2}f_I(x) + \frac{1}{2}f_N(x).$

Then ${f_C}$ and ${f_B}$ are both the constant function with value ${1/2}$ for any ${x}$. 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 ${0}$ and ${1}$ are represented by qubit values ${{\mathbf{0}}}$ and ${{\mathbf{1}}}$. These in turn are formally two-dimensional standard-basis vectors

$\displaystyle {\mathbf{0} = \left(\begin{array}{c} 1 \\ 0 \end{array}\right); \quad {\mathbf{1}} = \left(\begin{array}{c} 0 \\ 1 \end{array}\right)}$

over the complex field ${\mathbb{C}}$. Now the relevant linear extensions of the four Boolean functions are the following ${2 \times 2}$ matrices:

$\displaystyle \begin{array}{cc} A_0 = \left(\begin{array}{cc}1 & 1\\ 0 & 0\end{array}\right) & A_1 = \left(\begin{array}{cc}0 & 0\\1 & 1\end{array}\right) \\ \\ A_I = \left(\begin{array}{cc}1 & 0\\ 0 & 1\end{array}\right) & A_N = \left(\begin{array}{cc}0 & 1\\1 & 0\end{array}\right) \end{array}$

The analogue of the argument ${1/4}$ which worked last time is ${u = (1/4){\mathbf{0}} + (3/4){\mathbf{1}} = \left(\begin{array}{c} 1/4 \\ 3/4 \end{array}\right)}$. We have the same distinctions as before:

$\displaystyle A_0 u = \left(\begin{array}{c} 1 \\ 0 \end{array}\right);\quad A_1 u = \left(\begin{array}{c} 0 \\ 1 \end{array}\right);\quad A_I u = \left(\begin{array}{c} 1/4 \\ 3/4 \end{array}\right);\quad A_N u = \left(\begin{array}{c} 3/4 \\ 1/4 \end{array}\right).$

In quantum, however, we have one more requirement—the computation must be reversible. This is violated above because the matrices ${A_0}$ and ${A_1}$ for the constant functions are not invertible. The standard remedy is to replace the original function ${f(x)}$ by the two-dimensional function ${f'(x,y) = (x,y \oplus f(x))}$. Here ${\oplus}$ on Boolean values is XOR (exclusive-or), while on arbitrary complex values we can put ${y \oplus z = y + z - yz}$.

Thus Deutsch’s algorithm is technically about distinguishing the resulting functions ${f'_0,f'_1}$ from ${f'_I,f'_N}$. We get these matrices:

$\displaystyle \begin{array}{cc} A'_0 = \left(\begin{array}{cccc}1&0&0&0 \\ 0&1&0&0 \\ 0&0&1&0 \\ 0&0&0&1\end{array}\right) & A'_1 = \left(\begin{array}{cccc}0&1&0&0 \\ 1&0&0&0 \\ 0&0&0&1 \\ 0&0&1&0\end{array}\right) \\ \\ A'_I = \left(\begin{array}{cccc}1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&1 \\ 0&0&1&0\end{array}\right) & A'_N = \left(\begin{array}{cccc}0&1&0&0\\ 1&0&0&0 \\ 0&0&1&0 \\ 0&0&0&1\end{array}\right) \end{array}$

Strangely, under this representation ${A'_0}$ not ${A'_I}$ has become the identity matrix, and all four are now permutation matrices. What ${A'_N}$ does is interchange the first two co-ordinates, ${A'_I}$ the latter two, and ${A'_1}$ swaps both. Thus we can distinguish the four matrices by their values on a query like ${u' = (1,-1,1,-1)}$ by seeing where the minus signs end up.

The quantum algorithm needs the query argument to be a unit vector, so ${u'' = u'/2}$ is used. The state ${u''}$ is easy to prepare by a few Hadamard transforms. To distinguish whether an unknown answer ${v = Au''}$ comes from ${A}$ in Box C or in Box B, we need only tell whether the minus signs in ${v}$ are in positions of the same or different parity. This can be done by a Hadamard transform on (part of) ${v}$ 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 ${f(x_1,\dots,x_n)}$. Box C still has just the constant functions ${f_0}$ and ${f_1}$, but Box B has every function ${f}$ on ${\{0,1\}^n}$ that is balanced, meaning that ${2^{n-1}}$ of the values ${f(x)}$ are ${0}$, and ${2^{n-1}}$ are ${1}$.

If one is limited to queries ${f(x)}$ for Boolean arguments ${x}$ then ${2^{n-1}}$ queries might still not be enough to tell Box C from Box B. The queries might all be answered ${0}$, and yet ${f}$ 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 ${u = (1,1,\dots,1)}$, normalizing by dividing by ${2}$ or ${\sqrt{n}}$ or whatever factor is desired. By linearity, the extension of every balanced Boolean function will give the same value strictly between ${0}$ and ${1}$. This separates the boxes with one query.

The quantum version of this, however, involves vectors ${u}$ of ${n}$-many qubits. The above encoding transforms them into ordinary vectors ${u'}$ of exponentially many bits, ${2^n}$, or ${2^{n+1}}$ 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

$\displaystyle B_s = \{f: f(x) = f(y) \iff y = x \oplus s\}$

over all ${s \in \{0,1\}^n}$, where ${\oplus}$ is bitwise exclusive-or. When ${s = 0^n}$ 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 ${s}$ is unknown this may require something like the ${N \times N}$ Hadamard transform where ${N = 2^n}$ even with our classical standpoint. Of course Simon’s algorithm was an inspiration for Shor, so this may isolate a critical difference.

## Open Problems

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?

1. October 26, 2011 9:18 pm

Hi, excellent post!

Could you please elaborate on what you mean by this paragraph:

“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 0 and 1. This separates the boxes with one query.”

What is a linear extension of a balanced function f:{0,1}^n -> {0,1}? Is it a multi-linear polynomial that gives the same answers as f on Boolean inputs?

Why does every balanced Boolean function give the same value?

Thanks!

• October 27, 2011 8:56 pm

Here’s a way with a twist. I’ve been interested in supplementing the theory of polynomial representations of Boolean functions. A [multi-linear] monomial is a product of [different] variables x_i, and supplying a coefficient makes a term. I’m interested in products of x_i and (1 – x_j), which for lack of a better name I’ve been calling “schematic monomials”. Notions of degree and multi-(affine-)linearity carry over. What can we say about representing polynomials as sums of schematic terms?

Since there are 2^n schematic multilinear monomials of degree n in n variables, Boolean functions f are in 1-1 correspondence with sums of such schematic terms with 0-1 coefficients. Every such schematic term is 0 except on one assignment a = (a_1,…,a_n), and its coefficient is f(a_1,…,a_n). Call the term T_a. The sum of the T_a is basically the unique DNF of f in which each clause has n distinct literals.

On argument (1/2,1/2,…,1/2), every term T_a contributes either 1/2^n or 0 according as the coefficient f(a) is 1 or 0. Hence a balanced function will give value 1/2 on that argument. (In that part of the post I was allowing for possible normalizing constants on top of that.)

Someone might say this is “groping toward Boolean algebra” 🙂 but I think there are some insights that the notion of “schematic term” can contribute to representations of Boolean functions over Z_m with m composite, for instance. For one, it makes the roles of k-ary AND and OR more symmetric. I haven’t yet made the insights “jell”, however.

• October 28, 2011 1:16 am

Ah, of course! Thanks for the explanation.

So it seems like you’ve “lifted” these Boolean functions to the Real field, and shown that evaluating them at non-0/1 values is equivalent to evaluating the Boolean functions simultaneously on a weighted linear combination (superposition) of 0 and 1, which could tell you in one shot about a global property of the algorithm.

So, this seems to work in your examples, but is there a rigorous correspondence between how (some) quantum algorithms _actually_ work and this multi-linear extensions? If so, then, for example, could we see the effect of amplitude interference via the evaluation of the functions on negative real numbers?

• October 28, 2011 9:03 am

Folks with a taste for geometric points-of-view (as being complementary to combinatoric points-of-view) may prefer to regard these newly-defined schematic monomials not as “groping toward Boolean algebra”, but rather regard them as “groping toward secant varieties of Segre varieties”, the latter class of geometric objects being the topic of Joe Landsberg’s recent (very accessible) Bul. AMS survey Geometry and the complexity of matrix multiplication (2008). This provides yet another illustration that it is neither necessary nor feasible nor even desirable for everyone to think alike in these matters … for the common-sense reason that blending these various points-of-view — algebraic, geometric, and informatic — helps us evolve deeper mathematical frameworks. Plus, it’s fun. 🙂

Kudos to too the Bulletin of the AMS for their open-access policy.

• October 28, 2011 9:13 am

PS: should have mentioned that Landsberg’s survey includes as Section 5.3 a discussion of “Entanglement and quantum computing” that explicitly addresses the questions that Henry Yuen raised, and moreover addresses (albeit implicitly) many practical issues associated to the spectroscopy and imaging of quantum dynamical systems.

October 27, 2011 2:44 am

It seems like you are groping towards stabilizer algebra. That’s fine, but it is 15 years old now, in a fast-moving and accelerating research area.

• October 27, 2011 12:10 pm

Anonymous, for students of STEM history it is by no means self-evident that quantum computation is a notably “fast moving and accelerating research area.”

For example, when we compare John von Neumann’s (sole) patent “Non-linear capacitance or inductance switching, amplifying and memory organs” (US 2815488, filed 1954) with Time Magazine’s special issue “Electronics: The New Age” (Monday, Apr. 29, 1957) of only three years later … it seems that a similarly natural question is “Why has progress in quantum computation (since Deutsch’s seminal 1985 work) been glacially slow, relative to historical precedents in classical computation? Do reasonable prospects exist for speed-up in coming decades?”

One way to read Dick’s post (and other Gödel’s Letter Posts too) is as a request for “burning arrow” ideas to catalyze a 50s-style QIT/QC/CT speed-up.

October 27, 2011 6:33 am

I don’t believe that quantum computers are technically feasible, basically because I believe that P!=NP holds in the real world. Nevertheless, the fact that Shor’s factorization algorithm has been tested only up to 15=3*5 doesn’t make them uninteresting at all. Quantum algorithms are studied for the sake of doing pure mathematics, as abstract objects which don’t have any single counterpart in reality.

October 28, 2011 12:57 pm

A very valid point indeed!
Although I don’t see a connection between NP!=P and QC.
It is not very long when people will recognize the collapse of the Polynomial Hierarchy to P.
And then will the QC become more relevant?

October 28, 2011 3:36 pm

When I say “P!=NP in the real world”, I don’t really mean the classical P!=NP statement but this extended one: “No physical device can solve SAT in polynomial time”. Quantum computers, if they existed, would be among those “physical devices”. Here’s the connection and also, by the way, the reason why they can’t exist. 🙂

As to the collapse of the Polynomial Hierarchy to P, is anybody close to a proof? I have serious doubts, for I’m rather convinced that the very same principle of physics, as applied to the brains of mathematicians, will prevent us forever from proving such a thing.

October 28, 2011 5:06 pm

I would just like to remind you of the tagline of Scott Aaronson’s blog, which includes “Quantum computers are not known to be able to solve NP-complete problems in polynomial time”. That statement is about abstract quantum computers, not just physical ones, which means that even if a “physical” P!=NP statement holds, physical quantum computers may still exist and be more powerful than ordinary classical computers, without being able to solve SAT.

October 28, 2011 5:32 pm

Thank you Ørjan for pointing this out to me. This sounds like good news for the prospects of quantum computers, but like bad news for cryptography. However I’m not sure about the scope of this principle of physics. It’s quite possible that it’ll also apply to polynomial factorization. Maybe P=NP but that’s just because PA and ZFC are two weak to reflect the true nature of computing.

4. October 27, 2011 10:16 am

You might be interested in Maarten Van den Nest’s monomial matrix formalism to describe quantum many-body states: http://arxiv.org/abs/1108.0531

• October 27, 2011 3:14 pm

Thanks! We are already scrutinizing other papers by van den Nest, and had not caught that one—it’s relevant to where we’re trying to head with (the chocolate box analogy for) quantum promise problems.