Quantum Networking

Rodney Van Meter

• Publisher: Wiley-ISTE
• Year: 2014
• ISBN:
  9781118648933
• Edition: 1
• Topic: Computer Science
• Subtopic: Optical Data Processing
• Index: Computer Science

Quantum networks build on entanglement and quantum measurement to achieve tasks that are beyond the reach of classical systems. Using quantum effects, we can detect the presence of eavesdroppers, raise the sensitivity of scientific instruments such as telescopes, or teleport quantum data from one location to another. Long-distance entanglement can be used to execute important tasks such as Byzantine agreement and leader election in fewer rounds of communication than classical systems, improving the efficiency of operations that are critical in distributed systems.

Chapter 1

Overview

“Teleportation” is a magic word, exotic and evocative, but it has been appearing in serious technical literature with increasing frequency. Both theoretically fascinating and experimentally demonstrated, teleportation is the key to quantum networks [GIS 07, KIM 08]. When used in discussions about quantum information, teleportation refers not to Captain Kirk stepping into a machine on the starship Enterprise, dissolving and reappearing on a planet’s surface, but to an operation in which a quantum variable dissolves here and reappears there, on a different physical device. Only the quantum state moves; the electron or other physical device remains where it was, and the receiver can in fact be a very different form of physical device than the sender. The quantum state is destroyed at the sender in the process.

Classical networks communicate by physically copying data and transmitting the copy, but the rules of quantum mechanics forbid the creation of independent copies of an unknown, arbitrary quantum state. Instead of risking the loss of valuable, fragile quantum data by directly transmitting our only copy, networks will prepare generic states that are used to teleport data or to perform teleportation-derived operations on the data.

Quantum networks bring new capabilities to communication systems. Quantum physical effects can be used to detect eavesdropping, to improve the shared sensitivity of separated astronomical instruments or to create distributed states that will enable numerical quantum computation over a distance using teleportation. Quantum communication is the exchange of quantum states over a distance, generally requiring the support of substantial classical communication.

The quantum states that are exchanged may be “standalone” states, an individual element of quantum data. They may also be part of a larger quantum state, spanning devices or even network nodes in a way no shared classical state can. These latter states we refer to as entangled states, which we will study extensively in this book.

Applications running on classical computers will use these quantum states to accomplish one of the above tasks. The classical computer is connected to a quantum device, which may do no more than measure the quantum states to find a classical value (such as a bit of a secret key), or may store them for use in more complex quantum computers. A classical computer will treat a quantum computer as a type of coprocessor; likewise, the classical computer will see the quantum network through the eyes of a separate device.

Because quantum data is fragile and some quantum operations are probabilistic, errors and distributed calculations must be managed aggressively and perhaps cooperatively among nodes. Solutions to these problems will have both similarities to and differences from purely classical networks. Architectures for large-scale quantum networking and internetworking are in development, paralleling theoretical and experimental work on physical layers and low-level error management and connection technologies. Unentangled quantum networks have already been deployed, starting in the early 2000s; as of early 2014, entangled networks are not yet deployed, but may appear within the next few years and will form a vibrant research topic in the coming decade.

1.1. Introduction

The motivations for building networks are the same for both quantum and classical networks: the desire to connect people, devices such as computers or sensors, or databases that are in separate locations, for technical, economic, political, logistical, or sometimes purely historical reasons. What differs is the type of data and operation involved. Quantum computers, and quantum networks, use quantum variables rather than classical ones; the analogue of the classical bit is the quantum bit, or qubit.

Proper use of quantum information opens up new possibilities, making feasible solutions to some problems that are computationally intractable for classical computers (most famously, factoring large numbers) [SHO 97, LAD 10, NIE 00, VAN 13a] and adding new physical capabilities (most famously, detection of eavesdropping, leading to new, secure, distributed cryptographic key generation mechanisms) [BEN 84]. Other applications for distributed quantum systems include long-baseline optical interferometry for telescopes [GOT 12], high-precision clock synchronization [JOZ 00, CHU 00] and quantum forms of distributed tasks such as leader election [TAN 12] Byzantine agreement [BEN 05a] and coin flipping. Quantum and classical networks and computing systems will hybridize, allowing applications to select the most efficient mechanism for accomplishing a particular function.

Modern work on quantum communications can be said to have begun with Stephen Wiesner’s quantum cryptography proposal, originating around 1970 [WIE 83], followed by Charlie Bennett and Giles Brassard’s 1984 proposal for quantum key distribution (QKD) [BEN 84, DOD 09], which utilizes the new low-level quantum capability of eavesdropping detection to build a specific system function, namely the creation of shared, secret random numbers for keying of classical cryptographic systems. However, QKD in its basic form is limited in distance to a few hundred kilometers in optical fiber or perhaps more through free space, and is a single-application system.

Bennett et al.’s 1993 proposal for quantum teleportation made it possible to move data and execute simple calculations remotely, extending the feasible distance for QKD and vastly expanding the range of conceivable distributed quantum applications [BEN 93]. Teleportation involves local quantum operations at each end and classical messages from the sender to the receiver. It consumes a quantum state known as a Bell pair (introduced below), shared between the two end points, so, a key function of quantum networks is to replenish the supply of distributed Bell pairs as necessary. As with any physical operation, teleportation operates imperfectly, requiring an extensive system that labors to suppress errors. More than a goal in itself, teleportation serves as a building block for distributed quantum applications.

The need to deal with imperfect quantum states and to span multiple hops spurred the development of the concept of quantum repeaters [DÜR 07, SAN 11], which are a vibrant area of research in both experiment and theory. Classical repeaters amplify a signal at the physical level, or receive a weak, distorted or noisy signal then regenerate a clean, strong signal. Quantum repeaters, however, are prevented by the laws of physics from performing such operations directly. Instead, they support high-fidelity, long-distance quantum communication using teleportation over shorter distances and forms of error correction ranging from a simple parity check on a Bell pair to extraordinarily complex, full error correction schemes based on the mathematics of topology. Some repeater architectures manage data movement using computations distributed across all of the nodes in a path between source and destination, while others are more akin to the hop-by-hop packet forwarding used in the Internet; the best approach for a given set of physical capabilities remains an important open question. The basics of teleportation and simple forms of error correction have been experimentally demonstrated, and the race is on to build more complete repeaters.

Although QKD networks using trusted relays and optical switches are in use in medium-scale testbeds, the key architectural issues in large-scale repeater networks are only beginning to be addressed. Protocols to actually implement the repeater functionality must be developed. Path selection and resource management, both at the node level, where memory resources are precious, and the network level, including choosing who gets access to the network, will play a role in determining whether the networks actually work.

Beyond single networks lies the issue of internetworking. An individual network will be built and managed by a single organization. Initially, it will be built using a single quantum networking technology. What happens when we want to bring in a second technology? What happens when we want to connect our network to another organization’s network? How do we get them to exchange quantum information? How do we manage the connection between the networks? Such a multi-network configuration is called an internetwork, or internet, for short. (Spelling it with an uppercase “I”, and sometimes attaching the article “the”, implies the primary, worldwide classical Internet we all use every day.)

Such an internet, of course, begins with the ability to recode quantum data from one form to another and physically connect heterogeneous technologies. Internetworking will require classical sharing of the correct abstraction for describing quantum states or computation requests and the ability to translate protocols for error management, as well as settling the issues of resource management and path selection.

Our goal, in this book, is to begin from scratch and build an understanding of quantum information, quantum repeaters and classical networking thorough enough to propose and evaluate a quantum internet architecture, including writing the classical software implementing the protocols.

1.2. Quantum information

To understand teleportation and distributed quantum information in principle, only a few concepts are required: superposition, measurement, interference, entanglement, no-signaling and no-cloning. To understand quantum networks in practice, it is equally imperative to study quantum systems in an imperfect world; all of the important behaviors of quantum networks arise from dealing with noise and loss using purification and quantum error correction. The primary mathematical tool for studying algorithms and basic concepts is the state vector, and for studying imperfect states, the primary tools are the density matrix and the fidelity, all of which we will see in the next chapter. Here, we restrict ourselves to a qualitative introduction to the key ideas.

1.2.1. Principles

Quantum computers have attracted interest because they are expected to asymptotically outperform classical computers on some important real-world problems [BAC 10, LAD 10, MOS 09, VAN 13a]. These gains in capability arise from the differences in storing and manipulating information using quantum states; here, we will restrict our discussion to qubits, though other forms of quantum information are possible. A qubit may be e.g. the direction of spin of a single electron, the direction of polarization of a single photon, or any of a large number of other proposed state variables. Like a classical bit, a qubit has two states, but unlike a classical bit, a qubit may be in a weighted superposition of the two states, allowing certain functions to be evaluated for both input values at the same time. A register of n qubits can, like a classical register, hold any of 2ⁿ possible values. The quantum register can in fact hold a superposition of all of these values and can, in principle, be used to compute on all 2ⁿ possible states at the same time.

The difficulty lies in extracting useful answers from a quantum computer. To read the results of a computation, dedicated hardware components measure the state of the system. The state of the quantum register collapses when the system is measured. It randomly picks one state out of the states that are part of the superposition, based on their relative weights. The other states go away, and it is as if they never existed.

A quantum algorithm manipulates the system to reduce the probability of undesirable states and increase the probability of desirable states, until the system has a high probability of measuring the quantum register and getting an answer to our problem, ideally in substantially fewer computational steps than a classical system would require. This is done by creating interference on the quantum states to reinforce good answers.

The concept of entanglement, in which the states of two or more quantum subsystems are correlated in a fashion that is not possible in classical systems, is the most difficult quantum concept to grasp. Two qubits can be entangled in a continuous spectrum of possible states; four types of entangled states known as Bell states or Bell pairs are commonly used. One such Bell state is a superposition of the state where both qubits are 0 and the state where both qubits are 1. In this state, when measured, each qubit has a 50% probability of being found in a 0 state and a 50% probability of being found in a 1 state. However, their probabilities are not independent; both values will be found to be the same.

Bell pairs form the basic communication and computation components for most distributed quantum computation, including teleportation, but are not the only form of entangled state. Bell states can be generalized into multi-party states called GHZ states or W states, and we also use entangled states known as graph states. Most distributed quantum computing algorithms will build around one or more of these key flavors of entangled state; so, the network must be able to create them efficiently. We will see Bell pairs in more mathematical detail in section 2.5, GHZ and W states in section 6.1.2 and graph states in section 6.1.3.

Basic teleportation is accomplished by first creating a Bell pair between the source and destination. The source entangles the qubit to be teleported with the source’s half of the Bell pair; then, both qubits are measured, destroying the entanglement of the Bell pair and any superposition state of the data qubit. The measurement results in two random classical bits, uncorrelated with the state of the data qubit, which must be transmitted to the destination. Local quantum operations at the destination determined by those classical bits then recreate the original data qubit’s state on the remaining Bell pair member. This sequence is illustrated in Figure 1.1. The latency of the classical information transmission prevents information from being transferred faster than the speed of light, and is known as the no-signaling constraint, and applies in many situations with quantum information.

Figure 1.1. Operations in teleporting a qubit from Alice to Bob

The final concept required to understand both quantum computation and communication is the no cloning theorem, as we will see in more mathematical detail in section 2.6. Perfect independent copies of an unknown quantum state cannot be made. “Copies” of some states remain entangled with the original state. This entanglement is actually useful in many quantum algorithms, but an unentangled copy would be wildly more useful, allowing faster-than-light communication. It would be and is too good to be true.

A major consequence of the no-cloning theorem is that the system cannot copy and send precious quantum data when there is a risk of losing the data; loss of the intransit copy would destroy even the copy kept due to the effects of entanglement and inadvertent measurement. This fact drives the common quantum networking approach of first building a high-quality, generic entangled state, then using that state to teleport or compute on our valuable data. We turn to handling these imperfections next.

1.2.2. Imperfect quantum systems

The central fact of all experimental quantum systems is this: the state of a quantum system is exceedingly fragile. Errors result in continuous degradation of our knowledge about the state of the quantum register. As the state drifts from its assigned value, the probabilities of the zero and one states change and the desired effects of interference may become muted or even incorrect. Beyond these errors that quickly accumulate, isolation of qubits from the environment is difficult, and qubits may be accidentally measured, destroying the valuable quantum state.

A measure known as the fidelity is one tool for tracking the quality of the state. Fidelity ranges from 0 to 1.0, with the latter being perfect. It is, essentially, the probability that our qubit or set of qubits is actually in the state we believe it ought to be in.

Various techniques for managing errors have been developed, some based on classical error correction and erasure correction techniques, others on uniquely quantum approaches [DEV 13, TER 13]. Purification, in which two or more multiqubit states are manipulated to form one higher-fidelity state, uses few quantum memory resources and simple quantum operations, but operates only on well-understood states such as Bell states rather than arbitrary application data. Purification is a type of error detection.

More complete protection of an arbitrary quantum state requires quantum error correction, in which we use a large number of physical qubits and add redundancy. It is possible to represent more than one qubit in an error correction block, as is done in classical error correction, but holding a single logical qubit is more common. The number of physical qubits can range from tens to possibly thousands, depending on the physical memory lifetime, quantum operation error rates and the performance required to successfully execute a given algorithm.

Besides errors involving the drift of the state, quantum communication systems are also subject to loss in the channel; for those systems expecting to use a single photon, this loss is fatal for that particular operation. Because losses in optical channels tend to be high, any communication system must be designed to manage this loss. Quantum optical states cannot be simply amplified without destroying the entanglement and superposition; so, other techniques must be used. Losses in the channel generally force a return message to be used acknowledging success or failure.

1.2.3. Quantum computers

Let us take a very short detour to look at quantum computers. After all, quantum networks will have some standalone applications, but a major goal is to use networks to connect computers!

The original concept goes back to the early 1980s, when Richard Feynman suggested that it was possible to simulate one quantum device using another, more efficiently than a classical computer could run such a simulation [FEY 02]. Paul Benioff suggested a quantum Turing machine [BEN 82]. David Deutsch explored some of the ideas behind such machines and proposed the first concrete quantum algorithm [DEU 85, DEU 92]. Seth Lloyd proposed the first plausible implementation of a real quantum computer in 1993 [LLO 93].

Theoretical approaches to organizing a computation using quantum effects include the gate model (similar to Boolean logic circuits), adiabatic quantum computation [AHA 04a, FAR 01], direct (analog) simulation, measurement-based quantum computation [RAU 03] and quantum random walks [AHA 93]. All have similar computational power, though the methods of creating algorithms for them are as different as classical digital and analog computers. To the extent that this difference affects quantum networks, in this book, we assume, and work with, the gate model. Measurement-based QC builds on top of a basic gate model and thus can benefit from the networks we describe here, but the adiabatic and direct models would need a very different form of network.

Peter Shor’s 1994 announcement of his algorithm for factoring large numbers on a quantum computer generated huge excitement and an increase in research budgets [SHO 94]. The algorithm can factor composite numbers or take discrete logarithms in time polynomial in the number of bits, whereas the best known classical algorithm is superpolynomial [LEN 03]. Realization of such a speedup would dramatically affect the security of encryption algorithms such as RSA and the Diffie-Hellman key exchange used on the Internet, in e-commerce websites and site-to-site network encryption.

Numerous other algorithms have been developed. Lov Grover showed how to get a polynomial speedup on any combinatori...