Quantum science and quantum technology arise from a synthesis of quantum mechanics, information theory, and computing. They investigate the preparation and control of the quantum states of physical systems to generate new knowledge and technologies for information processing and transmission, computation, measurement, and fundamental understanding in ways that classical approaches can only do much less efficiently, or not at all. The fields comprise quantum communication, quantum information, quantum computation, quantum simulation, and quantum metrology (also known as quantum sensing), where quantum communication utilizes quantum means to transmit data in a provably secure way; quantum information describes the information of the state of a quantum system and the process of the information by quantum devices; quantum computation uses quantum effects to speed up certain calculations dramatically; quantum simulation reproduces the behavior of hard accessible quantum systems by manipulating well-controlled quantum systems; quantum metrology exploits the high sensitivity of coherent quantum systems to external perturbations for enhancing the performance of measurements of physical quantities. Quantum science and quantum technology differ Yazhen Wang is Professor, Department of Statistics, University of Madison,Wisconsin 53706,. Xinyu Song is Assistant Professor, School of Statistics and Management, Shanghai University of Finance and Economics, Shanghai 200433, China (e-mail: song.xinyu@mail.shufe.edu.cn).
from existing applications of quantum mechanics and information theory, such as lasers, transistors, MRI, and currently used classical computers and classical communication tools, in ways that we utilize distinct quantum phenomena like quantum superposition, entanglement, and tunneling, which do not have classical counterparts. In the past two decades, we have made tremendous progress in the study of quantum science and quantum technology for harnessing quantum phenomena to advance information processing and transmission, computation, and measurement.
Quantum science not only establishes a foundation for gaining a deeper understanding of nature, but also makes it possible to invent new quantum technology for accomplishing tasks that are impossible to achieve by classical techniques. Here quantum technology refers to technologies that explicitly deal with individual quantum states and specifically exploit special quantum properties that do not have classical analogue. They enable us to build quantum devices for achieving faster computation, more secure communication, and better physical measurements than classical techniques. This article intends to present an overview of such quantum aspects of science and technology, particularly in quantum information, quantum communication, and quantum computation.
The rest of the paper proceeds as follows. Section 2 briefly introduces quantum physics. Section 3 reviews basic quantum concepts used in quantum science and quantum technology. Sections 4 and 5 discuss quantum communication and quantum information, respectively. Section 6 illustrates quantum computation. It covers universal quantum computing based on the gate (or circuit) model, adiabatic quantum computing based on quantum annealing, and current development on building quantum computers. This section also includes quantum algorithms, quantum simulation, quantum machine learning, and quantum computational supremacy. Section 7 provides a short description of quantum metrology. Section 8 features concluding remarks and points out potential applications of quantum science and quantum technology to statistics and data science as well as the need of statistics in the development of quantum science and quantum technology.
Unlike the typical literature on quantum mechanics that adopts technically more complicated concepts and notations such as operators with a continuous spectrum on an infinite-dimensional Hilbert space, for simplicity we choose to use relatively easy finite-dimensional linear algebra for the purpose of discussing quantum science and quantum technology. Since operators correspond to matrices in the finite dimensional case, we need to deal with only matrices and their operations such as eigenanalysis. Denote by R and C, respectively, the sets of all real numbers and all complex numbers. A simple vector space is C d comprising all d-tuples of complex numbers (z 1 , . . . , z d ). We use Dirac notations |• (which is called ket) and •| (which is called bra) to show that the objects are column vectors or row vectors in the vector space, respectively. Denote by superscripts * , and † the conjugate of a complex number, the transpose of a vector or matrix, and conjugate transpose operation, respectively. For |u and |v in the vector space, we denote their inner product by u|v , which induces a norm u = √ u|u , and a distance uv between |u and |v . For example, C d has a natural inner product
where u| = (u 1 , . . . , u d ) and |v = (v 1 , . . . , v d ) . Given a matrix A = (a ij ), we say it is Hermitian if A = A † , and denote its trace by tr(A) = k j =1 a jj . A matrix U is said to be unitary if UU † = U † U = I. For two matrices A 1 and A 2 , define their commutator
Denote by ⊗ the tensor product operation of vectors or matrices. To analyze computer algorithms, we adopt a notation O(h(m)) to denote that the asymptotic scaling of an algorithm is upper-bounded by a function h(m) of the input size m, with the notation Õ(h(m)) ignoring logarithmic factors.
Quantum mechanics describes microscopic phenomena such as the positions and momentums of individual particles like atoms or electrons, the spins of electrons, the emissions and absorptions of light by atoms, and the detections of light photons. Unlike classical mechanics that can precisely measure physical entities like position and momentum, quantum physics is intrinsically stochastic in the sense that only a probabilistic prediction can be made about the results of the measurements performed.
We may describe a quantum system by its state and the dynamic evolution of the state. A quantum state is often characterized by a unit complex vector with dynamic unitary evolution, where the unitary evolution means that quantum states are connected by unitary matrices, and the dynamic evolution is governed by a differential equation called the Schrödinger equation. Specifically, let |ψ(t) be the state of the quantum system at time t (also a wave function at time t). The states |ψ(t) and |ψ(t + s) at times t and t + s, respectively, are connected through |ψ(t + s) = U(s)|ψ(t) , where U(s) = exp(-√ -1Hs) is a unitary matrix, and H is a Hermitian matrix on C d , which is known as the Hamiltonian of the quantum system. Differentiating both sides of |ψ(t + s) = exp(-√ -1Hs)|ψ(t) with respect to s and letting s go to 0, we obtain the following Schrödinger equation for governing the continuous time evolution of |ψ(t) :
(2.1) √ -1 ∂|ψ(t) ∂t = H ψ(t) .
Note that although the Schrödinger equation is regarded as somewhat mysterious when it is first encountered, for a Markov chain in continuous time with a finite state space, transition probability matrix P t and Q-matrix Q, we use exactly the same argument: from P s+t = P s P t , by differentiation we obtain the Kolmogorov equation ∂P t ∂t = QP t , which has the solution P t = exp(Qt)P 0 .
As an alternative, we can describe a quantum system by a so-called density matrix. For a d-dimensional quantum system, its quantum state can be characterized by a density matrix ρ on the d-dimensional complex space C d , where ρ satisfies (1) Hermitian; (2) positive semi-definite;
(3) unit trace. We often classify a quantum state as a pure state or an ensemble of pure states. A pure state corresponds to a density matrix ρ = |ψ ψ|, where |ψ is a unit vector in C d . An ensemble of pure states has a density matrix
p j |ψ j ψ j |, which corresponds to the scenario that the quantum system is in one of states |ψ j , j = 1, . . . , J , with probability p j being in the state |ψ j . The quantum evolution in the density matrix representation can be described as follows.
Let ρ t be the density matrix of the state of the quantum system at time t. With the unitary matrix U(•) and Hamiltonian H introduced above, the density matrix evolution is given by ρ t+s = U(t)ρ s U † (t), with the Schrödinger equation in the form of
See Sakurai and Napolitano (2017) and Shankar (2012) for details. As we will see in Section 3.1, the number of complex numbers and the dimensionality of vectors and matrices required to describe a quantum state and its evolution usually increase exponentially in the system size, rather than linearly in a classical system. As a result, a quantum system can store and manage an exponential number of complex numbers and perform data manipulations and calculations during the evolution of the system, while classical computers find it difficult to cope with the quantum system as it requires an exponential number of bits of memory to store the quantum state. Unlike the classical case where we often need to consider some extra structural assumptions or approximations when handling high-dimensional objects, quantum systems have potential to deal with exponentially high-dimensional problems without imposing additional constraints. Special quantum phenomena are utilized to accomplish quantum communication and computational tasks, and subsequent sections will illustrate that the quantum phenomena are often strange, and counter-intuitive. For example, light can be particles and waves (wave-particle duality); a cat can be alive and dead at the same time (quantum superposition); information can transmit instantaneously over a long distance without going through the intervening space (quantum teleportation); without sufficient energy, quantum particles can pass a barrier that is classically impossible (quantum tunneling).
In classical information and computation, the most fundamental entity is the bit, and the information encoded in a bit has two state values, 0 and 1. Classical bits can be materialized in multiple means, for example, they may be realized mechanically as switches or magnetically as hard drives. An important fact of the classical bit is that its two state values are mutually exclusive, namely, its state can only be either 0 or 1. This fact leads to one thing in common for all of the realization means, that is, all classical physical devices prevent the simultaneous occurrence of the states, with an example of the switch being either on or off.
In quantum science and quantum technology, the counterpart of the classical bit is the quantum bit, which we call qubit for short. Similar to a classical bit with two state values 0 and 1, a qubit has states |0 and |1 , where we use the customary Dirac notation |• to denote the qubit state. However, one key difference exists between a classical bit and a qubit. Specifically, the theory of quantum physics allows the description of a quantum physical system through probabilistic combinations of its states, which is referred to as the superposition property. The superposition of states can accommodate all predictions for the outcomes of physical measurements, moreover, it bears drastic consequences for the nature of the physical states ascribed to a system. In this regard, besides the states |0 and |1 , a qubit can be in superposition states with the following form:
where complex numbers α 0 and α 1 are called amplitudes and satisfy
As a result, the states of a qubit are unit vectors in a two-dimensional complex vector space C 2 . The states |0 and |1 form an orthonormal basis for the space and are often referred to as computational basis states. Unlike classical bits that have mutually exclusive states, qubits can be one and zero simultaneously, which is known as the most fundamental aspects of qubits. In other words, a superposition state is a state of matter that can be viewed as simultaneous occurrence of zero and one at the same time.
Qubits can be realized in various physical systems. Examples of qubits include the two states of an electron orbiting a single atom, the two different polarizations of a photon, the alignment of a nuclear spin in a uniform magnetic field, or the two directions of current flows in superconducting circuits. Specifically, in the atom model, |0 and |1 can be treated respectively, as the so-called 'ground' and 'excited' states of the electron; if the atom is shined by light with appropriate energy and for a suitable amount of time, we may transfer the electron from the |0 state to the |1 state and vice versa. Furthermore, by adjusting the time length for shining the light on the atom, the electron can be moved from the initial state |0 into 'halfway' between |0 and |1 , for example, into state
, where |+ and |form a qubit basis that is equivalent to the computational qubit basis |0 and |1 . Note that the quantum state transformations are solutions of the Schrödinger equation (2.1) for particular choices of Hamiltonian H and time interval, and it is an interesting exercise for readers to find the appropriate Hamiltonians.
It is easy to examine a classical bit to determine its state, being 0 or 1, however, it is impossible to examine a qubit |ψ to determine its state or find the values of its amplitudes α 0 and α 1 defined in (3.1). Because of the stochastic nature of quantum theory, performing measurements on the qubit |ψ will result in measurement outcome 0 with probability |α 0 | 2 , or measurement outcome 1 with probability |α 1 | 2 . Moreover, performing measurements on the qubit will change its state.
Like classic bits, we may define multiple qubits. The states of one b-qubit are unit vectors in a 2 b -dimensional complex vector space. The quantum exponential complexity is then shown in the exponential growth of dimensionality 2 b and the number of 2 b amplitudes required to specify superposition states. For the 2-qubit case, its superposition states are unit vectors in a 4-dimensional complex vector space, with the following form:
where |00 , |01 , |10 , and |11 are four computational basis states, amplitudes α x are complex numbers satisfying
As in the single qubit case, when measuring the 2-qubit, we obtain measurement outcome x as one of 00, 01, 10, 11, with a corresponding probability |α x | 2 . Furthermore, we may perform a measurement just on the first qubit of the 2-qubit system and obtain either the measurement outcome 0, with probability |α 00 | 2 + |α 01 | 2 , or the outcome 1, with probability |α 10 | 2 + |α 11 | 2 . As quantum measuring changes the quantum state, depending on the measurement outcome obtained for the first qubit, being either 0 or 1, the 2-qubit system will be in the state
, respectively. See Nielsen and Chuang (2010) and Wang (2012) for details.
As one of the most mind-bending creatures known to science, quantum entanglement is often cited as the phenomenon that two particles that are connected by an invisible wave can share each other's properties regardless of the distance between them, just like a twin. It leads to the fact that none of the particles involved in a quantum system can be described by quantum states of individual subsystems. In other words, all information content of an entangled quantum system is fully entailed in the correlations between the individual subsystems while none of the subsystems on their own convey essential information of the entangled quantum system. For a multi-qubit system, its entangled states are superposition states that are described by joint properties of the individual qubits in the multi-qubit system. Consider an entangled 2-qubit system, we obtain a completely random outcome when performing measurements on only one of its entangled qubits. The measurement outcome is absolutely random, and it is impossible to gain information about the entangled system from the obtained random measurement outcome. As the entangled state involves two qubits, their correlation must contain two bits of classical information, and the classical information can only be gathered by comparatively examining the outcomes of the individual measurements on the separate subsystems. We as well point out an intriguing feature of entangled states: measuring one of the entangled qubits instantaneously casts the other one into the corresponding perfectly correlated state, which immediately destroys the entanglement as qubit measuring changes their quantum state. We take a Bell state
as an example to demonstrate entanglement, where α 00 = α 11 = 0, α 01 = 1/ √ 2, and α 10 = -1/ √ 2 in the expression of (3.2). As described in Section 3.1, measuring the first qubit of the Bell state |ψ , we obtain measurement outcome 0 or 1 with probability |α 00 | 2 + |α 01 | 2 = 1/2 and |α 10 | 2 + |α 11 | 2 = 1/2 respectively, which is completely random. According to (3.3), if the measurement outcome is 0 (or 1), then the state will be |01 (or |10 , respectively). This result means that if the first measurement outcome is 0 (or 1), then the second qubit's state must be |1 (or |0 , respectively) with measurement always being 1 (or 0, respectively), which indicates perfect correlation. Quantum states like the Bell state in (3.4) that cannot be expressed as products of some single qubits are called entangled states, while product states refer to quantum states that can be written in the product form of single qubits. Over the past decades many physical experiments have been designed and conducted to test quantum entanglement through the so-called Bell inequality.
For the case of a 2-qubit system realized by the spins of two particles, imagine that the two-particle system is first prepared in an entangled state, then the two particles are drifted far away from each other. We now have Alice and Bob measure the first and second particles, respectively, and sequentially. The perfect correlation suggests that after Alice obtains her spin measurement result (i.e., +1 or -1) on the first particle, the system has its state immediately plunged into the untangled state. As a result, the second particle now has a definite spin state, and Bob's spin measurement on the second particle always provides a definite opposite result (i.e., -1 or +1, respectively). This phenomenon of perfect correlation is referred to as anti-correlation in entanglement experiments. We will show that quantum properties such as superposition and entanglement play key roles in quantum science and quantum technology. See Horodecki et al. (2009), Nielsen and Chuang (2010) and Wang (2012) for more details.
As its classical analog, quantum information targets at determining the laws governing any information process based on quantum theory. The core of classical information theory is Shannon's two coding theorems on noiseless and noisy channels. The coding theorems quantify classical bits by Shannon entropy for transmission over a noiseless channel and character the amount of information transmitted over a noisy channel with some error-correction scheme. On the other hand, the quantum-based theory has been established to apprehend quantum resources such as superposition, entanglement, nonlocality, no-cloning, and quantum randomness. The quantum counterparts of Shannon entropy and Shannon noiseless coding theorem are von Neumann entropy and Schumacher's noiseless channel coding theorem, respectively. Schumacher's noiseless channel coding theorem describes quantum information needed to compress quantum states by von Neumann entropy (Schumacher, 1995). The quantum analog of Shannon's noisy channel coding theorem is Holevo-Schumacher-Westmoreland theorem employed to calculate the product quantum state capacity for some noisy channels (Holevo, 1998, Schumacher andWestmoreland, 1997).
Despite the resemblance, there exist inherent distinctions between classical information and quantum information. For example, while classical information such as digital images can be distinguished and copied, quantum superposition and no-cloning theorem imply that unknown quantum states cannot be completely distinguished or exactly copied. Consider another example, besides the computational basis |0 and |1 for the qubit space, we have another basis
√ 2 given in Section 3.1, and quantum information can be encoded under each of these bases. Different ways of encoding quantum information are employed in quantum error-correction for reliable quantum computation and quantum information processing. Moreover, the information encoded under one basis cannot be extracted by performing measurement under another basis, which plays an important role in quantum cryptography. For example, consider encoding one bit of information in different bases by the polarization of light. Suppose that the computational basis formed by |0 and |1 represents the horizontal and vertical basis (corresponding to horizontally and vertically polarized photons). As diagonally and anti-diagonally polarized photons can be expressed in the horizontal and vertical basis as coherent superpositions of horizontal and vertical parts, the basis formed by |+ and |corresponds to the diagonal and anti-diagonal basis. We may encode a bit of information in the |0 and |1 basis by treating 0 to be horizontal polarization and 1 to be vertical polarization. For a photon encoded in either horizontal or vertical polarization, if we measure it in the diagonal and anti-diagonal basis, its information cannot be extracted. Indeed, as described in Section 3.1, we have
and thus, when measuring |0 or |1 in the basis |+ and |-, we observe + andwith equal probability, that is, we observe a diagonally polarized photon in 50% of the cases and an anti-diagonally polarized photon in the other 50% of the cases.
Quantum physics provides new types of resources for information processing and transmission such as quantum teleportation, superdense coding, quantum key distribution, and quantum error-correction. Also, quantum information ideas have effectively been employed in other scientific studies such as many-body physics, quantum gravity, high-energy physics, quantum chemistry, quantum biology, and even for solving conjectures in the fields of classical information and computation. See Hayashi (2006), Krenn et al. (2017), Nielsen and Chuang (2010) and Wang (2012) for more details.
Quantum teleportation is a process through which we transfer the state of a quantum system (or qubit) to another distant quantum system (or qubit) without ever existing in the intervening space in between. The phenomenon can be illustrated by a three-step protocol of quantum teleportation as follows. First, Alice (the sender) and Bob (the receiver) together generated a special pair of entangled qubits, and each took one qubit of the two shared qubits when they split. Second, Alice was given a third qubit whose state was undisclosed to her, and she would like to teleport the unknown state. Third, Alice interacted the third qubit with her qubit and performed a special measurement on her original qubit so that, while the measurement destroyed the entanglement and ruined any information about the state of her qubit, it would make Bob's qubit instantaneously project onto a new state that Bob could use to recover the original state of Alice's qubit. After the three steps, the state of Alice's qubit was transported to that of Bob's qubit. A key feature in the quantum teleportation protocol is the special entanglement and measurement, and the teleportation protocol only works when Bob was informed by Alice about her measurement outcome so that Bob could work accordingly to recover Alice's state. That is, a successful teleportation event requires classical communication between Alice and Bob, which necessarily restricts the speed of information transfer in the teleportation protocol to the speed of the classical communication channel. See Nielsen and Chuang (2010) and Wang (2012) for details.
It is important to note from the entire three-step protocol of quantum teleportation that contrary to what is usually mistakenly cited, quantum teleportation in principle does not allow faster-than-light communication or any transfer of matter or energy. Quantum teleportation transfers only the state of Alice's qubit to Bob's qubit but does not physically move Alice's qubit (particle) to Bob. Because it is required to send information via the classical channel, quantum teleportation is not capable of transmitting information faster than the speed of light. Otherwise, if Bob can obtain a copy of Alice's qubit (in the sense to physically obtain her 'qubit'), then Bob can make a direct measurement on the copied qubit to obtain the information that was sent over via the classical communication between Alice and Bob. In this way, faster-than-light communication becomes possible, however, the famous no-cloning theorem prevents the teleportation from copying any qubit.
The no-cloning theorem is referred to the fact that quantum mechanics prohibits the creation of identical copies of a general quantum state. Specifically, cloning a quantum state |ψ means a procedure with the product state |ψ |ψ as an output. We begin by introducing an ancilla quantum system whose state |ϕ is not related to the state |ψ being cloned. The no-cloning theorem means that there exists no unitary matrix U such that it evolves the initial state |ψ |ϕ to the desired output state |ψ |ψ , that is, (5.1)
where e -1θ(ψ,ϕ) stands for a phase factor, with phase θ(ψ, ϕ) being some real number. Indeed, if such U exists, it has a similar effect on any arbitrarily selected state |φ since cloning should work for any state. For the pair of states |ψ and |φ in C d , we consider their inner product together with the ancilla state |ϕ , and use (5.1) to obtain
namely, | ψ|φ | equals to 0 or 1. By the Cauchy-Schwarz inequality, we conclude that |ψ is either equal to |φ (with a phase factor) or orthogonal to |φ , which is not possible for an arbitrary pair of states |ψ and |φ . This shows the nonexistence of such U and thus proves the no-cloning theorem. Moreover, we may provide a simple illustration to show that no-cloning is a natural consequence of quantum theory as follows. Consider qubits |0 , |1 , and
√ 2, along with an ancilla qubit |a . Cloning implies there exists a unitary matrix U such that
Using the first two equalities in (5.2) and linearity of U we immediately obtain
which is an entangled state. It is easy to see that the entangled state cannot be written as product state
Therefore, an inconsistency occurs in (5.2), and it is impossible to have all three equalities in (5.2). See Krenn et al. (2017) and Nielsen and Chuang (2010) for more details.
The classical communication required in quantum teleportation does not carry complete information about the qubit being teleported. Even if the information communicated in the classical channel is intercepted by an eavesdropper who may have complete knowledge about what Bob is required to do to recover the desired state, the information is futile if the eavesdropper cannot interact with the entangled qubit held in Bob's hands. Quantum physics opens the door to various distinct quantum secret sharing protocols such as quantum cryptography.
In quantum computation and quantum communication, we need to link qubits in quantum networks and transfer their states. As the no-cloning theorem forbids us to perfectly clone a quantum state, we cannot use classical methods like amplifiers to carry out any transfer of qubits' states. The solution to this problem is a so-called quantum repeater, which allows the end-to-end generation of quantum entanglement in a way that every two connective particles of independent entangled pairs is combined so that the entanglement is relayed onto the remaining two particles. Thus, we are able to achieve the end-to-end state transmission of qubits via quantum teleportation. A quantum repeater is an important building block to interconnect different nodes in a quantum network, and quantum teleportation is one crucial requirement for the quantum repeater. This process is referred to as entanglement swapping and enables us to achieve long-distance quantum communication. See Krenn et al. (2017), Nielsen and Chuang (2010) and Sangouard et al. (2011) for more discussions.
Cryptography allows two parties, the sender Alice and the receiver Bob, to exchange secret messages in their private communications, while at the same time, keeps it very hard for the third parties to 'eavesdrop' on the content of their communications. Applications of cryptography include online bank transactions, electronic commerces, and military communications. We discuss two cryptographic methods adopted in such communications. The first method is a private key cryptosystem, which calls for the two parties to share a secret key. Specifically, Alice employs the key to encrypt a message and obtain the cipher while the cipher can only be understood if the key is known. Alice sends the cipher to Bob who utilizes the key to decrypt the received cipher and read her message. The challenge for the private key cryptosystem lies in guarding the secret key against eavesdropping.
The alternative method is a public key cryptosystem invented in the 1970s that does not require the sharing of a secret key. This method is based on the complexity of hard computational problems such as finding the prime factors of very large numbers. Specifically, Bob first generates a pair of keys, a public one and a private one. He then announces his 'public key' to the general public, everyone including Alice can use the public key to encrypt messages and send him the encrypted messages. The real trick is that the encryption transformation generated by Bob's keys is specially designed such that with only the public key, it is extraordinarily hard, though not impossible, to reverse the encryption transformation. When announcing the public key, Bob retains a corresponding secret key for simple inversion of the encryption transformation and decryption of the received messages. A case in point is the RSA cryptosystem (Rivest, Shamir and Adleman, 1978), one of the most widely used cryptographic protocols. RSA is built on the extreme difficulty of finding prime factors for large composite numbers. Note the mathematical asymmetry of factoring: it is easy to compute a composite number from its prime factors by multiplying the primes, no matter how large they are; however, the reverse process can be very hard, in fact, it is extremely difficult to find the prime factors of some very large composite numbers. RSA encryption retains the large primes as a secret key and makes use of their product to design a 'public key'. Since the best known classical factoring algorithms have exponential complexity, and massive computational attempts to break the RSA system so far have led to no success, it is widely believed that the RSA system is secure against any classical computer-based attacks.
On the other hand, Peter Shor in 1994 discovered the so-called Shor's quantum factoring algorithm that can solve the factoring problem exponentially faster than the best known classical algorithms, thus quantum computers may be able to break the RSA system easily (Shor, 1994). That is, as quantum computers can factor prime numbers significantly faster than classical computers, an eavesdropper equipped with a quantum computer can decipher the encrypted text and read the secret message, with only the public information distributed by RSA. An approach to circumventing this difficulty is a quantum procedure known as quantum cryptography or quantum key distribution so that communication security cannot be undermined. The security of the quantum key distribution is based on the quantum principle that observing or measuring an unknown quantum system will disturb the system that is being monitored. When an eavesdropper listens to the transmission of the quantum key between Alice and Bob, the quantum communication channel employed to set up the key will be disturbed by the eavesdropping, and the disturbance will make eavesdropping noticeable. As a result, Alice and Bob are able to discard the compromised key and retain only the secured key for their communication.
Specifically, quantum key distribution enables two authorized parties to create a secret key at a distance in two stages. In the first stage, the two communicating parties, Alice and Bob, obtain a preliminary key by exchanging quantum signals over the quantum channel and performing measurements. The obtained key is preliminary in the sense that it has two strongly correlated, but nonidentical, and only partly secret strings. In the second stage, Alice and Bob utilize the classical channel to carry out an interactive post-processing protocol. The protocol permits them to refine the preliminary key and extract two identical and absolutely secret (known only to themselves) strings as two identical copies of the created secret key. During the two-stage process, the quantum channel is open to any possible maneuver from a third person. However, the classical channel communication needs the following authentication: while Alice and Bob recognize themselves, a third person may listen to their exchange, but cannot engage in it. In particular, the mission of Alice and Bob is to guarantee security against an adversarial eavesdropper, whom we call Eve, engaging in the conversation over the classical channel and tapping on the quantum channel. Here we use 'security' to convey precisely that the authorized parties never use a nonsecret key, namely, either they can actually generate a secret key, or the protocol is aborted. Hence after transmitting the quantum signals, Alice and Bob need to evaluate the possible amount of information about the preliminary keys may have leaked out to Eve. This is the crucial advantage of quantum communication where information leakage in a quantum channel is quantitatively linked to a degradation of the communication. Such degradation and evaluation are not possible in classical communication. For example, when classical communication channels are tapped, such as phone conversations are bugged, the communication proceeds without any change, as nothing happens.
Besides taking advantage of quantum property that observing a quantum channel disturbs the quantum communication, we may employ quantum entanglement to further enhance the security of quantum key distribution by creating an entanglement-based quantum key distribution. The quantum entanglement property offers secure advantages for designing and implementing the protocol of the entanglement-based quantum key distribution. Let us consider the case where Alice and Bob share an entangled state of a qubit (or particle) pair. When they perform measurements on the qubits, the obtained random measurements will always be opposite due to the perfect correlation between entangled qubits. Alice and Bob then need to communicate over a classical channel regarding how the measurements are performed and obtained in order to sift through the results and obtain a secret key.
The security foundation of quantum key distribution can be established by the core principles of quantum physics such as superposition and no-cloning. When Eve is tapping on a quantum communication channel to extract some information, her act is some kind of measurement performing on the state of the quantum communication system, and the measurement will generally alter the state of the system. On the other hand, if Eve wants a correct copy of the state that Alice conveys to Bob, she will not be successful as the no-cloning theorem shows that an unknown quantum state cannot be duplicated without being altered.
To be specific, the essential idea behind quantum key distribution is that Eve cannot obtain any information from the qubits, whose state is transmitted from Alice to Bob, without disturbing their state. Our proof arguments are as follows. First, the no-cloning theorem described in Section 5.1 prevents Eve from copying Alice's qubit. Second, information gain implies disturbance in the sense that for any try to differentiate between two nonorthogonal quantum states, gaining information is only possible at the cost of bringing in disturbance to the signal. Indeed, suppose that |ψ and |φ are two nonorthogonal quantum states. Eve attempts to gain information about |ψ and |φ by unitarily interacting the states |ψ or |φ with an ancilla quantum system prepared in a state |u . If Eve's attempt does not disturb the states, we obtain two unitary matrices U 1 and U 2 such that
where |v 1 and |v 2 are different states so that Eve can gain information about the identity of the states |ψ and |φ . However, since unitary transformations preserve inner products, it must be that
As |ψ and |φ are nonorthogonal, ψ|φ = 0, and thus we obtain
which indicates that |v 1 and |v 2 have to be equal. This leads to a contradiction, as |v 1 = |v 2 . Therefore, distinguishing between |ψ and |φ must disturb at least one of the states, and we can make secure quantum communication by transmitting nonorthogonal qubit states between Alice and Bob and checking for disturbance in their transmitted states.
Furthermore, the quantum key generation relies on the same quantum physical principles that quantum computation is based on. Unlike classical cryptography, the quantum key distribution does not merely depend on the computational difficulty of solving mathematical problems such as the factoring problem. Hence, it cannot be broken even by quantum computers. In a nutshell, the fundamental quantum physical principles allow for the unconditional security of quantum key distribution, namely, the possibility of guaranteeing security without setting any power limitation on the eavesdropper. See Bennett and Brassard (2014), Bernstein and Lange (2017), Buhrman et al. (2010), Krenn et al. (2017), and Nielsen and Chuang (2010) for more details.
Quantum physics was established to describe nature at the microscopic domain, but many ongoing research endeavors seek answers to what extent the quantum physical laws are relevant to the macroscopic realm. In particular, research efforts in quantum science and quantum technology aim to increase the distance between entangled quantum particles, and search for any possible fundamental restrictions to quantum entanglement, as well as to investigate if it is viable to create a global-scale quantum communication network in the future. Physical experiments on quantum key distribution have been successfully conducted in a long distance with current records of over a hundred kilometers on earth (Krenn et al., 2017) and over a thousand kilometers in space (Yin et al., 2017).
In contrast to classical computation where transistors are used to crunch the ones and zeroes individually, the new quantum resources such as quantum superposition and entanglement can allow quantum computation to manage both one and zero at the same time and do the trick of performing simultaneous calculations. Thus, quantum computers may outperform classical computers for solving certain computational problems. See Browne (2014), Campbell, Terhal and Vuillot (2017), Chong, Franklin and Martonosi (2017), Deutsch (1985), Mohseni et al. (2017), Nielsen and Chuang (2010) and Wang (2012).
Classical computers are constructed from electrical circuits containing wires for carrying information around the circuits and logic gates for executing simple computational tasks. Similarly, quantum computers are built from quantum circuits with quantum gates to carry out quantum computation and process quantum information. In spite of the similarity, quantum computers are built on the unitary evolution of b logical qubits operating on a computational state space of 2 b dimensions, and the new quantum resources make it possible for quantum computers to outperform classical computers for certain tough tasks. Quantum information and quantum computation investigate how to harness the enormous information hidden in the quantum systems and how to make use of the immense potential computational power of quantum particles to perform computation and to process information. Intensive efforts are underway around the world to explore a number of physical systems and fabrication technologies for constructing quantum computers, where viable constructions must meet a set of requirements known as the DiVincenzo criteria (DiVincenzo, 1995). Major systems and technologies include superconducting circuits, ion traps, quantum dots, and other electronic semiconductor circuits, impurity spins, and linear optics (Nielsen and Chuang, 2010). Quantum computers of small scale have been built to demonstrate numerous simple examples of quantum algorithms and protocols. Over the years there are steadily increasing efforts by academics, government labs, large companies, and startups to reach the challenging goal of large scale quantum computation (DiCarlo et al., 2009, Johnson et al., 2011, Mariantoni et al., 2011, Sayrin et al., 2011).
As mentioned above, the physical equipment for the quantum computer fabrication must meet the DiVincenzo criteria including requirements that a quantum system realized qubits has to be well isolated to maintain its quantum properties and at the same time, the quantum system needs to be accessible so that the qubits can be operated to carry out computations and perform output measurements. In reality, there always exists some coupling of a quantum system to its environment, and the coupling leads to quantum decoherence, where decoherence refers to the loss of coherence between the components of the quantum system or quantum superposition from the interaction of the quantum system with its external entities. Therefore, the coupling strength dictates the two opposing requirements stated above. It is very challenging but critical to manage a quantum system of qubits for controlling the coupling strength and rectifying the effects of decoherence in quantum technology. Given the significant difficulties to build large-scale quantum computers with present technology, it is very important to have scalable architectures for building quantum computers with about 100 well-behaved logical qubits in the near future. Such architectures may enable us to demonstrate the so-called quantum (computational) supremacy that is actively pursued by academic labs and companies like Google and IBM, where quantum supremacy refers to any major milestone achievement in the quest for outperforming classical computers on some tough computational tasks (Aaronson and Chen, 2017, Boixo et al., 2018, Harrow and Montanaro, 2017).
The quantum computing approach discussed so far is logic-gate based that has its purpose in developing a quantum version of classic logic gate operations and constructing a universal (or general purpose) quantum computers. Since significant technological difficulties present in the implementation of the gate (or circuit) model for building universal quantum computers, alternative quantum computing architectures, such as adiabatic quantum computing, are actively being explored to build specialpurpose quantum computers for solving specific computational problems, though subjected to different challenges (Aharonov and Ta-Shma, 2003, Aharonov et al., 2008, Albash and Lidar, 2018). Examples of specialpurpose quantum computers include quantum annealers and quantum simulators for solving tough simulation and optimization problems. Next, two Sections 6.2 and 6.3 will present detailed discussions on quantum annealers and quantum simulators, respectively. Quantum annealers mean physical hardware implementations of quantum annealing. Quantum simulators refer to quantum devices utilized for simulating one quantum system by using another more controllable one, with the aim to solve special simulation problems that are computationally too demanding on classical computers.
Quantum annealing may be considered as adiabatic quantum computing that is based on the quantum adiabatic theorem for building special-purpose quantum computers, called quantum annealers, to solve combinatorial optimization problems. Quantum annealing is the quantum analog of classical annealing, with thermodynamics replaced by quantum dynamics. Quantum annealers are physical hardware devices to implement quantum annealing. See Albash andLidar (2018), McGeoch (2014), and Wang, Wu and Zou (2016).
Given an optimization problem, we identify its objective function to be minimized with the energy of a physical system and assign the physical system a temperature that serves as an artificially-introduced control parameter. Classical annealing like simulated annealing takes into account the relative configuration energies and a fictitious time-dependent temperature when exploring the immense search space probabilistically. By decreasing the temperature slowly from a high value to zero, with certain probability we move the system toward the state with the lowest value of the energy and hence arrive at the solution of the optimization problem.
Specifically, consider a classical Ising model characterized by a graph G = (V(G), E(G)), where V(G) and E(G) represent the vertex and edge sets of G, respectively. Each vertex has a random variable whose value is +1 or -1, and each edge corresponds to the coupling (or interaction) between two vertex variables linked by the edge. Define a configuration s to be a set of values assigned to all vertex variables s j , j ∈ V(G), that is, s = {s j , j ∈ V(G)}. Vertices and vertex variables also refer to sites and spins in physics, respectively, where the values +1 and -1 of a spin stand for spin up and spin down, respectively. A case in point is a 2-dimensional lattice considered as a simple graph, with a magnet put at each lattice site pointing either up or down. Denote by b the total number of the lattice sites. At site j = 1, . . . , b, let s j be a binary random variable representing the position of the magnet, where s j = ±1 means that the j th magnet points up or down, respectively. The classical Ising model has the following Hamiltonian:
where (i, j ) denotes the edge between the sites i and j , the first sum takes over all pairs of vertices with edge (i, j ) ∈ E(G), δ ij represents the interaction (or coupling) between sites i and j associated with edge (i, j ) ∈ E(G), and γ j stands for an external magnetic field on vertex j ∈ V(G). We refer to a set of fixed values {δ ij , γ j } as one instance of the Ising model. H c I (s) is also called the energy of the Ising model at configuration s. The probability of a specific configuration s is given by the following Boltzmann distribution:
here T serves as the fundamental temperature of the system with units of energy. The configuration probability P T (s) describes the probability that the physical system is in a state with configuration s in equilibrium.
When using the Ising model to represent a combinatorial optimization problem, the goal is to find a ground state of the Ising model, that is, we need to find a configuration that can minimize the energy function H c I (s). If the Ising model contains b sites, then the configuration space is {-1, +1} b and the total number of possible configurations is equal to 2 b . We note that the system complexity increases exponentially in b (the number of sites), and thus, it is very difficult to find a ground state and solve the minimization problem numerically when b is large. In fact, the search space that grows exponentially prohibits us to solve the minimization problem with deterministic exhaustive search algorithms. Instead, annealing methods such as simulated annealing are employed to search the space probabilistically. To find a configuration with minimal energy, simulated annealing uses Markov chain Monte Carlo (MCMC) methods such as the Metropolitan-Hastings algorithm to generate configuration samples from the Boltzmann distribution P T (s) while decreasing the temperature T slowly. See Bertsimas and Tsitsiklis (19932), Kirkpatrick, Gelatt and Vecchi (1983), and Wang, Wu and Zou (2016).
Quantum annealing utilizes the physical process of a quantum system whose lowest energy, or equivalently, a ground state of the system, renders a solution to the posed optimization problem. It begins by creating a simple quantum system initialized in its ground state and then drives the simple system slowly to the target complex system. The quantum adiabatic theorem (Farhi et al., 2000, 2001, Farhi, Goldstone and Gutmann, 2002, Kadowaki and Nishimori, 1998) implies that, as the system gradually evolves, it likely stays in a ground state, and therefore with some probability, we can find a solution to the original optimization problem by measuring the state of the final system. In other words, by replacing thermal fluctuations in simulated annealing by quantum fluctuations via quantum tunneling, quantum annealing manages to keep the system close to its instantaneous ground state during the quantum annealing evolution, similar to a quasiequilibrium state to be maintained during the time evolution of simulated annealing As in the classical annealing case, graph G is used to describe the quantum Ising model, where the vertex set V(G) stands for the quantum spins, and the edge set E(G) denotes the couplings (or interactions) between two quantum spins. As qubits can be realized by quantum spins, each vertex is occupied by a qubit. Suppose that G has b vertices. The quantum system is described by vector space C d (d = 2 b ), with its quantum state described by a unit vector in C d , and its dynamic evolution governed by the Schrödinger equation (2.1) via a quantum Hamiltonian, which is a Hermitian matrix of size d. The energies of the quantum system are represented by the eigenvalues of the quantum Hamiltonian, and the ground states are given by the eigenvectors corresponding to the smallest eigenvalue. Since quantum mechanics is based on mathematics of matrices with dimensionality equal to d = 2 b (the number of possible configurations), we substitute the classical spins (or bits) in (6.1) with quantum spins (or qubits) to obtain the quantum Hamiltonian. To be specific, define
where σ x j and σ z j are Pauli matrices in x and z axes, respectively. For the quantum system, each classical vertex variable s j = ±1 in (6.1) is replaced by σ z j for the j th quantum spin (or qubit). The two eigenvalues ±1 of the Pauli matrix σ z j correspond to the eigenstates |+1 and |-1 which further represent the spin up state |↑ and spin down state |↓ , respectively. In total, there are 2 b possible quantum configurations formed by selecting b eigenstates from the 2b eigenstates of the Pauli matrices {σ z j } b j =1 and then putting them in the form | ± 1, . . . , ±1 .
We replace s j in the classical Ising Hamiltonian H c I (s) by σ z j to obtain the quantum Hamiltonian, (6.3)
where δ ij stands for the Ising coupling along the edge (i, j ) ∈ E(G), and γ j represents the local field on the vertex j ∈ V(G). Here we adopt the convention in quantum literature that σ z j and σ z i σ z j in (6.3) stand for their tensor products along with identical matrices as follows:
All elements in (6.4) are identity matrices except for the j th element being a Pauli matrix σ z j , and σ z i σ z j in (6.5) is simply an ordinary matrix multiplication of matrices σ z i and σ z j treated as tensor products of b matrices in the sense of (6.4). Each qubit in (6.4) and (6.5) is operated by one matrix, either a Pauli matrix σ z i or an identity matrix I i . The quantum convention singles out the qubits with Pauli matrices for actual actions but leaves out the identity matrices and tensor product signs. To generate quantum Hamiltonian H q I we in fact replace s j in (6.1) by these 2 b × 2 b matrices, with scalars γ j and δ ij unchanged. Furthermore, since each term in (6.3) is a tensor product of b diagonal matrices of size two, quantum Hamiltonian H q I is a 2 b × 2 b diagonal matrix constructed so that its diagonal elements are completely in agreement with all values of classical Hamiltonian H c I in (6.1) corresponding to the 2 b configurations ordered lexicographically.
As a diagonal matrix H q I has eigenvalues equal to its diagonal entries, which in turn are the 2 b possible values of classical Hamiltonian H c I , thus finding the minimal energy of the classical Ising Hamiltonian H c I is equivalent to finding the minimal energy of the quantum Ising Hamiltonian H q I . That is, we need to find a quantum spin configuration with the minimal energy, namely, a ground state of quantum Hamiltonian H q I . Although we have formulated the original optimization problem in the quantum framework, up to now the computational task for solving the optimization problem is still the same as in the classical case.
To carry out quantum annealing for solving the optimization problem, it is essential to engineer a transverse magnetic field that is orthogonal to the Ising axis and obtain the corresponding Hamiltonian in the transverse field. The transverse field represents kinetic energy that does not commute with the potential energy H q I , therefore, it induces transitions between the up and down states of every single spin, and converts the system behavior from classical to quantum. Define the following quantum Hamiltonian governing the transverse magnetic field (6.6)
where again following the quantum convention we denote by σ x j the tensor products of b matrices of size 2 as follows:
Furthermore, σ x j does not commute with σ z j in H q I , and H X is a nondiagonal matrix of size 2 b that does not commute with diagonal matrix H q I . We note that Pauli matrix σ x j has two eigenvalues +1 and -1 associated with the eigenvectors |u j,+1 = (1, 1) and |u j,-1 = (1, -1) . As a result, the eigenvector corresponds to the smallest eigenvalue of
We start the quantum annealing procedure with a quantum system that is driven by the transverse magnetic field H X and initialized in its ground state |u + . The system then slowly moves from the initial Hamiltonian H X to its final target Hamiltonian H q I . During the Hamiltonian evolution, according to the adiabatic quantum theorem, the system has a tendency to stay in the ground states of the instantaneous Hamiltonian via quantum tunneling (Farhi et al., 2000, 2001, Farhi, Goldstone and Gutmann, 2002, McGeoch, 2014). At the end of the annealing procedure, if the quantum system stays in a ground state of the final Hamiltonian H q I , we can measure the quantum system to obtain a solution of the optimization problem. In specific, quantum annealing is accomplished by the following instantaneous Hamiltonian for the Ising model in the transverse field:
where A(t) and B(t) are smooth functions that depend on time t and control the annealing schedules, and t f is the total annealing time. To drive the system from H X to H q I , we take A(t f ) = B(0) = 0 where A(t) is decreasing and B(t) is increasing. It follows that when t = 0,
Since A(0) and B(t f ) are known scalars, H D (t) has the same eigenvectors as H X at the initial time t = 0 and as H q I at the final time t = t f , where the corresponding eigenvalues differ by factors of A(0) and B(t f ), respectively. Therefore, H D (t) moves the system from H X initialized in its ground state to the final target H q I . When the control functions A(t) and B(t) are chosen appropriately, the quantum adiabatic theorem indicates that the annealing procedure driven by (6.8) will have a sufficiently high probability in finding the global minimum of H c I (s) and solving the minimization problem at the final annealing time t f . See Brooke, Bitko and Aeppli (1999) While classical annealing depends on thermal fluctuations to drive the system to hop from state to state over intermediate energy barriers and find a desired lowestenergy state, quantum annealing substitutes thermal hopping by quantum-mechanical fluctuations to search for a ground state. We realize the quantum fluctuations in quantum annealing by quantum tunneling that enables the annealing process to explore different states by crossing directly through energy barriers, rather than climbing over them thermally. Here quantum tunneling refers to the quantum phenomenon where particles tunnel through a barrier in the situation that is classically infeasible. We cannot directly observe the tunneling process nor use classical physics to explain it satisfactorily. Quantum tunneling is generally described by the Heisenberg uncertainty principle and the wave-particle duality of matter in quantum physics (Crosson and Harrow, 2016, Das and Chakrabarti, 2005, 2008, Denchev et al., 2016, Wang, Wu and Zou, 2016).
Quantum annealing devices are actively pursued by a number of academic labs and companies such as Google and D-Wave Systems, with uncertain quantum speedup. In particular, the D-Wave quantum computer is a commercially available hardware device that is designed and built to physically implement quantum annealing. It is an analog computing device based on superconducting qubits to process quantum annealing and solve certain combinatorial optimization problems. Also although it is extremely difficult to simulate quantum annealing by classical computers, classical Markov chain Monte Carlo simulations have been developed to approximate quantum annealing by path-integral formulation and mean field approximation. See Albash et al. (2015), Boixo et al. (2014Boixo et al. ( , 2016Boixo et al. ( , 2018)), Brady and van Dam (2016), Rønnow et al. (2014), and Wang, Wu and Zou (2016) for more discussions.
Quantum simulation is to intentionally and artificially mimic interacting quantum systems, which are hard to access and analyze, by employing other precisely controllable quantum systems that are easy to manipulate and investigate. Since the dimensionality of the space describing a quantum system scales exponentially with the system size, the classical simulation of quantum systems demands exponentially increasing resources. Likewise, it takes exponentially large resources to solve certain classical optimization problems particularly the NP-hard problems, such as finding the ground-state energy of a classical spin glass and solving the traveling salesman's problem. Quantum simulation may provide scientific means to simulate complex biological, chemical or physical systems in order to study and understand certain scientific phenomena and solve the related hard computational problems. Experimental platforms for quantum simulation consist of ultra-cold atomic and molecular quantum gases, ultra-cold trapped ions, polariton condensates in semiconductor nanostructures, circuit-based cavity quantum electrodynamics, arrays of quantum dots, photonic quantum technology, and superconducting qubits with commercial applications in quantum annealers (Aspuru-Guzik and Walther, 2012, Blatt and Roos, 2012, Bloch, Dalibard and Nascimbene, 2012, Boghosian and Taylor, 1998, Houck, Türeci and Koch, 2012, Jané et al., 2003, Johnson et al., 2011, Nielsen and Chuang, 2010, Wang, Wu and Zou, 2016).
The essential of quantum simulation is to understand the dynamic evolution of a quantum system governed by the Schrodinger equation (2.1). That is, quantum simulation needs to describe and solve the Schrodinger equation (2.1) by either digital quantum computers or analog quantum machines. The solution of (2.1) has expression (6.9)
and we need to evaluate e -iHt numerically. It is extremely difficult to exponentiate the Hamiltonian H because its size increases exponentially in the system size. Common numerical approach often uses the first-order linear expansion 1 -iHδ to approximate e -iH(t+δ)e -iHt , which often yields unsatisfactory numerical solutions. Mathematically, quantum simulation is to explore whether higher order approximations are available to provide efficient methods for the evaluation of e -iHt . For example, consider a system with α particles in a d-dimensional space that has the following Hamiltonian:
where L is a polynomial in α + d, and each H acts on a small subsystem of finite size free from α and d. Note that it is easy to evaluate e -iH δ numerically, but very difficult to compute e -iHδ . Because H and
By the Trotter formula (Proposition 3.1 in Wang ( 2011)), we obtain
Thus, we obtain a second order approximation of e -iHδ by the first term on the right-hand side of (6.10), which only needs us to evaluate each e -iH δ , = 1, . . . , L.
Introduced by Feynman (1981/82), quantum simulation itself has been developed into a core field within quantum computation. A quantum simulator can be any physical quantum system precisely prepared or manipulated in a way targeting at studying interesting features of an interacting complex quantum system, which is computationally intractable or difficult to simulate on classical computers. A quantum simulator can be a digital quantum simulator so that the controllable quantum system is implemented on a universal quantum computer, or an analog quantum simulator so that the controllable quantum system is a quantum physical device to reconstruct the time evolution of an interacting quantum system under precisely controlled conditions. Like universal quantum computers, digital quantum simulators face significant challenges in scaling architectures. However, analog quantum simulators can be addressed and experimented in a relatively large scale with currently available technology, and thus may provide new tools for us to investigate interacting many-particle quantum systems and attack optimization problems beyond the reach of classical computers. See Childs et al. (2018), Jiang et al. (2017), Kassal et al. (2008Kassal et al. ( , 2011)), Lanyon et al. (2010), Nielsen and Chuang (2010), and Wang (2011, 2012).
It is likely that the first practical application of quantum computation is quantum simulation since even moderate quantum simulation devices have the potential to carry out simulations infeasible by classical computers. For example, in quantum chemistry, molecular energies can be computed by digital quantum simulation devices of size 100 to 150 logical qubits with excellent precision and accuracy that considerably exceed the limitations of classical computers. In particular, in the near to medium term, analog quantum simulators may offer us a novel tool to study complicated quantum systems and hard optimization problems that are unreachable by classical computers. Again a computational advantage of quantum simulators over classical ones may clearly demonstrate quantum supremacy (given in Section 6.1) in realistic applications. In the long run, the importance of quantum simulation may lie in the applications of large-scale quantum simulations to solve fundamental problems in physics, materials science and quantum chemistry (Abrams and Lloyd, 1997, Aspuru-Guzik et al., 2005, Boghosian and Taylor, 1998, Cirac and Zoller, 2012, Kassal et al., 2011, Lloyd, 1996).
Quantum algorithms are algorithms that run on quantum computation models, such as the most commonly used quantum gate or circuit model, by taking input qubits and producing output measurements for the solutions of specific computational tasks. While a classical algorithm takes a step-by-step procedure to solve a given problem on a classical computer, a quantum algorithm is a stepby-step problem-solving procedure, with each step performed on a quantum computer. We note that all classical algorithms can be in principle executed on a quantum computer, all problems solvable on a quantum computer are solvable on a classical computer, and problems undecidable by classical computers remain undecidable on quantum computers. However, quantum algorithms are essentially different from their classical counterparts in the sense of being genuine quantum, that is, quantum gate operations are reversible unitary transformations, and quantum algorithms utilize fundamental quantum properties such as quantum superposition and quantum entanglement. We refer to quantum algorithms as the algorithms that are inherently quantum for achieving faster speed than classical algorithms in solving some tough problems. It should be pointed out that while quantum algorithms cannot be worse than classical algorithms, we should not expect quantum algorithms to yield advantage for every single problem; in fact, they usually do not. As a matter of fact, quantum computers augment, but do not replace classical computers. A continual challenge in quantum science is to invent new quantum algorithms to speed up the best classical algorithms. For example, quantum superposition indicates that we can potentially carry out exponentially many computations in parallel, but it is tricky to extract the solution from such an exponential superposition to achieve some quantum speedup, as observing the qubit system destroys its state. This is where we need clever designs of quantum software. Common techniques employed to create quantum algorithms include quantum Fourier transform, phase estimation, amplitude amplification, quantum walk, quantum annealing and quantum simulation. The widely known quantum algorithms include Shor's factoring algorithm and Grover's search algorithm, which are, respectively, exponentially faster and quadratically faster than the best known and best classical algorithms for the same tasks. Many other algorithms were created for a wide range of problems and applications such as searching, sorting, counting, sampling, simulation, and optimization. See Montanaro (2016), Nielsen and Chuang (2010) and Wang (2012) for more discussions.
As a case in point, we consider quantum computation for the Grover and parity problems. Let f (x) be a function defined on the integers from 1 to N and taking the values ±1. Define the parity of f (x) by
The parity of f (x) can be either +1 or -1, and always depends on the values of f (x) at all N points. It has been proved that with no further information about f (x), both classical and quantum algorithms have O(N) timecomplexity to determine its parity, and thus quantum computers cannot outperform classical computers for the parity problem. For the Grover problem, there is a further information that f (x) is either identically equal to 1 or it is 1 for N -1 of the x's and equal to -1 at one unknown value of x. For such f (x), its parity indicates its type, and the computational task for the Grover problem is to determine the type of f (x) and search for the unknown value of x (if it exists). With the additional information about f (x), the best classical and quantum algorithms for the Grover problem have complexity O(N) and O( √ N), respectively, and thus there is an optimal √ N quantum speedup. It is interesting to note that, although there is a quadratic quantum speedup for the Grover problem, the parity problem has no quantum speedup (see Farhi et al. (1998) and Grover (1997)). This example indicates that neither classical nor quantum computers are expected to be best for all computational tasks.
Quantum machine learning extends classical machine learning to the quantum realm. Classical machine learning and statistical learning often refer to an array of statistical approaches to analyzing data, with the goal of inferring the future behavior of target variables (such as the function relationships of variables and their dynamic processes) from training data. The learning procedure involves inference, which addresses how statistically efficient we can learn the functions or processes from given data, and computation, which handles how much computational resources are required to perform a learning task and how fast algorithms can be designed to carry out the learning task. The learning objective is to search for a model that fits well to training data but more importantly enjoys good generalization capability, which refers to the property of the learned model with good prediction performance on new observations. Common learning approaches rely on regularization-based methods leverage on optimization techniques to solve learning problems. Quantum learning theory investigates how quantum resources can affect the learning efficiency. The theory indicates that it is possible for quantum learners to achieve higher efficiency such as better generalization errors in learning difficult functions for some particular learning models. However, the major advantages that quantum mechanics can provide is largely in terms of computation. In other words, quantum machine learning can offer advantages over its classical counterpart in terms of computational complexity. Therefore, it is reasonable to expect quantum computers to be faster than classical computers for solving some machine learning problems, but it is important and challenging to explore quantum softwares that enable quantum machine learning to realize such quantum speedups. Recent development indeed shows a class of quantum machine learning algorithms exhibit some quantum speedups. For example, from a computational perspective, solving linear equation systems is almost ubiquitous in machine learning, and finding a learning solution usually comprises a sequence of standard linear algebra operations such as matrix multiplication and inversion. Quantum linear algebra algorithms offer quantum speedups over their classical analogs. As a case in point, quantum basic linear algebra subroutines (BLAS), which include finding eigenvectors and eigenvalues and solving linear equations, exhibit exponential quantum speedups over their best known classical counterparts. The quantum BLAS renders quantum speedups for an array of data analysis and machine learning algorithms including linear algebra operation, gradient descent, Newton's method, linear programing, semidefinite and quadratic programming, topological analysis, least-squares, nearest-neighbor, support vector machines, clustering, and principal component analysis (PCA). Also special-purpose quantum computers, such as quantum annealers and programmable quantum optical arrays, bear architectures well suited to quantum optimization and deep learning particularly quantum deep learning with Boltzmann machines. More discussions can be found in Adachi and Henderson (2015), Amin et al. (2018), Arodz and Saeedi (2019), Arunachalam and de Wolf (2018), Benedetti et al. (2016), Biamonte et al. (2017), Brandão et al. (2019), Ciliberto et al. (2018), Dunjko, Taylor and Briegel (2016), Dunjko and Briegel (2018), Jordan (2005), Lloyd, Mohseni and Rebentrost (2014), O 'Gorman et al. (2015), Rebentrost, Mohseni and Lloyd (2014), Salakhutdinov and Hinton (2009), Shenvi, Kempe and Whaley (2003), Svore, Hastings and Freedman (2014), Wiebe, Kapoor andSvore (2016, 2015), Wiebe andGranade (2016), andWittek (2014). Below we provide short illustrations for some selected topics in quantum machine learning. 6.5.1 Bayesian quantum phase estimation. Quantum phase estimation is the key to achieve quantum speedups in many well-known quantum algorithms (Nielsen andChuang, 2010, Wang, 2012). Suppose that a unitary operator U has an eigenvector |ξ with corresponding eigenvalue e √ -12πϕ , ϕ ∈ (0, 1). We do not know the phase ϕ of the eigenvalue, and our goal is to find ϕ based on a set of experiments performed on a quantum circuit. The experiments involve preparing the state |ξ and performing measurement on U multiple times at some angle, where the angle θ and the number M of times are randomly chosen. The Bayesian phase estimation procedure is to perform a series of random measurements and then solve a classical reconstruction problem using Bayesian inference. Given ϕ, and randomly chosen M and θ , the conditional probabilities of obtaining measurement outcomes 1 and 0 are as follows:
For a given measurement sequence, with a uniform priori distribution on ϕ, we obtain the posterior distribution of ϕ. We may repeat this process for a series of experiments, and the Bayesian phase estimation approach provides posterior distributions over the phase ϕ, which offer estimates of the true eigenvalue and the algorithm's uncertainty in that value. More details can be found in Paesani et al. (2017), Svore, Hastings and Freedman (2014) and Wiebe and Granade (2016). More generally, Hamiltonian learning has been developed to infer quantum Hamiltonians via Bayesian inference for understanding quantum dynamics. See Granade et al. (2012), Wiebe et al. (2014) and Wiebe, Granade and Cory (2015) for details. 6.5.2 Quantum principal component analysis. PCA depends on the eigendecomposition of a covariance matrix, which, in the quantum context, can be converted into simulating a Hamiltonian in quantum simulation described in Section 6.3. Suppose that data are observed in the form of vectors v j in a d-dimensional vector space, j = 1, . . . , n. Assume that v j have zero mean and finite variance. Without loss of generality we further assume v j are unit vectors (otherwise we may normalize each to be a unit vector and then use their norms to adjust selection probability below). Quantum principal component analysis randomly selects a vector from v 1 , . . . , v n and then maps each selected vector v j into a pure quantum state |v j . The random encoding procedure yields a quantum state with b = log 2 d qubits and a density matrix ρ = 1 n n j =1 |v j v j |, which is equal to the sample covariance matrix up to an overall factor.
We first describe a quantum technique called density matrix exponentiation. Using a simple trick with the partial trace over the first variable and the swap operator S, we get
where tr 1 denotes the partial trace over the first variable, and swap operator S has a matrix representation
S is a sparse matrix of size d 2 , which can be clearly seen from the following explicit expression for the case of d = 2:
Thus, for sparse S, e - √ -1S t can be performed efficiently. As a result, simply performing infinitesimal swap operations on ρ ⊗ π allows us to simulate the unitary time evolution e - √ -1ρ t πe
and thus construct the unitary operator e - √ -1ρt via the Schrödinger equation (2.3) in the density matrix form, where we have used the Baker-Campbell-Hausdorff formula that for matrices A and B, -1ρt comprises the preparation of an environment state π and the application of the global swap operator S to the combined system and environment state ρ ⊗ π followed by partial trace tr 1 to discard the environmental degrees of freedom.
Applying the density matrix exponentiation procedure to ρ we construct e - √ -1 ρ t . Then we utilize the quantum phase estimation algorithm to find eigenvalues and eigenvectors of the density matrix ρ, which renders the principle components. The quantum PCA procedure has computational complexity O(log 2 d) with potential to be exponentially faster than classical PCA. See Lloyd, Mohseni and Rebentrost (2014) and Rebentrost, Mohseni and Lloyd (2014) for more details. 6.5.3 Quantum support vector machines. Consider the binary classification problem where we have training data (x 1 , y 1 ), . . . , (x n , y n ), with x i = (x ij ) ∈ R p and y i ∈ {-1, 1}, and the goal is to use the training data to learn how to predict classes y for feature vectors x. Define a hyperplane f (x) = x τ β to induce a classification rule sign(x τ β), where β = (β j ) ∈ R p is a parameter. We need to find a suitable value for parameter β based on the training data. The training of the sparse support vector machines model with the hinge loss is often converted into solving the following minimization problem:
where λ > 0 is a tuning parameter. The nonlinear unconstrained optimization problem can be transformed to an equivalent constrained linear programming problem with n + 2p nonnegative variables and n linear inequality constraints, arg min
The support vector machines solution is β j = β + jβ - j . While classical algorithms for solving such linear programming problems have asymptotic computational complexity Õ(mn) where m = n + 2p, quantum algorithms have been proposed recently for the optimization problems with time complexity Õ( √ mn) or even Õ( √ m + √ n), which offers potential for a quadratic speedup compared to the classical algorithms. Furthermore, for the least squares support vector machines (with the minimization problem: min β 1 2 β 2 + λ n i=1 ξ 2 i subject to ξ i ≥ 0, y i x τ i β = 1ξ i , i = 1, . . . , n), quantum algorithms offer an exponential speedup over classical algorithms. Also nonlinear classification rules can be derived by using kernels. For a polynomial kernel matrix K, we normalize it by its trace to obtain K = K/ tr(K). Using density matrix exponentiation in (6.11) to construct e - √ -1 Kt and then applying quantum phase estimation to e - √ -1 Kt we perform eigen-analysis and matrix inversion for K and thus efficiently solve the optimization problem for finding the support vector machines solution. See Arodz and Saeedi (2019) and Rebentrost, Mohseni and Lloyd (2014) for more details. 6.5.4 Quantum deep learning with Boltzmann machines. Deep learning has been widely explored in quantum machine learning. The literature has been mainly concentrated on speeding up the training of classical models and on developing relatively less matured quantum neural networks, which refer to that all their component parts, ranging from the single neurons to the training algorithms, are carried out on quantum computers. Boltzmann machines are stochastic models that enable to produce new data based on prior observations, which are called generative models in deep learning. Because of their intrinsic link to the Ising model, Boltzmann machines are especially suitable for learning exploration from a quantum viewpoint.
As a classical machine learning technique, Boltzmann machines serve as the basis of powerful deep learning models. A Boltzmann machine usually consists of visible and hidden binary units that are jointly denoted by s i , i = 1, . . . , N, where N is the total number of units. We use the notation s i = (s v , s h ) to distinguish the visible and hidden variables with index v for visible variables and h for hiddens, and reserve vector notations v, h, and s = (v, h) for representing random vectors corresponding to visible, hidden, and combined units, respectively. A classical Ising model is employed to describe the variables s j . As in Section 6.2, the Hamiltonian (or energy function) of the Ising model is H c I ≡ H c I (s) defined in (6.1), where now we take N = b, and γ j and δ ij are considered as model parameters to be tuned during the training in machine learning. In equilibrium, the probability of observing a state v of the visible variables is described by the Boltzmann distribution summed over all hidden variables, (6.12)
which is called the marginal distribution of the visible random vector v. We aim to find parameters θ = {γ j , δ ij } in the Hamiltonian H c I such that P v becomes as close as possible to the corresponding empirical distribution defined by the training data. The common classical approaches to finding the parameters are to maximize likelihoods, and the maximization is often achieved via some combination of gradient descent and sampling. Research has demonstrated that sampling from Boltzmann machines and calculating their likelihoods are computationally very difficult, and MCMC simulations are often employed as standard techniques to overcome the hard computational tasks, though MCMC can be be very costly or even impossible for models with a large number of neurons. Training with quantum resources can be very helpful in reducing the training cost and offering some quantum speedup. Thus, it makes quantum deep learning more feasible or preferable than the classical approach. Quantum techniques, which include quantum linear algebra, quantum sampling, and quantum annealers, have been developed to train the classical Boltzmann machines. Special-purpose quantum computers such as quantum annealers and programmable photonic circuits are very suitable for training Boltzmann machines. In particular the D-Wave devices, quantum annealers with tunable transverse Ising models, have been applied to encode deep quantum learning protocols on over thousands of spins. See Adachi and Henderson (2015), Benedetti et al. (2016) and Wiebe, Kapoor and Svore (2016) for details.
Quantum resources can give new, fundamentally quantum, models for deep learning. Quantum Boltzmann machines are introduced to cross-breed between training artificial neural networks and fully quantum neural networks. They induce an array of quantum effects such as quantum tunneling. Unlike classical Boltzmann machines, quantum Boltzmann machines can yield quantum states as outputs, and thus deep quantum networks can learn to produce quantum states for representing a broad range of systems, which is beyond the capability of classical machine learning. Quantum Boltzmann machines are defined by quantum Ising models in transverse fields. Similar to the classical case, as described in Section 6.2, the quantum Hamiltonian of the quantum Ising model is H q I given by (6.3), where again we take N = b, and γ j and δ ij are model parameters to be tuned during the training. Note that H q I is a 2 N × 2 N diagonal matrix, which is in contrast to vectors with dimensionality equal to N , the number of variables, used in classical machine learning.
Denote by |v, h the eigenstates of Hamiltonian H q I , where again v and h stand for vectors of visible and hidden variables, respectively. For diagonal Hamiltonian H q I , e -H q I is also a diagonal matrix with its 2 N diagonal elements being e -H c I corresponding to all 2 N configurations. Define its partition function Z = tr[e -H q I ] and density matrix (6.13) ρ = Z -1 e -H q I .
Then the diagonal elements of ρ are equal to the Boltzmann probabilities of all 2 N configurations. Given a state |v of the visible variables, we get the following marginal Boltzmann probability P v by tracing over the hidden variables:
(6.14)
where v is a diagonal matrix whose diagonal elements are equal to 1 if the visibles are in state v, and 0 otherwise. The use of v is to limit the trace only to diagonal elements corresponding to the visible variables which are in state v. It is easy to see that definitions (6.12) and (6.14) are identical for the diagonal Hamiltonian and density matrix, but (6.14) is still valid for the nondiagonal case.
To add a transverse field to the quantum Hamiltonian H q I , as described in Section 6.2, we need nondiagonal matrices σ x j described in (6.7) to obtain the transverse field Ising Hamiltonian as follows:
where besides the original parameters γ j and δ ij , we have additional model parameters i . A quantum Boltzmann machine is defined by the quantum Boltzmann distribution of the transverse field Ising Hamiltonian H q . As H q is a nondiagonal matrix, we may express its eigenvectors by superpositions in the computation basis composed of the classical states |v, h , and the corresponding quantum Boltzmann machine has quantum probability distribution with nondiagonal density matrix ρ given by (6.13) with H q I replaced by H q as well as the marginal Boltzmann probability distribution P v defined in (6.14). Performing each measurement on the states of the qubits in the σ zbasis we obtain the outcome ±1, and thus the measurement output for the visible variables follows the marginal probability distribution P v given by (6.14).
Our learning goal is to train the quantum Boltzmann machine and find the model parameters θ = { i , γ j , δ ij } in the Hamiltonian H q such that the probability distribution P v gets as near as possible to the corresponding empirical distribution determined by the input data. The method of finding the parameters is to maximize some bounds on relevant likelihoods, due to the likelihood intractability for quantum Boltzmann machines. Treating as a class of recurrent quantum neural networks, quantum Boltzmann machines can be trained for machine learning tasks such as discriminative and generative learning, as well as quantum state tomography and quantum annealing. More details can be found in Amin et al. (2018) and Kieferova and Wiebe (2016).
6.5.5 Quantum machine learning for quantum data. In general quantum machine learning is particularly suitable for quantum data which are the actual output states generated by quantum systems and processes, and the speciality of quantum data analysis is the capability of using quantum simulators to probe quantum dynamics. We may apply quantum machine learning algorithms like quantum PCA and quantum Boltzmann machines to quantum data (such as quantum states of light and matter) for exploiting the quantum states and uncovering their hidden features and patterns. The obtained analysis results in quantum modes are often much more efficient and more enlightening than the the classical analysis of data drawing from quantum systems. See Granade et al. (2012) 2011) for details. 6.5.7 Quantum machine learning with noise. Noise can be potentially beneficial for solving machine learning problems. Research has shown in the classical case that noise may play a positive role in perturbing gradients for jumping out local optima and improving generalization performance. It becomes promising to analyze noisy learning problems from a quantum perspective and particularly exploit advantageously the effects of noise in quantum machine learning. For example, we may study whether the kinds of noise occurred in quantum systems have similar distributional and structural behaviors to those usually seen in classical settings, and if they can play a beneficial role in quantum machine learning as in the classical case. See Cross, Smith and Smolin (2015) and Grilo, Kerenidis and Zijlstra (2018) for details.
Determining a quantum speedup depends on how we define the quantum speedup notation. One approach is to take a formal computational complexity perspective based on rigorous mathematical proofs. Another realistic perspective is based on what can be achieved with feasible finite size devices and requires sound statistical evidence to confirm a scaling advantage over certain finite range of problem sizes. For example, it has already been rigorously proved in terms of computational complexity that quantum algorithms like Grover's search algorithm and Shor's factoring algorithm offer speedups over known classical algorithms. Unfortunately, such rigorous proofs are often not available for most cases, and even available, many existing quantum algorithms fail to provide reference for any specific implementation such as the exact number of qubits needed to implement them; in fact, they often cannot be implemented on about 100 qubit platforms available in the near to medium term. We need to resort to the second perspective, and detecting a scaling advantage of quantum computing over classical computing would hinge on the so-called benchmarking problem, namely, the existence of a quantum computer performed on well designed computational tasks with sound statistical analysis of computing experiments and resulting data. Such advantages may include improved computational speed, accuracy, and sampling for classically inaccessible systems. Quantum algorithms and computational problems are created for these platforms with a limited number of qubits where classical computation is impossible. The mission involving both hardware and software along with statistical analysis aims at demonstrating the quantum computational supremacy given in Section 6.1. Quantum scientists are building quantum computers of 50 to 100 qubits to demonstrate quantum supremacy. For example, the Google quantum AI group has achieved quantum supremacy by building a quantum processor named 'Sycamore' of 54 superconducting qubits to sample from the output distributions of random quantum circuits, while it is hard for current supercomputers to handle the sampling problem beyond around 50 qubits. See Aaronson and Chen (2017), Arute et al. (2019), Boixo et al. (2018), Bouland et al. (2018), Bravyi, Gosset andKönig (2018), Harrow andMontanaro (2017), Lund, Bremner andRalph (2017), Markov et al. (2018), Neill et al. (2018) and Rønnow et al. (2014). Below we briefly describe boson sampling and random quantum circuits. 6.6.1 Boson sampling. Boson sampling is a quantum computation model where n identical bosons pass through a network of passive optical elements (beamsplitters and phase-shifters) and then the locations of the bosons are detected. Quantum supremacy can be demonstrated by implementing boson sampling with a medium size network. A network system with 50 photons (qubits) and 2500 paths is currently intractable for classical computers. To implement boson sampling all required physical devices are single-photon sources, beamsplitters, phase-shifters and photon-detectors. The physical implementation of the scheme encounters a myriad of technicalities such as synchronization of pulses, mode-matching, quickly controllable delay lines, tunable beamsplitters and phase-shifters, single-photon sources, and accurate, fast, single photon detectors.
To define the boson sampling model, we adopt a statistical approach based on the permanents of the submatrices of a unitary matrix, which requires minimal quantum physics and quantum computation terminology. For a n × n matrix A = (a ij ), we define its permanent by
where the sum is over all permutations π of 1, 2, . . . , n. Consider the quantum system involving n identical photons and m modes, where we may loosely interpret 'mode' as the location of a photon, and we are only interested in the case of m ≥ n. The quantum system has computational basis states of the form |s = |s 1 , s 2 , . . . , s m , where s i indicates the number of photons in the ith mode. Denote the set corresponding to all the computational basis states by m,n = s = (s 1 , s 2 , . . . , s m ) :
It is easy to see that the total number of elements in m,n is equal to M = m+n-1 n . For a given m × m unitary matrix U and each s ∈ m,n , we obtain matrix U s from U by keeping its first n columns and repeating s j times its j th row. Define a discrete probability distribution on m,n as follows:
It can be shown that Pr(s) is a well-defined probability distribution on m,n and corresponds to the quantum system with n photons, m modes and an optical network whose action is determined by the unitary matrix U. Boson sampling refers to sampling from distribution Pr(s). As classical computers cannot handle the sampling problem even with moderate size, we may demonstrate the quantum supremacy by successfully implementing boson sampling of reasonable size on quantum computing devices. More details can be found in Harrow and Montanaro (2017) and Lund, Bremner and Ralph (2017).
6.6.2 Random quantum circuits. Random quantum circuits are created in a specific way so that when they are generated with enough 'complexity', even the most powerful classical supercomputer cannot directly simulate the generated quantum circuits. However, quantum computers can sample from the output distributions corresponding to the obtained quantum circuits. Here a quantum circuit is a sequence of d clock cycles of one-and two-qubit gates with gates applied to different qubits in the same cycle. The number d of cycles is called the depth of the circuit. We say a random quantum circuit has enough 'complexity', if both its qubits and depth are large enough. If the gates to be applied are chosen from a universal quantum gate set, the unitary matrix U of the circuit is a random matrix whose distribution converges to the Haar measure on the collection of unitary matrices when the depth of the circuit goes to infinity. Specifically when a quantum circuit contains n qubits, with 2 n computational basis states |x = |x 1 x 2 • • • x n , x i ∈ {0, 1}, a quantum state |ψ d produced by the random quantum circuit is a linear combination of the computational basis and thus has 2 n amplitudes, each with real and imaginary parts. Therefore there are 2 n+1 parameters in each quantum state. As the unitary matrix U of the random quantum circuit converges in distribution to the Haar measure, the random vector of the amplitude parameters asymptotically follows a uniform distribution on the unit sphere. Define the output distribution of the random quantum circuit to be measurement probability p(x) = | x|ψ d | 2 . As the depth d of the random quantum circuit goes to infinity, p(x) approaches the Porter-Thomas distribution. The Google research group is working on finding ways to generate random quantum circuits so that their output distributions quickly converge to the Porter-Thomas distribution. Based on the asymptotic distribution, we may develop a statistical approach to determine if a sample is generated from the theoretical output distribution of a desired random quantum circuit. Since it is difficult for classical supercomputers to deal with the sampling problem beyond around 50 qubits at the present time, the Google quantum scientists have designed a quantum processor named 'Sycamore' of 54 transmon qubits and implemented quantum random circuits in a two dimensional lattice to demonstrate quantum supremacy. See Arute et al. (2019), Boixo et al. (2018), andNeill et al. (2018) for more details.
Measurement is at the heart of science, technology, industry, and commerce. We need measurements and metrological standards to quantitatively assess scientific phenomena and technological progress, and gauge the exchange of goods and service including information. Measurement devices are physical apparatuses whose functions and accuracy are governed by the laws of physics, and transformative improvements in measurement technologies often follow the utilization of a new physical law. Quantum metrology (or quantum sensing) is to exploit the strange laws of quantum physics to build new and better sensors and measuring devices. Fueling with quantum laws, quantum metrology may lead to a game-changing shift in scientific studies, technological progress, as well as commerce and industry developments.
The basic concept of quantum metrology is that a probe device interacts with an appropriate system to learn the properties of the system, where the interaction alters the state of the probe, and measurements of the probe uncover the characteristic parameters of the system. For quantum sensing, the probe is usually prepared in one certain quantum state, its encounter with the system normally changes its state with both beneficial and adversarial effects in the sense that it not only responds to the parameters of interest but also decoheres the probe (which means there is loss of information from the probe into the system due to quantum decoherence, illustrated in Section 6.1). Then appropriately devised measurements can ascertain in what way and to what extent such encounter has changed the state of the probe, which enables quantum sensing to evaluate the system parameters. Quantum sensing promises to develop high-resolution and highly sensitive measurement techniques that will provide better precision than the same measurement performed under a classical framework. They include quantum sensors, quantum clocks, and quantum imaging. The applications range from the sub-nano to the galactic scale, while some are in fact close to commercial use. The potential impact of quantum metrology is far-reaching. An array of distinct platforms allow quantum-enhanced measurement of time, space, rotation, as well as gravitational, electrical and magnetic fields. The technologies are promising to make fundamental changes in a wide range of fields such as physics, chemistry, biology, medicine or data storage and processing.
There is a strong link between quantum metrology and quantum information. For example, both quantum information and quantum sensing rely on the same quantum properties such as entanglement, in particular, high level of multipartite entanglement, to achieve better performance than their classical counterparts. See Degen, Reinhard and Cappellaro (2017), Kruse et al. (2016), andPezzè et al. (2018) for more details.
Quantum tomography plays an important role in quantum sensing. Quantum state tomography refers to reconstruction of a quantum state based on measurements performed on the quantum state. Statistically it is a density matrix estimation problem based on quantum measurements. Common quantum measurements are on observable M, which is defined as a Hermitian matrix on C d . For example, the Pauli matrices as observables are widely employed to perform quantum measurements in quantum science and quantum technology, and we may represent many density matrices through Pauli matrices. Suppose that the observable M has the following spectral decomposition:
where λ a are r different real eigenvalues of M, and Q a are projections onto the eigen-spaces corresponding to λ a . Given a quantum system prepared in state ρ, we use a probability space ( , F, P ) to define measurement outcomes when performing measurements on the observable M. Let R be the measurement outcome of M. The theory of quantum physics indicates that R is a random variable on ( , F, P ) which takes values in {λ 1 , λ 2 , . . . , λ r }, and has probability distribution P (R = λ a ) = tr(Q a ρ), (7.2) a = 1, 2, . . . , r, E(R) = tr(Mρ).
Quantum state tomography is to reconstruct ρ from independent and identically distributed measurement outcomes R 1 , . . . , R n . See Artiles, Gill and Guţȃ (2005), Cai et al. ( 2016), Malley and Hornstein (1993) and Wang and Xu (2015). Designing and controlling quantum systems are complex and challenging in the development of quantum science and quantum technology. Statistical methods provide powerful tools for the study of quantum design and quantum control. Examples of successful applications include quantum gate constructions with high fidelity precision in quantum computation and quantum information, extraction of theoretical insights about quantum states in condensed matter, and quantum control procedures in optimizing adaptive quantum metrology. Like quantum phase estimation and quantum tomography, many quantum problems are in essence statistical problems, and it is our firm belief that statistics and data science have great potential to make significant improvement in quantum metrology.
Quantum science and quantum technology gain enormous attention in multiple frontiers of many scientific fields. Quantum computation can give rise to an exponential speedup over classical counterpart for tackling certain computational tasks, quantum information can bring about exponential savings in information transmission for handling computational and communication jobs, and quantum communication can offer more secure cryptosystems than classical analogue for solving communication problems. Some of the quantum protocols are already in practical implementation, such as quantumfingerprinting, quantum key distribution, quantum annealing, and quantum simulation. This paper reviews quantum science and quantum technology from a statistical perspective. We introduce concepts like key quantum properties and qubits. We present quantum communication and quantum information, illustrate quantum computation and quantum metrology, and discuss major quantum technologies associated with them. We show the advantages of quantum techniques over the available classical counterparts.
As statistics and machine learning nowadays heavily involve computation, it is natural to expect quantum computation to play a major role in data science. Indeed, quantum computation and quantum simulation may have tremendous potential to revolutionize computational statistics and data science. On the other hand, there is great demand in studying statistical issues for theoretical research and experimental work in quantum science and quantum technology. As quantum phenomena are intrinsically stochastic, and data collected in quantum experiments become more and more complex, we need to develop sophisticated statistical methods for enhancing data analysis and improving understanding of quantum events (Paesani et al., 2017, Wang, 2011, 2012, 2013, Wang, Wu and Zou, 2016, Wiebe et al., 2014, Wiebe, Kapoor and Svore, 2016). A great deal of current work is taken place on creating new protocols and developing novel approaches to certifying quantum devices such as testing and assessing their quantum performances. Clearly, such certification requires efficient and scalable statistical methods for calibrating and validating quantum properties. Moreover, certification needs to take into account commercial considerations for compliance with industry standards by working together with industry, academics, national labs, and government organizations (Acín and Masanes, 2016, Wang, Wu and Zou, 2016, Wiebe et al., 2014).
As indicated in Section 6.1, the bottleneck of quantum computing at the present time is primarily on quantum hardware, and current quantum computing largely depends on what kinds of quantum computers experimentalists can build. On the other hand, as we have demonstrated in Section 6.6 for the quantum computational supremacy endeavor, besides hardware quantum computing also requires sophisticated mathematical models, sound statistical analysis, and better computational tools. As a matter of fact, in general we call for some combination of new experimental techniques, better mathematical and statistical understanding, and improved computational tools in order to significantly advance the development of quantum science and quantum technology.