Graphs, Games, and Quantum Secrets

January 6, 2026

There is a comfortable story we tell about quantum cryptography. It goes like this: physics gives us unbreakable secrecy. A photon cannot be copied, a measurement disturbs what it touches, and therefore an eavesdropper always leaves fingerprints. Case closed, the universe protects our secrets.

It is a beautiful story. It is also, on its own, useless.

Because the moment you try to build something with quantum cryptography, you stop asking “is this photon secure?” and start asking questions that physics alone cannot answer. How do I connect fifty cities into one secure network when my photons die after a hundred kilometers of fiber? How much can an eavesdropper actually learn if she plays her best possible strategy, not just the naive one? If ten banks share a secret and three of them are lying, who can I trust?

None of those are physics questions. They are mathematics questions. And it turns out that two fields most people file under “abstract pure math”, graph theory and game theory, are exactly the tools that answer them. This article is about that unlikely marriage: how the mathematics of networks and the mathematics of conflict became the working language of quantum secrecy.

Let me show you both lenses.

First, a one-paragraph refresher

If you have read my BB84 piece, skip this. Otherwise: Quantum Key Distribution (QKD) lets two parties, Alice and Bob, produce a shared random secret key over an untrusted channel. The trick is that the key is encoded in quantum states (say, the polarization of single photons), and any eavesdropper, Eve, who tries to intercept them unavoidably disturbs them. Alice and Bob compare a sample of their results; too many errors means Eve was listening, and they throw the key away. The original protocol is BB84, from Bennett and Brassard in 1984 [1]; the entanglement-based cousin is Ekert’s E91 [2]. That is the whole idea.

Now, everything interesting happens around that idea. That is where the math lives.

Part I — The graph theory lens

Clue 1: a quantum network is a graph, whether you like it or not

Here is the brutal engineering fact that ruins the fairy tale: photons do not travel far. In optical fiber, the signal attenuates exponentially, and because you cannot amplify a quantum state without destroying it (no-cloning again, this time working against you), you cannot just stick repeaters along the line like the phone company does. Past a couple hundred kilometers, direct QKD simply fails.

So how did Vienna get a working city-wide quantum network in 2008? And Tokyo in 2010? The answer is trusted nodes: you place secure relay stations between the endpoints, run QKD on each short hop, and hand the key along the chain. And the instant you do that, you have built a graph.

Each node (a relay station, a city, a lab) is a vertex.
Each QKD link between two nodes is an edge.
Each edge has a weight: how many secret key bits per second that link can produce.

Suddenly, every question you care about is a classic graph problem in disguise:

How do I route a key from Alice in one corner to Bob in the other? → shortest-path problem.
What is the maximum key rate I can push between two endpoints using all available paths? → maximum-flow / min-cut problem.
Which single node, if it fails or is compromised, disconnects my network? → cut vertices and connectivity.
How do I lay fiber to maximize resilience on a fixed budget? → graph design / network optimization.

The SECOQC network in Vienna [3] was the first large-scale demonstration to take this seriously: it defined an explicit network layer that treated the mesh of QKD links as a routed graph, relaying keys hop by hop across trusted nodes. The Tokyo QKD Network [4] did the same with a multi-vendor mesh and a live key-management layer deciding routes in real time. These are not photon experiments. They are graph algorithms running on top of photon experiments.

The uncomfortable footnote is that “trusted node” means exactly what it says: you have to trust the relay, because it holds the key in the clear for a moment. So the graph is not just about capacity, it is about trust topology. Minimizing how many nodes you must trust, and how badly a compromised one hurts you, is itself an optimization problem over the graph. (This is why the whole field is racing toward true quantum repeaters, which would let the edges carry entanglement instead of trust. But that is another article.)

Clue 2: the secret itself can be a graph

The network story uses graphs as bookkeeping. The next idea is stranger and, to me, more beautiful: certain quantum states are graphs, and their graph structure directly encodes what a cryptographic protocol can and cannot do.

Meet the graph state. Take a graph. Put a qubit on every vertex, each prepared in a particular superposition. Then, for every edge, apply an entangling operation between its two qubits. What you get is a single, highly entangled multi-qubit state whose entanglement pattern is literally drawn by the edges of the graph [5, 6]. Cluster states, the resource behind measurement-based quantum computing [5], are just graph states on a grid.

Why does a cryptographer care? Because of quantum secret sharing.

Classical secret sharing (Shamir’s famous scheme) lets you split a secret among $n$ people so that any authorized coalition can reconstruct it, but unauthorized ones learn nothing. The set of “who is allowed to reconstruct” is called the access structure. Markham and Sanders showed in 2008 that if you distribute the qubits of a graph state to the players, the access structure is determined by the graph’s connectivity [7]. The topology of the graph tells you, exactly, which subsets of players can recover the secret and which are locked out. Change an edge, change who you trust.

Read that again, because it is the whole point: a combinatorial property (graph connectivity) becomes a security property (who can decrypt). The math is not decorating the physics; it is the physics of the protocol. This was later demonstrated experimentally with real photonic graph states [7, follow-up].

Clue 3: graphs also tell you how much abuse a protocol survives

There is a third, quieter role for graphs, and it is about survival. Real qubits decohere, real channels are noisy, and any protocol you deploy has to be wrapped in quantum error correction (QEC).

The dominant family of quantum codes, the stabilizer codes, turn out to be deeply graph-theoretic. Schlingemann and Werner proved that quantum error-correcting codes can be built directly from graphs, and that every stabilizer code is equivalent to a graph code [8]. So the same graph-state formalism that describes your secret-sharing resource also describes your error-correcting armor. The connectivity of the graph controls both what you can hide and how much noise you can shrug off.

One formalism, three cryptographic jobs: routing keys, sharing secrets, surviving noise. That is a remarkably high return on a single mathematical idea.

Part II — The game theory lens

Graphs tell you about structure. But cryptography is not really about structure, it is about conflict. There is an adversary. She is smart, she is adaptive, and she gets to react to what you do. Modeling conflict between rational, strategic agents is the entire subject of game theory [11, 12]. So of course it belongs here.

Clue 4: QKD is a two-player game, and security is its equilibrium

Strip QKD down to its bones and you find a game:

Players: the legitimate team (Alice + Bob) versus the eavesdropper (Eve).
Eve’s strategy: which attack to mount, how hard to probe the channel.
Payoffs: Eve wants to maximize the information she steals; Alice and Bob want to maximize their guaranteed secret-key rate. Every bit Eve learns is a bit they lose. It is essentially zero-sum.
The tension: the more Eve learns, the more errors she injects, and the more visible she becomes. Information gained versus disturbance caused. That trade-off is the game board.

A security proof, in this language, is nothing but the search for an equilibrium: what happens when both sides play optimally? You must assume Eve plays her best possible move, not a convenient one, and show you are still safe. This is textbook minimax reasoning, the same principle von Neumann built game theory on in 1944 [12].

And this is not a loose analogy. Fuchs, Gisin, Griffiths, Niu, and Peres [9] did exactly this for BB84: they derived Eve’s optimal eavesdropping strategy, the precise attack that squeezes the maximum information out for a given disturbance. Knowing the adversary’s best response is what lets you draw the hard line: below some error threshold you are provably secure, above it you abort. The famous QKD error thresholds are, quite literally, the value of the game.

The information-theoretic capstone is the Devetak–Winter bound [10]: the extractable secret-key rate is

K  ≥  I(A : B)  −  I(A : E)

what Alice and Bob share, minus what Alice and Eve share. You give Eve the benefit of the doubt (she holds the entire environment, the “purification”), and whatever key survives that worst case is genuinely yours. It is the minimax answer to “how much secrecy is left after the adversary does her worst?”

Clue 5: when the strategies themselves go quantum

Here the story loops back on itself in a way I find delightful. We have been using classical game theory to analyze quantum protocols. But what if the game itself is quantum, if the players can make entangled, superposed moves?

That is quantum game theory, opened up by Eisert, Wilkens, and Lewenstein in 1999 [13]. Their result is genuinely spooky: take the Prisoner’s Dilemma, that classic trap where two rational players are doomed to betray each other, and let them play with entangled quantum strategies. The dilemma dissolves. A new equilibrium appears, one that beats anything possible classically. Entanglement changes what “rational play” even means.

The cryptographic payoff is that many security scenarios are two-party quantum games, and you can bound the adversary by bounding her probability of winning the game. The cleanest example is the monogamy-of-entanglement game of Tomamichel, Fehr, Kaniewski, and Wehner [14]. Monogamy is a deep quantum fact: if two qubits are maximally entangled, neither can be entangled with a third. Frame the security question as a game where Eve tries to guess Alice’s measurement while also having correlated with Bob, and monogamy caps her winning probability. That cap is the security proof, and it holds even if you do not trust your own devices (this is the seed of device-independent QKD). Security as a bounded game. It does not get more elegant than that.

Clue 6: what if your own allies are self-interested?

There is one last twist, and it is the most human. Every scheme above splits the world into “honest us” and “malicious Eve.” But real participants are neither saints nor demons, they are rational and selfish. They will deviate from the protocol if, and only if, it benefits them.

This is rational cryptography, launched by Halpern and Teague in 2004 [15]. They looked at secret sharing and multiparty computation and asked: what if the players are strategic agents who prefer to learn the secret while others do not? The result is unsettling, standard secret-sharing protocols can collapse under game-theoretic reasoning. By backward induction, if there is a known last round, no rational player will bother to broadcast their share in it (why help others?), so no one does, so the round before becomes the last, and the whole thing unravels. The fix requires designing protocols where honest behavior is a Nash equilibrium, where following the rules is each player’s self-interested best move.

For quantum secret sharing on the graph states of Part I, this closes the loop beautifully: the graph tells you who is able to reconstruct the secret, and game theory tells you who will actually choose to cooperate. Structure and incentive, the two lenses pointed at the same protocol.

Zooming out: two kinds of “optimize and analyze”

Notice the clean division of labor that emerged.

Graph theory optimizes the architecture. It answers how to build: route keys across a network (max-flow), design resilient topologies (connectivity), encode secrets whose access structure is drawn by edges (graph states), and armor everything against noise (graph codes). It is the mathematics of the protocol’s body.

Game theory analyzes the adversary. It answers how safe are we: find Eve’s optimal attack (minimax), bound the leftover secrecy (Devetak–Winter), cap the adversary via a game she cannot win (monogamy games), and keep even self-interested allies honest (rational cryptography). It is the mathematics of the protocol’s threat.

Physics gives quantum cryptography its raw power, the no-cloning theorem, the disturbance of measurement, the monogamy of entanglement. But raw power is not a protocol. The protocol, the thing you can build, deploy, route, and trust, is built out of mathematics. Graphs give it a skeleton. Games give it a conscience.

The fairy tale said physics protects our secrets. The truer version is quieter: physics gives us the pieces, and mathematics tells us how to assemble them so that even a perfectly rational, device-independent, fully quantum adversary walks away with nothing.

That is a better story anyway.

Appendix — Two pieces of the puzzle, made concrete

A. Key routing as max-flow. Consider a trusted-node QKD network. Model it as a graph $G = (V, E)$ where each edge $e$ has capacity $c(e)$ = the secret-key rate (bits/sec) that link can generate. To send key material from source $s$ (Alice) to sink $t$ (Bob), you want the maximum flow from $s$ to $t$ . The classic max-flow min-cut theorem tells you this maximum equals the smallest total capacity you would have to cut to disconnect $s$ from $t$ :

max_flow(s → t)  =  min over all s-t cuts of  Σ c(e)

Practically: your end-to-end secret-key rate is throttled by the weakest bottleneck of links separating the two parties, not by any single path. It also tells you exactly which links to upgrade (the ones in the min-cut) to raise the whole network’s capacity. This is why QKD network design is, at its core, a flow-optimization problem on a weighted graph [3, 4].

B. Security as the value of a game. In the zero-sum picture, let Eve choose an attack strategy $\sigma$ and let it induce an error rate $Q(\sigma)$ (how much she disturbs the channel) and an information gain $I_E(\sigma)$ (how much she learns). Alice and Bob’s guaranteed extractable key is, schematically,

K  =  max over their processing of  [ I(A:B)  −  max over Eve's σ of  I(A:E | σ) ]

The inner $\max$ over $\sigma$ is the crucial part: you assume Eve plays her best response. Solving that inner optimization is precisely what Fuchs et al. [9] did for BB84, and the Devetak–Winter bound [10] is the general information-theoretic value of the game. When $K > 0$ you have secrecy; the error rate at which $K = 0$ is the protocol’s security threshold. Security is, quite literally, the game having a positive value for the defenders.

References

C. H. Bennett and G. Brassard, “Quantum Cryptography: Public Key Distribution and Coin Tossing,” Proc. IEEE Int. Conf. on Computers, Systems and Signal Processing (Bangalore, 1984), pp. 175–179. Reprinted in Theoretical Computer Science 560 (2014), 7–11. DOI: 10.1016/j.tcs.2014.05.025.
A. K. Ekert, “Quantum Cryptography Based on Bell’s Theorem,” Phys. Rev. Lett. 67, 661 (1991). DOI: 10.1103/PhysRevLett.67.661.
M. Peev et al. (SECOQC collaboration), “The SECOQC quantum key distribution network in Vienna,” New J. Phys. 11, 075001 (2009). DOI: 10.1088/1367-2630/11/7/075001.
M. Sasaki et al., “Field test of quantum key distribution in the Tokyo QKD Network,” Opt. Express 19, 10387 (2011). arXiv:1103.3566. DOI: 10.1364/OE.19.010387.
R. Raussendorf and H. J. Briegel, “A One-Way Quantum Computer,” Phys. Rev. Lett. 86, 5188 (2001). DOI: 10.1103/PhysRevLett.86.5188.
M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Van den Nest, and H.-J. Briegel, “Entanglement in Graph States and its Applications,” Proc. Int. School of Physics “Enrico Fermi”, Course CLXII (IOS Press, 2006), pp. 115–218. arXiv:quant-ph/0602096.
D. Markham and B. C. Sanders, “Graph states for quantum secret sharing,” Phys. Rev. A 78, 042309 (2008). arXiv:0808.1532. DOI: 10.1103/PhysRevA.78.042309. (Experimental follow-up: B. A. Bell et al., Nature Commun. 5, 5480 (2014), arXiv:1411.5827.)
D. Schlingemann and R. F. Werner, “Quantum error-correcting codes associated with graphs,” Phys. Rev. A 65, 012308 (2002). arXiv:quant-ph/0012111. DOI: 10.1103/PhysRevA.65.012308.
C. A. Fuchs, N. Gisin, R. B. Griffiths, C.-S. Niu, and A. Peres, “Optimal Eavesdropping in Quantum Cryptography. I,” Phys. Rev. A 56, 1163 (1997). arXiv:quant-ph/9701039. DOI: 10.1103/PhysRevA.56.1163.
I. Devetak and A. Winter, “Distillation of Secret Key and Entanglement from Quantum States,” Proc. R. Soc. A 461, 207 (2005). arXiv:quant-ph/0306078. DOI: 10.1098/rspa.2004.1372.
M. J. Osborne and A. Rubinstein, A Course in Game Theory (MIT Press, 1994).
J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton Univ. Press, 1944).
J. Eisert, M. Wilkens, and M. Lewenstein, “Quantum Games and Quantum Strategies,” Phys. Rev. Lett. 83, 3077 (1999). arXiv:quant-ph/9806088. DOI: 10.1103/PhysRevLett.83.3077.
M. Tomamichel, S. Fehr, J. Kaniewski, and S. Wehner, “A Monogamy-of-Entanglement Game with Applications to Device-Independent Quantum Cryptography,” New J. Phys. 15, 103002 (2013). arXiv:1210.4359. DOI: 10.1088/1367-2630/15/10/103002.
J. Halpern and V. Teague, “Rational Secret Sharing and Multiparty Computation,” Proc. 36th ACM STOC (2004), pp. 623–632. DOI: 10.1145/1007352.1007447.

For the broad landscape, two reviews are worth your time: V. Scarani et al., “The Security of Practical Quantum Key Distribution,” Rev. Mod. Phys. 81, 1301 (2009); and S. Pirandola et al., “Advances in Quantum Cryptography,” Adv. Opt. Photon. 12, 1012 (2020). For the pure-math foundations, Bondy & Murty’s Graph Theory and Osborne & Rubinstein’s A Course in Game Theory.