6
Quantum Algorithms

Julia Kempe

LIAFA ‐ case 7014, Cedex 13, 75205 Paris, France

6.1 Introduction

The idea to use quantum mechanics for algorithmic tasks may be traced back to Feynman (1,2). The application he had in mind was the simulation of quantum mechanical systems by a universal quantum system, the quantum computer. Feynman argued that quantum mechanical systems are well equipped to simulate other quantum mechanical systems; hence a universal quantum machine might be able to efficiently do such simulations. Another approach to this question was taken by Deutsch (3), who tried to reconcile quantum mechanics and the Church–Turing principle, which (roughly speaking) states that any computable function can be calculated by what is known as a universal Turing machine. Deutsch put the notion of a universal machine on a physical footing and asked if the principle had to be modified if the machine was quantum mechanical, establishing what has since been known as the Church–Turing–Deutsch principle. In his work, Deutsch was also the first to exhibit a concrete computational task, which is impossible to solve on a classical computer yet which has an easy quantum mechanical solution, Deutsch's algorithm (see the next section). What is interesting about this algorithm is that not only it is the smallest algorithm, involving only two quantum bits (qubits) but also carries the main ingredients of later quantum algorithms, and is a nice toy model for understanding why and how quantum algorithms work.

A major breakthrough in quantum algorithms was made by Peter Shor, who gave an efficient quantum factoring algorithm. Factoring numbers into primes is an important problem, and no efficient classical algorithm is known for it. In fact, many cryptographic systems rely on the assumption that factoring and related problems, such as discrete logarithm, are hard problems. Shor's algorithm has put a threat on the security of many of our daily transactions – should a quantum computer be built, most current encryption schemes will be broken immediately.

The way Feynman put it, a quantum computer is a machine that obeys the laws of quantum mechanics, rather than Newtonian classical physics. In the context of computation, this has two important consequences, which define the two aspects in which a quantum computer differs from its classical counterpart. First, the states describing the machine in time are quantum mechanical wavefunctions. Each basic unit of computation – the qubit – can be thought of as a two‐dimensional complex vector of norm 1 in some Hilbert space. The two‐dimensional basis for such a qubit is often labeled as |0〉 and |1〉, where the basis states correspond to the classical bit, (which takes values 0 and 1). Second, the dynamics that governs the evolution of the state in time is unitary, that is, described by a unitary matrix that transforms the state at a certain time to the state at some later time. A second dynamical ingredient is the measurement. In quantum mechanics, observing the system changes it. In the more restricted setting of a quantum algorithm, a measurement can be thought of as a projection on the basis states. A particular basis state will be measured with a probability, which is given by the squared amplitude in the state that is being measured.

Given this model, it is not even clear if such a quantum computer is able to perform classical computations. After all, a unitary matrix is invertible and hence a quantum computation is necessarily reversible. Classical computation given by some circuit with elementary gates, such as the AND and NOT gate, is not reversible, let alone because a gate such as the AND gate has two inputs and only one output. However, the question of reversibility of classical computation has been studied in the context of energy dissipation by Bennett in the 70s (4) (see also (5)), who established that classical computation can be made reversible with only a polynomial overhead in the number of bits and gates used. Classical reversible computation then implements just a permutation on the bitstrings of its input, and is in particular unitary. As a result, quantum computation is at least as strong as classical computation.

The next important question is whether it is possible to build a universal quantum machine (rather than special purpose computers). In other words, is there a small set of operations that implements any unitary transformation? Classically, it is well known that any Boolean function can be computed with a small set of gates, such as AND and NOT. Fortunately, it turns out that a similar statement is true for the quantum world; it was shown (6,7) that there is a small set of universal quantum gates on at most two qubits. One such gate set is {X, PI/8, H, CNOT}, where X implements a single qubit bit‐flip, PI/8 is a gate that multiplies the |1〉 basis state with images , the Hadamard gate H maps images and images and the controlled NOT gate, a two‐qubit operation, flips the second bit if the first bit is |1〉.

This paved the road for general quantum algorithm design. In this chapter, we will trace the history of quantum algorithms with a focus on the milestones – Shor's algorithm and Grover's algorithm for unstructured search – and finish with a brief overview of recent developments. As we progress, we will strip off more and more details to try to convey the general intuitions behind the main ideas in this exciting field. The reader will find detailed expositions of the classic quantum algorithms in the literature (in particular (8,9)) and of more recent developments in the reference list.

6.2 Precursors

As mentioned before, the first quantum algorithm is Deutsch's algorithm (3). Before we describe it, let us clarify the notion of a quantum black‐box function. Classically, a black‐box function can be simply thought of as a box that evaluates an unknown function f. The input is some n‐bit string x and the output is given by an m‐bit string f(x). Quantumly, such a box can only exist if it is reversible. To create a reversible box, the input (x) is output together with f(x) and the black box looks like in Figure 6.1.

Geometrical illustration of reversible black box for a function f : {0,1}n →{0, 1}m.

Figure 6.1 A reversible black box for a function f : {0, 1} n → {0, 1} m .

Geometrical illustration of Deutsch's circuit.

Figure 6.2 Deutsch's circuit.

To make the box reversible, an additional m‐bit input y is added and the output of the result is f(x) ⊕ y where ⊕ denotes bitwise addition mod 2. In particular, if y is fixed to be y = 0 … 0, the output is f(x). This reversible box, when given to a classical machine, is not stronger than the corresponding simple nonreversible box that maps x to f(x). Note that this box now induces a transformation on n + m‐bit strings that can be described by a permutation of the 2 n + m possible strings; in particular it is unitary.

6.2.1 Deutsch's Algorithm

With these notions in place, we can give Deutsch's algorithm (3).

Note that classically, to solve this problem with a success probability bigger than one half, a machine has to query the black box twice; both f(0) and f(1) are needed. Deutsch's ingenuity is to use interference of the amplitudes of the quantum state such that only one query to the black box suffices. The following circuit on two qubits gives the quantum algorithm (Figure 6.2).

  1. The qubits are initialized in |0〉|1〉, the first ket denotes the qubit 1 and the second one qubit 2.
  2. After the Hadamard transform is applied to each qubit, the state is images (|0〉 + |1〉) (|0〉 − |1〉).
  3. After the invocation of the black box the state of the two qubits is
    equation

    Note that the state of the second qubit in this expression is ± (|0〉 − |1〉); the sign depends on the value of f(0) (resp. f(1)). The state can be rewritten as

    equation
  4. After the last Hadamard is applied, the state of the first qubit becomes
    equation

    which can be rewritten as images ((−1) f(0) + (−1) f(1)) |0〉 + ((−1) f(0) − (−1) f(1)) |1〉. If the function is constant, this state is ±|0〉, if it is balanced, the state is ±|1〉. The final measurement will completely distinguish these two cases.

As a result, Deutsch's algorithm saves one query compared to the best possible classical algorithm for this problem. One query might seem very little, yet we will see how this algorithm has been generalized in several steps to ultimately factor numbers.

6.2.2 Deutsch–Josza Algorithm

In a first step, Deutsch and Josza (10) generalized Deutsch's algorithm to give a problem where the quantum algorithm gives more than just a single query advantage. It is, however, a promise problem.

Note that classically, to solve this problem deterministically, one needs 2 n − 1 + 1 queries in the worst case, as in the balanced case one might have to query 2 n − 1 different y for some x before one finds a y such that f(x) ≠ f(y). The Deutsch–Josza algorithm solves this problem with one quantum query with the following algorithm: The analysis of this algorithm is very similar to Deutsch's algorithm. The difference in the circuit is that the Hadamard transform on one qubit is replaced with the tensor product of n Hadamard transforms H ⊗n on n qubits. Let us first analyze the action of H ⊗n on a basis state |x〉 (x is an n‐bit string). The transformation induced by a single Hadamard on a qubit i in the basis state |xi 〉 can be written as (Figure 6.3)

equation
Geometrical illustration of Deutsch-Josza algorithm.

Figure 6.3 Deutsch–Josza algorithm.

Applying this to H ⊗n with |x〉 = |x 1 … xn 〉 we get

6.1 equation

where x · y is the inner product of the vectors x and y mod 2. The Hadamard transform H and H ⊗n are instances of a more general transformation, called the quantum Fourier transform (QFT). In our circuit H ⊗n gives in step 2 the state

equation

As before, at step 3 the state of the system on the first n qubits is

equation

If the function is constant, then this state is just the uniform superposition over all bit strings (up to a global phase) and using Eq. 6.1 we see that the state at step 4 is simply (−1) f(0) |0 … 0〉. If the final measurement gives the all zero string the output of the algorithm is “constant.” Otherwise the overlap of our state of the first n qubits at step 4, H ⊗n |φ3〉, with the state |0 … 0〉 is 0, which means a measurement never gives the all zero string. To see this, note that 〈0 … 0(H ⊗n |φ3〉) = (〈0 … 0|H ⊗n )|φ 3〉 and let us calculate the inner product of |φ 3〉 with the Fourier transform of the all zero state:

equation

Using that f is balanced we get that this sum is 0. Hence in case that f is constant a measurement will always give the all zero string whereas in the balanced case we will always get an outcome different from all zeros. This completes the analysis.

Note, that the speed‐up achieved by the quantum algorithm from O(2 n ) queries to 1 query only holds if we compare with a classical deterministic machine. If the classical machine is allowed to be probabilistic, then the classical query complexity reduces to O(1): If we query the function at random then in the balanced case each of the two function values will be seen with probability 1/2 and with very high probability we will see two different function values after a constant number of queries.

In the next algorithm, a quantum computer solves a problem with an exponential speed‐up over the best classical probabilistic machine.

6.2.3 Simon's Algorithm

This algorithm of Simon (11) finds the “period” of a function.

One can show that the best any classical probabilistic machine can do is to query elements at random until a collision is found. The probability of a collision for two randomly chosen elements is about 2 −n , and a slightly more elaborate analysis shows that the expected number of queries until a collision happens among the queried elements is O(2 n/2).

Interestingly, the quantum algorithm is very similar to the Deutsch–Josza algorithm with the difference that there are now 2n qubits as input to the black box and no Hadamard transforms on the second block of qubits, see Figure 6.4. This circuit implements a special case of what is called quantum Fourier sampling.

Geometrical illustration of Simon's algorithm - quantum Fourier sampling.

Figure 6.4 Simon's algorithm – quantum Fourier sampling. In our algorithm QFT = H ⊗n . In general, a QFT over a group G gives the quantum Fourier sampling algorithm over G.

Note that there is a partition of the 2 n input strings into two sets X and images  = {x ⊕ a|x ∈ X} with |X|, | images | = 2 n−1, such that all the values f(x) are distinct for x ∈ X and similar for images . At step 3 the state is

equation

A measurement of the qubits in the second register will yield one of the 2 n − 1 values of f(x) with equal probability and collapse the state of the first register to images (|x〉 + |x ⊕ a〉) for a random x ∈ X. At step 4 the state becomes

equation

A measurement of the first register gives a random y = y 1 such that a · y 1 = 0. We can now repeat this algorithm to obtain y 2 with a · y 2 = 0, y 3 with a · y 3 = 0, and so on. These yi form a subspace of the n‐dimensional vector space of all n‐bitstrings (over GF (2)). If among the yi there are n − 1 vectors that are linearly independent (i.e., such that they span a space of dimension n − 1), then the equations a · yi completely determine a ≠ 0. But for each set of yi that do not yet span a space of dimension n − 1 the probability that the next y will be outside the space is at least 1/2, because the space spanned by them contains at most 2 n − 2 out of the 2 n − 1 possible y's. Hence after O(n) repetitions of the algorithm with a probability exponentially close to 1 we will have enough information to determine a.

6.3 Shor's Factoring Algorithm

Conceptually it is now only a small step from Simon's algorithm to Shor's algorithm for factoring. The first necessary observation is that in order to find a factor of a number, it is sufficient to solve a problem called period finding, the problem Shor's algorithm (12) actually solves:

6.3.1 Reduction from Factoring to Period Finding

Let us assume that we want to factor the number N. Once we have an algorithm that gives one factor q of N, we can restart the algorithm on q and N/q; we obtain all factors of N after at most log N iterations. Assume N is odd and not a power of a prime (both conditions can be verified efficiently and moreover in these cases it is easy to find a factor of N). First, we select a random 1 < y < N and compute GCD(y, N) (this can be done efficiently using the Euclidean algorithm). If this greatest common divisor is larger than 1, we have found a nontrivial factor of N. Otherwise, y generates a multiplicative group modulo N. This group is a subgroup of images , the multiplicative group modulo N. The order of this group is determined by the factors of N (and is unknown to us). The smallest integer a such that ya ≡ 1 mod N, known as the order of y, is the period of the function fy (x) = yx mod N. This function can be viewed as a function over ℤ.

Invoking now the period finding algorithm, we can determine a. If a is even then images . We know that N ∤ images (images is not the period of fy ), so if N ∤ images then N must have a common factor with each of images and we can determine it by computing GCD(N, images  − 1). It remains to be shown that with probability at least 1/2 over the choice of y both conditions are satisfied, that is, both a is even and N ∤ images . This can be shown using the Chinese remainder theorem (see e.g., (8,9,13)).

In what follows we focus on solving the period finding problem. We use essentially the same quantum circuit as in Simon's algorithm, Figure 6.4, namely quantum Fourier sampling with an appropriate definition of the QFT.

Note that the QFT over ℤ2 is just the Hadamard transform on one qubit, and in general the transformation H ⊗n in Deutsch–Josza and in Simon's algorithms implements the QFT over the group images . The Fourier transform in that case is just a tensor product of single qubit unitaries. The ingenious part of Shor's algorithm is to show that the QFT over ℤ M is also implementable efficiently, that is, in time polynomial in log M, by a quantum circuit.

6.3.2 Implementation of the QFT

Note that the QFT implements an M × M unitary matrix with entries ωx·y . A naive classical algorithm that computes each entry separately and then sums the appropriate rows to compute each of the amplitudes images will require O(M 2) steps. However, there is a well‐known trick to speed up the evaluation of all these sums: The classical fast Fourier transform (FFT) takes only time O(M log M) for this task. For ease of presentation let us assume that M = 2 n . To evaluate ω x · y  = images , let us expand x in binary notation x = x n − 12 n − 1 + x n − 22 n − 2 +⋯+ x 12 + x 0 and similarly for y. In the product x · y, we can ignore all terms divisible by 2 n as they do not contribute to the exponent. Now

equation

The terms in parentheses are binary expansions, for example, .x 2 x 1 x 0 = x 22 −1 + x 12 −2 + x 02 −3. The amplitude

equation

can now be evaluated sequentially in time O(log M) for each of the M values of x.

Quantum parallelism improves this drastically. We can write

equation

Figure 6.5 shows a circuit that implements this transformation on ℤ8. The Hadamard on qubit xi can be thought of as performing |xi 〉 → (|0〉 + images |1〉). The conditional rotations Rd give a phase of images to the qubit on which they act whenever the control qubit is in the state |1〉. The obvious generalization of this circuit to n qubits has images  = O(log2 M) gates.

Geometrical illustration of QFT on -8.

Figure 6.5 QFT on ℤ8. An element of ℤ8 is represented in binary notation x = x 2 x 1 x 0, y = y 2 y 1 y 0.

6.3.3 Shor's Algorithm for Period Finding

With this implementation of the QFT in place we can analyze the algorithm in Figure 6.4 for period finding. We need to chose the integer M over which the QFT is performed. For our problem (a ≤ N) we chose M = 2 n to be a power of 2 such that N 2 < M ≤ N 4.

For the moment, let us make the simplifying assumption that the period a divides M. At step 2 the first register is in a uniform superposition over all elements of ℤ M . As in Simon's algorithm, the state at step 3 after the measurement of the second register is

6.2 equation

for some random x ∈ ℤ M . The QFT transforms the state of the first n qubits into

6.3 equation

Since a divides M, we have that whenever ωay  ≠ 1, that is, whenever y ∉ {0, M/a, 2M/a, …, (a − 1)M/a}

equation

This implies that in Eq. 6.3 the amplitudes of basis states |y〉 for y not a multiple of M/a are zero. Consequently the state at step 4 is a superposition over all y ∈ {0, M/a, 2M/a, …, (a − 1)M/a} and a measurement gives a uniformly random y = cM/a. To extract information about a we need to solve y/M = c/a. Whenever c is coprime to a (which can be shown to happen with a reasonably good probability Ω(1/log log a)) we can write y/M as a minimal fraction; the denominator gives a.

In the (more likely case) that a does not divide M it is not hard to see that the same algorithm will give with high probability a y such that |y/M − c/a| ≤ 1/2M for some 0 ≤ c < a. But two distinct fractions with denominator at most N must be at least 1/N 2 > 1/M apart, so c/a is the unique fraction with denominator at most N within distance 1/2M from y/M and can be determined with the continued fraction expansion.

Note that in Shor's algorithm the function fy (x) = yx mod M is not given by a black box, but needs to be computed every single time. This could be difficult since the exponent x is very large. However, using the binary expansion of x and repeated squaring, it is not hard to see that there exists a classical subroutine for computing fy in time polynomial in log M. As a result Shor's algorithm gives a factor of N with high probability in time polynomial in log N.

6.4 Grover's Algorithm

The second milestone in quantum algorithm design is Grover's algorithm for unstructured search (14,15). The problem of unstructured search is paradigmatic for any problem where an optimal solution needs to be found in a black‐box fashion, that is, without using the possible structure of the problem:

Classically, a deterministic algorithm needs to make 2 n − 1 queries to identify w in the worst case and a probabilistic algorithm still needs O(2 n ) queries. Grover gave a quantum algorithm that solves this problem with O images queries and this is known to be the best possible. Grover's algorithm can hence speed up quadratically any algorithm that uses searching as a subroutine.

Grover's quantum algorithm applies the subroutine of Figure 6.6 about images times. Here, the n‐qubit gate C[P] denotes a controlled phase; it flips the sign of all basis states except for the all zero state. Its action can be concisely written as C[P] = 2 |0 … 0〉 〈0 … 0| − In , where In denotes the identity on n qubits. This operation is conjugated by the Hadamard transform, which maps |0 … 0〉 to the uniform superposition |Ψ〉 = images . So the net operation between steps 1 and 2 can be written as R Ψ = 2 |Ψ〉 〈Ψ| − In . It is sometimes called diffusion or reflection around the mean, because it flips the amplitude of a state around its “mean” images . The operation between steps 2 and 3 with the ancillary qubit set to images (|0〉 − |1〉) is similar to Figure 6.3; it gives a phase of (−1) f(x) to the basis state |x〉. In our case only f(w) is nonzero and so only the phase of |w〉 is flipped. This operation can be written as Rw  = In − 2 |w〉〈w|. It is called reflection around w. Grover's algorithm first applies H ⊗n to the state |0 … 0〉 and then iterates T times the subroutine RwR Ψ of Figure 6.6.

Geometrical illustration of Subroutine in Grover's algorithm.

Figure 6.6 Subroutine in Grover's algorithm.

Note that with input |Ψ〉 the subroutine in Figure 6.6 leaves invariant the subspace spanned by |Ψ〉 and |w〉. Inside this space it acts as a real rotation with angle φ, where φ ≈ sin φ = images . After T time steps the state rotates from |Ψ〉 toward the nearly orthogonal |w〉 by an angle Tφ. Choosing T = images gives a state that overlaps with |w〉 very close to 1. A measurement now gives w with very high probability.

It is not hard to see that this algorithm also works in the case of k marked items in the database; in this case its running time is O images .

6.5 Other Algorithms

Developments in quantum algorithm design after Shor's and Grover's algorithms can be loosely grouped into three categories: algorithms that generalize Shor's algorithm (hidden subgroup algorithms), algorithms that perform some version of unstructured search (“Grover‐like” algorithms) and a few algorithms that do not fit into either of these categories. The scope of this chapter restricts us to mention only a small selection of new quantum algorithms and techniques.

6.5.1 The Hidden Subgroup Problem

Shor's algorithm can be seen as an instance of a more general problem, the hidden subgroup problem (HSP). The function f in the period finding problem, viewed over ℤ M , is constant on sets {x, x + a, …} for each x and distinct on such disjoint sets; if a divides M it is constant on cosets x + 〈a〉 of the subgroup of ℤ M generated by a and distinct on different such cosets.

The HSP is an important problem. An efficient algorithm for the group ℤ M yields an efficient factoring algorithm. It is also a component of an efficient algorithm for the discrete logarithm over ℤ M . Discrete logarithm is another cryptographic primitive in classical cryptography which would be broken by a quantum computer. Quantumly, a slight generalization of Shor's algorithm gives an efficient algorithm for HSP for all Abelian groups. Kitaev (8,16,17) developed a quantum algorithm for the Abelian Stabilizer problem, another instance of the HSP, using phase estimation, which corresponds in a way to the QFT and also solves the HSP over Abelian groups. Using the Abelian HSP Hallgren (18) gives a polynomial time quantum algorithm for Pell's equation, a number theoretic problem known to be at least as hard as factoring. Among other applications of the HSP, Friedl et al. (19) solve the hidden translation problem: given two functions f and g defined over some group images such that f(x) = g(x + t) for some hidden translation t, find t.

One of the most interesting challenges since Shor is to design quantum algorithms for the non‐Abelian HSP. For instance, an efficient solution for the symmetric group Sn (permutations of n elements) would give an efficient algorithm for the graph isomorphism problem: to determine whether two given graphs are equal up to permutation of the vertices. Another important problem is the HSP over the dihedral group DN (the group of symmetries of a regular N‐gon). A solution in this case would give an algorithm for the shortest vector problem in a lattice; this reduction was shown by Regev (20). The shortest vector problem is at the base of several classical cryptographic schemes designed as an alternative to those based on factoring or discrete logarithm.

In the context of the HSP over any group, Ettinger, Høyer, and Knill (21) showed that a polynomial amount of coset states of the form

equation

(compare with Eq. 6.2) are enough to theoretically obtain all the information about the hidden subgroup H. However, to extract this information they need exponential amount of time in the worst case; hence this algorithm is not efficient in general. For the HSP over the dihedral group images Kuperberg (22) gives a quantum algorithm that runs in time images , a quadratic improvement in the exponent over (21) (and over any classical algorithm). There has been a lot of effort in analyzing the performance of quantum Fourier sampling (Figure 6.4), when the QFT is the Fourier transform over the group G, when the hidden subgroup H is a subgroup of G. In the case of the symmetric group, the (non‐Abelian) QFT is efficiently implementable by a quantum computer (23); however a series of papers (24–27) showed that this approach to the problem cannot work (in the case of measurements of one or two copies on the state in step 4 in Figure 6.4). It is an open question whether there are any efficient quantum algorithms for the HSP using other tools, not necessarily based on the QFT.

6.5.2 Search Algorithms

Several quantum algorithms that use Grover's search as a subroutine have been found and shown to have a polynomial speed up over their classical counterparts. For example, Brassard et al. (28) give a quantum algorithm for the problem of finding collisions in a k‐to‐1 function. For a k‐to‐1 black‐box function f the task is to find a collision, that is, two inputs x ≠ y such that f(x) = f(y). The idea is to first classically query a set K of size |K| = (N/k)1/3 and check it for collisions, which can be done with O((N/k)1/3) queries. If a collision is found the algorithm outputs it and stops, otherwise we set up a Grover search for a function f defined outside K that is 1 if there is a collision with an element in K. In that case there are (k − 1)|K| ≈ k 2/3 N 1/3 “marked items” and Grover's search runs in time images . So the total number of queries of this algorithm is O((N/k)1/3), better than any classical algorithm.

Other applications of Grover's algorithm include deciding whether all elements in the image of a function on N inputs are distinct (29), which can be done in time O(N 3/4) with Grover's algorithm as a subroutine. Note that recently a better quantum algorithm based on quantum walks has been given for this problem (30) (see the next section). In (31) optimal quantum algorithms for graph problems such as (strong) connectivity, minimum spanning tree and shortest path are given using Grover's search.

6.5.3 Other Algorithms

Most known quantum algorithms are based on either the QFT or Grover's search. A few quantum algorithms fall outside these two frameworks. One such remarkable algorithm is for searching in an ordered list, a problem that classically takes time log2 N + O(1). Two quantum algorithms have been given for this problem, both based on binary trees. The best known algorithm by Farhi et al. (32) finds a good quantum algorithm on a small subtree and then recurses, running with 0 .526 log2 N queries. A very appealing algorithm was given by Høyer et al. (33) using the Haar transform on the binary tree with log3 N + O(1) ≈ 0 .631 log2 N + O(1) queries; a very interesting application of alternative efficient quantum transformations outside the QFT.

6.6 Recent Developments

We have seen that two types of quantum algorithms dominate the field, those that implement a version of the HSP or use the QFT and those that use a version of Grover's search. Recently, two alternative trends have entered the field, which we will briefly outline.

6.6.1 Quantum Walks

One of the biggest breakthroughs in classical algorithm design was the introduction of randomness and the notion of a probabilistic algorithm. Many problems have good algorithms that use a random walk as a subroutine. To give just one example, the currently best algorithm to solve 3SAT (34) is based on a random walk. Keeping this motivation in mind, quantum analogues of random walks have been introduced. There exist two different models of a quantum walk, the continuous‐time model introduced in (35) and the discrete‐time model of (36,37). The continuous model gives a unitary transformation directly on the space on which the walk takes place. The discrete model introduces an extra coin register and defines a two‐step procedure consisting of a “quantum coin flip” followed by a coin‐controlled walk step. The quantities important for algorithm design with random walks are their mixing time – the time it takes to be close to uniformly distributed over the domain – and the hitting time – the expected time it takes to hit a certain point. These quantities have been analyzed for several graphs in both the continuous and the discrete model. It turns out that a quantum walk can speed up the mixing time up to quadratically with respect to its classical counterpart; so the classical and quantum performance are polynomially related. The hitting behavior of a quantum walk, however, can be very different from classical. It has been shown that there are graphs and two vertices in them such that the classical hitting time from one vertex to the other is polynomial in the number of vertices of the graph, whereas the quantum walk is exponentially faster. Using this idea in (38) an (artificial) problem is constructed for which a quantum walk based algorithm gives a provable exponential speed‐up over any classical probabilistic algorithm. It is open whether quantum hitting times can be used to speed up classical algorithms for relevant problems.

Based on this work a quantum walk algorithm has been introduced in (39) for the problem of finding a marked vertex in a graph. The idea is very simple: the algorithm starts in the uniform superposition over all vertices. At each step it performs a quantum walk; there are two local rules for the walk, at an unmarked vertex the walk proceeds as usual, but at a marked vertex a different transition rule is applied (usually at an unmarked vertex a quantum coin is flipped and at a marked vertex it is not flipped). It turns out that after some time the amplitude of the state concentrates in the marked item(s); a measurement finds a marked item with high probability.

This algorithm solves Grover's problem on a graph. Why do we need a quantum walk search if we have Grover's algorithm? It turns out that there are situations when the diffusion step R Ψ of Grover's algorithm cannot be implemented efficiently (because the local topology of the database does not allow for it, because of limitations on the quantum gates or because it is too costly in a query setting). A quantum walk only makes local transitions and can be more advantageous. One example is the search for a marked item in a two‐dimensional database. In this case Grover's algorithm requires images queries, but to shift amplitude from one item of the database to another on the grid takes an additional images steps on average per query. The net complexity of the algorithm becomes images and the quantum advantage is lost. The quantum walk algorithm has been shown to find a marked item in time O(images log N) (40).

A second example of the superiority of the quantum walk search over Grover's algorithm has been given in (30). Ambainis uses a quantum walk to give an improved algorithm for element distinctness, which runs in optimal time O(N 2/3), thus improving over Grover‐based algorithms for this problem (which runs in time O(N 3/4), see Section 6.5). Several new quantum walk based algorithms with polynomial improvements over Grover‐based algorithms have followed suit. For references on quantum walks, see (41,42).

6.6.2 Adiabatic Quantum Algorithms

Another recent alternative for algorithm design has been the introduction of adiabatic quantum algorithms by Farhi et al. (43) The idea is as follows: many optimization and constraint satisfaction problems can be encoded into a sum of local Hamiltonians images such that each term Hi represents a local constraint. The ground state of H violates the smallest number of such constraints and represents the desired optimal solution. In order to obtain this state, another Hamiltonian H′ is chosen such that the ground state of H′, |Φ′〉, is easy to prepare. An adiabatic algorithm starts in the state |Φ′〉 and applies H′. The Hamiltonian is then slowly changed from H′ to H, usually in a linear fashion over time, such that the Hamiltonian at time t is given by H(t) = (1 − t/T)H′ + (t/T)H. Here T is the total runtime of the algorithm. If this is done slowly enough, the adiabatic theorem guarantees that the state at time t will be the ground state of H(t), leading to the solution, the ground state of H, at time T. The instantaneous ground state of the system is “racked.” But how slow is slow enough? The adiabatic theorem gives bounds on the speed of change of H(t) such that the state remains close to the ground state. These bounds are determined by the energies of the Hamiltonian H and by the inverse gap of the Hamiltonians H(t). The gap of a Hamiltonian is the energy difference between its ground state and first excited state, or the difference between its smallest and second smallest eigenvalue when viewed as a matrix. To design an efficient adiabatic algorithm, one has to pick H and H′ such that the gap of H(t) at all times t is at least inverse polynomial in the size of the problem.

Farhi et al. set up adiabatic algorithms for NP‐complete problems like 3SAT (43). It has been impossible so far to determine the gap analytically and the number of qubits in numerical simulations is limited. However, this approach seems promising, even though there is now mounting evidence that an adiabatic algorithm cannot solve NP‐complete problems efficiently. For instance, quantum unstructured search has been implemented adiabatically and shown to have to same runtime as Grover's algorithm (44,45).

It is not hard to see that an adiabatic algorithm can be simulated efficiently with a quantum circuit (43) – one needs to implement a time‐dependent unitary that is given by a set of local Hamiltonians, each one acting only on a few qubits. Recently it has been shown (46) that also any quantum circuit can be simulated efficiently by an appropriate adiabatic algorithm; hence these two models of computation are essentially equivalent. This means that a quantum algorithm can be designed in each of the two models. The advantage of the adiabatic model is that it deals with gaps of Hermitian matrices, an area that has been widely studied both by solid state physicists and probabilists. Hopefully this new toolbox will yield new algorithms.

Exercises

  1. 6.1 Universality.

    Give an implementation of the n‐qubit gate C[P] in Grover's algorithm C[P] = 2 |0 … 0〉 〈0 … 0| − In in terms of the elementary one‐ and two‐qubit gates from the universal set {X, PI/8, H, CNOT} (see Section 6.1).

  2. 6.2 Bernstein–Vazirani algorithm (47).

    Give a quantum algorithm for the following problem. Given a function fa : {0, 1} n → {0, 1}, fa (x) = a · x(=images ) for some a ∈ {0, 1} n , find a with one query only. How many queries are needed in a classical deterministic algorithm? In a classical probabilistic algorithm?

  3. 6.3 QFT with bounded precision.

    Quantum gates cannot be implemented with perfect precision. Define the error of a gate U that is supposed to implement V as E(U, V) := max |v〉:‖|v〉‖=1 ||(U − V)|v〉||. We have seen an implementation of the QFT over ℤ N with about images gates.

    1. Show: If each gate in the QFT is implemented with error at most ɛ for some ɛ > 0, then this circuit approximates the QFT with error O(log2 N/ɛ).
    2. Give a circuit with only O(log N log log N) gates that for any c > 1 approximates the QFT to within error 1/log c N.
  4. 6.4 Grover with several marked items.

    First, compute the runtime of Grover's algorithm when there are exactly k marked items and k is known in advance. Then, give an algorithm for Grover's problem when the number of marked items is not known.

  5. 6.5 Minimum finding (48).

    Given N distinct integers, design a quantum algorithm that finds their minimum with O(images log N) queries. Hint: Pick a random element and use O(log N) rounds. In each round use Grover's search to replace this element with another one that is smaller.

References

  1. 1 Feynman, R. (1982) Simulating physics with computers. Int. J. Theor. Phys., 21, 467–488.
  2. 2 Feynman, R. (1985) Quantum mechanical computers. Opt. News, 11, 11–21.
  3. 3 Deutsch, D. (1985) Quantum theory, the Church–Turing principle and the universal quantum computer. Proc. Phys. Soc. London, Sect. A, 400, 97–117.
  4. 4 Bennett, C. (1973) Logical reversibility of computation. IBM J. Res. Dev., 17, 5225.
  5. 5 Toffoli, T. (1980) Reversible computing, in Automata, Languages and Programming (eds W. de Bakker and J. van Leeuwen), Springer, New York, p. 632.
  6. 6 Deutsch, D., Barenco, A., and Ekert, A. (1995) Universality in quantum computation. Proc. Phys. Soc. London, Sect. A, 449, 669.
  7. 7 DiVincenzo, D.P. (1995) Two‐bit gates are universal for quantum computation. Phys. Rev. A, 51 (2), 1015–1022.
  8. 8 Kitaev, A.Y., Shen, A.H., and Vyalyi, M.N. (2002) Classical and Quantum Computation, (Number 47 in Graduate Series in Mathematics), AMS, Providence, RI.
  9. 9 Nielsen, M.A. and Chuang, I.L. (2000) Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, UK.
  10. 10 Deutsch, D. and Jozsa, R. (1992) Rapid solution of problems by quantum computation. Proc. Phys. Soc. London, Sect. A, 439, 553–558.
  11. 11 Simon, D. (1997) On the power of quantum computation. SIAM J. Comput., 26 (5), 1474–1483. preliminary version in Proceedings of the 26th ACM Symposium on Theory of Computing (STOC), pp. 116–123, 1994.
  12. 12 Shor, P.W. (1997) Polynomial‐time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26 (5), 1484–1509. preliminary version in Proceedings of the 35th Annual IEEE Symposium on the Foundations of Computer Science (FOCS), pp. 124–134, 1994.
  13. 13 Preskill, J. (1998) Quantum Information and Computation. Lecture Notes, http://www.theory.caltech.edu/people/preskill/ph229/ (accessed 06 November 2017).
  14. 14 Grover, L. (1996) A fast quantum mechanical algorithm for database search. Proceedings of the 28th ACM Symposium on Theory of Computing (STOC), pp. 212‐219.
  15. 15 Grover, L.K. (1997) Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 79, 325.
  16. 16 Kitaev, A. (1995) Quantum measurements and the Abelian stabilizer problem, Preprint quant‐ph/9511026.
  17. 17 Kitaev, A.Y. (1997) Quantum computations: algorithms and error corrections. Russ. Math. Surv., 52, 1191–1249.
  18. 18 Hallgren, S. (2002) Polynomial‐time quantum algorithms for Pell's equation and the principal ideal problem. Proceedings of the 34th ACM Symposium on Theory of Computing (STOC), pp. 653‐658.
  19. 19 Friedl, K., Ivanyos, G., Magniez, F., Santha, M., and Sen, P. (2003) Hidden translation and orbit coset in quantum computing. Proceedings of the 35th ACM Symposium on Theory of Computing (STOC), pp. 1‐9.
  20. 20 Regev, O. (2002) Quantum computation and lattice problems. Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 520‐529.
  21. 21 Ettinger, M., Høyer, P., and Knill, E. (2004) Hidden subgroup states are almost orthogonal. Inf. Process. Lett., 91 (1), 43–48.
  22. 22 Kuperberg, G. (2005) A subexponential‐time algorithm for the dihedral hidden subgroup problem. SIAM J. Comput., 35 (1), 170–188.
  23. 23 Beals, R. (1997) Quantum computation of Fourier transforms over symmetric groups. Proceedings of the 29th STOC, pp. 48‐53.
  24. 24 Grigni, M., Schulman, L., Vazirani, M., and Vazirani, U. (2001) Quantum mechanical algorithms for the nonabelian hidden subgroup problem. Proceedings of the 33rd ACM Symposium on Theory of Computing (STOC), pp. 68–74.
  25. 25 Hallgren, S., Russell, A., and Ta‐Shma, A. (2000) Normal subgroup reconstruction and quantum computation using group representations. Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), pp. 627‐635.
  26. 26 Kempe, J. and Shalev, A. (2005) The hidden subgroup problem and permutation group theory. Proceedings of the 16th ACM‐SIAM Symposium on Discrete Algorithms (SODA), pp. 1118‐1125.
  27. 27 Moore, C., Russell, A., and Schulman, L. (2005) The symmetric group defies strong Fourier sampling. Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 479‐490.
  28. 28 Brassard, G., Hoyer, P., and Tapp, A. (1998) Quantum cryptanalysis of hash and claw‐free functions. Proceedings of the 3rd Latin American Symposium on Theoretical Informatics (LATIN), (number 1380 in LNCS), pp. 163‐169.
  29. 29 Buhrman, H., Dürr, C., Heiligman, M., Høyer, P., Magniez, F., Santha, M., and de Wolf, R. (2005) Quantum algorithms for element distinctness. In Proceedings of the 15th IEEE Conference on Computational Complexity. Extended version in. SIAM J. Comput., 34 (6), 1324–1330.
  30. 30 Ambainis, A. (2004) Quantum walk algorithm for element distinctness. Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 22‐31, (Preprint quant‐ph/0311001).
  31. 31 Dürr, C., Heiligman, M., Høyer, P., and Mhalla, M. (2004) Quantum query complexity of some graph problems. Proceedings of the 31st International Colloquium on Automata, Languages, and Programming (ICALP), (number 3142 in LNCS), pp. 481‐493.
  32. 32 Farhi, E., Goldstone, J., Gutmann, S., and Sipser, M. (1999) Invariant Quantum Algorithms for Insertion into an Ordered List. Technical Report 1999 , (Preprint quant‐ph/9901059).
  33. 33 Høyer, P., Neerbeck, J., and Shi, Y. (2002) Quantum complexities of ordered searching, sorting and element distinctness. Algorithmica, 34 (4), 429–448. (Special issue in Quantum Computation and Cryptography).
  34. 34 Schöning, U. (1999) A probabilistic algorithm for k‐SAT and constraint satisfaction problems. 40th IEEE Annual Symposium on Foundations of Computer Science, New York, pp. 410‐414.
  35. 35 Farhi, E. and Gutmann, S. (1998) Quantum computation and decision trees. Phys. Rev. A, 58, 915–928.
  36. 36 Aharonov, D., Ambainis, A., Kempe, J., and Vazirani, U. (2001) Quantum walks on graphs. Proceedings of the 33th ACM Symposium on the Theory of Computing (STOC), pp. 50‐59.
  37. 37 Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., and Watrous, J. (2001) One‐dimensional quantum walks. Proceedings of the 33rd ACM Symposium on the Theory of Computing (STOC), New York, NY, pp. 60‐69.
  38. 38 Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., and Spielman, D.A. (2003) Exponential algorithmic speedup by a quantum walk. Proceedings of the 35th ACM Symposium on the Theory of Computing (STOC), pp. 59‐68.
  39. 39 Shenvi, N., Kempe, J., and Whaley, K.B. (2003) A quantum random walk search algorithm. Phys. Rev. A, 67 (5), 052307.
  40. 40 Ambainis, A., Kempe, J., and Rivosh, A. (2005) Coins make quantum walks faster. Proceedings of the 16th ACM‐SIAM Symposium on Discrete Algorithms (SODA), pp. 1099‐1108.
  41. 41 Ambainis, A. (2004) Quantum search algorithms (survey). SIGACT News, 35 (2), 22–35.
  42. 42 Kempe, J. (2003) Quantum random walks – an introductory overview. Contemp. Phys., 44 (4), 302–327.
  43. 43 Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., and Preda, D. (2001) A quantum adiabatic evolution algorithm applied to random instances of an NP‐complete problem. Science, 292 (5516), 472–476.
  44. 44 van Dam, W., Mosca, M., and Vazirani, U. (2001) How powerful is adiabatic quantum computation? Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 279‐287.
  45. 45 Roland, J. and Cerf, N. (2002) Quantum search by local adiabatic evolution. Phys. Rev. A, 65, 042308.
  46. 46 Aharonov, D., van Dam, W., Kempe, J., Landau, ℤ., Lloyd, S., and Regev, O. (2004) Adiabatic quantum computation is equivalent to standard quantum computation. Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 42‐51.
  47. 47 Bernstein, E. and Vazirani, U. (1997) Quantum complexity theory. SIAM J. Comput., 26, 1411.
  48. 48 Dürr, C. and Høyer, P. (1996) A Quantum Algorithm for Finding the Minimum. Technical Report 1996, (Preprint quant‐ph/9607014).
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset