A Quantum Algorithm for Cake-Cutting

Okay so this one is a bit different from what I usually post about. I've been thinking a lot about fairness in networked systems lately, and I went down a rabbit hole into the cake-cutting problem, which is this classic model from fair division theory. The idea is simple: you have a cake (some divisible resource), a bunch of agents who all value different parts of the cake differently, and you need to divide it so that nobody envies anyone else's piece. That's called an envy-free allocation.

Sounds easy enough for two people. One person cuts, the other chooses. Done. For three people, Selfridge and Conway figured out a clever bounded protocol a while back. But for four or more agents? That was an open problem for decades.

Brams and Taylor eventually gave a protocol that works for any number of agents, but the number of queries and cuts it needs can be unbounded. Then Aziz and Mackenzie gave a bounded protocol for any number of agents, which was a major theoretical step. The catch is the query complexity. It is a tower of exponentials in the number of agents, roughly $2^{n^{n^{n^{n^n}}}}$ territory. So, not exactly something you run as a practical allocation routine.

Why Quantum?

That complexity is what got me thinking. Classical protocols for envy-free division hit combinatorial walls that seem hard to get around. Quantum computing gives you tools like superposition, interference, and amplitude amplification, which are at least designed for searching large spaces. So the natural question is: can we design a quantum cake-cutting algorithm that does better?

That's the core of this project. We want to build a quantum analogue of the cake-cutting problem and design an algorithm that can find envy-free allocations more efficiently than the best classical protocols.

Cake-Cutting on Networks

There's also a really interesting line of work on cake-cutting where agents are connected via a graph or network. In the networked version, you only care about envy relative to your neighbors in the graph, not every other agent. So an allocation is envy-free if no agent prefers any of her neighbor's shares to her own. This is way more natural for real systems where agents don't have global visibility.

Bei, Qiao, and Zhang showed you can get envy-free allocations on trees using a moving-knife procedure, and Bei, Elkind, Segal-Halevi, and Suksompong extended things to arbitrary graphs. This network structure maps really nicely onto quantum networks, where you've got nodes connected by entanglement sources and you need to fairly distribute quantum resources across the network.

What Does "Quantum Cake" Even Mean?

Before you can cut a quantum cake you have to figure out what the cake actually is. In the classical problem the cake is just the interval [0, 1] and agents have valuation functions over subintervals. In the quantum version, the "cake" is a pool of quantum resources: entanglement, qubits, quantum channels distributed across a network. And agent valuations aren't just preferences over intervals anymore. They're measures like fidelity, entanglement entropy, or mutual information that capture how useful a chunk of quantum resource actually is to a given agent.

We built a quantum analogue of the classical Webster-Webber model to formalize this. It gives a way to define envy-freeness and proportionality when the resources obey quantum mechanics, where things like no-cloning and entanglement monogamy put hard constraints on what can be divided. It also gives a starting point for characterizing when fair allocations exist under those constraints.

Is It Possible to Come Up With Such Algorithm?

With the model in place, the algorithm uses quantum primitives like Grover search, variational circuits, and adiabatic evolution to look for envy-free allocations. The core idea is to use interference and amplitude amplification to bias the search toward fair outcomes, instead of checking the combinatorial space in a purely classical way.

The goal is to understand whether there is a provable speedup over the Aziz-Mackenzie protocol. Ideally, one would like sub-exponential or even polynomial query complexity in settings where the classical protocol has that tower-of-exponentials behavior. The early simulations are small, so I do not want to oversell them, but they are useful for checking that the formulation is not nonsense.

Why This Matters Beyond Quantum

Here's the thing I find most exciting. Even if large-scale quantum networks are years away, the algorithmic insights from this project translate directly to classical systems. The quantum algorithm can be used as a subroutine for classical resource allocation problems: bandwidth distribution in telecom networks, GPU scheduling in cloud computing, load balancing in distributed systems. If you can get provably fairer allocations without killing your performance, that's immediately useful today.

Fairness in resource allocation isn't just a nice theoretical property. In real networks, unfair allocation leads to resource starvation, degraded quality of service, and all sorts of downstream problems. And as quantum networks start to become real, the question of how to fairly distribute quantum resources (which are fundamentally different from classical ones because of entanglement and no-cloning) is going to be critical.

The Aziz-Mackenzie protocol proved that bounded envy-free division is possible for any number of agents, which is a big result. But the complexity keeps it mostly theoretical. The question I care about is whether quantum tools can make some version of that guarantee more tractable, especially in networked resource-allocation settings.

References

1. Z.-P. Xu, J. I. de Vicente, L.-L. Sun, and S. Yu. "Quantum network-entanglement measures." Quantum, 9:1736, 2025. Link
2. F. E. Su. "Rental harmony: Sperner's lemma in fair division." The American Mathematical Monthly, 106(10):930-942, 1999.
3. S. J. Brams and A. D. Taylor. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, 1996.
4. S. J. Brams and A. D. Taylor. "An envy-free cake division protocol." The American Mathematical Monthly, 102(1):9-18, 1995.
5. H. Aziz and S. Mackenzie. "A discrete and bounded envy-free cake cutting protocol for any number of agents," 2017. arXiv:1604.03655
6. X. Bei, Y. Qiao, and S. Zhang. "Networked fairness in cake cutting," 2017. arXiv:1707.02033
7. X. Bei, E. Elkind, E. Segal-Halevi, and W. Suksompong. "Dividing a graphical cake." SIAM Journal on Discrete Mathematics, 39(1):19-54, 2025. Link
8. M. Pant, H. Krovi, D. Towsley, L. Tassiulas, L. Jiang, P. Basu, D. Englund, and S. Guha. "Routing entanglement in the quantum internet," 2017. arXiv:1708.07142