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 came along and finally gave a bounded protocol for any number of agents, which was a huge theoretical breakthrough. But the query complexity is... let me just say it's a tower of exponentials in the number of agents. Like $2^{n^{n^{n^{n^n}}}}$ kind of territory. So yeah, not exactly something you're running on your laptop.

Why Quantum?

That insane complexity is what got me thinking. Classical protocols for envy-free division hit these combinatorial walls that seem really hard to get around. But quantum computing gives you tools like superposition, interference, and amplitude amplification that are specifically good at navigating huge search 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 that formalizes all of this. It lets us define what envy-freeness and proportionality mean when the resources obey quantum mechanics, where things like no-cloning and entanglement monogamy put hard constraints on how you can divide things up. It also lets us characterize exactly when fair allocations exist under those quantum constraints.

The Algorithm

With the model in place, the actual algorithm uses quantum primitives like Grover search, variational circuits, and adiabatic evolution to find envy-free allocations. The core idea is that you can use interference and amplitude amplification to bias the search toward fair outcomes, navigating the combinatorial space way faster than any classical protocol can.

We're targeting provable speedup over the Aziz-Mackenzie protocol. Ideally sub-exponential or polynomial query complexity where classical methods need that absurd tower of exponentials. Early simulation results on small instances are validating that the approach works, and we're actively pushing to characterize exactly where and how much quantum advantage we get.

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 was a massive result. But the complexity makes it purely theoretical. Quantum computing can bring that complexity down to something tractable, and that's a genuinely meaningful contribution to both fair division theory and practical network design.

I'll be posting updates as we lock down the formalization and start building the algorithm. Stay tuned.

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