Skip to Main Content

The Mathematics of Quantum Coin-Flipping

Carl A. Miller

Communicated by Notices Associate Editor Emilie Purvine

Article cover

The individual, on the one hand, and the world, on the other, are simply the abstract limits or terms of a concrete reality which is “between” them, as the concrete coin is “between” the abstract, Euclidean surfaces of its two sides. Similarly, the reality of all “inseparable opposites”—life and death, good and evil, pleasure and pain, gain and loss—is that “between” for which we have no words.

Alan Watts, The Way of Zen Wat57

Mathematical models are the lenses by which mathematics reflects the world we live in, and thus they are fundamental for progress in scientific applications. And yet, science is fluid, and a lot of growth happens when fundamental assumptions are changed. This kind of growth is exemplified in the subject of quantum information. Quantum physics alters basic rules of information processing and leads to new results in computing and communication.

The scenario of two-party coin-flipping illustrates how the answer to a problem can change simply depending on the nature of the model. Let’s suppose that two parties, Alice and Bob, are connected by a communication channel and wish to flip a coin together. Alice wants the outcome of the coin flip to be ,” and Bob wants the outcome to be .” Alice and Bob are permitted to send messages back and forth to one another, and at the end of the communication they will each broadcast bits, denoted and respectively, declaring what they each believe the outcome of the coin flip to be. Our goal is to prescribe behavior for Alice and Bob — including, possibly, each making some independent random choices — such that the following conditions hold.

(1)

If both players behave honestly, then .

(2)

If Alice behaves dishonestly and Bob behaves honestly, then Alice will not be able to skew Bob’s outcome much in her favor — that is, will always be less than or equal to for some small .

(3)

If Bob behaves dishonestly and Alice behaves honestly, then will likewise always be less than or equal to .

Here is an argument that this kind of protocol is, in fact, impossible. In the case where both Alice and Bob behave honestly, let be a random variable that represents the transcript of all communication, and let and be random variables representing the information that Alice and Bob each possess at the end of the protocol. An easy induction argument shows that any shared randomness between the two parties at the end of the protocol must be reflected in the transcript, that is,

where denotes the mutual information between and conditioned on . This implies in particular that

We also know that and must always agree (condition 1). There is only one way both of these assertions can hold: and must be deterministic functions of . This means that Alice and Bob are effectively playing a competitive two-player game. A referee could look at the transcript and determine who has “won” the exchange: if the anticipated outcome is , then Alice won; if the anticipated outcome is , then Bob won. And, von Neumann’s minimax theorem vNM07 guarantees that any such game has a winning strategy for either Alice or Bob, thus violating conditions 23. QED!

How sound is that impossibility argument? Is there any way around it? Well, we could question whether Alice and Bob have the computational ability to find this winning strategy that we know exists. That angle leads to designing coin-flipping protocols based on the assumed hardness of certain computational problems, which is a very interesting avenue itself — see, e.g., MNS16.

But here’s another, more basic, question: how do we know that it’s even possible to record the transcript ? Assumptions that may seem like common sense are not always valid. If Alice and Bob were connected by a quantum channel — for example, if they could exchange photons across a quantum network — then the proof above wouldn’t apply because quantum states generally cannot be copied. And this is much more than a mere technicality: quantum information processing takes its power from unique properties like no-cloning, superposition, and entanglement. In quantum cryptography (which generally does not need to rely on computational assumptions, unlike much of classical cryptography) these properties form the basis for proofs of security.

Quantum coin-flipping turns out to be a different problem altogether. It is a research question with a long historical arc, and as such it provides a good window into the exotic logic of quantum information.

The Theory of Quantum Information

Quantum information consists of quantum “systems” or “registers” whose state at any given time is described by a matrix. The basic data element in quantum information is the qubit. The state of an isolated qubit is a matrix of the form

where and are real numbers that sum to , and is a complex number such that . Expressed in different terms, can be any positive semidefinite matrix of trace . When a qubit in this state is measured, the result is a bit that is equal to with probability and equal to with probability .

Let

Then, the set of all qubit states consists of linear operators of the form , where is a real vector of length at most , and denotes the identity matrix. (For the matrix from the previous paragraph, , , and .) These states form a -dimensional ball, namely, the Bloch ball, shown in Figure 1. Quantum operations on a qubit are maps of the form , where is a unitary operator, and they are rotations of the Bloch ball. (An example of a qubit is the polarization of a photon. A photon traveling in space can have a polarization that is diagonal, circular, or rectilinear, corresponding to the principal directions , , and .)

Figure 1.

The Bloch ball.

Graphic without alt text

Similar definitions apply in higher dimensions. A quantum system of dimension is a complex Hilbert space⁠Footnote1 with a fixed isomorphism . The classical (non-quantum) states of are probability distributions written as diagonal matrices:

1

Some authors make a distinction between a quantum system and its Hilbert space, and denote them by different letters. For this article, it is convenient to treat them as one and the same.

Any such state can also be manipulated via a unitary base change , yielding a trace- positive semidefinite matrix (“density matrix”) that may have off-diagonal elements. If another quantum system is present, its joint state with is described by a density matrix on the tensor product space, . (A full treatment of these concepts can be found in Wat18.)

From here, we can begin to unfold some uniquely quantum phenomena. One is the concept of inherent randomness. Suppose that is a qubit in state

We know that the outcome of measuring will be a uniformly random bit. But we can go further. If is an additional quantum system, then the joint state of and together must be a positive semidefinite block matrix

where are matrices satisfying . An easy argument shows that the only way that these conditions can all be satisfied is if for some positive semidefinite matrix . Any measurement on will be uncorrelated with the measurement of . This means that no outside system can provide any information at all about the outcome of measuring — the result is not only unknown in advance, but unknowable.

Also, we can observe the phenomenon of exponential complexity. The state of a system of qubits is a linear operator on the vector space , which has dimension . The problem of simulating even a small number of qubits thus involves keeping track of an enormous matrix, and it quickly becomes intractable for a classical computer. This intractability becomes particularly significant when a measurement of the system yields data that we do not know how to obtain in an efficient classical manner. This is the basis of quantum algorithms such as Shor’s algorithm Sho99, and for claims of a “quantum advantage” in computing.

I have been working in quantum information for about twelve years, starting from a time when a computer science professor told me it was a “niche topic,” up to the present day, when we are in the midst of what some people are calling the “second quantum revolution.” (Recent technology has made the quantum phenomena discussed above quite tangible — see SZB21 and Aea19.) When studying this field, it is interesting to observe how various lines of progress — just like currents in a river — can accelerate or subside, overlap, or split. The shape that this river takes can exhibit hidden surprises in the underlying theory.

A Story of Two Problems

This is the very coinage of your brain. This bodiless creation ecstasy Is very cunning in.

Gertrude (Hamlet)

In 1984, Bennett and Brassard BB84 sketched two ways to use quantum physics to perform basic cryptographic tasks. Much of quantum cryptography can be seen as an attempt to harness inherent quantum randomness for a practical purpose, and BB84 proposes two (different but related) approaches to this goal. In key distribution, two parties, Alice and Bob, wish to share a secret random bit string in the presence of an untrusted eavesdropper, Eve. In coin-flipping, Alice and Bob instead wish to create a single shared random bit using a quantum channel, in such a way that both parties are assured that the bit was fair and unbiased. The primary difference between the two scenarios is that in key distribution, the only adversary is the eavesdropper (Eve), whereas in coin-flipping, either of the parties Alice and Bob could be an adversary who will attempt to cheat. See Figure 2.

Figure 2.

Quantum key distribution (top) and quantum coin-flipping (bottom).

Graphic without alt text

The paper BB84, along with Stephen Wiesner’s work on quantum money Wie83, are considered to be the seminal works in quantum cryptography. Quantum key distribution (QKD) is a mainstay problem in the field, and since 1984, has been the subject of thousands of experimental and theoretical papers XMZ20 as well as commercialization. Quantum coin-flipping, meanwhile, has followed a substantially different track. While BB84 sketched a protocol for QKD that has been central to a lot of follow-up work, they did not give a secure protocol for quantum coin-flipping, and it was left to future authors to find one.

A standard way to measure the effectiveness of a quantum coin-flipping protocol is via the (weak) bias of the protocol. Assuming that Bob behaves honestly, let denote the supremum, over all possible cheating strategies for Alice, of the probability that Alice will achieve her desired outcome (). Likewise, let denote the supremum of the probability that Bob will achieve outcome if he cheats and Alice behaves honestly. The bias is the quantity . The goal is to achieve a bias of zero.

Simple protocols for coin-flipping tend not to be effective. For example, we could instruct Alice to send a photon in the state

to Bob, and instruct Bob to measure the photon and report the result. But, this allows Alice to cheat (by preparing a different state) or Bob to cheat (by faking the measurement result). The goal in quantum coin-flipping is to use multiple rounds of interaction to mutually restrain the parties from gaining any advantage by cheating.

After this problem was fully formalized, a series of several works initiated in the 1990s gave protocols with increasingly smaller bias. However, the protocols were also increasingly complex. The progression reached a climax in 2007, when the physicist Carlos Mochon proved a remarkable result showing that the bias could be brought arbitrarily close to zero Moc07. But the number of communication rounds was absurdly large — a later analysis of Mochon’s work ACG16 estimated it at . In the years after Mochon’s work, despite continued theoretical progress on the problem, this figure was not improved. A basic question was thus left unanswered: can quantum coin-flipping be performed in a reasonable amount of time?

We can use the quantum formalism from the previous section of this article to get an idea of why this problem is hard. Specifying a protocol for coin-flipping requires specifying the prescribed “honest” behavior by each player. We assume that Alice has a quantum system for some that serves as her local memory during the protocol. Let us assume that the initial state of is simply given by the orthogonal projector onto . Let (Bob’s local memory) and (the message register) be quantum systems with similar initial states. At time , Alice applies a joint quantum operation to and . This operation has the effect of conjugating the state of by some unitary operator . Alice then sends the register across the quantum channel to Bob.

At time , Bob performs a joint quantum operation on and which has the effect of conjugating the state of by a unitary operator . Now, at this point, Bob wishes to check whether Alice has cheated, and so he performs a binary measurement on and agrees to continue the protocol only if the outcome of that measurement is .” Mathematically, this is represented by Bob applying an operation of the form to the state of , where is a Hermitian projection operator. Bob then sends back to Alice, and the process iterates. Finally, after the th round, Alice and Bob each perform binary measurements on their respective systems and to produce bits and representing what each party believes that the outcome was. The protocol succeeds only if neither party has aborted, and if .

Summing up, a coin-flipping protocol is specified by the following mathematical information:

(1)

A positive integer (the number of communication rounds).

(2)

Quantum registers , , and .

(3)

For each odd , a unitary operator and Hermitian projection operator on the space .⁠Footnote2

2

We include the projection operator for convenience, even though it is impossible for Bob to have cheated at time .

(4)

For each even , a unitary operator and Hermitian projection operator on the space .

(5)

Complementary Hermitian projection operators on , and on , representing the final measurements performed by Alice and Bob.

The assumption is that if Alice and Bob are honest, they will use these prescribed operations. A dishonest party may perform arbitrary operations during their rounds of the protocol. Once the data above are specified, we can give an explicit expression for the bias of the protocol (see ACG16 for details). Finding a good coin-flipping protocol is thus equivalent to an optimization problem: compute explicit matrices that will make the bias as small as possible.

This optimization problem is no easy thing. We have no upper bound on the dimension of the space in which we are searching, and indeed, Mochon’s work suggests that it may be necessary to consider spaces of arbitrarily large dimension. Moreover, obvious properties that can make an optimization problem easier — such as convexity of the search-space, or linearity of the objective function — are lacking here.

Mochon left academia not long after publicizing his work on coin-flipping, although fortunately there were ample ideas in Moc07 to enable further developments. The path to an answer for the efficient coin-flipping question turns out to be a surprisingly non-linear one that draws on a diverse range of tools.

Point Game Solitaire

Pure mathematics is full of seemingly mysterious connections between mathematical models — i.e., instances in which there is a dictionary that can broadly translate statements about two fundamentally different mathematical constructions. The more dissimilar the constructions are, the more there is to learn, since connections like this can enable the application of a new kind of mental agility to a problem (e.g., geometry instead of algebra). It is particularly a delight to use such a doorway when studying an application.

One such doorway occurs in the study of quantum coin-flipping, and its discovery is attributed to Alexei Kitaev Kit02. The existence of coin-flipping protocols with small bias has been proved to be equivalent to the existence of a different class of mathematical objects called valid point games. The proof of this equivalence is out of the scope of this article, but an excellent exposition (of a nonconstructive version of the proof) can be found in ACG16. Essentially, the concept of a valid point game strips away some of the information used in the search for optimal coin-flipping protocols and distills a part of the problem that is particularly challenging.

Valid point games are not unlike peg solitaire, where one has to manipulate and remove pegs from a grid of holes on a board according to a fixed rule, in such a way that at the end there is only one peg left. Valid point games are different, though, in particular because they involve quantities that are continuous rather than discrete. The following are the rules.

A function with finite support that satisfies is called a one-dimensional configuration.

A pair of one-dimensional configurations is called a valid move if

and

for all .⁠Footnote3

3

This rule arises from the classification of operator monotone functions.

A function with finite support that satisfies is called a two-dimensional configuration.

A pair of two-dimensional configurations is a horizontally valid move if the restriction of and to any horizontal line in is a valid move.

A pair of two-dimensional configurations is a vertically valid move if the restriction of and to any vertical line in is a valid move.

A valid point game is a sequence of two-dimensional configurations such that is horizontally valid for all even , and vertically valid for all odd .

Valid point games thus consist of manipulations of weighted points in a quadrant of a Cartesian coordinate system. Figure 3 gives an example of a move that could occur in one of these games.

Figure 3.

One example of a horizontally valid move. (The points that lie on the same horizontal line are collapsed to their center of mass.)

Graphic without alt text

If are nonnegative real numbers, let denote the function on that maps to , and all other points to . The following results are known.

Theorem 1.

Suppose that is a valid point game consisting of moves such that the starting configuration is

and the final configuration is

Suppose that . Then, there exists an -round coin-flipping protocol that achieves bias .

Theorem 2.

Suppose that is an -round coin-flipping protocol that achieves bias , and suppose that . Then, there exists a valid point game with moves such that the starting configuration is and the final configuration is .

Thus, we have a way to translate problems about coin-flipping into simply-stated point game problems (modulo the term , which is practically irrelevant). For example: suppose that we wish to prove that it is possible to achieve coin-flipping with bias with only communication rounds. Then, it suffices to construct valid point games involving moves that transform into . But, for better or worse, this translation is not the end of the story, or anywhere close. Constructing valid point games is hard, and it is fair to say that it has not yet been generally mastered in the research literature. (Only a few examples, including the family of games used in Moc07, are known.) Figuring out what is really going on with coin-flipping will require penetrating further layers of the problem.

Solving a Toy Model

Then the shimmery sphere around them abruptly contracted, like a taut rubber band being let go, and the coin pulsed with sudden heat.

But they were still in his universe.

Quantum Coin by E. C. Myers Mye12

So, why is it difficult to construct valid point games? One reason is that the rule that defines a valid move is not a merely local rule. Valid moves can involve simultaneously manipulating points that are at large distances from one another on a single row or a single column. A natural first step towards general constructions of point games is to try to separate the “local” and “global” parts of the problem. Suppose that we first limit ourselves to considering valid point games that are confined to the box formed by the vertices

where are positive real numbers and is small. What kind of manipulations can take place within this region using valid moves? If we choose to ignore any terms that are , then the question is essentially answered by the following construction.

Let us say that a pair of finite-support functions from to is a legal move if

and

A legal point game is a sequence of nonnegative functions on , defined as before, such that the pairs alternate between being horizontally legal and vertically legal.

Since the family of legal moves is merely defined by two linear conditions (instead of an infinite number of linear conditions), legal point games turn out to be much easier to characterize. The following results can be proved.

Proposition 3.

Let be a legal point game. Then the following inequalities hold.

Proposition 4.

Let and be two-dimensional configurations such that inequalities 13 above are strictly satisfied (when is replaced with and is replaced with ). Then, there exists a legal point game with initial configuration and final configuration .

The outcome of a legal point game can thus be completely characterized (up to arbitrarily small error) by the inequalities 13. Moreover, legal point games that achieve Proposition 4 are not too difficult to construct explicitly. The question then becomes: Can we translate this to similar criteria for valid point games?

Profile Functions

The following is a modified version of reasoning in Mil20. Considering the definition of a valid move (and taking inspiration from condition 3 above) we note that it is easy to prove that for any valid point game , and any positive real numbers , the inequalities

must hold for any . In an intuitive sense, the expression on the left-hand side of the above inequality is a monotone quantity that allows us to track the progress in a point game from the initial configuration to the final one. A profile function draws together these quantities into a single family. There are many ways that the profile can be defined, but, for the purpose of this article, the following definition will be convenient to use.

Definition 5.

For any finitely supported function , the profile of is the function

defined by

This definition allows us to make a simply-stated criterion that must be satisfied in order for a valid point game to exist between two given configurations.

Proposition 6.

If is a valid point game, then .

What can the profile construction tell us about the coin-flipping problem? It is not obvious that it can tell us directly how to construct intermediate steps in a valid point game, but, fortunately, it is useful for narrowing down the possibilities.

Let be a valid point game such that and . Let denote the sum of the differences over all even (i.e., the sum of all the horizontally valid moves). Let denote the sum of the differences over all odd (i.e., the sum of all the vertically valid moves). Then, by linearity,

Note that the function can be written out explicitly from its definition.

Figure 4.

The domain of the function .

Graphic without alt text

The observations we have made so far have been pretty elementary, but, from here, we can start to deduce hidden structure. Chasing through a series of inequalities, one can show the following fact. Fix any real interval with , and let

The function is the sum of the horizontal and vertical moves that occur within certain restricted regions in — see Figure 4. Let

Then, for any that is of distance at least away from both of the points and , the following inequality holds:

In other words, the shape of the graph of matches that of very closely, except at neighborhoods of size around the points of discontinuity at and . (The use of the constant in this assertion is arbitrary – any positive real number could be used in its place.)

We are thus able to make strong conclusions about the profiles of the moves in based on where those moves occur in the -dimensional coordinate system. The sharpness with which we can make these conclusions depends on the bias parameter . At an extreme, if we take the interval itself to be of width , then the profile of has a pinched shape of width like the one shown in Figure 5.

Figure 5.

A nonnegative function that is concentrated at a single point ().

Graphic without alt text

Having now touched down on a concrete assertion, the question is: can we deduce a result on the efficient coin-flipping problem? A natural approach would be to take this new insight and trace it backwards through the series of simplifying steps that we have made (coin flipping protocols valid point games profile functions) to deduce something about the existence of coin-flipping protocols. And, indeed, that is the approach that we will ultimately take. A final, more “complex” detour is needed in order to enable the last steps.

Highly Concentrated Rational Functions

The conclusion of the previous section can be distilled as follows: if there exists a valid point game from to , then we can construct a finitely supported real function on such that the function

is significantly large at a chosen point (say, ) and is close to zero elsewhere in the domain . And importantly, since the function is constructed by summing up valid moves from the original point game , its weights must be bounded like so:

When is such a thing possible? What can be said about a real rational function in this form — a rational function that has poles in the interval and that obeys certain inequalities in the interval ? Fortunately, there are known methods to answer a question of this type, and they come from complex analysis.

Let us suppose that for all values that are outside of an interval of the form . Treat the function as a rational function on the set of complex numbers , and let

This value will allow us to interpolate between the various properties that we have assumed about the function . The following argument is written out in detail in section 5 of Mil20.

Figure 6.

The function on the unit disc in .

Graphic without alt text

There exists an explicit continuous map

that has the form shown in Figure 6 and is analytic on the interior disc . Under , the unit circle around is mapped onto the unit circle around together with the two line segments and . The point in Figure 6 is within distance from the -axis.

By the defining properties of analytic functions, the map obeys an averaging rule: its value at (which is ) must be the same as its average value on the unit circle :

As a consequence, since the values that takes on the line segments and are all significantly less than , there must exist points on the unit circle around for which the magnitude of is significantly more than . Precisely:

This inequality itself is not terribly strong. However, when we instead consider the logarithm of the absolute value of , the following similar relation holds:

and we deduce the much more powerful inequality

or equivalently,

At the same time, it is easy to see from the expression for the function that