Author Archives: Johannes Bausch

About Johannes Bausch

Quantum complexity theorist and outdoor fanatic. I'm currently at Cambridge University, researching the interplay between many-body quantum systems and universal computation.

The World Cup from a Quantum Perspective

Posted on by
4

Two weeks into the Football World Cup and the group stages are over: 16 teams have gone home, leaving the top 16 teams to contend the knock-out stages. Those fans who enjoy a bet will be poring over the odds in search of a bargain—a mis-calculation on the part of the bookmakers. Is now the time to back Ronaldo for the golden boot, whilst Harry Kane dominates the headlines and sports betting markets? Will the hosts Russia continue to defy lowly pre-tournament expectations and make the semi-finals? Are France about to emerge from an unconvincing start to the tournament and blossom as clear front-runners?

But, whilst for most the sports betting markets may lead to the enhanced enjoyment of the tournament that a bet can bring (as well as the possibility of making a little money), for others they represent a window into the fascinating world of sports statistics. A fascination that can be captured by the simple question: how do they set the odds?

Suppose that a bookmaker has in their possession a list of outcome probabilities for matches between each pair of national football teams in the world and wants to predict the overall winner. There are 32768 possible ways for the tournament knock-out rounds to pan-out—a large, but not insurmountable number of iterations by modern computational standards.

However, if the bookmaker instead considers the tennis grand-slams, with 128 competitors in the first round, then there are a colossal 1.7 × 1038 permutations. Indeed, in a knock-out format there are 2n-1 permutations, where n is the number of entrants. And for those of a certain mindset, this exponentially growing space immediately raises the question of whether a quantum algorithm can yield a speed-up for the related prediction tasks.

A Tiny Cup

The immediate question which we want to answer here is, perhaps, who will win the World Cup. We will walk through the idea on the blackboard first, and then implement it as a quantum algorithm—which, hopefully, will give some insight into how and where quantum computers can outperform classical ones, for this particular way of answering the question.

Let us take a toy setup with four teams A, B, C and D;
the knockout stage starts with a game A vs. B, and C vs. D.
Whoever wins each game will play against each other, so here we have four possible final games: A vs. C, A vs. D, B vs. C, or B vs. D.
Let’s denote by p(X, Y) the probability that X wins when playing against Y.

The likelihood of A winning the cup is then simply given by

p(A, B) × ( p(C, D) × p(A, C) + p(D, C) × p(A, D) ),

i.e. the probability that A wins against B, times the probabilities of A winning against C in case C won against D, plus the probability of A winning against D in case D won.

How can we obtain the same quantity with a quantum algorithm?

First, we set up our Hilbert space so that it can represent all possible Cup scenarios.
Since we have four teams, we need a four-dimensional quantum system as our smallest storage unit—we commonly call those qudits as generalizations of a qubit, which having dimension 2 would be fit to store two teams only (we can always “embed” a qudit into a few qubits of the same dimension.

Remember: k qubits have dimension 2k, so we could also store the qudit as two qubits).
If we write |A\rangle, this simply stands for a qudit representing team A; if we write |A\rangle |B\rangle, then we have a state representing two teams.

To represent a full knockout tree, we follow the same logic: Take four qudits for the initial draw; add two qudits for the winners of the first two matches, and one qudit for the final winner.

For instance, one possible knockout scenario would be

|\text{Game 1}\rangle = \underbrace{|A\rangle |B\rangle |C\rangle |D\rangle}_\text{Initial Draw} \ \underbrace{|A\rangle |D\rangle}_\text{Finals} \ |D\rangle.

The probability associated with Game 1 is then precisely p(A, B) × p(D, C) × p(D, A).

Here is where quantum computing comes in.

Starting from an initial state |A\rangle |B\rangle |C\rangle |D\rangle, we create two new slots in a superposition over all possible match outcomes, weighted by the square-root of their probabilities (which we call q instead of p):

\begin{aligned} |\text{Step 1}\rangle = |A\rangle |B\rangle |C\rangle |D\rangle \big(\ \ &\text{q(A, B)q(C, D)} \,|A\rangle\ |C\rangle +\\ &\text{q(A, B)q(D, C)} \,|A\rangle\ |D\rangle +\\ &\text{q(B, A)q(C, D)} \,|B\rangle\ |C\rangle +\\ &\text{q(B, A)q(D, C)} \,|B\rangle\ |D\rangle\ \big). \end{aligned}

For the final round, we perform the same operation on those two last slots; e.g. we would map |A\rangle |C\rangle to a state |A\rangle |C\rangle ( q(A, C) |A\rangle + q(C, A) |C\rangle ). The final state is thus a superposition over eight possible weighted games (as we would expect).

So you can tell me who wins the World Cup?

Yes. Or well, probably. We find out by measuring the rightmost qudit.
As we know, the probability of obtaining a certain measurement outcome, say A, will then be determined by the square of the weights in front of the measured state; since we put in the square-roots initially we recover the original probabilities. Neat!

And since there are two possible game trees that lead to a victory of A, we have to sum them up—and we get precisely the probability we calculated by hand above. This means the team that is most likely to win will be the most likely measurement outcome.

So what about the World Cup? We have 16 teams; one team can thus be stored in four qubits. The knockout tree has 31 vertices, and a naive implementation can be done on a quantum computer with 124 qubits. Of course we are only a bit naive, so we can simulate this quantum computer on a classical one and obtain the following winning probabilities:

0.194 Brazil
0.168 Spain
0.119 France
0.092 Belgium
0.082 Argentina
0.075 England
0.049 Croatia
0.041 Colombia
0.04 Portugal
0.032 Uruguay
0.031 Russia
0.022 Switzerland
0.019 Denmark
0.018 Sweden
0.012 Mexico
0.006 Japan

It is worth noting that all operations we described can be implemented efficiently with a quantum computer, and the number of required qubits is quite small; for the four teams, we could get away with seven qudits, or fourteen qubits (and we could even save some, by ignoring the first four qudits which are always the same).

So for this particular algorithm there is an exponential speedup over its non-probabilistic classical counterpart: as mentioned, one would have to iterate over all trees; tedious for the World Cup, practically impossible for tennis. However…

Classical vs. Quantum

Does using a quantum algorithm give us a speedup for this task? Here, the answer is no; one could obtain similar results in comparable time using probabilistic methods, for instance, by doing Monte Carlo sampling.

But there are several interesting related questions that we could ask for which there might be a quantum advantage.

For some team A, we can easily create a state that has all game trees in superposition that lead to a victory of A—even weighting them using their respective probabilities.
Given this state as a resource, we can think of questions like “which game tree is most likely, given that we fix A and B as semifinalists”, or “which team should A play in the knockout stages to maximize the probability that B wins the tournament”.

Or, more controversially: can we optimize the winning chances for some team by rearranging the initial draw?

Some questions like these lend themselves to applying Grover search, for which there is a known speedup over classical computers. To inquire deeper into the utility of quantum algorithms, we need to invent the right kind of question to ask of this state.

Let us think of one more toy example. Being part physicists, we assume cows are spheres—so we might as well also assume that if A is likely to win a match against B, it always wins—even if the probability is only 51%. Let’s call this exciting sport “deterministic football”. For a set of teams playing a tournament of deterministic football, does there exist a winning initial draw for every team?

This becomes an especially interesting question in cases where there is a non-trivial cyclic relation between the teams’ abilities, a simple example being: A always beats B, B always beats C, and C always beats A. For example, if this problem turns out to be NP-hard, then it would be reasonable to expect that the quadratic improvement achieved by quantum search is the best we can hope for in using a quantum algorithm for the task of finding a winning initial draw for a chosen team—at least for deterministic football (phew).

To the finals and beyond

World Cup time is an exciting time: whatever the question, we are essentially dealing with binary trees, and making predictions can be translated into finding partitions or cuts that satisfy certain properties defined through a function of the edge weights (here the pairwise winning probabilities). We hope this quantum take on classical bookmaking might point us in the direction of new and interesting applications for quantum algorithms.

Hopefully a good bargain!

(Written with Steven Herbert and Sathyawageeswar Subramanian)

What Clocks have to do with Quantum Computation

Posted on by
Reply

Have you ever played the game “telephone”? You might remember it from your nursery days, blissfully oblivious to the fact that quantum mechanics governs your existence, and not yet wondering why Fox canceled Firefly. For everyone who forgot, here is the gist of the game: sit in a circle with your friends. Now you think of a story (prompt: a spherical weapon that can destroy planets). Once you have the story laid out in your head, tell it to your neighbor on your left. She takes the story and tells it to her friend on her left. It is important to master the art of whispering for this game: you don’t want to be overheard when the story is passed on. After one round, the friend on your right tells you what he heard from his friend on his right. Does the story match your masterpiece?

If your story is generic, it probably survived without alterations. Tolstoy’s War and Peace, on the other hand, might turn into a version of Game of Thrones. Passing along complex stories seems to be more difficult than passing on easy ones, and it also becomes more prone to errors the more friends join your circle—which makes intuitive sense.

So what does this have to do with physics or quantum computation?

Let’s add maths to this game, because why not. Take a difficult calculation that follows a certain procedure, such as long division of two integer numbers.

long-division

Now you perform one step of the division and pass the piece of paper on to your left. Your friend there is honest and trusts you: she doesn’t check what you did, but happily performs the next step in the division. Once she’s done, she passes the piece of paper on to her left, and so on. By the time the paper reaches you again, you hopefully have the result of the calculation, given you have enough friends to divide your favorite numbers, and given that everyone performed their steps accurately.

I’m not sure if Feynman thought about telephone when he, in 1986, proposed a method of embedding computation into eigenstates (e.g. the ground state) of a Hamiltonian, but the fact remains that the similarity is striking. Remember that writing down a Hamiltonian is a way of describing a quantum-mechanical system, for instance how the constituents of a multi-body system are coupled with each other. The ground state of such a Hamiltonian describes the lowest energy state that a system assumes when it is cooled down as far as possible. Before we dive into how the Hamiltonian looks, let’s try to understand how, in Feynman’s construction, a game of telephone can be represented as a quantum state of a physical system.

telephone-history-state

In this picture, | \psi_t \rangle represents a snapshot of the story or calculation at time t—in the division example, this would be the current divisor and remainder terms; so e.g. the snapshot | \psi_1 \rangle represents the initial dividend and divisor, and the person next to you is thinking of | \psi_2 \rangle, one step into the calculation. The label |t\rangle in front of the tensor sign \otimes is like a tag that you put on files on your computer, and uniquely associates the snapshot | \psi_t \rangle with the t-th time step. We say that the story snapshot is entangled with its label.

This is also an example of quantum superposition: all the |t\rangle\otimes|\psi_t\rangle are distinct states (the time labels, if not the story snapshots, are all unique), and by adding these states up we put them into superposition. So if we were to measure the time label, we would obtain one of the snapshots uniformly at random—it’s as if you had a cloth bag full of cards, and you blindly pick one. One side of the card will have the time label on it, while the other side contains the story snapshot. But don’t be fooled—you cannot access all story snapshots by successive measurements! Quantum states collapse; whatever measurement outcome you have dictates what the quantum state will look like after the measurement. In our example, this means that we burn the cloth bag after you pick your card; in this sense, the quantum state behaves differently than a simple juxtaposition of scraps of paper.

Nonetheless, this is the reason why we call such a quantum state a history state: it preserves the history of the computation, where every step that is performed is appropriately tagged. If we manage to compare all pairs of successively-labeled snapshots (without measuring them!), one can verify that the end result does, in fact, stem from a valid computation—and not just a random guess. In the division example, this would correspond to checking that each of your friends performs a correct division step.

So history states are clearly useful. But how do you design a Hamiltonian with a history state as the ground state? Is it even possible? The answer is yes, and it all boils down to verifying that two successive snapshots | \psi_t \rangle and | \psi_{t+1} \rangle are related to each other in the correct manner, e.g. that your friend on seat t+1 performs a valid division step from the snapshot prepared by the person on seat t. In fancy physics speak (aka Bra-Ket notation), we can for example write

local-check

The actual Hamiltonian will then be a sum of such terms, and one can verify that its ground state is indeed the one representing the history state we introduced above.

I’m glossing over a few details here: there is a minus sign in front of this term, and we have to add its Hermitian conjugate (flip the labels and snapshots around). But this is not essential for the argument, so let’s not go there for now. However, you’re totally right with one thing: it wouldn’t make sense to write down all snapshots themselves into the Hamiltonian! After all, if we had to calculate every snapshot transition like | \psi_2 \rangle \langle \psi_1 | in advance, there would be no use to this construction. So instead, we can write

local-check-2.png

Perfect. We now have a Hamiltonian which, in its ground state, can encode the history of a computation, and if we replace the transition operator \mathbf U_\text{DIVISION} with another desired transition operator (a unitary matrix), we can perform any computation we want (more precisely, any computation that can be written as a unitary matrix; this includes anything your laptop can do). However, this is only half of the story, since we need to have a way of reading out the final answer. So let’s step back for a moment, and go back to the telephone game.

Can you motivate your friends to cheat?

Your friends playing telephone make mistakes.

no-mistakes

Ok, let’s assume we give them a little incentive: offer $1 to the person on your right in case the result is an even number. Will he cheat? With so much at stake?

no-mistakes-bribe.png

In fact, maybe your friend is not only greedy but also dishonest: he wants to hide the fact that he miscalculates on purpose, and sometimes tells his friend on his right to make a mistake instead (maybe giving him a share of the money). So for a few of your friends close to the person at the end of the chain, there is a real incentive to cheat!

local-check-3.png

Can we motivate spins to cheat?

We already discussed how to write down a Hamiltonian that verifies valid computational steps. But can we do the same thing as bribing your friends to procure a certain outcome? Can we give an energy bonus to certain outcomes of the computation?

In fact, we can. Alexei Kitaev proposed adding a term to Feynman’s Hamiltonian which raises the energy of an unwanted outcome, relative to a desirable outcome. How? Again in fancy physics language,

local-check-4.png

What this term does is that it takes the history state and yields a negative energy contribution (signaled by the minus sign in front) if the last snapshot | \psi_T \rangle is an even number. If it isn’t, no bonus is felt; this would correspond to you keeping the dollar you promised to your friend. This simply means that in case the computation has a desirable outcome—i.e. an even number—the Hamiltonian allows a lower energy ground state than for any other output. Et voilà, we can distinguish between different outputs of the computation.

The true picture is, of course, a tad more complicated; generally, we give penalty terms to unwanted states instead of bonus terms to desirable ones. The reason for this is somewhat subtle, but can potentially be explained with an analogy: humans fear loss much more than they value gains of the same magnitude. Quantum systems behave in a completely opposite manner: the promise of a bonus at the end of the computation is such a great incentive that most of the weight of the history state will flock to the bonus term (for the physicists: the system now has a bound state, meaning that the wave function is localized around a specific site, and drops off exponentially quickly away from it). This makes it difficult to verify the computation far away from the bonus term.

So the Feynman-Kitaev Hamiltonian consists of three parts: one which checks each step of the computation, one which penalizes invalid outcomes—and obviously we also need to make sure the input of the computation is valid. Why? Well, are you saying you are more honest than your friends?

local-check-5.png

Physical Implications of History State Hamiltonians

If there is one thing I’ve learned throughout my PhD it is that we should always ask what use a theory is. So what can we learn from this construction? Almost 20 years ago, Alexei Kitaev used Feynman’s idea to prove that estimating the ground state energy of a physical system with local interactions is hard, even on a quantum computer (for the experts: QMA-hard under the assumption of a 1/\text{poly} promise gap splitting the embedded YES and NO instances). Why is estimating the ground state energy hard? The energy shift induced by the output penalty depends on the outcome of the computation that we embed (e.g. even or odd outcome). And as fun as long division is, there are much more difficult tasks we can write down as a history state Hamiltonian—in fact, it is this very freedom which makes estimating the ground state energy difficult: if we can embed any computation we want, estimating the induced energy shift should be at least as hard as actually performing the computation on a quantum computer. This has one curious implication: if we don’t expect that we can estimate the ground state energy efficiently, the physical system will take a long time to actually assume its ground state when cooled down, and potentially behave like a spin glass!

Feynman’s history state construction and the QMA-hardness proof of Kitaev were a big part of the research I did for my PhD. I formalized the case where the message is not passed on along a unique path from neighbor to neighbor, but can take an arbitrary path between beginning and end in a more complicated graph; in this way, computation can in some sense be parallelized.

Well, to be honest, the last statement is not entirely true: while there can be parallel tracks of computation from A to B, these tracks have to perform the same computation (albeit in potentially different steps); otherwise the system becomes much more complicated to analyze. The reason why this admittedly quite restricted form of branching might still be an advantage is somewhat subtle: if your computation has a lot of classical if-else cases, but you don’t have enough space on your piece of paper to store all the variables to check the conditions, it might be worth just taking a gamble: pass your message down one branch, in the hope that the condition is met. The only thing that you have to be careful about is that in case the condition isn’t met, you don’t produce invalid results. What use is that in physics? If you don’t have to store a lot of information locally, it means you can get away using a much lower local spin dimension for the system you describe.

Such small and physically realistic models have as of late been proposed as actual computational devices (called Hamiltonian quantum computers), where a prepared initial state is evolved under such a history state Hamiltonian for a specific time, in contrast to the static property of a history ground state we discussed above. Yet whether or not this is something one could actually build in a lab remains an open question.

Last year, Thomas Vidick invited me to visit Caltech, and I worked with IQIM postdoc Elizabeth Crosson to improve the analysis of the energy penalty that is assigned to any history state that cheats the constraints in the Feynman-Kitaev Hamiltonian. We identified some open problems and also proved limitations on the extent of the energetic penalty that these kinds of Hamiltonians can have. This summer I went back to Caltech to further develop these ideas and make progress towards a complete understanding of such “clock” Hamiltonians, which Elizabeth and I are putting together in a follow-up work that should appear soon.

It is striking how such simple idea can have so profound an implication across fields, and remain relevant, even 30 years after its first proposal.

feynman-clever.png

Feynman concludes his 1986 Foundations of Physics paper with the following words.

At any rate, it seems that the laws of physics present no barrier to reducing the size of computers until bits are the size of atoms, and quantum behavior holds dominant sway.

For my part, I hope that he was right and that history state constructions will play a part in this future.