Quantum Information: Turning Points

Device independent quantum cryptography

Quantum mechanics provides new challenges, and new opportunities, for the field of cybersecurity. An important example is quantum key distribution (QKD), which provides a way for two people (Alice and Bob) to share a secret key, and detect if an eavesdropper (Eve) tries to listen in. The laws of quantum mechanics state that observing a quantum system will always disturb the system. So if Alice sends a simple quantum system, such as a single photon, to Bob, and Eve tries to measure the photon to learn what Alice is sending, her measurement will disturb the system. This disturbance allows Alice and Bob to immediately detect Eve’s presence. If they do not detect any eavesdropper disturbance, Alice and Bob know that it is safe to use their key to encrypt private messages.

In 2005, Perimeter Research Faculty Lucien Hardy, graduate student (and later postdoctoral researcher) Jonathan Barrett, and Adrian Kent (now a Distinguished Visiting Research Chair), started to consider whether QKD could be secure even if quantum mechanics isn’t quite right. If any part of the theory ever proved to be incorrect, a sufficiently advanced eavesdropper using post-quantum physics might be able to listen in without causing a disturbance. Could we safeguard against such an event using existing technology?

To achieve this, they developed a new construction of QKD that relied on fewer assumptions about how the QKD devices work internally. The proof, inspired by ideas from quantum foundations, guarantees secure quantum key distribution even against an advanced, post-quantum Eve. The only requirement: that Eve not be capable of sending a signal faster than light.

This paper spurred an immense amount of work developing the idea of device independent QKD. Researchers realized that the new proof was also useful even in cases where you assume quantum mechanics is correct, but you don't want to make any assumptions about the devices (e.g. you bought the devices from a third party, and can't directly verify how they work or if they can be trusted).

In 2011, Kent and Perimeter postdoctoral researcher Roger Colbeck made another important contribution to this area, a protocol known as ‘private randomness expansion.’

Randomness is useful in encryption as a source for producing secure keys. A quantum device can produce a random result by sending a photon through a beamsplitter, where it will emerge randomly on one side or another. But how do you ensure that an untrusted device built by an adversarial agent is outputting something truly random, without testing the device itself?

Kent and Colbeck propose a new way to ensure you can trust the output of an untrusted device. It requires seeding the untrusted device with your own private random string of numbers, and working with the output to produce a longer random string of numbers (a randomness expansion). This technique lets all parties trust the randomness of the outcome, regardless of who owns the device.

Both of these novel ideas have sparked significant progress in the field of quantum cryptography to date.

QIP = PSPACE

Computational complexity theory is the study of computational problems and attempts to sort and classify problems by their level of difficulty. The complexity class known as ‘PSPACE’ (which stands for ‘Polynomial Space’) consists of problems that can be solved with potentially large amounts of time, but only a reasonable amount of ‘scratch space’ (temporary storage on a hard drive).

One example of a PSPACE problem is determining who will win a game of Go based on the current position with optimal play by both sides, an exceedingly difficult problem given the number of possible moves each turn.

A major result of classical complexity theory from the early 1990s determined that IP=PSPACE, where IP is the set of problems for which there is an ‘interactive proof’ of reasonable size. What this means is that someone sufficiently knowledgeable could, with a short back-and-forth conversation, convince you completely that, for instance, Black would win the Go game from a particular position against any possible strategy by White. In practical terms, these ‘conversations’ happen between two computers, with one attempting to prove its case, while the other checks to be sure.

In 2011, Perimeter postdoctoral researcher Zhengfeng Ji and his collaborators took IP=PSPACE into the realm of quantum computing. They established that quantum interactive proofs (QIP), where the conversation consists of quantum systems sent back-and-forth between quantum computers, are no more powerful than classical proofs.

This is surprising, since quantum mechanics seems to provide some sort of advantage over classical mechanics in many other situations. As part of this research, Ji and his collaborators were one of the first to use a powerful technique known as “semidefinite programming” in the field of quantum information. Today semidefinite programming is widely-used, in part because their paper helped establish its usefulness to the field.

QIP=PSPACE is now a seminal, textbook standard result in quantum complexity theory.

Quantum information meets black holes

Can information be retrieved from a black hole? This question has been debated for decades, sparked in part by research from Stephen Hawking (Faculty at Cambridge University and a Distinguish Visiting Research Chair at Perimeter Institute). Hawking theorized that a black hole would slowly evaporate via a process known as Hawking radiation, causing information to be lost forever – a seeming violation of a core principle in physics: that information about the past should be retrievable from the present state.

More recent investigations into the paradox via string theory suggest that information may be preserved in Hawking radiation after all, and investigations into these processes have sparked productive new lines of research.

While sharing an office at Perimeter Institute in 2007 for a conference, Perimeter Affiliate Patrick Hayden and John Preskill (later a member of Perimeter’s Scientific Advisory Committee) developed a highly influential thought experiment known as the Hayden-Preskill protocol. In this experiment, they ask how long it would take to decode information rescued from a black hole via Hawking radiation. The answer: surprisingly quickly, implying that black holes act like ‘information mirrors’ that quickly reflect quantum information back out of them, taking only as long as the scrambling time plus the time it takes for the black hole to radiate enough qubits.

The protocol kickstarted a new way of studying quantum information and helped launch an influential global Simons Collaboration, It from Qubit, to explore it further. It also led to new interest in the information scrambling processes that occur inside black holes.

In 2017, Beni Yoshida (Perimeter Institute) and Alexei Kitaev (CalTech) produced an influential update to Hayden and Preskill’s work. While the original protocol demonstrated that reconstructing information from a black hole was possible, it didn’t explain precisely how to do so. Yoshida and Kitaev established a concrete – and rather simple – protocol for decoding the information retrieved from the black hole, one that could even be tested via experiment in real life (using thermalized systems in a lab in lieu of a black hole).

This ‘information-centric’ approach to studying black holes has proven extremely valuable, leading to new descriptions of how quantum information is spread through a system of qubits. Experiments at Berkeley, Harvard, and the University of Maryland are now testing this protocol in their quantum simulators.

By bringing quantum information theory in contact with black holes, the most extreme gravitational objects in the universe, this research program has spurred a flurry of new insights. Its influence has rippled across multiple fields of physics and into the design of quantum technologies, from quantum computing to next-generation quantum materials and many-body systems.