Quantum Computation and Quantum Information

Introduction

For decades computer hardware has grown in power approximately according to Moore’s law, which states that the computer power doubles for constant cost roughly once every two years. However, because of the fundamental difficulties of size in conventional computer technology, this dream run is ending. The conventional approaches to the fabrication of computer technology are to make electronic devices smaller and smaller in order to increase the computer power. As the sizes of the electronic devices get close to the atomic scale, quantum effects are starting to interfere in their functioning, and thus the conventional approaches run up against the size limit. One possible way to get around the difficulties is to move to a new computing paradigm provided by quantum information science. Quantum information science is based on the idea of using quantum devices to perform computation and manipulate and transmit information, instead of electronic devices following the laws of classical physics, see Deutsch (1985), DiVincenzo (1995), Feynman (1981/82). Quantum mechanics and information theory are two of the great scientific developments and technological revolutions in the 20th century, and quantum information science is to marry the two previously disparate fields and form a single unifying viewpoint. Quantum information science studies the preparation and control of the quantum states of physical systems for the purposes of information transmission and manipulation. It includes quantum computation, quantum communication and quantum cryptography. This revolutionary field will enable a range of exotic new devices to be possible. There is now a general agreement that quantum information science will likely lead to the creation of a quantum computer to solve problems that could not be efficiently solved on a classical computer. Already scientists have built rudimentary quantum computers in the research laboratory to run quantum algorithms and perform certain calculations. Intensive research efforts are under way around the world to investigate a number of technologies that could lead to more powerful and more prevalent quantum computers in the near future. It is believed that quantum information and quantum bits are to lead to a 21st century technological revolution much as classic information and classic bits did to the 20th century. Since the theory of quantum mechanics is fundamentally stochastic, randomness and uncertainty are deeply rooted in quantum computation and quantum information. As a result, quantum algorithms are of random nature in the sense that they yield correct solutions only with some probabilities, and Monte Carlo methods are widely employed in quantum simulation. Thus statistics has an important role to play in quantum computation, quantum simulation and quantum information. On the other hand, quantum computation and quantum simulation have tremendous potential to revolutionize computational statistics.

A quantum system is generally described by its state, and the state is mathematically defined to be a unit vector in some complex Hilbert space. The number of complex numbers required to characterize the quantum state usually grows exponentially with the size of the system, rather than linearly, as occurs in classical systems. As a consequence, it takes an exponential number of bits of memory on a classical computer to store the quantum state, which puts classical computers in a difficult position to simulate a quantum system. On the other hand, nature quantum systems are able to store and keep track of an exponential number of complex numbers and perform data manipulations and calculations as the systems evolve. Quantum information science is to grapple with understanding how to take advantage of the enormous information hidden in the quantum systems and to harness the immense potential computational power of atoms and molecules for the purpose of performing computation and processing information. Already it has been shown that quantum algorithms like Grover’s search algorithm and Shor’s factoring algorithm provide great advantage over known classical algorithms.

Contemporary scientific studies often rely on understanding complex quantum systems, such as those in biochemistry and nanotechnology for the design of biomolecules and nano-materials. Quantum simulation is to use computers to simulate a quantum system and its time evolution. Classical computers are being used for quantum simulation in designing novel molecules and creating innovative nano-products. Quantum computers built upon quantum systems may excel in simulating naturally occurring quantum systems, while large quantum systems may be impossible to simulate in an efficient manner by classical computers. A quantum system with $b$ distinct components may be described with $b$ quantum bits in a quantum computer, while a classical computer requires $2^{b}$ bits of memory to store its quantum state. This advantage allows quantum computers to efficiently simulate general quantum systems that are not efficiently simulatable on classical computers.

In this article we review the concepts of quantum computation and introduce quantum algorithms and quantum simulation. The quantum algorithms are known to be much faster than the available classical algorithms. Statistical analyses of quantum algorithms and quantum simulation are provided. We give a brief description on quantum information. The article sections start with presentations in broad brushstrokes, followed by specific discussions along with some mathematical derivations if necessary. The intention is to give each topic first an overview and then a general description and a precise characterization. It is recommended to focus on the qualitative discussions but skip the derivations for the readers who would like to get a quick picture of quantum computation and quantum simulation.

The rest of the paper proceeds as follows. Section 2 briefly introduces quantum mechanics, quantum probability and quantum statistics. Section 3 reviews basic concepts of quantum computation and entanglement. Section 4 illustrates some widely known quantum algorithms and provides a statistical framework for the study of quantum algorithms. Section 5 presents quantum simulation and discusses its statistical analysis. Section 6 gives a short description on quantum information theory. Section 7 features concluding remarks and lists some open research problems.

Brief Background Review on Quantum Theory

Quantum mechanics has been applied to everything under and inside the Sun, from chemical reaction and superconductor to the structure of DNA and nuclear fusion in stars. Although the significant difference between classical physics and quantum physics lies in the quantum prediction of physical entity when the scale of observations becomes comparable to the atomic or sub-atomic scale, many macroscopic properties of systems can only be fully explained and understood by quantum physics. The quantum world is extremely strange, and quantum theory is completely counterintuitive. Light waves behave like particles and particles behave like waves (wave particle duality); matter can go from one spot to another without moving through the intermediate space (quantum tunneling); information can be moved across a vast distance without transmitting it through the intervening space (quantum teleportation). Quantum theory provides a mathematical description of wave particle duality and interaction of matter and energy. It describes the time evolutions of physical systems via wave functions. The wave functions encapsulate the probabilities that particles are to be found in a given state at a given time. For example, the probability of finding a photon in some region is the square of the modulus of a wave function, and, since at some point the sum of two wave functions can be zero but neither wave function is zero, probabilities appear to cancel out each other in a way totally unexpected from classical probability. The intrinsic stochastic nature of quantum theory indicates a deep connection between quantum mechanics and probability. Since the main focus of this paper is on quantum computation and quantum information, we give a brief description of quantum theory in this section to provide some quantum background for the purpose of reviewing quantum computation and quantum simulation in subsequent sections. For further reading on the subjects we recommend textbooks by Sakurai and Napolitano (2010) at the graduate level and Griffiths (2004) at the undergraduate level for quantum mechanics, Holevo (1982), Parthasarathy (1992) and Wang (1994) for quantum probability and quantum stochastic processes, and Artiles, Gill and Guţă (2005) and Barndorff-Nielsen, Gill and Jupp (2003) for quantum statistics.

where $\langle u|=(u_{1},\ldots,u_{k})$ and $|v\rangle=(v_{1},\ldots,v_{k})^{\prime}$. An inner product induces a norm $\|u\|=\sqrt{\langle u|u\rangle},$ and a distance $\|u-v\|$ between $|u\rangle$ and $|v\rangle$. For the finite-dimensional case, a Hilbert space ${\cal H}$ is simply a vector space with an inner product.

2 Quantum System

Quantum mechanics depicts phenomena at microscopic level such as position and momentum of an individual particle like an atom or electron, spin of an electron, detection of light photons, and the emission and absorption of light by atoms. Unlike classical mechanics where physical entities like position and momentum can be measured precisely, the theory of quantum mechanics is intrinsically stochastic in a sense that we can only make probabilistic prediction about the results of the measurements performed.

Quantum mechanics is mathematically described by a Hilbert space $\cal H$ and self-adjoint operators on $\cal H$. A quantum system is completely characterized by its state and the time evolution of the state. A state is defined to be a unit vector in ${\cal H}$. Let $|\psi(t)\rangle$ be the state of the quantum system at time $t$, which is also referred to as a wave function. The states $|\psi(t_{1})\rangle$ and $|\psi(t_{2})\rangle$ at $t_{1}$ and $t_{2}$ are connected through $|\psi(t_{2})\rangle=\mathbf{U}(t_{1},t_{2})|\psi(t_{1})\rangle,$ where $\mathbf{U}(t_{1},t_{2})$ is a unitary operator depending only on time $t_{1}$ and $t_{2}$. In fact, there exists a self-adjoint operator $\mathbf{H}$, which is known as the Hamiltonian of the quantum system, such that $\mathbf{U}(t_{1},t_{2})=\exp[-i\mathbf{H}(t_{2}-t_{1})].$ With Hamiltonian $\mathbf{H}$, we may describe the continuous time evolution of $|\psi(t)\rangle$ by the Schrödinger equation

Alternatively a quantum system can be described by a density operator (or density matrix). A density operator $\bm{\rho}$ is an operator on ${\cal H}$ which (1) is self-adjoint; (2) is semi-positive definite; (3) has unit trace [i.e., $\operatorname{Tr}(\bm{\rho})=1$]. Following the convention in quantum information science, we reserve notation $\bm{\rho}$ for state, density operator or density matrix. A state is often classified as a pure state or an ensemble of pure states. A pure state is a unit vector $|\psi\rangle$ in $\cal H$, which corresponds to a density operator $\bm{\rho}=|\psi\rangle\langle\psi|$, and an ensemble of pure states corresponds to the case that the quantum system is in one of states $|\psi_{j}\rangle$, $j=1,\ldots,J$, with probability $p_{j}$ being in state $|\psi_{j}\rangle$, and the corresponding density operator

See Griffiths (2004), Sakurai and Napolitano (2010) and Shankar (1994).

3 Quantum Probability

We can test the theory of quantum mechanics by checking its predictions with experiments of performing measurements on quantum systems in the laboratory. The usual quantum measurements are on observables such as position, momentum, spin, and so on, where an observable $\mathbf{X}$ is defined as a self-adjoint operator on Hilbert space $\cal H$. The observable definition is motivated from the fact that the eigenvalues of self-adjoint operators are real. Assume that an observable $\mathbf{X}$ has a discrete spectrum with the following diagonal form

where $x_{a}$ are real eigenvalues of $\mathbf{X}$ and $\mathbf{Q}_{a}$ are the corresponding one-dimensional projections onto the orthogonal eigenvectors of $\mathbf{X}$. Consider such an observable in the quantum system prepared in state $\bm{\rho}$. Measure space $(\Omega,{\cal F})$ is used to describe possible measurement outcomes of the observable, and the result of the measurement is a random variable on $(\Omega,{\cal F})$ with probability distribution $P_{\bm{\rho}}$. We denote by $X$ the result of the measurement of observable $\mathbf{X}$ given by (3). Then $X$ is a random variable taking values in $\{x_{1},x_{2},\ldots,\}$, and under pure state $|\psi\rangle$, the probability that measurement outcome $x_{a}$ occurs is defined to be

With the probability we derive the expectation under pure state $|\psi\rangle$,

Note the difference between an observable $\mathbf{X}$ which is a Hermitian matrix and its measurement result $X$ which is a real-valued random variable.

Measuring observable $\mathbf{X}$ will alter the state of the quantum system (Kiefer (2004); von Neumann (1955)). If the quantum system is prepared with initial state $|\psi\rangle$, the state of the system after the measurement result $x_{a}$ is defined to be

For an ensemble state with density operator $\bm{\rho}$ given by (2), if the quantum state is $|\psi_{j}\rangle$, the probability that result $x_{a}$ occurs is

Applying the law of total probability, we obtain that under state $\bm{\rho}$, the probability that $x_{a}$ occurs is equal to

The expectation of $\mathbf{X}$ under state $\bm{\rho}$,

We may derive the density operator of the quantum system after obtaining the measurement result $x_{a}$ by conditional probability arguments as follows. If the quantum system is in pure state $|\psi_{j}\rangle$ before the measurement, the quantum state after measurement result $x_{a}$ has occurred is

If the quantum state is $\bm{\rho}$ before the measurement, after observing measurement outcome $x_{a}$ we have the following ensemble of states: the quantum system is in pure state $|\psi_{j}^{a}\rangle$ with probability $P(j|a)$, where Bayes’s theorem shows

Thus after measurement $x_{a}$ the density operator for the ensemble state is given by

See Holevo (1982), Parthasarathy (1992) and Sakurai and Napolitano (2010).

4 Quantum Statistics

For a given quantum system, it is very important but difficult to know its state. If we do not know in advance the state of the quantum system, we may infer the quantum state by the measurement results of some observables obtained from the quantum system and show that a certain state has been created. In statistical terminology, we want to estimate density matrix $\bm{\rho}$ based on measurements on an often large number of systems which are identically prepared in the state $\bm{\rho}$. That is, after measuring observables on some identical quantum systems, we can make statistical inference about probability distribution $P_{\bm{\rho}}$ of the measurements and thus indirectly about density matrix $\bm{\rho}$. In the literature of quantum physics, quantum tomography is referred to as the reconstruction of the underlying density matrix $\bm{\rho}$ by probing identically prepared quantum systems from some different angles. Specifically, suppose that we perform measurements of observables on identically prepared quantum systems in an unknown state $\bm{\rho}$ and obtain measurement results $X_{1},\ldots,X_{n}$. Assume that $\bm{\rho}$ is known up to some unknown parameter $\theta$; then $X_{1},\ldots,X_{n}$ are i.i.d. observations with distributions $P_{\bm{\rho}}$ which depend on $\theta$. This gives a quantum parametric statistical model. We may then define quantum likelihood and Fisher quantum information and establish quantum point estimation and quantum hypothesis testing theory. Alternatively we may model $\bm{\rho}$ nonparametrically by assuming that $\bm{\rho}$ is an infinite matrix and then use nonparametric methods to estimate the density matrix. For details see Artiles, Gill and Guţă (2005), Barndorff-Nielsen, Gill and Jupp (2003), Butucea, Guţă and Artiles (2007) and Nussbaum and Szkoła (2009).

Quantum Computing Concepts

Unlike classical computers using transistors tocrunch the ones and zeroes individually, quantum computers can handle both one and zero simultaneously via what are known as superposition quantum states. A superposition state is a state of matter which we may think of as both one and zero at the same time. Quantum computers use the strange superposition states and quantum entanglements to do the trick of performing simultaneous calculations and extracting the calculated results. The spooky phenomena of quantum entanglement and superposition are the key that enables quantum computers to be superfast and vastly outperform classical computers.

Analogous to the fundamental concept of bit in classical computation and classical information, we have its counterpart, quantum bit, in quantum computation and quantum information. Quantum bit is called qubit for short. Just like a classical bit with state either or $1$, a qubit has states $|0\rangle$ and $|1\rangle$. However, the real difference between a bit and a qubit is that besides states $|0\rangle$ and $|1\rangle$, a qubit may take the superposition states,

where $\alpha_{0}$ and $\alpha_{1}$ are complex numbers and called amplitudes satisfying $|\alpha_{0}|^{2}+|\alpha_{1}|^{2}=1$. That is, the states of a qubit are unit vectors in a two-dimensional complex vector space, and states $|0\rangle$ and $|1\rangle$ consist of an orthonormal basis for the space and are often referred to as computational basis states. For a classical bit we can examine it to determine whether it is in the state or $1$. However, for a qubit we cannot determine its state and find the values of $\alpha_{0}$ and $\alpha_{1}$ by examining it. The stochastic nature of quantum theory shows that we can measure a qubit and obtain either the result , with probability $|\alpha_{0}|^{2}$, or the result $1$, with probability $|\alpha_{1}|^{2}$. Physical experiments have realized qubits as physical objects in different physical systems, such as the two states of an electron orbiting a single atom, the two different polarizations of a photon, or the alignment of a nuclear spin in a uniform magnetic field. Consider the case of atom model by corresponding $|0\rangle$ and $|1\rangle$ with the so-called “ground” and “excited” states of the electron, respectively. As the atom is shined by light with suitable energy and for a proper amount of time, the electron can be moved from the $|0\rangle$ state to the $|1\rangle$ state and vice versa. Furthermore, by shortening the length of time shining the light on the atom, we may move the electron initially in the state $|0\rangle$ to “halfway” between $|0\rangle$ and $|1\rangle$, say, into a state $(|0\rangle+|1\rangle)/\sqrt{2}$.

Note that for qubit state $|\psi\rangle$ the only measurable quantities are the probabilities $|\alpha_{0}|^{2}$ and $|\alpha_{1}|^{2}$; since $|e^{i\theta}\alpha_{x}|^{2}=|\alpha_{x}|^{2}$, where $x=0,1$, $i=\sqrt{-1}$, and $\theta$ is a real number, from the viewpoint of the qubit measurements, states $e^{i\theta}|\psi\rangle$ and $|\psi\rangle$ are identical. That is, multiplying a qubit state by a global phase factor $e^{i\theta}$ bears no observational consequence.

Note the distinction between superposition states and probability mixtures (or ensemble of pure states defined in Section 2.1). Consider superposition $(|0\rangle+|1\rangle)/\sqrt{2}$ as a pure state. Its density matrix is given by

while the first term on the right-hand side of the above equation corresponds to the ensemble of pure states $|0\rangle$ and $|1\rangle$, that is, a probabilistic mixture of states $|0\rangle$ and $|1\rangle$ with equal probability.

Similar to classic bits, we can define multiple qubits. The states of $b$ qubits are unit vectors in a $2^{b}$-dimensional complex vector space with $2^{b}$ computational basis states of the form $|x_{1}x_{2}\cdots x_{b}\rangle$, $x_{j}=0$ or $1$, $j=1,\ldots,b$. For example, the states of two qubits are unit vectors in a four-dimensional complex vector space, with four computational basisstates labeled by $|00\rangle$, $|01\rangle$, $|10\rangle$ and $|11\rangle$. The computational basis states $|00\rangle$, $|01\rangle$, $|10\rangle$ and $|11\rangle$ generate the four-dimensional complex vector space, and the superposition states are all unit vector in the space with the forms

where amplitudes $\alpha_{x}$ are complex numbers satisfying $|\alpha_{00}|^{2}+|\alpha_{01}|^{2}+|\alpha_{10}|^{2}+|\alpha_{11}|^{2}=1$. As in the single qubit case, when two qubits are measured we get result $x$ being one of $00,01,10,11$, with probability $|\alpha_{x}|^{2}$. Moreover, we may measure just the first qubit of the two-qubit system and obtain either the result , with probability $|\alpha_{00}|^{2}+|\alpha_{01}|^{2}$, or the result $1$, with probability $|\alpha_{10}|^{2}+|\alpha_{11}|^{2}$. As quantum measuring changes the quantum state, if the measurement result on the first qubit is , after the measurement the qubits are in the state

A qubit is the simplest quantum system. The quantum system of $b$ qubits is described by a $2^{b}$-dimensional complex vector space with each superposition state specified by $2^{b}$ amplitudes. As $2^{b}$ increases exponentially in $b$, it is very easy for such a system to have an enormously big vector space. A quantum system with even a few dozens of “qubits” will strain the resources of even the largest supercomputers. Consider a quantum system of $50$ qubits. $2^{50}\approx 10^{15}$ complex amplitudes are needed to specify its quantum states. With $128$ bits of precision, it requires approximately $32$ thousand terabytes of information to store all $10^{15}$ complex amplitudes. Such storage capacity may be available in future supercomputers. For a quantum system with $b=500$ qubits we need to specify $2^{500}$ complex amplitudes for its states. It is unimaginable to store all $2^{500}$ complex numbers in any classical computers. In principle, a quantum system with only a few hundred atoms can manage such an enormous amount of data and execute calculations as the system evolves. Quantum computation and quantum information are to find ways to utilize the immense potential computational power in quantum systems.

2 Quantum Circuit Model

As a classical computer is built from an electrical circuit consisting of wires for carrying information around the circuit and logic gates for performing simple computational tasks, a quantum computer can be created from a quantum circuit with quantum gates to perform quantum computation and manipulate quantum information. A number of physical systems are being investigated for building quantum computers. These include optical photon, optical cavity quantum electrodynamics, ion traps, nuclear magnetic resonance with molecules, quantum dots, and superconductors (Nielsen and Chuang (2000)). In fact, primitive solid-state quantum processors have been created in research laboratories to run quantum algorithms (DiCarlo et al. (2009); Johnson et al. (2011); Mariantoni et al. (2011); Sayrin et al. (2011)). The circuit model is particularly important in quantum computation and quantum information, and a quantum computer is often synonymous with the quantum circuit model. A quantum circuit operates on $b$ qubits for some integer $b$. The state takes a form of $|x_{1}\cdots x_{b}\rangle$, with state space being a $2^{b}$-dimensional complex Hilbert space. When $x_{i}=0$ or $1$, states $|x_{1}\cdots x_{b}\rangle$ are the computational basis states of the quantum computer and often written as $|x\rangle$, where $x$ is the integer with binary representation $x_{1}\cdots x_{b}$.

As a classical logic gate converts classical bits from one form to another such as $0\rightarrow 1$ and $1\rightarrow 0$, a quantum gate operates on qubits. Quantum mechanics dictates that quantum gates operating on $b$ qubits are $2^{b}$ by $2^{b}$ unitary matrices on the $2^{b}$-dimensional Hilbert space. For example, a Hadamard gate on one qubit is the $2\times 2$ unitary matrix that realizes the following transformation:

Consider another important gate on two qubits which is called control-NOT gate. It takes the two input qubits as control qubit and target qubit, respectively, and the output target qubit of the gate retains the input target qubit if the control qubit is $|0\rangle$ and is flipped if the control qubit is $|1\rangle$, that is,

Generally for any single qubit unitary operation $\mathbf{U}$, a control-$\mathbf{U}$ gate is a two-qubit gate, with one control qubit and one target qubit. If the control qubit is $|1\rangle$, $\mathbf{U}$ is applied to the target qubit; if the control qubit is $|0\rangle$, the target qubit is left alone, that is,

If $f(x)$ maps $\{0,1\}^{b}$ onto $\{0,1\}$, we define a unitary transformation $\mathbf{U}_{f}$ that operates on $b+1$ qubit state

where $x=x_{1}\cdots x_{b}$ with $x_{j}=0$ or $1$ is the data register, $y=0$ or $1$ is the target register, $\oplus$ denotes additional modulo $2$. If $y=0$, after the transformation $\mathbf{U}_{f}$, the state of the last qubit is the value of $f(x)$.

3 Entanglement

Quantum entanglement is one of the most mind-bending creatures known to science. It is referred to as the phenomenon that two qubits behave like twins that are connected by an invisible wave to share each other’s properties.

Consider a quantum gate on two-qubit basis states $|00\rangle$, $|01\rangle$, $|10\rangle$ and $|11\rangle$ that is composed of a Hadamard gate on the first qubit and then is followed by a control-NOT gate. The output states of the gate are as follows:

Physicists Bell, Einstein, Podolsky and Rosen discovered the amazing properties of these four states, which are often referred to as the Bell states, EPR states or EPR pairs (Bell (1964); Einstein, Podolsky and Rosen (1935)). In general states such as these four states that cannot be expressed as products of some single qubits are called entangled states. Entangled states, which are not fully understood in quantum physics, have remarkable properties.

For the two-qubit system consider a Bell state

where $(a_{x},a_{y},a_{z})$ is a real unit vector (i.e., $a_{z}^{2}+a_{y}^{2}+a_{z}^{2}=1$), and $\bm{\sigma}_{x}$, $\bm{\sigma}_{y}$ and $\bm{\sigma}_{z}$ are Pauli matrices given by

It is easy to show that $\mathbf{M}$ has eigenvalues $\pm 1$ for any real unit vector $(a_{x},a_{y},a_{z})$. If measuring observable $\mathbf{M}$ on each qubit of $|\psi\rangle$, we will obtain a measurement result of $+1$ or $-1$. Surprisingly, no matter what choice of $(a_{x},a_{y},a_{z})$, the measurement results on the two qubits are always opposite of each other, that is, when the first qubit measurement is $-1$, then the second qubit measurement will be $+1$, and vice versa.

The two-qubit system can be realized by the spins of two particles, and the measurement of $\mathbf{M}$ is referred to as a measurement of spin along the $(a_{x},a_{y},\break a_{z})$ axis. After the two-particle system is prepared in the Bell state $|\psi\rangle$, the two particles drift far apart. Alice measures the spin of the first particle and Bob measures the spin of the second particle. The above opposite measurement phenomenon corresponds to that due to the entangled state $|\psi\rangle$, if Alice gets a result $+1$ from her spin measurement on the first particle, then the state of the system immediately jumps to the untangled state so that the second particle now has definite spin state and Bob’s spin measurement on the second particle gives definite result $-1$. This phenomenon is often referred to as anti-correlation in entanglement experiments (Neumann et al. (2008); Sakurai and Napolitano (2010)).

Denote by $|\varphi_{\pm}\rangle$ the two orthonormal eigenvectors of $\mathbf{M}$ corresponding to eigenvalues $\pm 1$, respectively, and let $\mathbf{Q}_{\pm}$ be the respective projections onto the eigenvectors $|\varphi_{\pm}\rangle$. Following (3)–(5) we have a diagonal representation $\mathbf{M}=\mathbf{Q}_{+}-\mathbf{Q}_{-}$; when we measure observable $\mathbf{M}$ on each qubit, the possible measurement results are $\pm 1$; measuring $\mathbf{M}$ on the first qubit changes the state of the two-qubit system, and after the measurement result $\pm 1$ on the first qubit, the post-measurement state of the two-qubit system is $\mathbf{Q}_{\pm}\otimes\mathbf{I}|\psi\rangle/\|\mathbf{Q}_{\pm}\otimes\mathbf{I}|\psi\rangle\|$. Below we will evaluate the post-measurement state and show that measuring $\mathbf{I}\otimes\mathbf{M}$ in the post-measurement state always yields measurement results opposite to the measurement results on the first qubit.

From the definitions of $|\varphi_{\pm}\rangle$ and $\mathbf{Q}_{\pm}$, $\mathbf{Q}_{+}\otimes\mathbf{I}|\varphi_{+}\varphi_{-}\rangle=|\varphi_{+}\varphi_{-}\rangle$, $\mathbf{Q}_{-}\otimes\mathbf{I}|\varphi_{-}\varphi_{+}\rangle=-|\varphi_{-}\varphi_{+}\rangle$, $\mathbf{Q}_{+}\otimes\mathbf{I}|\varphi_{-}\varphi_{+}\rangle=0$, and $\mathbf{Q}_{-}\otimes\mathbf{I}|\varphi_{+}\varphi_{-}\rangle=0$. If the measurement result of $\mathbf{M}$ on the first qubit is $+1$ (or $-1$), from (3.3.1) we obtain the post-measurement state of the two-qubit system as follows:

(or $\mathbf{Q}_{-}\otimes\mathbf{I}|\psi\rangle/\|\mathbf{Q}_{-}\otimes\mathbf{I}|\psi\rangle\|=e^{i\theta}|\varphi_{-}\varphi_{+}\rangle\sim|\varphi_{-}\varphi_{+}\rangle$). Since

that is, the post-measurement state $|\varphi_{+}\varphi_{-}\rangle$ (or$|\varphi_{-}\varphi_{+}\rangle$) is the eigenvector of $\mathbf{I}\otimes\mathbf{M}$ corresponding to eigenvalue $-1$ (or $+1$), performing measurement on $\mathbf{I}\otimes\mathbf{M}$ in the post-measurement state must always yield measurement result $-1$ (or $+1$). Thus, the measurement results of $\mathbf{M}$ on the two qubits of $|\psi\rangle$ are always opposite to each other.

3.2 Quantum teleportation

Quantum teleportation is a process by which we can transfer the state of a qubit from one location to another, without transmitting it through the intervening space. We illustrate the phenomenon as follows. Alice and Bob together generated a Bell state long ago. Each took one qubit of the Bell state when they split. Now they are far away from each other. The mission for Alice is to deliver a qubit $|\psi\rangle$ to Bob, while he is hiding, and she can only send classical information to Bob but does not know the state of the qubit $|\psi\rangle$. Quantum teleportation is a way that Alice utilizes the entangled Bell state to send a qubit of unknown state to Bob, with only a small overhead of classical communication. Recently a breakthrough in quantum teleportation has been made by successfully transferring complex quantum data instantaneously from one place to another, paving the way for real-world applications of quantum communications (Lee et al. (2011)).

Here is how it works. Alice interacts the qubit $|\psi\rangle$ to be teleported with her half of the Bell state, and then performs a measurement on the two interacted qubits to obtain one of four possible two-classical-bit results: $00,01,10$ and $11$. She sends the two-bit information via classical communication to Bob. Depending on Alice’s classical message, Bob performs one of four operations on his half of the Bell state. Surprisingly, the described procedure allows Bob to recover the original state $|\psi\rangle$.

Specifically assume that the state to be teleported is $|\psi\rangle=\alpha_{0}|0\rangle+\alpha_{1}|1\rangle$, where $\alpha_{0}$ and $\alpha_{1}$ are unknown amplitudes. First, consider a three-qubit state

where the first two qubits (on the left) belong to Alice, and the third qubit to Bob. Note that Alice’s second qubit and Bob’s third qubit are from the entangled Bell state. Second, Alice applies a control-NOT gate to her qubits in $|\varphi_{0}\rangle$ and obtains

Third, she applies a Hadamard gate to the first qubit in $|\varphi_{1}\rangle$ and gets

We regroup the terms of $|\varphi_{2}\rangle$ and rewrite it as follows:

The new expression has four terms, and each term has Alice’s qubits in one of four possible states $|00\rangle,\break|01\rangle,|10\rangle$ and $|11\rangle$, and Bob’s qubit is in the state related to the original state $|\psi\rangle$. If Alice performs a measurement on her qubits and informs Bob of the measurement result, then his post-measurement state is completely determined. For example, the first term has Alice’s qubits in the state $|00\rangle$ and Bob’s qubit in state $|\psi\rangle$. Therefore, if Alice’s measurement result on her qubits is $00$, then Bob’s qubit will be in state $|\psi\rangle$. Below is a list of Bob’s four post-measurement states corresponding to the results of Alice’s measurements:

As Alice’s measurement outcome on her qubits is one of $00,01,10$ and $11$, depending on her measurement outcome Bob’s qubit will be one of the above four possible states. Once Alice sends to Bob her two-classical-bit measurement outcome througha classical channel, he applies appropriate quantum gates to his state and recovers $|\psi\rangle$. For example, if her measurement is $00$, Bob’s state is $|\psi\rangle$, and he does not need to apply any quantum gate. If her measurement is $01$, then Bob needs to apply a $\bm{\sigma}_{x}$ gate to his state $\alpha_{0}|1\rangle+\alpha_{1}|0\rangle$ and yields $|\psi\rangle$. If her measurement is $10$, then applying a $\bm{\sigma}_{z}$ gate to his state $\alpha_{0}|0\rangle-\alpha_{1}|1\rangle$ Bob recovers $|\psi\rangle$. If her measurement is $11$, then Bob can fix up his state $\alpha_{0}|1\rangle-\alpha_{1}|0\rangle$ to recover $|\psi\rangle$ by applying first a $\bm{\sigma}_{x}$ gate and then a $\bm{\sigma}_{z}$ gate. Here the $\bm{\sigma}_{x}$ and $\bm{\sigma}_{z}$ gates are defined by Pauli matrices $\bm{\sigma}_{x}$ and $\bm{\sigma}_{z}$ given by (3.3.1). In summary, according to Alice’s measurement outcome, applying some appropriate quantum gates to his qubit Bob will recover the state $|\psi\rangle$.

A few important remarks about quantum teleportation are in the line. First, quantum teleportation does not involve any transfer of matter or energy. Alice’s particle has not been physically moved to Bob; only its state has been transferred. Second, after the teleportation Bob’s qubit will be on the teleported state, while Alice’s qubit will become some undefined part of an entangled state. In other words, what the teleportation does is that a qubit was destroyed in one place but instantaneously resurrected in another. Teleportation does not copy any qubits, and hence is consistent with the no-cloning theorem (which forbids the creation of identical copies of an arbitrary unknown quantum state; see Wootters and Zurek (1982)). Third, in order to teleportate a qubit, Alice has to inform Bob of her measurement by sending him two classical bits of information. These two classical bits do not carry complete information about the qubit being teleported. If the two bits are intercepted by an eavesdropper, he or she may know exactly what Bob needs to do in order to recover the desired state. However, this information is useless if the eavesdropper cannot interact with the entangled particle in Bob’s possession. Also the requirement of sending two bits of information via classical channel prevents quantum teleportation from transmitting information faster than the speed of light.

3.3 Bell’s inequality

The Bell test experiments are designed to investigate the validity of the entanglement effect in quantum mechanics through Bell’s inequality. Over the past four decades many physical experiments on quantum systems were conducted to check the validity of Bell’s inequality and resulted in some violation of the inequality. For example, Aspect, Grangier and Roger (1981, 1982a, 1982b) provided overwhelming support to the violation of Bell’s inequality. The experimental results are often invoked as the proof of quantum non-locality and lack of realism that no particle has definite form until it is measured and measuring a quantum entity can instantaneously influence another far away. See Aspect, Grangier and Roger (1981, 1982a, 1982b), Bohm (1951), Bell (1964), Clauser et al. (1969) and Einstein, Podolsky and Rosen (1935). Below we describe the CHSH version of the Bell’s inequality (Clauser et al. (1969)).

Suppose $X_{i}$, $i=1,2,3,4$, are four random variables taking values $\pm 1$. Consider an ordinary experiment with two people, Alice and Bob. In the experiment Alice observes $X_{1}$ or $X_{2}$ while Bob measures $X_{3}$ or $X_{4}$. Consider the quantity $X_{1}X_{3}+X_{2}X_{3}+X_{2}X_{4}-X_{1}X_{4}$. It is equal to

Regardless of the distributions of $X_{i}$, taking expectation on both sides of the above inequality we arrive at the famous Bell inequality,

The violation of Bell’s inequality demonstrates entanglement effect in quantum mechanics. In fact, quantum experiments yield a quantum version of the inequality. Consider that a quantum system of two qubits is prepared in a Bell state

Alice takes the first qubit of $|\psi\rangle$ while Bob gets its second qubit. Define four observables with eigenvalues $\pm 1$,

on the second qubit, where $\bm{\sigma}_{x}$ and $\bm{\sigma}_{z}$ are Pauli matrices given by (3.3.1). Again Alice performs measurements on $\mathbf{X}_{1}$ or $\mathbf{X}_{2}$ while Bob measures $\mathbf{X}_{3}$ or $\mathbf{X}_{4}$. The quantum expectations of $\mathbf{X}_{1}\mathbf{X}_{3}$, $\mathbf{X}_{2}\mathbf{X}_{3}$, $\mathbf{X}_{2}\mathbf{X}_{4}$, $\mathbf{X}_{1}\mathbf{X}_{4}$ in the state $|\psi\rangle$ are calculated below:

Here the observable product is in the sense of tensor product. Thus we obtain a value in the quantum framework for the analog quantity on the left-hand side of the Bell’s inequality (3.3.3)

which exceeds $2$ and hence violates the Bell’s inequality. In fact, the quantum version of the Bell’s inequality is the Tsirelson’s inequality (Tsirelson, 1980) which shows that in any quantum state $\bm{\rho}$,

4 Quantum Parallelism

Quantum computation has an amazing feature termed as quantum parallelism, which may be heuristically explained by the following oversimplifying description: a quantum computer can simultaneously evaluate the whole range of a function $f(x)$ at many different values of $x$.

For function $f(x)$ with $b$ bit input $x=x_{1}\cdots x_{b}$ and $1$ bit output $f(x)$, we illustrate quantum parallel evaluation of its values at many different $x$ simultaneously as follows. First we apply $b$ Hadamard gates to the first $b$ qubits of $|0\cdots 0\rangle|0\rangle$ to obtain

where the sum is over all possible $2^{b}$ values of $x$. Second, apply quantum circuit $\mathbf{U}_{f}$ defined in (6) to the obtained $b+1$ qubit state to yield

The quantum circuit with $b$ Hadamard gates is extremely efficient in producing an equal superposition of all $2^{b}$ computational basis states with only $b$ gates; and quantum parallelism enables simultaneous evaluation of the whole range of the function $f$, although we evidently evaluate $f$ just once with single quantum circuit $\mathbf{U}_{f}$ applied to the superposition state. To make it more clear we consider the case of $b=1$. Apply circuit $\mathbf{U}_{f}$ to a superposition state as follows:

One application of a single circuit $\mathbf{U}_{f}$ results in a superposition state whose two components contain information about both $f(0)$ and $f(1)$, as if we have evaluated $f(x)$ at values and $1$ simultaneously. The quantum parallelism is in contrast with classical parallelism, where multiple circuits each built to compute one value of $f(x)$ are executed simultaneously. Quantum parallelism arises from superposition states. A superposition state has many components, each of which may be thought of as a single argument to function $f(x)$. Because of quantum nature, a single circuit $\mathbf{U}_{f}$ applied once to the superposition state is actually performed on each of the components of the superposition, and the whole range of the values of function $f(x)$ is stored in the resulted outcome superposition state.

The quantum parallelism can be a potentially powerful tool for computational statistics. For example, Bayesian analysis often encounters the problems of evaluating sums over $2^{b}$ quantities, with $b$ proportional to sample size or the number of variables. For moderate to large $b$, the evaluation of such sums is computationally prohibitive by classical computers (Vidakovic (1999)). Because of the quantum parallelism, it is possible for quantum computers to perform such computing tasks.

Quantum Algorithms

Quantum algorithms are described by quantum circuits that take input qubits and yield output measurements for the solutions of the given problems. As a classical algorithm is a step-by-step problem-solving procedure, with each step performed on a classical computer, a quantum algorithm is a step-by-step procedure to solve a problem, with each step executed by a quantum computer. Although all classical algorithms can also be carried out on a quantum computer, we refer to quantum algorithms as the algorithms that utilize essential quantum features such as quantum superposition and quantum entanglement. While it is true that all problems solvable on a quantum computer are solvable on a classical computer, and problems undecidable by classical computers remain undecidable on quantum computers, what makes quantum algorithms exciting is the faster speed that quantum algorithms might be able to achieve, compared to classical algorithms, for solving some tough problems. The well-known quantum algorithms are Shor’s factoring algorithm and Grover’s search algorithm. Shor’s algorithm and Grover’s algorithm run, respectively, exponentially faster and quadratically faster than the best known classical algorithms for the same tasks. Common techniques used in quantum algorithms include quantum Fourier transform, phase estimation and quantum walk.

The quantum Fourier transform is defined to be a linear transformation on $n$ qubits that maps the computational basis states $|j\rangle$, $j=0,1,\ldots,2^{n}-1$, to superposition states as follows:

The inverse of quantum Fourier transform is given by

It can be easily checked from the product representation that with quantum parallelism the quantum Fourier transform can be realized as a quantum circuit with only $O(n^{2})$ operations, while classically the fast Fourier transform requires $O(n2^{n})$ operations for processing $2^{n}$ data, which indicates an exponential speed-up (Nielsen and Chuang (2000)). Realizing such an exponential saving accommodated by quantum parallelism requires clever measurement schemes. Successful examples include quantum phase estimation and Shor’s algorithms for factoring and discrete logarithm.

2 Phase Estimation

Quantum algorithms are of random nature in the sense that they are able to produce correct answers only with some probabilities. Consider quantumphase estimation which provides the key to many quantum algorithms. Assume that a unitary operator $\mathbf{U}$ has an eigenvector $|x\rangle$ with eigenvalue $e^{2\pi i\varphi}$. The phase $\varphi$ of the eigenvalue is unknown and the goal of the phase estimation algorithm is to estimate $\varphi$ based on the assumption that the state $|x\rangle$ can be prepared and the controlled-$\mathbf{U}^{2^{j}}$ operations [see Section 3.2 for control gate] can be performed for suitable nonnegative integers $j$.

The registers are used in phase estimation. The first register consists of $b$ qubits initially in the state $|0\rangle$. The second register starts in the state $|x\rangle$ and involves enough qubits to store $|x\rangle$. The phase estimation procedure is performed in two stages.

First, we apply Hadamard transform to the first register and then controlled-$\mathbf{U}$ operations on the second register, with $\mathbf{U}$ raised to successive powers of 2, to obtain the final state with the second register unchanged and the first register given by

If $\varphi$ is expressed exactly in $b$ bits as $\varphi=0.\varphi_{1}\cdots\varphi_{b}$, (4.2) becomes

which is the quantum Fourier transform of the product state $|\varphi_{1}\varphi_{2}\cdots\varphi_{b}\rangle$.

The second stage of phase estimation is to take the inverse quantum Fourier transform on the first register. For $\varphi=0.\varphi_{1}\cdots\varphi_{b}$, the output state from the second stage is $|\varphi_{1}\varphi_{2}\cdots\varphi_{b}\rangle$, and a measurement in the computational basis yields $\varphi_{1}\cdots\varphi_{b}$ and dividing the measurement by $2^{b}$ gives $\varphi_{1}\cdots\varphi_{b}/2^{b}=0.\varphi_{1}\cdots\varphi_{b}=\varphi$. We obtain a perfect estimate of $\varphi$.

Now we consider the case that $\varphi$ cannot be expressed exactly with a $b$ bit binary expansion. Take $0\leq\eta<2^{b}$ to be the integer that its binary fraction $\eta/2^{b}=0.\eta_{1}\eta_{2}\cdots\eta_{b}$ is the first $b$ bit representation in the binary expansion of $\varphi$, which satisfies $0\leq\varphi-\eta/2^{b}\leq 2^{-b}$.

Perform the inverse quantum Fourier transform on the first register given by (4.2), which is obtained in the first stage results, and get

3 Statistical Analysis

The phase estimation algorithm requires $b$ qubits for the first register to achieve $[-\log_{2}\zeta]$ bit accuracy and success probability $1-\epsilon$. With accuracy fixed, to increase the success probability the required qubits

which grows at a very fast rate. For example, an increase in success probability from $90\%$ to $99\%$ requires eighteen times of qubit increase compared to the change from $80\%$ to $90\%$.

If the outcome result of the algorithm is verifiable to be a correct answer or not [as in the case of Shor’s algorithms for factoring and order-finding in Section 4.4 below], the obtained result from each run is checked to be a correct answer or not. Then the number of times required to run the algorithm for obtaining a correct answer follows a geometric distribution. Thus the probability that we obtain a correct answer in $n$ repetitions is equal to

Since $\epsilon^{n}$ goes to zero geometrically fast, we may choose a moderate $\epsilon$ with fewer qubits to achieve very high probability of successfully obtaining a correct answer by repeatedly running the algorithm enough times.

As $n\rightarrow\infty$, $n\epsilon$ approaches to infinity. The binomial probability can be approximated by resorting to a normal approximation, yielding

where $\Phi(\cdot)$ is the standard normal distribution function. Since $2\alpha-\epsilon>0$, as $n$ increases, $P(|\bar{\varphi}-\varphi|\leq\zeta)$ approaches to $1$ exponentially fast. Combining the two cases together, we arrive at the following theorem.

For a quantum algorithm that produces a correct answer with probability $70\%$ and $\alpha=0.2$, in order to obtain a correct answer with $0.999$ probability we need to run the algorithm five times and 20 times, respectively, for the cases that the outcome results are verifiable and not verifiable.

4 Factoring and Order-Finding Algorithms

The factoring problem is to find all prime factors of a given positive composite number such that the product of these prime numbers is equal to the composite number. Factoring is known to be a very hard problem for classical computers. Shor (1994, 1997) developed a quantum algorithm for the factoring problem that is exponentially faster than the most efficient known classical factoring algorithm.

Shor’s quantum algorithms work as follows. Mathematically the factoring problem is equivalent to the order-finding problem that for two positive integers $x$ and $N$, $x<N$, with no common factors, find the smallest integer $r$ such that dividing $x^{r}$ by $N$ we obtain a reminder $1$ (Shor (1997); Nielsen and Chuang (2000)). The quantum algorithm for factoring is reduced to a quantum algorithm for order-finding. The quantum algorithm for order-finding is to apply the phase estimation algorithm to the unitary operator

with corresponding eigenvalues $\exp(2\pi is/r)$. Using the phase estimation algorithm we can obtain the eigenvalues $\exp(2\pi is/r)$ with high accuracy and thus find the order $r$ with certain probability.

While the quantum factoring algorithm can accomplish the task of factoring an $n$-bit integer with operations of order $n^{2}\log n\log\log n$, the current best known classical algorithm requires operations of order $\exp(n^{1/3}\log^{2/3}n)$ to factor an $n$-bit composite number (Crandall and Pomerance (2001)). Note that the number of operations required in the best classical algorithm grows exponentially in the size of the number being factored. Because of the exponential complexity, the factoring problem is generally regarded as an intractable problem on classical computers.

The factoring problem plays an important role in cryptography. Cryptography is to enable two parties, Alice and Bob, to communicate privately, while it is very difficult for the third parties to “eavesdrop” on the contents of the communications. Examples include ATM cards, computer passwords, internet commences, clandestine meetings and military communications. Two cryptographic protocols used in the communications are private key cryptosystem and public key cryptosystem. A private key cryptosystem requires the two communicating parties to share a private key. Alice uses the key to encrypt the information, sends the encrypted information to Bob who uses the key to decrypt the received information. The severe drawback of the private key cryptosystem is that the parties have to safeguard the key transmission from being eavesdropped. A public key cryptosystem invented in the 1970s requires no sharing secret key in advance. Bob publishes a “public key” available to the general public, and Alice uses the public key to encrypt information and sends the encrypted information to Bob. The encryption transformation is specially created such that with only the public key, it is extremely difficult, though not impossible, to invert the encryption transformation. When publishing the public key Bob keeps a matched secret key for easy inversion of the encryption transformation and decryption of the received information. One of the most widely used public key cryptosystems is the RSA cryptosystem, which is named after its creator Rivest, Shamir and Adleman (Menezes, van Oorschot and Vanstone (1996); Rivest, Shamir and Adleman (1978)). RSA is built on the mathematical asymmetry of factoring: it is easy to multiply large prime numbers and obtain their product as a composite number but hard to find the prime factors of a given large composite number. RSA encryption keeps the large primes as a secret key and uses their product to make a “public key.” Because of its exponential complexity, tremendous efforts tried to break the RSA system so far have resulted in vain, and there is a widespread belief that the RSA system is secure against any classical computer based attacks. As the factoring problem can be efficiently solved by Shor’s quantum factoring algorithm, a quantum computer can break the RSA system easily. Fortunately, while quantum mechanics takes away with one hand, it gives back with the other. A quantum procedure known as quantum cryptography or quantum key distribution can do key distribution so that the communication security cannot be compromised. The idea is based on the quantum principle that observing a quantum system will disturb the system being observed. If there is an eavesdropper during the transmission of the quantum key between Alice and Bob, eavesdropping will disturb the quantum communication channel that is used to establish the key, and the disturbance will make eavesdropping visible. Alice and Bob will throw away the compromised key and keep only the secured key for their communication.

5 Quantum Search Algorithm

Suppose that you would like to find the name corresponding to a given phone number in a telephone directory; or suppose that there are some locations in a given city you would like to visit and wish to find the shortest route passing through all the locations. If there are $N$ names in the telephone directory or $N$ possible routes to pass through all the locations, search algorithms by classical computers usually require operations of order $N$. One such simple classical algorithm is to check exhaustively all names to find a name matching with the given phone number or to search all possible routes and then find the shortest route among all routes. However, Grover (1996, 1997) developed a quantum search algorithm that needs only operations of order $\sqrt{N}$ to find a solution to the search problem.

The quantum search algorithm works as follows. Suppose that the search space has $N$ elements and the search problem has exactly $M$ solutions. Assume $M\leq N/2$. (For the silly case of $M>N/2$, we either search for the solution by doing random selection from the search space or double the number of the elements in the search space by adding $N$ extra non-solution elements to the search space.) The algorithm works by creating superposition state with Hadamard gate,

and then applying a so-called Grover iteration (or operator) repeatedly. Set

where the summations over $x^{\prime}$ and $x^{\prime\prime}$ denote sums over all non-solutions and solutions, respectively.Then we can express $|\psi\rangle$ as follows:

The Grover operator is to perform two reflections, one about the vector $|\phi\rangle$ and another about the vector $|\psi\rangle$. The two reflections together are a rotation with angle $\theta$ in the two-dimensional space spanned by $|\phi\rangle$ and $|\varphi\rangle$, where

After the rotation, the initial state $|\psi\rangle=\cos(\theta/2)|\phi\rangle+\sin(\theta/2)|\varphi\rangle$ becomes state

Thus each application of the Grover operator is a rotation with angle $\theta$. The initial state $|\psi\rangle$ has angle $\pi/2-\theta/2$ with $|\varphi\rangle$; after the first rotation, the resulted state has angle $\pi/2-3\theta/2$ with $|\varphi\rangle$; and in general after the $r$th rotation, the resulted state has angle $\pi/2-(2r+1)\theta/2$ with $|\varphi\rangle$. Repeatedly applying the Grover operator, we rotate the state vector near $|\varphi\rangle$. With the initial state $|\psi\rangle=\cos(\theta/2)|\phi\rangle+\sin(\theta/2)|\varphi\rangle$, we need to rotate through $\arccos\sqrt{M/N}$ radians to transform the state vector to $|\varphi\rangle$. After $R=\arccos(\sqrt{M/N})/\theta=O(\sqrt{N/M})$ times of applications of the Grover operator, we rotate the state vector $|\psi\rangle$ to within an angle $\theta/2$ of $|\varphi\rangle$. Performing measurements of the state yields a solution to the search problem with probability at least $\cos^{2}(\theta/2)\geq 1-M/N$.

The number of iterations $R$ depends on $M$, the number of solutions. Since $R\leq\pi/(2\theta)$ and $\theta/2\geq\sin(\theta/2)=\sqrt{M/N}$, $R\leq(\pi/4)\sqrt{N/M}$. Typically,$M\ll N$, $\theta\approx\sin\theta\approx 2\sqrt{M/N}$, thus $R\approx(\pi/4)\cdot\sqrt{N/M}$. We estimate the number of solutions by quantum counting, which is to combine the Grover operator with the phase estimation method. Under the basis $|\phi\rangle$ and $|\varphi\rangle$ the Grover operator has eigenvalues $e^{i\theta}$ and $e^{i(2\pi-\theta)}$. Applying the phase estimation method we can estimate the eigenvalues and thus $\theta$ with prescribed precision and probability, which in turn yields $M$. The combination of the quantum counting and search procedure will find a solution of the search problem with certain probability. Repeating the quantum search algorithm will boost the probability and enable us to obtain a solution to the search problem.

Quantum walk and quantum Markov chain are currently being investigated for new quantum search algorithms and quantum speed-up of Markov chain based algorithms (Aharonov and Ta-Shma (2003), Childs et al. (2003); Childs (2010); Tulsi (2008); Shenvi, Kempe and Whaley (2003) and Szegedy, 2004). In Section 5 we show that the quantum search algorithm can also be viewed as a quantum simulation procedure.

Quantum Simulation

Quantum simulation is to intentionally and artificially mimic a natural quantum dynamics, which is hard to access, and analyze, by a computer-generated quantum system, which is easy to manipulate and investigate. It provides scientific means for simulating complex biological, chemical or physical systems in order to study and understand certain scientific phenomena and evaluate hard-to-obtain quantities in the systems. Examples in modern scientific studies include the estimation of dielectric constant, proton mass, and precise energy of molecular hydrogen, the study of superconductivity, the test of novel nano-materials, and the design of new biomolecules.

To simulate a quantum system we need to solve the Schrödinger equation (1) which governs the dynamic evolution of the system. For a typical Hamiltonian with real particles the Schrödinger equation usually consists of elliptical differential equations, each of which can be easily simulated by a classical computer. However, the real challenge in simulating a quantum system is to solve the exponential number of such differential equations. For a quantum system of $b$ qubits, its states have $2^{b}$ amplitudes. To simulate the dynamic behavior of $b$ qubits evolving according to the Schrödinger equation, we need to solve a system of $2^{b}$ differential equations. Due to the exponential growth in the number of differential equations, the simulation of general quantum systems by classical computers is very inefficient. Classical simulation of quantum systems is feasible for the cases where insightful approximations are available to dramatically reduce the effective number of equations involved. Quantum computers may excel in simulating physically interesting and important quantum systems for which efficient simulation by classical computers may not be available.

The key of quantum simulation is to solve the Schrödinger equation (1) which has solution

Numerical evaluation of $e^{-i\mathbf{H}t}$ is needed. The Hamiltonian $\mathbf{H}$ is usually exponentially large and extremely difficult to exponentiate. The common approach in numerical analysis is to use the first-order linear approximation, $1-i\mathbf{H}\delta$, of $e^{-i\mathbf{H}(t+\delta)}-e^{-i\mathbf{H}t}$, which often yields unsatisfactory numerical solutions.

Many classes of Hamiltonians have sparse representations. For such sparse Hamiltonians we can find efficient evaluation of the solutions (14) with high-order approximation. For example, the Hamiltonians in many physical systems involve only local interactions, which originate from the fact that most interactions fall off with increasing distance in location or increasing difference in energy. In the local Hamiltonian case, the Hamiltonian of a quantum system with $\alpha$ particles in a $d$-dimensional space has the form

While classical computers are inefficient in simulating general quantum systems, quantum computers can efficiently carry out the quantum simulation procedure and provide an exponential speedup for the quantum simulation on classical computers. In spite of the inefficiency, classical computers are currently being used to simulate quantum systems in biochemistry and material science. Quantum simulation will be among the important applications of quantum computers. See Abrams and Lloyd (1997), Aspuru-Guzik, Dutoi and Head-Gordon (2005), Bennett et al. (2002), Berry et al. (2007), Freedman, Kitaev and Wang (2002), Jané et al. (2003), Boghosian and Taylor (1998), Lloyd (1996), Nielsen and Chuang (2000), and Zalka (1998).

2 Recast Quantum Search Algorithm as Quantum Simulation

Grover’s search algorithm discussed in Section 4.5 is an important finding in quantum computation. It can be heuristically sketched as a quantum simulation by writing down an explicit Hamiltonian $\mathbf{H}$ such that a quantum system evolves from its initial state $|\psi\rangle$ to $|x\rangle$ after some specified time, where $x$ is a solution of the search problem. Of course the Hamiltonian $\mathbf{H}$ depends on the initial state $|\psi\rangle$ and solution $x$. Suppose that $|y\rangle$ is another state such that $|x\rangle$ and $|y\rangle$ form an computational basis, and $|\psi\rangle=\alpha|x\rangle+\beta|y\rangle$ for real $\alpha$ and $\beta$ with $\alpha^{2}+\beta^{2}=1$. Define Hamiltonian

where $\bm{\sigma}_{x}$ and $\bm{\sigma}_{z}$ are Pauli matrices defined in (3.3.1). Then

Measuring the system at time $t=\pi/(2\alpha)$ yields the solution state $|x\rangle$.

3 Quantum Monte Carlo Simulation

Quantum theory is intrinsically stochastic andquantum measurement outcome is random. As many naturally occurring quantum systems involve a large number of interacting particles, due to the computational complexity we are forced to utilize Monte Carlo techniques in the simulations of such quantum systems. The combination of Monte Carlo methods with quantum simulation makes it possible to obtain reliable quantifications of quantum phenomena and estimates of quantum quantities. Such combination procedures are often referred to as quantum Monte Carlo simulation (Nightingale and Umrigar (1999); Rousseau (2008)). Consider the problem of estimating the following quantity:

where $\mathbf{X}$ is an observable, $X$ is its measurement result, and $\bm{\rho}$ is the state of the quantum system under which we perform the measurements and evaluate the quantity $\theta$.

Quantum Information

Classical information theory is centered on Shannon’s two coding theorems on noiseless and noisy channels. The noiseless channel coding theorem quantifies the number of classical bits required to store information for transmission by Shannon entropy, while the noisy channel coding theorem quantifies the amount of information that can be reliably transmitted through a noisy channel by an error-correction coding scheme. The quantum analogs of Shannon entropy and Shannon noiseless coding theorem are von Neumann entropy and Schumacher’s noiseless channel coding theorem, respectively. The von Neumann entropy is defined to be $S(\bm{\rho})=-\operatorname{tr}(\bm{\rho}\log\bm{\rho}).$ Schumacher’s noiseless channel coding theorem quantifies quantum resources required to compress quantum states by von Neumann entropy (Schumacher (1995)). Analogous to Shannon’s noisy channel coding theorem, a theorem known as Holevo–Schumacher–Westmoreland theorem can be used to compute the product quantum state capacity for some noisy channels (Holevo (1998); Schumacher and Westmoreland (1997)). However, communications over noisy quantum channels are much less understood than the classical counterpart. It is an unsolved problem to determine quantum channel capacity or the amount of quantum information that can be reliably transmitted over noisy quantum channels. See Hayashi (2006) and Nielsen and Chuang (2000).

In spite of the above similarity, there are intrinsic differences between classical information and quantum information. Classical information can be distinguished and copied. For example, we can identify different letters and produce an identical version of a digital image for back-up. However, quantum mechanics does not allow unknown quantum states to be distinguished or copied exactly. For example, we cannot reliably distinguish between quantum states $|0\rangle$ and $(|0\rangle+|1\rangle)/\sqrt{2}$. If we perform measurement for quantum state $|0\rangle$, the measurement result will be with probability 1, while measuring quantum state $(|0\rangle+|1\rangle)/\sqrt{2}$ yields measurements or $1$ with equal probability. A measurement result of cannot tell the identity of the quantum state being measured. A theorem known as a no-cloning theorem states that unknown quantum states cannot be copied exactly (Wootters and Zurek (1982); Nielsen and Chuang (2000)).

As we discussed in Section 3.3, quantum entanglement plays a crucial role in strange quantum effects such as quantum teleportation, violation of Bell’s inequality, and superdense coding (Hayashi (2006); Nielsen and Chuang (2000)). Entanglement is a new type of resource that differs vastly from the traditional resources in classical information theory. We are far from having a general theory to understand quantum entanglement but encouraging progress made so far reveals the amazing property and intriguing structure of entangled states and remarkable connections between noisy quantum channels and entanglement transformation. Considerquantum error-correction for reliable quantum computation and quantum information processing. Quantum error-correction is employed in quantum computation and quantum communication to protect quantum information from loss due to quantum noise and other errors like faulty quantum gates. Classical information uses redundancy to achieve error-correction, but the no-cloning theorem presents an obstacle to copying quantum information and formulating a theory of quantum error-correction based on simple redundancy. Again quantum entanglement comes to the rescue. It is forbidden to copy qubits but we can spread the information of one qubit onto a highly entangled state of several qubits. Shor (1995) first discovered the method of formulating a quantum error-correction code by storing the information of one qubit onto a highly entangled state of nine qubits. Over time several quantum error-correction codes are proposed (Calderbank and Shor (1996); Cory et al. (1998); Steane, 1996a, 1996b). These quantum error-correction codes can protect quantum information against quantum noise, and thus quantum noise likely poses no fundamental barrier to the performance of large-scale quantum computing and quantum information processing.

Here is how quantum error-correction codes work. We consider the single qubit case. First assume that a qubit $\alpha_{0}|0\rangle+\alpha_{1}|1\rangle$ is passed through a bit flip channel which flips the state of a qubit from $|0\rangle$ to $|1\rangle$ and from $|1\rangle$ to $|0\rangle$, each with probability $p$, and leaves each of states $|0\rangle$ and $|1\rangle$ untouched with probability $1-p$. We describe a bit flip code that protects the qubit against quantum noise from the bit flip channel.

We encode states $|0\rangle$ and $|1\rangle$ in three qubits, with $|0\rangle$ encoded as $|000\rangle$ and $|1\rangle$ as $|111\rangle$. Thus the qubit state $\alpha_{0}|0\rangle+\alpha_{1}|1\rangle$ is encoded in three qubits as $\alpha_{0}|000\rangle+\alpha_{1}|111\rangle$. We pass each of the three qubits through an independent copy of the bit flip channel, and assume that at most one qubit is flipped. The following simple two-step error-correction procedure can be used to recover the correct quantum state.

Step 1. Perform a measurement on a specially constructed observable and call the measurement result an error syndrome. The error syndrome can inform us what error, if any, occurred on the quantum state. The observable has eigenvalues , $1$, $2$ and $3$, with corresponding projection operators,

If one of three qubits has one or no bit flip, the error syndrome will be one of , $1$, $2$ and $3$, with corresponding to no flip, and $1$, $2$ and $3$ to a bit flip on the first, second and third qubit, respectively. For example, if the first qubit is flipped, the corrupted state is $|\psi\rangle=\alpha_{0}|100\rangle+\alpha_{1}|011\rangle$. Since $\langle\psi|\mathbf{Q}_{1}|\psi\rangle=1$ and $\langle\psi|\mathbf{Q}_{j}|\psi\rangle=0$ for $j\neq 1$, in this case the error syndrome is $1$. Although performing measurements usually causes change to the quantum state, the speciality of the constructed observable is that syndrome measurement does not perturb the quantum state: it is easy to check that the state is $|\psi\rangle$ both before and after the syndrome measurement. While the syndrome provides information about what flip error has occurred, it does not contain any information about the state being protected, that is, it does not allow us to deduce anything about the amplitudes $\alpha_{0}$ and $\alpha_{1}$. Such a special property is the generic feature of syndrome measurement.

Step 2. The error type supplied by the error syndrome can inform us what procedure to use to recover the original state. For example, error syndrome $1$ indicates a bit flip on the first qubit, and a flip on the first qubit again will perfectly recover the original state $\alpha_{0}|000\rangle+\alpha_{1}|111\rangle$. The error syndrome implies no error and doing nothing, and error syndromes $1$, $2$ and $3$ correspond to a bit flip again on the first, second, third qubit, respectively. The procedure will recover the original state with perfect accuracy, if there is at most one bit flip in the encoded three qubits. The probability that more than one bit flipped is $p^{3}+3p^{2}(1-p)=3p^{2}-2p^{3}$, which is much smaller than the error probability $p$ of making no-correction for the typical bit flip channel. Thus the encoding and decoding scheme makes the storage and transmission of the qubit more reliable.

Next we consider a more interesting noisy quantum channel: a phase flip channel which, with probability $p$, changes a qubit state $\alpha_{0}|0\rangle+\alpha_{1}|1\rangle$ to $\alpha_{0}|0\rangle-\alpha_{1}|1\rangle$, and with probability $1-p$, leaves alone the qubit. The following scheme is to turn the phase flip channel into a bit flip channel. Let $|+\rangle=(|0\rangle+|1\rangle)/\sqrt{2}$ and $|-\rangle=(|0\rangle-|1\rangle)/\sqrt{2}$ be a qubit basis. The phase flip channel leaves alone states $|+\rangle$ and $|-\rangle$ with probability $1-p$ and changes $|+\rangle$ to $|-\rangle$ and vice versa with probability $p$. In other words, the phase flip channel with respect to the basis $|+\rangle$ and $|-\rangle$ acts just like a bit flip channel with respect to the basis $|0\rangle$ and $|1\rangle$. Thus we encode $|0\rangle$ as $|{+}+{+}\rangle$ and $|1\rangle$ as $|{-}-{-}\rangle$ for protection against phase flip errors. The operations for encoding, error-detection and recovery are the same as for the bit flip channel but with respect to the $|+\rangle$ and $|-\rangle$ basis instead of the $|0\rangle$ and $|1\rangle$ basis.

Last we describe Shor error-correction code. It is a combination of the three-qubit phase flip and bit flip codes. First use the phase flip code to encode states $|0\rangle$ and $|1\rangle$ in three qubits, with $|0\rangle$ encoded as $|{+}+{+}\rangle$ and $|1\rangle$ as $|{-}-{-}\rangle$; next, use the three-qubit bit flip code to encode each of these qubits, with $|+\rangle$ encoded as $(|000\rangle+|111\rangle)/\sqrt{2}$ and $|-\rangle$ encoded as $(|000\rangle-|111\rangle)/\sqrt{2}$. The resulted nine-qubit code has codeworks as follows:

With the mixture of both phase flip and bit flip codes, the Shor error-correction code can protect against bit flip errors, phase flip errors, as well as a combined bit and phase flip errors on any single qubit. In fact it has been shown that this simple quantum error-correction code can protect against the effects of any completely arbitrary errors on a single qubit (Shor (1995)).

Concluding Remarks

Quantum information science gains enormous attention in computer science, mathematics, physical sciences and engineering, and several interdisciplinary subfields are developing under the umbrella of quantum information. This paper reviews quantum computation and quantum information from a statistical perspective. We introduce concepts like qubits, quantum gates and quantum circuits in quantum computation and discuss quantum entanglement, quantum parallelism and quantum error-correction in quantum computation and quantum information. We present major quantum algorithms and show their advantages over the available classical algorithms. We illustrate quantum simulation procedure and Monte Carlo methods in quantum simulation. As classical computation and simulation are ubiquitous nowadays in statistics, we expect quantum computation and quantum simulation will have a paramount role to play in modern statistics. This paper exposes the topics to statisticians and encourages more statisticians to work in the fields. There are many statistical issues in theoretical research as well as experimental work in quantum computation, quantum simulation and quantum information. For example, as measurement data collected in quantum experiments require more and more sophisticated statistical methods for better estimation, simulation and understanding, it is imperative to develop good quantum statistics methods and quantum simulation procedures and study interrelationship and mutual impact between quantum estimation and quantum simulation. Since quantum computation is intrinsically random, and quantum simulation employs Monte Carlo techniques, as we point out in Section 4.3 and Wang (2011), it is important to provide sound statistical methods for analyzing quantum algorithms and quantum simulation in general and study high-order approximations to exponentiate Hamiltonians and the efficiency of the resulted quantum simulation procedures in particular. On the other hand, quantum computation and quantum simulation have great potential to revolutionize computational statistics. Below are a few cases in point.

The “random numbers” generated by classical computers are pseudo-random numbers in thesense that they are produced by deterministic procedures and can be exactly repeated and perfectly predicted given the deterministic schemes and the initial seeds. On the contrary, superposition states enable quantum computers to produce genuine random numbers. For example, measuring $(|0\rangle+|1\rangle)/\sqrt{2}$ yields and $1$ with equal probability. In general we generate $b$-bit binary random numbers $x=x_{1}\cdots x_{b}$, $x_{j}=0,1$ as follows. Apply $b$ Hadamard gates to $b$ qubits of $|0\cdots 0\rangle$ to obtain

where the sum is over all possible $2^{b}$ values of $x$, and then measure the obtained qubits and yield $b$-bit binary random numbers $x=x_{1}\cdots x_{b}$ with equal probability. Quantum theory guarantees that such random numbers are genuinely random. Thus quantum computers are able to generate genuine random numbers and perform true Monte Carlo simulation. It is exciting to design general quantum random number generator and study quantum Monte Carlo simulation. Perhaps we may need to re-examine Monte Carlo simulation studies conducted by classical computers.

It is interesting to investigate the potential of quantum computation and quantum simulation for computational statistics. We expect that quantum computers may be much faster than classical computers for computing some statistical problems. Moreover, quantum computers may be able to carry out some computational statistical tasks that are prohibitive by classical computers. Specific examples are as follows: (a) We may use the basic ideas of Grover’s search algorithm to develop fast quantum algorithms for implementing some statistical procedures. For example, finding the median of a huge data set is to search for a numerical value that separates the top and bottom halves of the data, and quantum algorithms can offer quadratical speedup for calculating median and trimmed mean. (b) With genuine random number generator and faster mean evaluation, quantum computers may offer significant advantages over classical computers for Monte Carlo integration. For example, Monte Carlo integration in high dimensions may be exponentially or quadratically faster on quantum computers than on classical computers. (c) It might be possible for quantum computers to carry out some prohibiting statistical computing tasks like the Bayesian computation discussed in Section 3. Some preliminary research along these lines may be found in Nayak and Wu (1999) and Heinrich (2003).

As quantum computation and quantum simulation are ideal for simulating interacting particle systems like the Ising model, it is fascinating to explore the interplay between quantum simulation and Markov chain Monte Carlo methodology and the quantum potential to speed up Markov chain based algorithms. In fact, it has been shown that quantum walk based algorithms can offer quadratical speedup for certain Markov chain based algorithms (Magniez et al. (2011); Richter (2007); Szegedy (2004), and Wocjan and Abeyesinghe (2008)).

Finally we point out that quantum computers are wonderful but it is difficult to build quantum computers with present technology. To build a quantum computer the physical apparatus must satisfy requirements that the quantum system realized qubits needs to be well isolated in order to retain its quantum properties and at the same time the quantum system has to be accessible so that the qubits can be manipulated to perform computations and measure output results. The two opposing requirements are determined by the strength of coupling of the quantum system to the external entities. The coupling causes quantum decoherence. Decoherence refers to the loss of coherence between the components of a quantum system or quantum superposition from the interaction of the quantum system with its environment. It is very crucial but challenging to control a quantum system of qubits and correct the effects of decoherence in quantum computation and quantum information. Quantum computing has witnessed great advances in recent years, and quantum computers of a handful of qubits and basic quantum communication devices have been built in research laboratories (see Barz et al. (2012); Clarke and Wilhelm (2008); DiCarlo et al. (2009); Johnson et al. (2011); Lee et al. (2011); Neumann et al. (2008)), but there are technological hurdles in the development of a quantum computer of large capacity. History shows that scientific innovations and technological surprises are a never-ending saga. It is anticipated that quantum computers with a few dozen of qubits will be built in near future. As we have discussed in Section 3.1, such a quantum computer has capacity of a classical supercomputer. We are very optimistic that someday quantum computers will be available for statisticians to crunch numbers. For the time being, instead of waiting in the sidelines for that to happen, statisticians should get into the field of play. It is time for us to dive into this frontier research and work with scientists and engineers to speed up the arrival of practical quantum computers. As a last note, in 2011 a Canadian company called D-Wave has sold the claimed first commercial quantum computer of 128 qubits to the Lockheed-Martin corporation, despite the D-Wave’s quantum system being criticized as a black box. Large scale quantum computers may be years away, but quantum computing is already here as a scientific endeavor to provoke deep thoughts and integrate profound questions in physics and computer science.

Acknowledgments

Wang’s research was supported in part by NSF Grant DMS-10-05635. He thanks editor David Madigan and two anonymous referees for helpful comments and suggestions which led to significant improvements in both substance and the presentation of the paper.

References