Bits and balls: Quantum computation is an island in theoryspace

Quantum computers are more powerful than ordinary computers because they work with coherent “quantum bits” instead of ordinary zeroes and ones. But what if the rules of nature were different from what we believe today - could there be efficient “science fiction” computers running on even more elaborate kinds of bits? Two researchers from IQOQI Vienna have now shown that the answer must be “no”, as long as those machines satisfy the same construction principles as classical and quantum circuits.

Computers have become an essential part of our everyday life. What has once seemed like a magical artifact is now real technology in our pockets. But computers are physical objects. And as quantum computation has taught us, new physics might enable us to envision new types of computers.

What other types of computation could there be if physics were different? Marius Krumm and Markus Müller from the Institute for Quantum Optics and Quantum Information in Vienna have taken up the challenge to answer this question. The stakes are high: even if we cannot build such a “science fiction” computer in the lab, studying its theoretical properties improves our understanding of quantum computation. And we can learn about nature, since the ultimate limits of computation are set by physics itself.

The key elements of classical and quantum computers are the bits: alternatives of “yes” and “no”, wired together in a circuit. On an ordinary laptop, these bits would have to be either 0 or 1. Quantum computers, on the other hand, work with quantum bits: we can think of these as points on a three-dimensional ball. The north pole represents 0 and the south pole 1, but a “qubit” can be in any place in between (say, on the equator) – in a superposition state.

Krumm and Müller start with bits that are points on a ball, too. But in contrast to quantum bits, this ball does not need to be three-dimensional. What happens to computation if we allow the balls to have, say, dimension four or five? Two other IQOQI researchers, Borivoje Dakić and Ćaslav Brukner, have previously made a compelling conjecture: that these bits describe alternative physics in universes with more than three spatial dimensions. To check this idea, Krumm and Müller make two assumptions on how these bits are wired: first, they are processed via reversible gates, like “AND” or “NOT”. Second, they satisfy an intuitive property of classical and quantum computation: knowing the single bits and how they are correlated tells us everything there is to know.

The surprising result: these computers would have extremely limited capabilities. They could not even run classical algorithms, let alone outperform quantum computers – even though their bits would be more complicated than quantum bits. In this sense, dimension three and the quantum bit are special, and so is quantum computation: in a phrase coined previously by Scott Aaronson, it is an “island in theoryspace”.