Suppose you are at a dinner party in a fancy French restaurant. As soon as there is a lull in the conversation, the person on your right – a friend of a friend – leans over and asks “What do you do for a living?”.
Now suppose that you, like us, belong to the first generation of scientists who have studied for PhDs in quantum information. This interdisciplinary field combines aspects of computer science, mathematics and physics, and naturally, you find it absolutely fascinating. However, launching into an explanation of how all of these things come together seems a little risky during dinner. The last time you tried it, the other guests ended up enduring a five-minute lecture – not a good empirical result. You can do better this time. So you offer a short, to-the-point answer: “I’m a theoretical physicist.”
“Really! But what do you do, exactly?”.
Experience has taught you that the most effective answer to this question is one that involves travelling to conferences in exotic countries. But on this occasion, your subconscious rebels. You find your brain filling with concepts such as quantum cellular automata, quantum lambda-calculus and different models of computation. These things are the core of your work. They are what get you out of bed in the morning. So instead, you blurt out something like “Models of quantum computation and the consequences for theoretical physics.” From the look on your companion’s face, you know that you messed up again.
Information focused
The importance of quantum computation for theoretical physics is not a subject that fits neatly into a dinner-party conversation. Yet it is an idea that is increasingly having its day, as a number of world-renowned physicists – including Seth Lloyd, Lee Smolin, Gerard ‘t Hooft and Anton Zeilinger – have argued that physics should shift away from “matter” and focus instead on “information”. In their view, phenomena such as particle interactions, scattering and forces should take a back seat to concepts such as entropy, observation and information exchanges between systems.
Arguably, this focus on information is not new. After all, entropy (a measure of information) is a fundamental component of thermodynamics, while observers and measurements (respectively, the receivers of information and the means of gaining it) are central to relativity and quantum mechanics. Moreover, the information-centred approach has already led to significant breakthroughs in our understanding of fundamental quantum phenomena such as entanglement (the “spooky” correlation at a distance that quantum particles have under certain conditions) and decoherence (the reason why nobody has ever seen a real cat in a superposition of dead and alive). So, to a large degree, modern physics is already “informational”. However, there is a growing opinion that in the future, physics will be computational as well.
To understand what this means, we need to start by going back to the 1970s, when scientists including Edward Fredkin, Norman Margolus, Tommaso Toffoli and Stephen Wolfram first proposed that the universe could be modelled as a giant parallel computer. In this “digital physics” view, particles should be treated as patterns of information moving across a vast grid of microprocessors, rather than material bodies colliding and scattering – much like a tennis ball can be thought of as a pattern of pixels moving across your TV screen during the Wimbledon final, rather than a lump of rubber ricocheting off a grassy surface. Digital physicists, for their part, are like characters in a video game who are desperately trying to understand the rules.
A striking result to come out of this 1970s work on digital physics was Robin Gandy’s argument that the universe can be simulated by a classical computer with unbounded memory. Gandy was a British mathematician, logician and student of Alan Turing, and he began his argument by noting that physicists agree on certain principles. One is that the laws of physics are homogeneous: they remain the same everywhere and at all times. If they did not, they would not deserve to be called “laws”. Another principle states that the laws of physics are causal: information has a bounded speed of propagation, c, meaning that events occurring at time t + Δt have their causes at time t lying within a disc of radius cΔt. Finally, and somewhat more controversially, Gandy stated that it is reasonable for physicists to believe that any finite volume of space can only contain a finite amount of information (a similar principle has been articulated by the Israeli theorist Jacob Bekenstein, although his bound also involves the energy of the system being considered).
From these three principles, it follows that if space is divided into cubes, each cube can be fully described by the finite information it contains. Moreover, the state of each cube at time t + 1 is a function of the state of the neighbouring cubes at time t; in other words, the state is obtained by applying what information theorists call a “local rule”. Finally, it follows that this local rule is the same everywhere and at all times. Thus, the state of the entire universe at time t + 1 can be computed by applying some fixed local rule everywhere in space.
The effect of this argument is to reduce the universe to a type of parallel computer known as a cellular automaton. Many readers have probably played with a simple cellular automaton before, in the form of John Conway’s “Game of Life”. The classic Game of Life consists of a 2D grid of cells in which each cell can be either “alive” or “dead” (figure 1). Once the user has decided which cells will be alive initially, the state of any given cell at a later time step will be determined by that cell’s state at the previous time step and the states of its eight immediate neighbours, according to rules that simulate the effects of underpopulation, overcrowding and reproduction. These rules are very simple, yet it has been shown that the Game of Life is universal, meaning that it can be made to compute any known classical algorithm – in the same way that one can use simple logic gates and wires to perform any computation using a more conventional computer.
But is there any chance that the real universe we see and experience could be such a simple game?
Back to the table
The problem for Gandy’s model – and the reason why the original digital-physics project was doomed to failure – boils down to one thing: quantum physics. To understand why, let us return to our dinner party at the French restaurant, where the food is getting cold.
Against your better judgement, you launched into an explanation of quantum theory using the knives and forks on the table. Now you hear yourself saying “Pick a system that can be one of two things – like this item of cutlery, which can be either a knife or a fork.” You place the knife and fork on the table with their handles touching at a right angle, forming the x and y axes of a 2D space. “Well, in quantum theory, this one piece of cutlery does not have to be one or the other. The possible states are the entire table. For instance, it can be here,” you say, jabbing your finger at the table. But although you are clearly touching the tablecloth at the point representing the 1/√2 |knife〉 + 1/√2 |fork〉 superposition state, you sense that your audience may not be grasping the full implications. You ponder the wisdom of an alternative explanation involving salt and pepper mills, but before you can begin, your waiter arrives with the dessert menu.
The reason we do not encounter superpositions of knives and forks on a daily basis is that as soon as one observes a quantum system, it becomes classical again. This means that the smallest unit of quantum information, referred to as a “qubit”, can only store a single bit of classical information: 0 or 1, knife or fork. In that sense, Gandy’s principle of finite information density remains compatible with quantum theory. However, as we saw in the restaurant, before one observes a qubit, it is allowed to be in any superposition of states. Hence, it is no longer the case that each cube of space can be fully described by the finite information stored in it, and this is where Gandy’s argument falls down.
Hopes that digital physics might be resurrected in some form rose in the early 1980s, when Richard Feynman proposed that the blatant gap between the power and information content of quantum theory and that of classical computers might be bridged by a new type of computer. His idea was born out of frustration at seeing classical computers take weeks to simulate quantum-physics experiments that happen faster than a blink of an eye. Intuitively, he felt that the job of simulating quantum systems could be done better by a computer that was itself a quantum system.
Like their classical counterparts, quantum computers consist of circuits. To construct quantum circuitry you need quantum wires, which are analogues of real wires carrying conventional bits (as voltages), except they carry qubits. There are many different ways of implementing qubits and wires experimentally; one example is to use the two spin states of a spin-half atomic nucleus as the qubit states, and manipulate them using nuclear magnetic resonance. But you also need quantum gates that can be applied to these wires. For instance, one can imagine that it might be useful to transform a qubit in state |0〉 into the 1/√2 |0〉 + 1/√2 |1〉 superposition state mentioned earlier. A device that performs this operation is called a Hadamard gate. You also need at least one two-qubit gate; one example is the controlled π/8 gate, which causes a universal phase change if both qubits are in state |1〉 and leaves them unchanged otherwise. These two-qubit gates are universal: by combining them, one can compute any quantum algorithm – just as one can use classical gates such as the two-bit NAND gate (which always returns a value of “true” unless both inputs are true) to compute any classical algorithm.
Towards quantum cellular automata
Over the past decade or so, experimentalists in many groups around the world have successfully implemented quantum wires and one-qubit gates such as the Hadamard gate described above. The true difficulties lie with precision two-qubit gates and with protecting many wires from the environment – remember, if the environment “observes” the quantum wires, they become classical again.
Working with Gilles Dowek, and building on previous research results with Vincent Nesme and Reinhard Werner, one of us (PA) developed a version of Gandy’s hypotheses that accounts for the complexities of quantum mechanics. Mainly, this means replacing Gandy’s finite-density principle with the hypothesis that a finite volume of space can contain only a finite number of qubits. Considering the implications of the three updated principles led us to a vision of the universe that behaves like a quantum version of the cellular automaton discussed earlier.
A quantum cellular automaton is very much like a classical cellular automaton, except that now the cells of the grid contain qubits. The time evolution from time t to t + 1 in this model is obtained by applying a quantum gate operation to neighbourhoods of cells repeatedly, across space. However, there are some subtleties to quantum cellular automata that cannot be explained quite so easily in a picture. For example, the cells can now be in a superposition of states, and they can also be entangled with any other cell.
A good example of a quantum cellular automaton is our proposed 3D “Quantum Game of Life”, which takes its name from Conway’s famous original. In this quantum cellular automaton, each cubic cell can be |empty〉, |full〉 or any superposition of these two qubit states, such as 1/√2 |full〉 – 1/√2 |empty〉. The behaviour of the system as it evolves in time can be obtained by applying a quantum gate to a 2 × 2 × 2 grid of cubes (figure 2). This local quantum gate defines the “rule of the game”.
There is, of course, a big gap between constructing a “toy-model” quantum cellular automaton and applying the lessons learned from it to the real world. But if the updated versions of Gandy’s hypotheses hold true – and we can indeed describe the universe as a gigantic quantum cellular automaton – then studying physics becomes a game of attempting to deduce the “program” of the vast, parallel quantum computer that we live in.
The conventional approach to deducing the program is, of course, not to use cellular automata or anything like them, but to probe the “rules of the game” with increasingly refined physics experiments, such as those performed using the Large Hadron Collider at the CERN particle-physics lab. We believe, however, that there is an alternative computer-science-oriented method, one that attempts to find the rules deductively.
We can begin this deductive process by discarding rules that are too simple, on the grounds that we live in a complex universe. Next, we note that all sufficiently complex rules can be made to simulate each other. In other words, if the rule of a particular quantum cellular automaton is complex enough, then it can simulate all other quantum cellular automata, even when the other automata have rules that are horrendously complicated. A quantum cellular automaton that can perform such a simulation is said to have intrinsic universality, a concept we have developed in the quantum setting. Hence, if we can find the simplest, intrinsically universal rule for a quantum cellular automaton, we can use it to find the simplest and most “natural” (in the sense of being how nature does it) way of implementing or simulating physical phenomena.
Beyond quantum digital physics
The Quantum Game of Life we have described is a minimal, intrinsically universal quantum cellular automaton, but it remains to be seen whether all physical phenomena can be encoded using the concepts developed here. Many difficulties lie ahead for those of us who are trying to answer the question “How does nature compute itself?”. One problem is that models of quantum cellular automata are typically not isotropic. For example, on a square grid, signals can generally propagate faster in the four cardinal directions than they can diagonally, so grid-type models cannot easily simulate ripple-like wavefronts. Another problem is that, just as classical digital physics did not integrate the radical features of quantum theory, and thus needed to be updated, quantum digital physics does not integrate general relativity, so it will have to be updated, too. Some members of the quantum-gravity community, including Alioscia Hamma, Fotini Markopoulou, Simone Severini and Lee Smolin, have already been making some attempts in this direction, so we may well be on the verge of a trend towards a new, relativistic, quantum digital physics.
Within this trend, the concepts discussed here, namely those of quantum cellular automata and intrinsic universality, are likely to prove key in finding simple, minimal and universal “toy models” to work on. From a computer-science point of view, reaching this goal will amount to understanding the nature of the ultimate parallel and relativistic quantum computer. Yet we are obliged to conclude with a word of caution: these ideas may not be all that helpful in a restaurant conversation. Attempting to explain them may, in fact, end with the other diners deciding that you are the best person to call the next time their (classical) computer breaks down. But on a more positive note, if we can find the rules, everyone will be a winner in this game of life.
![The "Gosper glider gun" formation in Conway's Game of Life](https://physicsworld.com/wp-content/uploads/2012/05/grattage2.jpg "The "Gosper glider gun" formation in Conway's Game of Life")
![Diagram illustrating the "rules" of the quantum game of life](https://physicsworld.com/wp-content/uploads/2012/05/grattage4.jpg "Diagram illustrating the "rules" of the quantum game of life")
