Whether it's in the pages of a book or the electrical circuits within a computer, information always has a physical manifestation. Professor Richard Jozsa, who has recently been elected a Fellow of the Royal Society, studies this link between physics and information. His work not only laid the foundations of quantum computation and information, but also probes the fundamental theory that underlies these fields.
At first sight, information seems entirely un-physical. The reason we can write novels or make up lies is that there's no limit to what we can dream up in our heads. Yet, that information ultimately resides in the physical world. "If I say 'yes' or 'no' to you, you are simply distinguishing two sound waves using your ears as a physical measuring device," explains Jozsa. "And if I write 0 or 1 on a piece of paper they are distinguishable by the patterns of ink on the page."
The possibilities and limitations of computation cannot be determined by pure thought or by mathematics alone. Richard Jozsa
This link between information and the physical world has extraordinary consequences for computation. If I told you that a particular computational task can't be solved because the laws of physics don't allow it, you would be surprised. But computation is nothing more than the processing of information, and if information is rooted in the physical world, then so is computation. "The possibilities and limitations of computation cannot be determined by pure thought or by mathematics alone," says Jozsa. "They must rest on the laws of physics and be constrained by them."
Into the quantum
The computing devices we have developed so far, from the simple abacus to fast supercomputers, rest on the capabilities of classical physics. Newton's laws of motion for example, and Maxwell's equations for electromagnetism. But classical physics has been superseded by quantum physics which is radically different.
"So we can ask what impact this new physics has on information processing tasks," says Jozsa. "And it turns out that this impact is extraordinary in almost every respect. There are entirely new ways of computing that are exponentially more powerful than any classical methods." In communications there are completely new protocols such as quantum teleportation, which allows information to be transmitted from a sender to a receiver without passing through the space in between (in a suitable sense). "And in cryptography we have whole new ways of implementing information security at a level that is fundamentally impossible in classical physics."
There isn't a single quantum effect that underlies all these new possibilities. But to give you a flavour of the kind of things we are dealing with, let's consider quantum entanglement: the fact that two quantum particles can be linked so that what happens to one particle (say an experimenter measuring its momentum) immediately affects the other particle (forcing its momentum to be the negative momentum of the other particle). The link can remain even when the particles are moved far apart. This "spooky action at a distance," as Einstein famously called it, can be exploited for novel communication techniques, for example the quantum teleportation already mentioned above.
Entanglement is also a crucial ingredient in quantum computing. Classical computing involves bits that can take the values 0 or 1. A string of n bits involves n pieces of information: whether each of the n bits is a 0 or a 1. Quantum computing involves so-called qubits. Not only can these be in a superposition state of simultaneously being 0 and 1, they can also be entangled with each other. The many quantum correlations between entangled qubits drive up the number of pieces of information that's involved in the system to 2n, which is a lot more than the n numbers involved in a classical string — it's this fact that allows quantum computation an exponentially enhanced information processing power over classical computation.
Laying foundations
Jozsa's contributions to quantum information and computation theory have been ground-breaking. Back in 1991, together with David Deutsch, he developed the first-ever example of a quantum algorithm that could be proven to work exponentially faster than any classical algorithm designed to perform the same task. More generally he laid the foundations for our understanding of how quantum entanglement and other quantum effects can be exploited in computation. In a seminal paper published in 1993, he also co-invented the idea of quantum teleportation.
Yet, paving the way for new technological advances isn't Jozsa's main motivation, at least not these days. "My work also sheds light on fundamental physics," he explains. "The novel conceptual framework of theoretical computer science gives an entirely new perspective on fundamental physics. To me this is by far the most exciting and important aspect of the subject. Quantum mechanics is notorious for being a complete enigma without any adequate conceptual foundation. Computer science provides new ways of probing it."
Probing the limits
In this context the limitations of quantum computing are as interesting as its possibilities. Jozsa and Deutsch's first quantum algorithm inspired another quantum algorithm, developed in 1994 by Peter Shor, that can factorise integers into their prime factors much more efficiently than classical computing. Integer factorisation belongs to a class of problems called the NP class, which contains certain types of classically hard problems computer scientists are particularly interested in. At first there was speculation that quantum algorithms would be able to nail all NP problems efficiently.
"But remarkably this turns out not to be the case," says Jozsa. "We haven't proved that yet, but it certainly seems that way." One of the problems is that while entanglement enables us to process an "exponential amount" of information efficiently, another quantum phenomenon snatches away some of that benefit: the fact that, when you extract information from a quantum system, you cannot help but disturb it. In cryptography this effect is welcome. An eavesdropper intercepting a suitably encoded message can't avoid leaving their mark on it, thereby alerting the intended recipient that communications aren't secure. But in quantum computation the phenomenon limits the amount of information you can extract from your quantum algorithm. The destructive effects of measurement are finely balanced against the exponential benefits of entanglement to set a fundamental limit to what we can feasibly compute.
"It's a remarkable thing for a physical theory to be limited in this way," says Jozsa. "This suggests a deep fundamental significance of ideas from computational complexity in the foundations of physics, which has never been entertained before."
Jozsa's work in the field is entirely theoretical — indeed we are only now on the verge of building functional quantum computers. But once they come into existence, Jozsa thinks they will be just as interesting from a fundamental physics point of view as they will be from a computational point of view. "I, for one, don't believe that quantum mechanics is the ultimate correct theory," says Jozsa. "It's wonderful in many ways, but it is plagued by foundational and conceptual inconsistencies." To really test the theory you need reliably controlled quantum devices that can manufacture and manipulate whatever quantum state you are interested in — and that's exactly what quantum computers will be. "I think the most exciting thing you can do with a quantum computing machine is to probe quantum physics and to try to find a failure of [the theory] and maybe precipitate the next great paradigm shift in physics."
The pleasure of maths
Jozsa has been Leigh Trapnell Professor of Quantum Physics at the Department for Applied Mathematics and Theoretical Physics since 2010. "I am very pleased to be working here," he says. "It's a wonderful environment both physically and intellectually. Our building is purpose-built for the needs of mathematicians. There are these wonderful open spaces for relaxed interaction, and a large central core that is always buzzing with intellectual activity with everyone united in the sheer pleasure of doing mathematics. And of course there are so many excellent, world-leading research groups within the Faculty."
"Also, the quality of the students is amazing here. It's a great privilege to stand up there and lecture to such a highly selected audience, even more so when it's your own subject."
Jozsa's subject only came into existence over the course of his career, to no small extent thanks to him. The Royal Society has recently recognised his pioneering contributions by electing him a Fellow. "I am totally delighted," he says. "I have always held the Royal Society in highest regard, from the earliest days of my career. To join a society with names like Newton, Faraday, Einstein, Darwin Maxwell and many others — it's absolutely amazing." The Faculty whole-heartedly endorses the Royal Society's wise choice — congratulations Richard Jozsa!
You can find out more about quantum computing in this series of articles on Plus magazine, based on an interview with Jozsa.
