CHAPTER 2

Relevant Background on Quantum Mechanics

In this section, we provide a concise survey of key concepts from quantum mechanics that are essential for quantum robotics. In general, our work is written for an audience familiar with typical robotic algorithms and technologies and presumes no prior knowledge of quantum mechanics.

2.1 QUBITS AND SUPERPOSITION

The fundamental unit of quantum computation is the qubit. The qubit can be thought of as the “transistor” of a quantum computer. A classical transistor controls a single binary bit that represents just a single discrete value, 0 or 1. A quantum bit, or qubit, assumes a complex combination of the two states, 0 and 1. This leads to some special properties unique to qubits. For instance, classical bits are independent of each other. Changing the value of a classical bit generally does not affect the value of other classical bits. This is not the case with qubits. As we will see, qubits can represent exponentially more data via special properties of quantum mechanics: superposition and entanglement.

As a simple illustration of the qubit, consider an electron orbiting a nucleus in an atom. The electron can be in one of two orbital states: the “ground” state or the “excited” state. Figure 2.1 shows an example depiction of this simple case. The electron functions as a qubit, and the qubit’s computational data is encoded by the electron’s orbital states.

Figure 2.1: Illustration of simple qubit.

Bra-ket notation, originally invented by Paul Dirac in 1939, is a standard notation for representing states of quantum systems. A ket |A represents the numeric state vector of a quantum system and is typically an element of a Hilbert space.¹ With ket notation, the ground state of our simple qubit can be represented as the ket |0 (an abbreviation for the state vector [10]^T), and the excited state can be represented as the ket |1 (an abbreviation for the state vector [01]^T). The bra A| is defined mathematically as the conjugate transpose² of a ket (e.g., A| = |A^†).

Before measurement, the electron is said to be in a superposition of the two states, denoted as a weighted sum:

where α and, β are complex numbers. The α and, β coefficients encode the probability distribution of states the electron can be found in when measured by a lab instrument. Until measurement, the true underlying state of the electron is not known. In fact, technically speaking, the true state of the electron is a linear superposition of both the ground and excited state. The superposition notation indicates that the electron is simultaneously in both the ground and excited state.

When the qubit is measured, its superposition collapses to exactly one state (either the ground or excited state), and the probability of measuring a particular state is given by its amplitude weights. The electron is measured to be in the ground state |0 with probability |α|² and in the excited state |1 with probability |β|² such that |α|² + |β|² = 1.

The notation can be generalized for describing k-level quantum systems. In a k-level quantum system, the electron can be in one of k orbitals as opposed to just one of two states. The state of the k-level quantum system |ψ (when in superposition) can be expressed as:

Upon measurement of the system, the superposition collapses to state |i with probability |α_i|². The α_i are complex numbers, potentially having both real and imaginary parts.

2.2 QUANTUM STATES AND ENTANGLEMENT

Previously, we illustrated how a simple electron-orbital system could be represented with bra-ket notation. The ket is a mathematical abstraction, a notation representing a physical state that exists in the real world. The beauty of this abstraction is that a variety of quantum systems, although implemented differently, can be described by the same underlying theory.

For a particular quantum system being studied, a physicist using the bra-ket notation will specify some of the system’s elementary physical states as “pure states.” Pure states are defined as fundamental states of a quantum system that cannot be created from other quantum states. A pure state |ψ can be described via a density matrix:

In general, each quantum state (pure or not) has an associated density matrix. Not all states are pure; many are mixtures of pure states. A probabilistic mixture of pure states (called a “mixed state”) can be represented by the following density matrix:

where |ψ_s are the individual pure states participating in the mixture, and the P_s are mixing weights.

Composite systems are quantum systems that consist of two or more distinct physical particles or systems. The state of a composite system may sometimes be described as a tensor product () of its components.

Here is an example of a 2-qubit system. |ψ_A and |ψ_B are two qubits that have probability distributions for being measured in states |0 and |1 respectively. The tensor product () of their distinct probability distributions can sometimes represent the joint probability distribution of the composite system’s measurement outcome probabilities.

The composite system, in this 2-qubit example, is measured in state |00 with probability αγ, |01 with probability αδ, |10 with probability βγ, and |11 with probability βδ. The tensor product operation is taking in two vectors representing probability distributions of possible measurement outcomes. Each of these input probability distributions sums to 1. The output is a new vector that holds the joint probability distribution (that also sums to 1), under the critical assumption that the measurement outcome probabilities are statistically independent.

In a key feature of quantum mechanics, a composite system is often more than the sum of its parts. Groups of particles can interact in ways such that the quantum state of each particle cannot be described independently. Composite states that cannot be written as a tensor product of components are considered “entangled.” For example, the composite state:

cannot be written as a product state of the two qubits forming the composite state. Expanding out the tensor product, we see that the system of equations {αγ = , αδ = 0, βγ = 0, βδ = } has no solution. The entangled composite system thus cannot be decomposed into its individual parts.

When the composite system can be represented using the tensor product decomposition, the qubit measurement events are effectively statistically independent probability events. The joint measurement outcome probabilities equal the numeric multiplication of individual measurement probabilities. In Equation (2.6), the composite system consists of entangled qubits, and the statistical independence assumption no longer holds. In an entangled system, the qubits exhibit state correlations. If one knows the state of one qubit in an entangled pair, he or she necessarily obtains information about the state of the other entangled qubit.

The overall quantum state (in superposition) of a composite system with N qubits having state |ψ (or more generally as N quantum subsystems each with quantum state |ψ) can be denoted as |ψ^N. Entanglement of qubits provides a potentially powerful data representation mechanism. Classically, N binary bits can represent only one N-bit number. N qubits, however, can probabilistically represent 2^N states in a superposition. N qubits can thus represent all possible 2^N N-bit numbers in that superposition. This advantage is partially offset by the additional processing overhead necessary to maintain quantum memory (since a qubit can only take on one state when measured and thus maintains the data only probabilistically). However, even with the additional overhead, quantum storage is expected to produce data representation advantages over classical implementations.

2.3 SCHRÖDINGER EQUATION AND QUANTUM STATE EVOLUTION

Quantum states change according to particular dynamics. The Schrödinger Equation can be used to describe a quantum system’s time-evolution:

where |ψ is the state of the quantum system, H is a Hamiltonian operator representing the total energy of the system, ℏ is Planck’s constant, and i = . Schrödinger’s Equation expresses that the time-evolution of a quantum system can be expressed in terms of Hamiltonian operators. This description of quantum systems is key to Adiabatic Optimization (see Section 2.5.4).

Hamiltonian operators that govern the evolution of quantum systems have special structure. In general, the evolution of a closed quantum system must be unitary, and the time-evolution of a closed quantum system can be described by application of a sequence of matrices that are unitary.

Formally, a complex square matrix U is unitary if its conjugate transpose U^† is also its inverse. This means:

where I is the identity matrix. Unitary matrices have several useful properties including being norm-preserving (i.e., U_x, U_y = x, y for two complex vectors x and y), being diagonalizable (i.e., writable as U = VDV*), having |det U| = 1, and being invertible.

Unitary matrices help formalize the evolution of a quantum system. The state vector |ψ of a quantum system can be pre-multiplied by a unitary matrix U. When a state vector containing a probability distribution over measurement outcomes is pre-multiplied by a unitary matrix, the operation always produces a new probability distribution vector whose elements also sum to 1. The resulting probability distribution represents the possible measurement outcomes of the quantum system after the system is evolved by the unitary matrix operator U. Unitary matrix operators can also be chain multiplied together (e.g., U₁U₂ … U_n) to represent a sequence of evolution steps on a quantum system. As we will see next, another view of unitary matrices is as logic gates in a quantum circuit that process input data (i.e., quantum states) and return outputs.

2.4 QUANTUM LOGIC GATES AND CIRCUITS

Quantum logic gates are the analogue to classical computational logic gates. Computational gates can be viewed as mathematical operators that transform an initial data state to a final data state. Since quantum state evolution must be unitary, quantum gates must be unitary operators.

2.4.1 REVERSIBLE COMPUTING AND LANDAUER’S PRINCIPLE

An interesting departure from classical computation is that quantum computer gates are always reversible. One can always, given the output and the operators, recover the initial state before the computation. This follows because a unitary matrix used to evolve a quantum system is also invertible.

Logic reversibility is the ability to determine the logic inputs by the gate outputs. For example, the classical NOT gate is reversible, but the classical OR gate is not. By definition, a reversible logic circuit has the additional following properties [Vos, 2010]:

1. The number of inputs and outputs are the same in the circuit.

2. For any pair of input signal assignments, there are two distinct pairs of output signal assignments.

Conveniently, the truth table of a reversible circuit with width n is represented as a square matrix of size 2ⁿ. While there are (2ⁿ)! different Boolean logic circuits of width n that can be realized, only a handful are valid reversible computing mechanisms.

Reversible quantum computing has a remarkable thermodynamic interpretation. In a physical sense, a reversible circuit will preserve information entropy, i.e., lead to no information content lost. Landauer’s principle [Landauer, 1961] states that any logically irreversible manipulation of information (such as the erasure of a classical digital bit) must lead to entropy increase in the system. The principle suggests the “Landauer Limit” that the minimum possible amount of energy required to erase one bit of information is kT ln (2) where k is Boltzmann’s constant and T is the temperature of the circuit. At room temperature, the Landauer Limit suggests that erasing a bit requires a mere 2.80 zettajoules!

The energy expenditure of current computers is nowhere near this theoretical limit. The most energy-efficient machines today still use millions of times this forecasted energy amount. In fact, in many realms of computer science and engineering, there is an expectation of intelligent computation being a highly power-intensive activity. Even neuroscientific predictions estimate human brain activities account for more than 20% of the body energy needs, with more than two-thirds of power consumption associated with problem solving activities [Swaminathan, 2008]. It seems natural to expect intelligence to be power-intensive. At the same time, the brain only uses about 20W of electricity, which is less than the energy required to run a dim light bulb [Swaminathan, 2008]. Clearly, more can still be done to optimize power consumption of digital circuits, even if generating intelligent behavior requires more energy consumption than other useful functions.

Excitingly, many studies appear to confirm the Landauer predictions for small-scale circuitry (though, convincing empirical proof is not without counterargument). Bennett [1973] showed the theoretical validity of implementing an energy efficient reversible digital circuit in terms of a three-tape Turing machine. In 2012, an experimental measurement of Landauer’s bound for the generic model of one-bit memory was demonstrated empirically [Bérut et al., 2012]. Recently, Hong et al. [2016] used high precision magnetometry to measure the energy loss of flipping the value of a single nanomagnetic bit and found the result to be within tolerance of the Landauer limit (about 3 zettajoules).

Since bulky battery technology is one of the key limiting factors of many current robotic systems, Landauer’s Principle provides hope for increasing the computational power of robots while simultaneously making robots more power-efficient. If true, Landauer’s Principle suggests a world with highly energy-efficient robots operating with quantum-scale circuits that allow massive reduction in power consumed.

2.4.2 NOTABLE QUANTUM GATES

In this section, we describe some of the common quantum gates used in quantum circuits. Since all operations that change a quantum system are unitary, all quantum gates must, by definition, be unitary matrices.

The logical NOT gate can be described by the following unitary matrix:

This matrix converts the quantum state α |0 + β |1 to α |1 + β |0 (via matrix multiplication). A gate useful throughout quantum computation is the Hadamard gate:

which converts and . Because of its effect, the Hadamard gate is sometimes called the “half way” gate. The Hadamard gate is an important building block for quantum parallelism (discussed in Section 2.5.1).

The Controlled Not (CNOT) gate converts |X₁, X₂ → |X₁, XOR(X₁, X₂). Effectively, this gate negates X₂ if X₁ is set to 1. The graphic representation of CNOT and its unitary matrix are shown in Figure 2.2.

Figure 2.2: Controlled NOT (CNOT) gate—Depending on the value of X₁, the value of X₂ may be flipped.

The “swap operation” (used in algorithms such as the quantum dot product described in Section 5.1.2 is created from three CNOT gates and converts |X₁, X₂ → |X₂, X₁.

For a three qubit network, the well-known Tofolli gate converts |X₁, X₂, X₃ → |X₁, X₂, XOR(X₃, X₁ AND X₂), flipping the third input X₃ if both X₁ and X₂ are set to 1.

Similarly, the Fredkin gate performs a controlled swap on three qubits, i.e., if X₁ = 1, the output state Y_1:3 is Y₁ = X₁, Y₂ = X₃, and Y₃ = X₂. Otherwise, Y₁ = X₁, Y₂ = X₂, and Y₃ = X₃.

The basic gates described here are useful for building more advanced quantum circuits.

2.4.3 QUANTUM CIRCUIT FOR FAST FOURIER TRANSFORM

The Fast Fourier Transform (FFT) plays an important role in classical image processing, pattern recognition, and signal processing. Hence, the FFT is likely to see implementation in quantum circuits for robots.

The classical FFT is a fast way to compute the classical Discrete Fourier Transform (DFT). The DFT calculates N coefficients of complex sine waves to model N complex samples of an unknown function. If A = {a₁, … , a_N} is the input data and P = {p₁, … , p_N} is the output data, DFT solves the linear equation P = F × A, where F is an N × N constant matrix with complex numbered elements F_x,y = . The solution requires O(N²) operations. Classical FFT exploits unique properties of the F matrix to reduce the calculations to O(N log₂(N)) operations.

A key difference between the Quantum Fast Fourier Transform (QFFT) and the classical FFT is that QFFT can be implemented in fewer circuit elements. For N input qubits, the QFFT equation is P′ = F′ × A′, where A′ = {a₁, … , a₂N}, P′ = {p₁, … , p₂N} and F′_x,y = .

Conveniently, the realization of this form requires only N(N + 1)/2 quantum gates [Vos, 2010]. Hadamard and Controlled phase gates can be used to construct QFFT circuits. The controlled phase gate implements a phase shift of the second qubit (as shown in Figure 2.3). In Figure 2.4, we see a quantum circuit realization for the Quantum Fast Fourier Transform for N = 3.

Figure 2.3: Controlled phase gate. Depending on X₁, the value of X₂ is flipped.

Figure 2.4: Quantum FFT, N = 3.

2.5 QUANTUM COMPUTING MECHANISMS

In general, quantum gates placed in a circuit can create interesting computational behavior not possible in classical circuits. Quantum computing methods offer potential speedups and improved properties for many classical algorithms. Some introductory background can be found in Kaye et al. [2006], Rieffel and Polak [2000], Steane [1998]. The key general mechanisms of quantum speedup and improvement are discussed in this section.

2.5.1 QUANTUM PARALLELISM

The first key mechanism for algorithmic speedup is quantum parallelism. A parallelized implementation of a function computes its value on multiple inputs simultaneously. By using quantum gates, one can create circuits that exhibit parallelism capability not possible in classical circuits. One can see the basic pattern in the following quantum circuit (shown in Figure 2.5).

Figure 2.5: Illustration of quantum parallelism circuit.

Let the goal be to parallelize the function f (x) : {0, 1} → {0, 1}. We define the unitary circuit gate U_f for that function as follows.

The x circuit line is known as the data register, and the y circuit line is known as the target register. Figure 2.5 puts together the designed U_f gate and a Hadamard gate.

Fix the inputs to circuit at X₁ = |0 and X₂ = |0. The Hadamard gate produces the output , which is then fed into the data register (x) of the U_f gate. The U_f gate evaluates its function at , the output of which forms a composite system with y = |0. The circuit produces the following pattern:

Thus, the circuit evaluates the function f (x) at both 0 and 1 simultaneously in parallel. It turns out that this pattern generalizes to n qubits for a U_f gate that has n data registers. Applying a Hadamard gate to each data register creates the famous pattern known as the “Hadamard transform.” For an input state, |0^⊗n |0, this pattern will generate the state:

where X is the set of 2ⁿ unique binary bit strings of length n. The Hadamard Transform produces a superposition of 2ⁿ states using n gates, simultaneously evaluating all values of the function while the system is in superposition. This is a remarkable amount of computation done, compared to classical systems.

2.5.2 CHALLENGES WITH QUANTUM PARALLELISM

The major limitation of quantum parallelism is that, while the output state contains information about multiple function evaluations of f (x) when the system is in superposition, only one of the function evaluations is returned when the quantum system is measured. In the basic Hardamard transform, any of the function values |f (x) can be returned, each with equal probability. Limited data return from measurement is a common theme in quantum computing. For many methods, it is common for a quantum system to perform a significant amount of computation while in superposition but to reveal only a small fraction of the result upon measurement.

Much research is dedicated to evolving quantum systems that encode useful information in superposition so that the most useful output information is returned upon measurement. For example, there exist quantum parallel techniques to extract some meaningful information about the global properties of a function as opposed to just raw function values at points. Deutsch’s algorithm [Deutsch and Jozsa, 1992] allows for the evaluation of the parity f(0) ⊕ f(1) using one parallel computation whereas classically two computations would be required.

In general, a convincing empirical demonstration of quantum parallelism is a subject of ongoing research. Some authors ask whether quantum parallelism (in the unitary circuit formulation) is even realizable. The construction of the U_f gate in practice may require internal logic that scales with the number of unit-cost operations for the precision of x. The quantum circuit complexity result may be benefiting from gate-level parallelism not realizable in classical circuits. When one looks at the complexity of the complete circuit, there may not always be an advantage of quantum parallelism to classical parallelism [Lanzagorta and Uhlmann, 2008b].

Despite the current challenges with quantum parallelism, it is still regarded as a major hope for the future success of quantum computing. It is also one of the fundamental pillars on which more sophisticated quantum algorithms are built.

2.5.3 GROVER’S SEARCH ALGORITHM

Grover’s search algorithm, which makes use of quantum parallelism, is a method for quantum computers to find an element in an unordered set of N elements quadratically faster than the theoretical limit for classical algorithms. The algorithm is expected to run in time as opposed to O(N) time classically.

In order to do this, the algorithm uses a quantum oracle, a black box able to indicate the solution for a given computational problem. While this sounds somewhat magical, the concept is quite logical. A quantum oracle is a function f (x) that is able to look at a possible solution to a computational problem and verify that it is a solution. For many computational problems, it is intensive to compute a solution but easy to verify one. The quantum oracle does not have to compute the solution, just to know when one is found.

A quantum oracle function f (x) is defined for the data that indicates if the sought element is found:

q is an ancilla bit that is flipped if f (x) = 1 and stays the same if f (x) = 0.

How many calls to the oracle are needed to find the sought element? Classically, O(N) calls to the abstract oracle are required since, in the worst case, the entire database may need to be searched. However, with a quantum computer, only calls to the oracle are needed to find the sought element.

If there are N items, an item’s binary index can be represented with n = log₂(N) bits. A Hadamard transform is used on |0^⊗n to prepare the equally-weighted superposition over the N items in the database:

The Grover operator is defined as:

where O is the oracle function and I is the identity matrix. After transforming the system with the Grover operator times, measurement of the resulting system will, with high probability, correspond to the index of the found item. The complete Grover’s algorithm is given below.

The intuition behind Grover’s algorithm is shown in Figure 2.6. All elements originally start in a superposition where each element has the equal weight. Each application of the Grover operator (which contains the oracle function) inverts the phase of solution elements x*, while keeping the elements of non-solution elements the same. The Grover operator then inverts solution elements x* above the mean.

As the Grover operator is applied multiple times, the amplitude weights of the solution elements become larger and larger. When the Grover operator is applied a sufficient number of times, the solution x* is obtained with extremely high probability when the quantum system is measured.

For an N-item database with 1 solution item, Grover’s algorithm will find the solution in time. If there are t (identical) solution items, the time complexity is [Boyer et al., 2004].

The fine print of Grover’s algorithm complexity is that these results only take into account the number of calls to the oracle function, not the complexity of implementing the oracle function circuit. Note that for many useful functions (such as those used in encryption), there exist relatively straightforward verification oracles. The oracle can check whether a solution exists, without going into the details of how the solution is computed. While the solution can be difficult to compute, if the oracle can verify the solution, it is often a sufficient condition for Grover’s algorithm to solve the search problem effectively.

Figure 2.6: Intuition behind mathematical principles of Grover’s algorithm.

2.5.4 ADIABATIC QUANTUM OPTIMIZATION

Many search problems can also be viewed as optimization problems. For example, many search problems can be cast with the objective of finding the global minimum (x₀, f₀) of a given function f(x):

Adiabatic Quantum Optimization, a particular approach to quantum computing, uses this formulation as its main mathematical machinery. An adiabatic process is one that changes conditions gradually so the system can adapt to its configuration. The adiabatic theorem [Born and Fock, 1928] describes the time-evolution of the Hamiltonian of an adiabatic process:

The Hamiltonian H₀ is a Hamiltonian whose ground state can easily be constructed in the lab. The Hamiltonian H₁ is one whose ground state energy is the target. The adiabatic theorem states that if the system starts in the ground state of H(0) = H₀ and the parameter λ(t) is slowly increased, the system will evolve to the ground state of H₁ if Hλ(t) is always gapped (i.e., there is no degeneracy for the ground state energy).

The adiabatic theorem forms the basis for adiabatic quantum computing and the design of adiabatic processors, though the question of how much speedup is achieved is complex [Rønnow et al., 2014]. The annealing time in the adiabatic theorem depends on the eigenvalue gap, which is not known a priori. Depending on how the eigenvalue gap scales with the problem size, the annealing time could grow anywhere from polynomially to exponentially. The speedup also depends on the classical algorithms that serve as benchmarks. Different classical algorithms may perform better or worse on different problems. Thus, it is sometimes difficult to decide what is a fair comparison. For many problem instances, quantum annealing is forecasted to offer roughly a quadratic factor speedup compared to many classical stochastic optimization approaches.

2.5.5 ADIABATIC HARDWARE AND SPEEDUPS

Quantum adiabatic optimization leverages stochastic quantum annealing procedures in hardware to produce speedups in optimizing robotic algorithms. In this section, we describe how algorithmic problems are mathematically mapped onto an adiabatic processor. Various implementations of adiabatic hardware exist and are discussed further in Chapter 7.

Figure 2.7: Illustration of Ising model.

The Ising model from statistical mechanics studies the magnetic dipole moments of atomic spin. Imagine a lattice of elements that can spin up or down (as shown in Figure 2.7). In the model, only neighboring pairs of elements are assumed to interact. The elements choose spins to minimize the lattice’s overall energy configuration:

where s_i ∈ {−1, + 1} are variables representing “spins,” J is a matrix describing interactions betweens spins, and h is a numeric vector that models the impact of an external magnetic field. The Ising objective function is represented by the following Hamiltonian:

where i and j are pairs of adjacent sites and is the spin variable of qubit i.

Define the start state of the adiabatic process as:

The adiabatic theorem (discussed in Section 2.5.4) can be used to solve the energy minimization problem:

Quadratic Unconstrained Binary Optimization (QUBO) is the mathematical optimization form of a simplified Ising model:

where x is an n × 1 vector of Boolean variables, and Q is an n × n square symmetric matrix of coefficients.

If an optimization problem can be cast as a QUBO, it can be represented as an Ising model and optimized by adiabatic hardware. Many computational problems can be cast as QUBOs. Abstractly, the Ising model represents a set of elements and their pair-wise interactions. The Ising model has seen many real-world modeling applications because interacting elements must be modeled in a large number of fields. The world is full of interacting elements (e.g., electrons in an atom, neurons in a network, birds in a flock, or even interacting social agents in a crowd psychology setting).

Current adiabatic hardware is mostly limited to solving QUBOs. As such, it is, at best, a limited form of universal quantum computing. In addition, current hardware does not allow many qubits, produces many defects such that not all pairs of qubits are entangled, and must use sparse, pre-specified topologies for qubit interconnections [Neven et al., 2009, Pudenz et al., 2014].

2.5.6 SHOR’S QUANTUM FACTORIZATION ALGORITHM

One of the hallmark results in quantum computing is Shor’s algorithm for integer factorization. When first proposed, Shor’s algorithm was one of the key theoretical insights that showed quantum computing could be very different from (and has the potential to be significantly more powerful than) classical computing.

Integer factorization is a fundamental problem in computer science. While it is relatively easy to find large prime numbers, it is particularly hard to resolve a composite number into its prime factors. A decomposition of an arbitrary N-bit number, executed on a classical computer, has an exponential complexity O(k^N), for some constant k. Prime factorization is among the class of NP problems.

The hardness of factorization has historically served as a boon in fields such as publickey cryptography and network communication. The widely used RSA encryption scheme [Rivest et al., 1978] has been one of the more popular algorithms for secure communication on networks [Menezes et al., 1996]. In a robotics context, algorithms such as RSA help keep robot communication and teleoperation secure from possible hackers. Quantum factorization, however, could be used to break RSA and change the nature of internet security.

In 1994, Peter Shor formulated a hallmark quantum factorization algorithm that performs factorization in polynomial time [Shor, 1999]. For an arbitrary odd number N, consider a random x, 1 < x < N, for which x^r = 1 mod N, for some r. The series (1, x, x², x³, … ) mod N is periodic with a period not greater than N. The above relations can be succinctly represented as:

From the equation (ab = 0 mod N), one can find, in polynomial time, the greatest common divisors, gcd(a, N) and gcd(b, N). These divisors, if they are found, will be factors of N. If a non-trivial divisor does not exist, the x variable can be re-picked and the computation repeated.

The described steps can be performed on a classical computer in polynomial time, with the exception of calculating the exponential function x^r. Shor’s algorithm uses the Discrete Fourier Transform (DFT) and quantum parallelism to calculate the periodic function simultaneously for many values x, so that all operations happen in O(N) time.

Shor’s algorithm is a major advancement in the theory of quantum computing, and one of the most interesting predictions posited by the field. A practical implementation for large integer factorization instances is still a subject of major research [Dattani and Bryans, 2014].

2.5.7 QUANTUM TELEPORTATION

Another major engineering possibility posited by quantum mechanics is quantum teleportation. Quantum teleportation is a technique which transmits a quantum state by using a pair of entangled qubits and a classical communication channel. In this section, we provide a brief outline of how quantum teleportation works.

Consider two parties, Alice and Bob, who wish to communicate the state |ψ of a qubit. Alice wants to send the qubit state to Bob. However, Alice does not know what the state of the qubit is and, by the laws of quantum mechanics, observing the state collapses the qubit into a definite value, |0 or |1. Furthermore, even if Alice knows the superposition state |ψ = α |0 + β |1, communicating it over a quantum channel would take an infinite amount of time, since the amplitudes α and β are complex numbers with infinite precision. However, the quantum teleportation technique allows one to transmit the state |ψ using an entangled pair of bits and communication of two bits of information over a classical communication channel.

The protocol for transmitting the state |ψ begins with forming an entangled pair of qubits A and B. The qubit A is given to Alice and the qubit B is given to Bob. Alice now takes the qubit |ψ that she wishes to communicate and makes a joint measurement of it with the entangled qubit A. This results in Alice entangling her two qubits and observing one of four states. This observed state can be encoded in two classical information bits. Alice encodes her observations into two classical bits and transmits them to Bob. As a result of Alice’s observation, B is now in one of four possible states, which correspond to the state |ψ. Using the information Alice sent with two classical bits, Bob can perform operations on B so that its state becomes |ψ. Bob can thus successfully recreate the state |ψ on his end.

Quantum teleportation has many potential applications in robotics. One could potentially use quantum teleportation to transmit information about qubits between a robot and a server operating in different locations. Note that information cannot be transmitted faster than the speed of light, since the communication of two classical bits of information is needed in the protocol. One does not expect a better network speed from quantum teleportation. However, quantum teleportation might one day allow qubit information to be transported with less effort than is currently required. Some additional applications in robotics include building noise-resistant quantum gates, quantum error correcting codes, and further development of quantum information theory.

2.6 QUANTUM OPERATING PRINCIPLES (QOPS) SUMMARY

We have discussed some key basic principles of quantum mechanics and quantum computation. Many techniques in quantum robotics can be understood as applications of these core principles which we call “Quantum Operating Principles” (or QOPs). In Table 2.1, key QOPs are mentioned as well as some of their potential applications in quantum robotics that will be discussed in upcoming chapters.

2.7 CHAPTER SUMMARY

The material on fundamental quantum mechanics forms the backbone of our discussion of quantum robotics. Entanglement of qubits is the basis of quantum parallelism, a key speedup strategy for algorithms. Quantum adiabatic processors allow one to cast certain classical optimization problems in the framework of quantum optimization. In the next section, we will apply these concepts to robotic search and planning.

Table 2.1: Summary of Quantum Operating Principles (QOPs) and application areas in Quantum Robotics

Quantum Operating Principle	Potential Quantum Robotic Applications
Quantum Measurement	Quantum Machine Learning (Ch. 5), Quantum Hidden Markov Model (Ch. 6), Quantum Kalman Filter (Ch. 6)
Quantum State Evolution	Quantum Markov Decision Process (Ch. 4), Quantum Partially Observable Markov Decision Process (Ch. 4), Quantum Filtering and Control (Ch. 6)
Grover’s Algorithm	Grover Tree Search (Ch. 3), Quantum Machine Learning (Ch. 5)
Adiabatic Theorem	Quantum STRIPS (Ch. 3), Quantum Machine Learning (Ch. 5)

¹Often, for us, just ^N, the space of complex numbered vectors.

²The conjugate transpose of a matrix A* = . To form the conjugate transpose of A, one takes the transpose of A and then computes the complex conjugate of each entry. The complex conjugate is simply the negation of the imaginary part (but not the real part).