How to Count Pigeons Using a Quantum Computer (Without Breaking Math)
By Maria Violaris, PhD student at the University of Oxford
The year is 2015. Having had enough of cats, a group of quantum physicists deliberate over which creature they will subject to their mind-bending thought experiments next. “Lions? Too fearsome. Dolphins? Too intelligent. Tardigrades? Too obscure. Quantum pigeons? …Perfect.” This, at least, is how I like to imagine Yakir Aharonov and his collaborators conceived of the quantum pigeonhole paradox — a thought experiment that doesn’t just swap one allegorical animal for another, but also claims to rewrite the fundamental principles of mathematics entirely.
Quantum pigeons appear to violate the famous pigeonhole principle, calling into question whether our basic rules of counting need an update. These pigeons play a starring role in the latest addition to our Quantum Paradoxes content series, where I transform quantum thought experiments into quantum circuits using Qiskit. In our first two installments, I explained the quantum bomb tester and Hardy’s paradox — two classic quantum thought experiments first proposed in the 1990s. In this blog and the accompanying YouTube video, I’ll show you how to implement Aharonov’s more recent thought experiment as a quantum circuit, and we’ll see for ourselves whether the pigeonhole paradox really poses a threat to our understanding of the most elementary principles of mathematics.
But, before we do that, let’s take a moment to go over the classical pigeonhole principle.
If you have three pigeons and two pigeonholes, can you fit your three pigeons into the two holes without placing two pigeons in the same hole? Classically, the answer is “no.” The pigeonhole principle states that if three pigeons are in two pigeonholes, at least two pigeons must occupy the same hole.
More generally, the pigeonhole principle tells us that if some number of objects are put into some number of groups that is fewer than the number of objects, then at least two objects must be in the same group. This is intuitively obvious.
Happy birthdays, hackathons, and hairy Londoners
If you do not have three pigeons on hand, you can see this principle at work using other examples from everyday life.
For example, if 367 different people watch my video about the pigeonhole paradox, at least two of them must have the same birthday. If you have only pink and blue socks in your sock drawer, and you pick out three socks at random, you are certain to have a matching pair.
If those seem too simple, try this on for size: London has a population of millions, but the maximum number of hairs on the human head is less than one million, meaning at least two non-bald people in London should have exactly the same number of hairs on their head. This example appears in writing as early as 1622, where a sentence in the Latin text Selectæ Propositiones says “It is necessary that two men have the same number of hairs, écus [French coin], or other things, as each other.”
This is one of many non-obvious mathematical results the unassuming pigeonhole principle enables us to prove, especially in fields like number theory and combinatorics.
Turning pigeons into qubits
In their 2015 paper, Aharanov and his collaborators set out to investigate whether the pigeonhole principle still holds when we make our pigeons quantum.
Thinking in quantum computational terms, we model a pigeon that can exist in one of two pigeonholes (e.g., top pigeonhole and bottom pigeonhole) as a qubit that can be in one of two states (e.g., 0 and 1). These quantum pigeons can also be in a superposition of two pigeonholes, just as a qubit can be in a superposition of two states.
Let’s imagine each of three quantum pigeons in a superposition of two pigeonholes. Specifically, our three qubits modelling the three pigeons begin in the |+++⟩ state (remember, H|0> = |+>). We can measure each of these three qubits in the y-basis, whose basis vectors are |+i⟩ = |0⟩ + i|1⟩ and |-i⟩ = |0⟩ — i|1⟩. There is some chance that our y-basis measurements will project the three qubits into the state |+i +i +i⟩, where they are once more in a superposition of the two pigeonholes.
To test the pigeonhole principle, we need to check whether any two of our three qubits were in the same state before we measured them. One way to do this would be to bring in an extra, fourth qubit before we make our y-basis measurements. For example, if we implement controlled-NOT gates between each of the first two qubits and the extra qubit we’ve just introduced to our circuit, then measuring this extra qubit will reveal whether the first pair of qubits are in the same state.
If the first two qubits are in the same state, then we know the measurement of the fourth qubit has projected our three quantum pigeons into a state that has zero overlap with the |+i +i +i⟩ state. If you enjoy your linear algebra and want to do the math to check this, you can do so by taking the inner product of two states — the |+i +i +i⟩ state and the state the three qubits are projected into after we measure the fourth. If you do this correctly, you should find that the inner product of the two states is zero.
This should hold true even if we use the fourth qubit to check whether the first and third qubits were the same, or if we use it to check whether the second and third qubits were the same. In either case, if the qubits are in the same state, we know the state they will be projected into should have zero overlap with the |+i +i +i⟩ state.
From this, the authors concluded that since our y-measurements projected the qubits to the |+i +i +i⟩ state, no two qubits were in the same state before the y-measurement. This would mean that our three quantum pigeons fit into two pigeonholes, with no two pigeons in the same hole!
This may seem to violate the pigeonhole principle, but we only need to make a small adjustment to the way we count our quantum pigeons to draw different conclusions. For example, if we check whether all three qubits were in the same state before the y-basis measurements, we find there is an overlap with the |+i +i +i⟩ state.
It’s also important to note that quantum systems do not have a definite state before they are measured. This prevents us from reasoning consistently about the outcomes of hypothetical measurements that we could have made to check whether the qubits are in the same state, but which never actually occurred.
Taking pigeons to class
The quantum pigeonhole paradox is still very much a subject of ongoing debate.
There are many arguments, including those I have summarized in this blog, which contend that the thought experiment does not truly violate the fundamental pigeonhole principle and all the results that depend on it. There are also researchers who claim to have demonstrated the pigeonhole paradox experimentally, and others who suggest that quantum theory does indeed violate the pigeonhole paradox — albeit in a different way to the original thought experiment.
Having carefully analyzed the pigeonhole thought experiments and its experimental implementations myself, I would argue that quantum systems have an inherent property that should protect the pigeonhole principle from being violated in any definitive way. Namely, quantum systems do not have definite states before we measure them.
This is not to suggest that the pigeonhole thought experiment does not have its uses.
The day after filming my video about the pigeonhole paradox, I found myself preparing to teach a problem class about quantum error correction — the process by which we identify and correct errors that occur in quantum computers. One of the problems I needed to explain was about detecting bit-flip errors, which is when the state of a qubit accidentally flips from 0 to 1 or vice-versa.
Solving the problem involved introducing an extra qubit to check if a set of two qubits were in the same state — in much the same way that I checked to see if a pair of quantum pigeons were in the same state. So, I brought my quantum pigeons to class, and took the opportunity to explain how there are at least two uses for the same quantum circuit: checking whether we are being fooled by a quantum computer, and checking to see if we are being fooled by basic math.
Watch my latest video on the Qiskit YouTube channel to learn more about the pigeonhole thought experiment, then try it out for yourself using Qiskit. You’ll find all the code you need as well as step-by-step instructions in the Jupyter Notebook we’ve created, linked here.
