Quantum Algorithm Design Techniques and Applications

See discussions, stats, and author profiles for this publication at: https://www.researchgate.
net/publication/331097538
Quantum Algorithm Design: Techniques and Applications
Article in Journal of Systems Science and Complexity · February 2019

DOI: 10.1007/s11424-019-9008-0
CITATIONS READS
7 989
3 authors, including:
Changpeng Shao
University of Bristol
29 PUBLICATIONS 30 CITATIONS
SEE PROFILE
Some of the authors of this publication are also working on these related projects:
Quantum computing View project
All content following this page was uploaded by Changpeng Shao on 18 February 2019.
The user has requested enhancement of the downloaded file.

J Syst Sci Complex (2019) 32: 375–452
Quantum Algorithm Design: Techniques and

Applications∗
SHAO Changpeng · LI Yang · LI Hongbo
DOI: 10.1007/s11424-019-9008-0
Received: 9 October 2018 / Revised: 31 December 2018
The
c Editorial Office of JSSC & Springer-Verlag GmbH Germany 2019
Abstract In recent years, rapid developments of quantum computer are witnessed in both the hard-
ware and the algorithm domains, making it necessary to have an updated review of some major tech-
niques and applications in quantum algorithm design.
In this survey as well as tutorial article, the authors first present an overview of the development
of quantum algorithms, then investigate five important techniques: Quantum phase estimation, linear
combination of unitaries, quantum linear solver, Grover search, and quantum walk, together with their
applications in quantum state preparation, quantum machine learning, and quantum search. In the
end, the authors collect some open problems influencing the development of future quantum algorithms.
Keywords Quantum algorithm, quantum computation, quantum machine learning, quantum search,
quantum walk.
1 Overview: Development of Quantum Algorithms

Quantum computer is based on a computational model obeying the laws of quantum me-
chanics. Quantum computing is regarded as a highly promising research direction in computer
science. Applications of quantum computing range from breaking cryptographic systems to
solving real-world problems related to big data, AI, communication, new medicine and mate-
rial, etc. Although large-scale general-purpose quantum computers are still not in existence,
the theory of quantum algorithms, i.e., algorithms that run on quantum computer, has been an
active research field for over 30 years.
SHAO Changpeng · LI Yang · LI Hongbo (Corresponding author)
Academy of Mathematics and Systems Science, University of Chinese Academy of Sciences, Chinese Academy
of Sciences, Beijing 100190, China.
Email: shaochangpeng11@mails.ucas.ac.cn; liyang815@mails.ucas.ac.cn; hli@mmrc.iss.ac.cn.
∗ This research was supported partially by the National Natural Science Foundation of China under Grant No.
11671388, CAS Project QYZDJ-SSW-SYS022, and GF S&T Innovation Special Zone Project.
This paper was recommended for publication by Editor-in-Chief GAO Xiao-Shan.
376 SHAO CHANGPENG · LI YANG · LI HONGBO
1.1 Early History

In 1980, Benioff[1] first pointed out the possibility of constructing a computer based on
quantum mechanics. Nevertheless, his model is essentially equivalent to the traditional Turing
machine. In 1982, Feynman[2] discussed a quantum computer model that can simulate quantum
mechanics. According to Feynman, quantum computer should have a computational mechanism
that obeys the laws of quantum mechanics.
In 1985, Deutsch[3] proposed the first quantum Turing machine model with more detailed
theory than Feynman’s. In 1989, Deutsch[4] also presented a theory of quantum gates as
another model of quantum computer: The quantum circuit model. In 1993, Yao[5] proved the
equivalence of quantum circuit model and quantum Turing machine. In 1993, Bernstein and
Vazirani[6] developed a universal quantum Turing machine model. They proved that quantum
Turing machine has at least the same computational power as traditional Turing machine.
Their research initiated the investigation of the theoretical computational aspect of quantum
computer.
The first quantum algorithm was proposed by Deutsch[3] in 1985. It is for the problem of
judging whether a function from Z2 to itself is constant. Deutsch’s algorithm only needs to
make one call of the function. In contrast, any classical algorithm requires two calls of the
function. In 1992, Deutsch and Jozsa[7] further generalized the problem to the following: judge
whether a function from Zn2 to Z2 is constant or balanced (two-valued, one for half the domain
of definition), based on the prior knowledge that the function is either constant or balanced.
The new quantum algorithm still makes query to the function only once. It is deterministic and
exponentially faster than any possible deterministic classical algorithm for solving this problem.
The underlying problems of the two quantum algorithms may be insignificant; however, they are
simple examples demonstrating the advantages of quantum superposition and entanglement.
In 1994, Simon[8] presented a quantum algorithm to solve a computational problem artifi-
cially contrived by himself. This algorithm is also exponentially faster than any possible classical
algorithm for solving this problem. Simon’s algorithm is more convincing than Deutsch-Jozsa’s
algorithm in demonstrating the supremacy of quantum computer.
Simon’s algorithm inspired Shor’s work on prime factorization and discrete logarithm[9] ,
the famous Shor’s algorithm. It is Shor’s algorithm that shocked the world with the power of
quantum computing: RSA and Diffie-Hellman cryptosystems can both be broken by a universal
quantum computer.
1.2 Hidden Subgroup Problem

In 1995, Kitaev[10] noticed that the problems dealt with by Deutsch-Jozsa’s algorithm and
Simon’s algorithm fit in a unified framework called Hidden Subgroup Problem (HSP). In the
same paper, Kitaev proposed a method of quantum phase estimation to estimate the eigenvalues
of unitary operators, which is nowadays a fundamental technique to design quantum algorithms.
Let G be a finite group, f be a map from G to a set X, such that there exists a subgroup H
of G, called the hidden subgroup, with the property that f (x) = f (y) whenever xy −1 ∈ H. The
HSP is to find a generator of H, with f as the “hiding” function. In 2004, Ettinger, et al.[11]
QUANTUM ALGORITHM DESIGN 377
proved that for an arbitrary group, the HSP is solvable by a polynomial number of evaluations
of the hiding function. The existence of time-efficient quantum algorithms for solving the HSP
for arbitrary groups is still open.
For finite Abelian groups, the HSP can be solved in polynomial time by the so-called stan-
dard method[12] . So any problem that can be transformed into an Abelian HSP can be solved
efficiently in quantum computer. There are two important algorithms within this framework.
The first is a polynomial-time quantum algorithm to solve Pell’s equation[13] , which can break
Buchmann-Williams key-exchange protocol. The second is a polynomial-time quantum algo-
rithm to compute the discrete logarithm over elliptic curve[14] , which can break ECDH and
ECDSA.
From 1995 to 2005, a variety of time-efficient quantum algorithms for solving the HSP of
certain non-Abelian groups were proposed, such as the semi-product groups[15–19] , the near-
Hamiltonian groups[20] , the normal subgroups[21, 22] , the almost Abelian groups[23] , etc. Two
kinds of important non-Abelian groups are the symmetric groups and the dihedral groups. For
the HSP of the two groups, no time-efficient quantum algorithm is found.
1.3 (Sub-)Exponential Speedup Quantum Algorithms for Breaking Cryptosys-

tems
Besides Shor’s algorithm and the standard method for Abelian HSP, in 2006 another quan-
tum algorithm was proposed by van Dam, et al.[24] , which broke the algebraically homomorphic
cryptosystem designed in [25] (the cryptosystem can also be broken by Shor’s discrete logarithm
algorithm). In their algorithm, van Dam, et al. used quantum Fourier transform to solve the
shifted Legendre symbol problem.
Using Simon’s algorithm to break cryptosystems started around 2010-2012. Kuwakado and
Morii showed that the 3-round Feistel cipher with internal permutations[26] and Even-Mansour
cipher[27] , can be broken with quantum superposition queries. In 2016, Santoli and Schaffner[28]
used Simon’s algorithm to attack symmetric-key cryptographic primitives. In the same year,
Kaplan, et al.[29] discovered that the most widely used modes of operation for authentication
and authenticated encryption (such as CBC-MAC, PMAC, GMAC, GCM, OCB, etc.), and
CAESAR candidates of authenticated encryption schemes (such as CLOC, AEZ, COPA, OTR,
POET, OMD, Minalpher, etc.), can be broken with quantum superposition queries.
Besides quantum algorithms with exponential speedup, some other algorithms with sub-
exponential speedup were also proposed for quantum cryptanalysis. There are two representa-
tives in this category.
Ajtai-Dwork cryptosystem[30, 31] is based on the computational difficulty of poly(n)-unique-
SVP problem[32] . In 2004, Kuperberg[18] proposed a quantum algorithm for the HSP of dihedral
groups, which solves the poly(n)-unique-SVP problem in sub-exponential time.
Finding an isogeny (a dense morphism of varieties preserving basepoints) between two ellip-
tic curves over a finite field that have the same cardinality and endomorphism ring, is another
problem with computational difficulty, for which the fastest known classical algorithm[33] takes
exponential time. The isogeny-based elliptic curve cryptography[34–36] is based on the com-
putational difficulty of this problem. By assuming the correctness of Generalized Riemann

Hypothesis, in 2014 Childs, et al.[37] proposed a sub-exponential time quantum algorithm to
compute the isogenies.
1.4 Grover’s Search Algorithm

In 1996, an important quantum algorithm for unstructured search was invented. This is
Grover’s algorithm[38] , which achieves quadratic speedup over classical search algorithms.
Given a finite set Ω and an oracle to query an element of Ω , let there be a nonempty subset
M of Ω composed of marked items. Grover’s algorithm can find an item of M by applying

O( |Ω |/|M|) times of the oracle. In 1997–1999, it was proved that Grover’s algorithm is
optimal for the search problem[39, 40] . When the number of marked items is known, then
Grover’s algorithm can be modified to be deterministic[41] .
Grover’s algorithm provides polynomial speedup for a large variety of important problems,
such as the 3-SAT problem[42–44] , the lattice shortest vector problem[45] , Hamiltonian cycle
problem[12] , multivariate quadratic equation solving[46] , weight decision[47] , matrix product
computing over semi-ring[48] , finding the minimum of a data set[49, 50] , etc. As an applica-
tion of Grover’s algorithm, in 1998 Brassard, et al.[51] proposed a quantum algorithm for the
counting problem to estimate the number |M| of marked items in set Ω . It returns an integer

k such that |1 − |M| k
| ε by applying O(ε−1 |Ω |/M) times of the oracle. In 2000, Brassard,
et al.[52] generalized Grover’s algorithm to a general technique in quantum algorithms called
amplitude amplification.
In the field of quantum cryptanalysis, in 1998 Brassard, et al.[53] applied Grover’s algorithm
to solve the collision problem, and achieved cubic speedup over classical algorithms. Their algo-
rithm is also optimal to this problem[54] . As a consequence, attacking cryptographic protocols
built on collision-resistant hash functions by quantum computer is faster. For example, break-
ing SHA-1 for a 160-bit hash function requires 263 operations on a classical computer[55, 56] ;
the number of operations is reduced to approximately 253.33 on a quantum computer.
NTRUEncrypt[57] is a public-key encryption system that is immune to attacks by Shor’s
algorithm. It is available as a free-for-noncommercial-use library from Security Innovation.
In 2015, Fluhrer[58] applied Grover’s algorithm to attack the encryption performed by this
library. For (EES401EP2, EES439EP1, EES593EP1, EES743EP1), the key recovery attacks
by classical computer vs. quantum computer require the following operations respectively:
(2112 vs. 2104 , 2128 vs. 2112 , 2192 vs. 2137 , 2256 vs. 2197 ); for plaintext recovery attacks, the
data are (2112 vs. 280 , 2128 vs. 280 , 2192 vs. 2128 , 2256 vs. 2128 ).
1.5 Quantum Walk

Random walk is a random process that models a walker on the vertices (or distribution of
vertices) of a graph. At every step of the process, the walker chooses a neighbor of the current
vertex at random and moves to that neighbor. It is a powerful classical algorithmic tool for
searching and sampling.
As the quantum counterpart, quantum walk is not only a powerful framework for design-
ing quantum algorithms, but a universal model of quantum computation[59] . Many important
problems, such as graph collision problem[60] , single-source shortest path[61–64] , search on the
grid[65–68] , NAND tree evaluation[69–73] , forbidden subgraph property[74] , triangle finding[60, 75, 76] ,
subset sum problem[77] , element distinctness problem[78] , group commutativity test[79] , matrix
product verification[80] , Boolean matrix multiplication[81] , algebraic property test[82] , etc., can
be solved by quantum walk more efficiently by constructing suitable graphs.
There are two models of quantum walk: Discrete-time and continuous-time. A discrete-
time quantum walk consists of two quantum systems: A walker and a coin, together with an
evolution operator which works only in discrete-time steps. A continuous-time quantum walk
consists of a walker and a Hamiltonian operator of the system that works any time.
In 1985, when Feynman proposed the concept of quantum computer[83] , he made another
proposal that was later interpreted as a continuous-time quantum walk[84] . The definition of
continuous-time quantum walk was given by Farhi, et al.[85] in 1998. As for discrete-time
quantum walk, in 1996, Meyer’s work[86] on quantum cellular automata already involved a
walker in quantum superposition. In 2000, Nayak, et al.[87] gave the definition of discrete-
time quantum walk by introducing the coin state. The relationship between continuous- and
discrete-time quantum walks was investigated by Strauch[88] and Childs[89] . The results show
that continuous-time quantum walk can be obtained as a limit of discrete-time quantum walks.
Early research works focused on investigating the difference of quantum walk from random
walk. In [87, 90, 91], two features different from random walk were disclosed. The first is
the quantum mixing time describing the speed of convergence to the uniform distribution,
and the second is the quantum hitting time describing the speed of reaching the marked set.
Sometimes, the mixing and hitting time of a random walk can be respectively quadratically
and exponentially longer than their quantum counterparts.
For the search problem on the hypercube, a quantum algorithm based on discrete-time
quantum walk was proposed by Shenvi, et al.[92] in 2003. The algorithm is quadratically faster
than classical algorithms for the same problem. For the traverse problem on glued tree graphs,
a quantum algorithm based on continuous-time quantum walk was proposed by Childs, et
al.[93, 94] in 2002–2003. The algorithm is exponentially faster than any (not necessarily random
walk based) classical algorithm.
One of the most important quantum walk algorithms was proposed by Ambainis[78] in 2007,
which is an optimal quantum algorithm for solving the element distinctness problem[54] . Later
in the same year, Szegedy[95] generalized Ambainis’ idea and proposed a general framework of
quantum walk on edges, which nowadays plays an important role in spatial search. For any
symmetric and ergodic Markov chain, Szegedy’s framework achieves quadratic speedup over
classical algorithms for the detection problem.
Besides Szegedy’s framework, another commonly used quantum walk framework on edges
was proposed by Magniez, et al.[96] in 2011. This is the well-known MNRS framework. Based
on this framework, many fast quantum algorithms were discovered, such as the algorithms for
triangle finding[60] , group commutativity test[79] , algebraic property test[82] , etc.
To obtain higher speedup, a quantum walk can be constructed inside another. This idea
leads to the so-called nested quantum walk framework[61] . In 2013, Childs, et al.[97] proposed a
nested quantum walk algorithm to solve the element 3-distinctness problem, which is better than
applying Ambainis’ element distinctness algorithm directly to element 3-distinctness problem.
1.6 Hamiltonian Simulation

Hamiltonian simulation is to find a quantum circuit that performs the unitary operation
e−iHt with error at most ε, where Hamiltonian H is an n × n Hermitian matrix with sparsity d,
and t is the time variable. Hamiltonian simulation is not only for simulating quantum systems,
but also an important subroutine in designing fast quantum algorithms[69, 93, 98, 99] .
In the black-box oracle model, there is an oracle to query the entries of a Hamiltonian
matrix. This model defines the query complexity of a Hamiltonian simulation.
The first quantum algorithm for simulating local Hamiltonians was given by Lloyd[100] in
1996, where the Hamiltonian is assumed to have a tensor product structure, so that the first

order Lie product formula[101] can be used. The algorithm has query complexity O (poly log n)

(Hsp t)2 /ε , where the spectral norm of a matrix A is defined as follows:
Asp := max Ax. (1.1)

x=1
In this paper, the norm refers to the L2 -norm (Frobenius norm) of a vector or matrix: for
any vector v = (v1 , · · · , vn )rmT and matrix A = (aij ),

v := |vi | ,
2 A := |aij |2 . (1.2)
i i,j
In 2003, Aharonov and Ta-Shma[102] generalized Lloyd’s algorithm substantially to simu-

late sparse Hamiltonians, by replacing the requirement of tensor product structure with two
requirements: 1) H is sparse, 2) there is an efficient method to calculate the nonzero entries
in any column of the Hamiltonian matrix. The latter requirement is called the sparse model
assumption, which is also satisfied by the Hamiltonian with tensor product structure in Lloyd’s
√
algorithm. Aharonov, et al.’s algorithm has query complexity O poly(d, log n)(Hsp t)3/2 / ε .
By applying the k-th order Lie product formula, in 2007 Berry, et al.[103] improved the result
1
of Aharonov, et al. to O 52k d4+ 2k
1
t(t/ε) 2k . In 2010, Childs and Kothari[104] further improved
1
the result of Berry, et al. by reducing the exponent of d to 3 + 2k .
Besides the Lie product formula, quantum walk can also be used in Hamiltonian simulation.
In 2012, Berry and Childs[105] proposed a quantum algorithm for Hamiltonian simulation, with
√
query complexity O dHmax t/ ε , where Hmax := maxi,j |Hij | is the maximum norm.
By Taylor expansion, e−iHt can be approximated by a polynomial in H. So the third
approach to simulate H is to implement a matrix polynomial approximating e−iHt . Following
this approach, in 2015 Berry, et al.[106] proposed an algorithm with query complexity
2

t t
O d2 Hmaxt log log log . (1.3)
ε ε
The algorithm achieves exponential speedup in parameter 1/ε. Later in the same year, in [107]
the dependence on d in (1.3) was decreased to be linear.
In conclusion, for any sparse Hamiltonian matrix (where d = O(log n)), the correspond-
ing Hamiltonian simulation is efficient. Currently the best algorithm for sparse Hamiltonian

simulation has query complexity O dHmax t + loglog(1/ε)
log(1/ε) , which was proposed by Low and
Chuang[108] in 2016 based on quantum signal processing and block-encoding[109, 110] .
For dense Hamiltonians (where d = O(n)), in 2010 Childs and Kothari[111] showed that

there is no general Hamiltonian simulation algorithm that uses only O poly(Hsp t, 1/ε, log n)
queries. In 2016, Rebentrost, et al.[112] presented a quantum algorithm to simulate low-rank

dense Hamiltonians with query complexity O t2 n2 H2max/ε .
Based on the memory model of storing a matrix with binary tree[113] , in 2018 Wang and
Wossnig[114] proposed a quantum algorithm for general dense Hamiltonian simulation by sin-
gular value estimation[113] and linear combination of unitaries[115] . The time complexity is
√
O t nHsp poly log(n, tHsp , 1/ε) . (1.4)
1.7 Quantum Linear Solver

Linear system solving is a basic computational task. Given a linear system Ax = b where
A is an M × M complex matrix with condition number κ, by quantum phase estimation and
Hamiltonian simulation, a quantum version of the SVD of matrix A can be obtained. Based
on this idea, in 2009 Harrow, Hassidim and Lloyd[99] proposed the first quantum algorithm to
solve sparse linear system. This is the well-known HHL algorithm. It has time complexity
O(κ2 (log M )/ε), where ε is the precision. The algorithm is exponentially faster than classical
algorithms for sparse linear system solving.
In 2012, Ambainis[116] proposed an improvement to decrease the complexity by reducing
the dependence on parameter κ to be linear. In 2017, Childs, et al.[115] further decreased the
complexity by reducing factor 1/ε to log(1/ε), using the fast Hamiltonian simulation in [107].
A linear system with large condition number is ill-posed. A classical method to cope with
ill-posed linear system is to use preconditioner[117] . In 2013, Clader, et al.[118] proposed a
preconditioned quantum algorithm to solve ill-posed linear system.
Quantum linear solver is also studied in the block-encoding framework[109] . When the block-
encoding is efficient, the complexity is linear in the condition number and logarithmic in the
precision. By singular value estimation[113] , in 2018 Wossnig, et al.[119] proposed a quantum
algorithm to solve dense linear system, with quadratic speedup over classical algorithms.
Quantum linear solver can be extended to solve nonlinear systems. In 2017, Chen and
Gao[120] proposed a quantum algorithm to solve Boolean polynomial systems, by reducing such
a system to an equivalent linear system over the complex numbers with Macaulay matrix tech-
nique. In 2018, Chen, et al.[121] further extended the algorithm to solve polynomial equations
over finite fields.
1.8 Quantum Machine Learning

The study of quantum machine learning boomed after the discovery of HHL algorithm[122, 123] .
The first application of HHL algorithm in machine learning is Wiebe, et al.’s work[124] on data
fitting, which was followed by a substantial amount of work on the same topic[109, 113, 125, 126] .
In 2013, Lloyd, et al.[127] proposed a quantum algorithm for supervised and unsupervised
classification, with exponential speedup. In 2014, Lloyd, et al.[128] proposed a method for
quantum principal component analysis. In 2014, Rebentrost, et al.[129] applied HHL algorithm
to achieve exponential speedup in least-square support vector machine.
In 2017, Rebentrost, et al.[130] proposed a quantum Hopfield neural network model. In
this model, the weight matrix is represented as a density matrix that can be simulated by the
method in [128]. The learning of the weights by minimizing the energy function is then reduced
to linear system solving.
By now quantum algorithms are found many important applications in machine learning:
neural network[131–136] , pattern recognition[137–139] , Bayesian theory[140, 141] , hidden Markov
model[142, 143] , deep learning[144, 145] , Boltzmann machine[146–148] , etc.
1.9 Robust Quantum Computing and Quantum Complexity Theory

Adiabatic quantum computing (AQC) is a class of procedures for solving optimization
problems with quantum computer. To solve a problem with AQC, suppose that an appropriate
Hamiltonian H1 can be found, so that the solution to the problem is represented as a ground
state of the Hamiltonian. An adiabatic algorithm begins with a system in the ground state of
a known and easily implementable Hamiltonian H0 . A path Ht for t ∈ [0, 1] is chosen between
the initial Hamiltonian H0 and the final Hamiltonian H1 , and the Hamiltonian is gradually
perturbed to follow this path. The theory of adiabatic quantum computation is established on
the Adiabatic Theorem[149] , which states that as long as the path is traversed slowly enough,
the system will remain in the ground state, and in the end it will be in the solution state.
AQC was first introduced by Farhi, et al.[150] in 2000. In 2001, Childs, et al.[151] showed that
AQC has some inherent protection against decoherence, meaning that it may be a particularly
good model for designing robust quantum algorithms. In 2002, Roland and Cerf[152] showed
how to recapture Grover’s algorithm and its optimality proof within the adiabatic context. In
2007, Aharonov, et al.[153] developed a model for AQC and proved its computational equivalence
with quantum circuit model.
Initial interests in AQC concentrated on the possibility of using adiabatic methods to design
quantum algorithms for some NPC problems[154–158] . Recently, AQC is used to solve some
problems in machine learning[159, 160] , graph theory[161, 162] , etc.
In 1997, Kitaev[163] proposed topological quantum computing, a more speculative approach
to quantum computing with excellent robustness. In 2003, Freedman, et al.[164] investigated the
relationship between topological quantum field theory and topological quantum computing, with
the result that on one hand, quantum computer can efficiently simulate topological quantum
field theory, on the other hand, topological quantum field theory essentially captures the power
of quantum computing.
One important application of topological quantum computing is a polynomial-time quan-

tum algorithm for the approximation of Jones polynomial[165] , which itself is a BQP-complete
problem[164] . This work inspired the creation of many efficient quantum algorithms, for prob-
lems such as approximation of the Tutte polynomial of a planar graph[166] , evaluation of the
Jones polynomial on a generalized closure of a braid[167] , computation of additive approximation
of a tensor network[168] , etc.
In computational complexity theory, BPP (bounded-error probabilistic polynomial time)
refers to the class of computational problems that can be solved efficiently by a classical com-
puter with success probability larger than 2/3. BQP (bounded-error quantum polynomial
time) is the quantum version of BPP. In 1993, Bernstein and Vazirani[6] proved the famous
result that BQP ⊆ PSPACE, the latter being all decision problems that can be solved using
polynomial space. It is conjectured[169] that BQP ∩ NPC = ∅, and NP BQP. It is also
suspected[170] that P ⊂ BQP.
In September 2018, Mahadev[171] proposed the first measurement protocol to show that a
BPP machine can interact with a BQP machine in order to verify BQP computations, based
on the assumption that the verifier may use post-quantum cryptography that the BQP prover
cannot break.
1.10 Hardware Development and Quantum Algorithm Demonstration

In 1995, Cirac and Zoller[172] developed a trapped ion quantum computer and realized
the CNOT gate. In 1997, Gershenfeld and Chuang[173] developed a 2-qubit NMR quantum
computer. In 1998, Loss and Divincenzo[174] made a new implementation of quantum computer
based on quantum dot.
In 2001, IBM developed a 7-qubit NMR quantum computer, and implemented Shor’s
algorithm[175] on it. In 2004, Pan’s group[176] demonstrated the first 5-photon entanglement
for universal quantum error correction. In 2006, the Institute for Quantum Computing and
the Perimeter Institute for Theoretical Physics in Waterloo, as well as MIT, benchmarked a
12-qubit quantum computer[177] . In 2007, D-Wave demonstrated a 28-qubit quantum annealing
computer[178] . In 2008, D-Wave produced a 128-qubit computer chip[179] .
In 2011, Monz, et al.[180] reported the creation of GHZ states with up to 14 qubits. In 2015,
D-Wave announced the breaking of the 1000-qubit barrier[181] . In 2016, Google simulated a
hydrogen molecule with an array of 9 superconducting qubits developed by the Martinis group
and UCSB[182] .
In 2017, IBM unveiled a 17-qubit quantum computer[183] , and Intel confirmed the develop-
ment of a 17-qubit superconducting test chip[184] . IBM also announced an industry-first initia-
tive to build a universal quantum computing system, called “IBM Quantum Experience”[185] ,
that enables developers and programmers to begin building interfaces between its existing 5-
qubit cloud-based quantum computer and classical computers. Coles, et al.[186] implemented
20 quantum algorithms on IBM Quantum Experience. In the same year, Pan, et al.[187] made
the first 10 entangled photons. Later in this year, IBM revealed a working 50-qubit quantum
computer that can maintain its quantum state for 90 microseconds[188] , and D-Wave released
a 2000-qubit quantum annealing computer[189] .

In 2018, Intel confirmed the development of a 49-qubit superconducting test chip[190] . In
the same year, Google announced the creation of a 72-qubit quantum chip[191] .
With the boost of quantum computer hardware, quantum algorithms are tested by exper-
iments of increasing (but still very small) scale. Table 1 collects some experiments on three
most famous quantum algorithms: Shor’s algorithm, Grover’s algorithm, and HHL algorithm.
Table 1 Experimental demonstration of quantum algorithms
Algorithm Problem solved # qubits: Technology

4: photonic[192] (2007)
factorizing 15
Shor 6: photonic[193] (2007)
7: NMR[175] (2001)
factorizing 21 5: photonic[194] (2012)
searching 1 marked item in 4 items 2: NMR[195] (1998)
Grover
searching 1 marked item in 8 items 3: NMR[196] (2000)
3: photonic[197] (2014)
HHL solving 2 × 2 linear system
4: photonic[198] (2013)
4: NMR[199] (2014)
In the development of quantum algorithms, some techniques are so important that they
become universal subroutines of many efficient algorithms. These techniques include quantum
phase estimation, quantum amplitude amplification, quantum singular value estimation, linear
combination of unitaries (LCU), classical vector input, quantum linear solver, swap test, Grover
search, Szegedy’s quantum walk, MNRS quantum walk, etc. More detailed description and
analysis of these subroutines and their applications are the content of the rest of this paper.
In Section 2, some basic terminology in quantum algorithms are presented. In Section 3, first
a detailed description of quantum phase estimation is given, then order finding and swap test
are introduced as applications of quantum phase estimation, and then LCU and its application
in quantum state preparation are investigated. In Section 4, first two major quantum linear
solvers are reviewed: HHL algorithm and singular value estimation, then an algorithm to solve
Boolean equation system is introduced as an application of HHL algorithm, and then three
aspects of quantum machine learning are investigated as applications of quantum linear solvers:
Supervised classification, linear regression, and support vector machine. In Section 5, basics
of quantum walk are introduced, together with applications in the search problems on glued
tree graphs and Boolean hypercubes. In Section 6, several frameworks of quantum search are
reviewed, together with their applications in collision problem, element distinctness problem,
and spatial search. In Section 7, several open problems and emerging research directions in
quantum algorithm design are listed.
Some earlier reviews on the development of quantum algorithms include [200–204]. Compre-
hensive introductions to quantum computing and quantum algorithm can be found in [12, 205–
207]. Previous surveys of quantum walk include [42, 208–212]. A comprehensive review of
Hamiltonian simulation is referred to [213]. Some reviews of quantum machine learning include
[68, 214–219]. A recent review of adiabatic quantum computation is [220]. A website that
collects many quantum algorithms can be found here: [221].
2 Basic Terminology in Quantum Algorithms

The following are standard notations in computational complexity. Let f, g be positive
functions in n ∈ N. Then
• f = O(g) if there exist constants c > 0 and n0 > 0 such that f (n) ≤ cg(n) for all n ≥ n0 .
• f = Ω (g) if there exist constants c > 0 and n0 > 0 such that f (n) ≥ cg(n) for all n ≥ n0 .
• f = Θ (g) if both f = O(g) and f = Ω (g).

Ω
• O, , Θ
differ from O, Ω , Θ respectively only by a logarithmic factor.
• poly(n) (or poly n) refers to a polynomial in n.
• log(n1 , · · · , nk ) refers to a product of logarithmic factors in n1 , · · · , nk respectively.
In quantum computing, the bra-ket notation or Dirac notation is standard for describing
quantum states. In this notation, a complex vector a = (a1 , · · · , an )T when representing a
quantum state, is written as |a, and its conjugate transpose a† is written as a| = (a1 , · · · , an ).
For two vectors a = (a1 , · · · , am )T and b = (b1 , · · · , bn )T , the m × n matrix
(ai bj )i=1,2,··· ,m,j=1,2,··· ,n
is denoted by |a b|. When m = n, then a|b denotes a · b. The tensor product a ⊗ b is a

column vector of dimension mn, and is written as
|ab = |a, b := |a ⊗ |b (2.1)
when representing a quantum state.

While the fundamental information unit of classical computer is “bit”, the fundamental
unit of quantum computer is quantum bit, or qubit for short. A qubit is a unit complex linear
combination of two orthonormal basis states (ground states) |0, |1 that correspond to classical
bits 0, 1 respectively. So a qubit has the form
|φ = α|0 + β|1 = α|0 + |0⊥ , (2.2)
where |0⊥ is a shorthand notation of a linear combination of quantum states orthogonal to |0.

A quantum state with n qubits is a normalized complex linear combination of several n-fold
tensor products of |0, |1. It is of the form (binary form)

|ψ = αi1 ,··· ,in |i1 · · · in , (2.3)
i1 ,··· ,in ∈{0,1}
where αi1 ,··· ,in ∈ C is the amplitude of |ψ in basis state |i1 · · · in . The basis states |i1 · · · in
are orthonormal.
n−1
By binary expression of integers, i.e., x = j=0 ij 2j for any integer 0 ≤ x < 2n , where the
ij ∈ {0, 1}, (2.3) can be written as the following integer form:
n
2 −1
|ψ = αx |x. (2.4)
x=0
When there is no need to make explicit the number of qubits, quantum state |0⊗n in binary
form is usually written as |0 in integer form. For example, for N = 2n , let |φ = (x1 , · · · , xN )T
be the coordinate form of |φ with respect to the basis states |0, · · · , |N − 1 (in integer form)
of CN . Let |0, |1 (in binary form) be the basis states of C2 . Then in the space C2 ⊗ CN ,
|0 ⊗ |φ = (x1 , · · · , xN , 0, · · · , 0)T , |1 ⊗ |φ = (0, · · · , 0, x1 , · · · , xN )T . (2.5)
Like classical computer, quantum computer uses quantum register composed of multiple
qubits. For quantum states |ψ1 , · · · , |ψk , in the tensor product state
|ψ1 ψ2 · · · ψk = |ψ1 |ψ2 · · · |ψk , (2.6)
the i-th register (1 ≤ i ≤ k) refers to position i of the tensor product, and |ψi is called the
state value of the i-th register in (2.6). Sometimes the i-th register is simply called register |ψi .
A quantum state is always represented by a unit vector of an appropriate dimension. For a
n−1
vector a = (a0 , · · · , an−1 )T = i=0 ai ei where the ei are an orthonormal basis,
1 1
n−1 n−1
|a := ai |ei = ai |i, (2.7)
a i=0 a i=0
where |i := |ei represents the basis state by its subscript.

A measurement to a quantum state can be understood as a projection from the vector
representation of the quantum state to a set of fixed vectors (called measurement basis) whose
span contains the quantum state to be measured. In a measurement at some register i, the
projection is only for the state value at register i, while all other registers remain unaffected.
After measurement, a quantum state collapses to a state of the measurement basis. For a
measurement at some register i, only the state value at register i collapses to a state of the
measurement basis, while all other registers remain unchanged. For example, when measuring
(2.3) with the |i1 · · · in as the default measurement basis, then any of the basis states |i1 · · · in
can be the result of measurement; the probability to obtain a specific result |j1 · · · jn is the
squared norm of the corresponding amplitude: |αj1 ,··· ,jn |2 . When the measurement occurs at
register k of (2.3) for some 1 ≤ k ≤ n, suppose |ik is collapsed to |0, then the result of
measurement of (2.3) is (after deleting register k):

αi1 ,··· ,ik−1 ,0,ik+1 ,··· ,in |i1 · · · ǐk · · · in (2.8)
i1 ,··· ,ǐk ,··· ,in ∈{0,1}
up to normalization.
Since quantum states are normalized, quantum computer only allows unitary operations.
Some frequently used unitary operators include:
(i) Complex rotation Ra,b in a 2-space with fixed orthonormal basis e1 , e2 , where a, b ∈ C
such that |a|2 + |b|2 = 1.
The matrix form of the rotation with respect to the basis is
⎡ ⎤
a −b
⎣ ⎦. (2.9)
b a

It changes |e1 into a|e1 + b|e2 . When a is given, a simple choice of b is 1 − |a|2 .
(ii) Reflection with respect to a subspace of CN .

A reflection with respect to an m-space W of CN is the unitary transformation preserving
all vectors of W while reversing all vectors of W ⊥ . If W is spanned by orthonormal basis
vectors {|wi , i = 1, 2, · · · , m}, then

m
RW = 2 |wi wi | − I, (2.10)
i=1
where I is the identity matrix. The reflection with respect to W ⊥ is RW ⊥ = −RW .

When N = 2, reflection R|0 is called Pauli-Z transformation in the 2-space spanned by
|0, |1.
(iii) Quantum Fourier transform: the matrix form is

1
FN = √ (e2πixy/N )x,y=0,1,··· ,N −1 . (2.11)
N
1
(iv) Hadamard transform (Hadamard gate) H⊗n , where H = √12 11 −1 .
n
−1
If |x is a basis state, then H⊗n |x = √12n y=0 (−1)x·y |y, where x·y is the inner product
2
of the binary expressions of integers x, y taken as vectors of dimension n.

When n = 1, denote
1 1
|+ := H|0 = √ (|0 + |1), |− := H|1 = √ (|0 − |1). (2.12)
2 2
When x = 0, then
n
2 −1
⊗n ⊗n 1
H |0 =√ |y =: |2n . (2.13)
2n y=0
It is the uniform superposition of all n-qubit ground states.
H⊗n has circuit implementation complexity O(n). It is often written as H when the
multiplicity n of the tensor product is omittable.
(v) Grover’s diffusion: R|2n , with |2n given by (2.13).

It has circuit implementation complexity O(n), because of the following decomposition:

R|2n = H⊗n 2|0⊗n 0|⊗n − I H⊗n . (2.14)
(vi) Elimination of register.

The inverse of Hadamard transform is itself. So for any |φ, |ψ,
2n −1
1
H √ |φ |y|ψ = |φ|0|ψ. (2.15)
2n y=0
(2.15) is called the elimination of state value |y for all y = 0 from the second register.
In many cases, the constant state value |0 is omitted for succinctness, and the result
of (2.15) becomes |φ|ψ. In this notation, (2.15) is called the elimination of the second
register, or elimination of register |y for all 0 ≤ y < 2n .
(vii) Quantum implementation of classical map.

Let f : Z2n −→ Z2m be a map. The quantum implementation of f refers to a unitary
transformation generating the following state from initial state |0⊗n |0⊗m :
n
2 −1
1
√ |x|f (x). (2.16)
2n x=0
The quantum implementation can be realized by Uf H, in which H is the Hadamard

transform, and Uf is the following unitary operator:
Uf : |x, y → |x, y ⊕ f (x), ∀x ∈ Z2n , y ∈ Z2m , (2.17)
where ⊕ denotes the bit-wise XOR.
(viii) Control transformation

k−1
C= |j j| ⊗ Cj , (2.18)
j=0
where each Cj is a unitary operator.

(2.18) is called the action of Cj (on the second register) controlled by register |j. For any
αj,x ∈ C,

C αj,x |j|x = αj,x |j Cj |x. (2.19)
j,x j,x
With a black-box oracle to query the entries of a unitary matrix, any sparse unitary operator
U can be efficiently implemented in quantum computer[105] . The reason is that for any quantum
state |φ,
e−iHπ/2 |1 ⊗ |φ = −i|0 ⊗ U |φ, (2.20)

where H = U0† U0 is a sparse Hermitian matrix. The notation “† ” refers to the matrix conjugate
transpose. Since e−iHπ/2 can be implemented efficiently by sparse Hamiltonian simulation, so
can unitary operator U .
A quantum algorithm contains an input, a series of unitary transformations, and an output
obtained by measurement. If Step 1 to Step k are the composition of unitary transformations
U1 , · · · , Uk , then “undo” step 1 to step k refers to the unitary transformation (U1 · · · Uk )−1 .
Any quantum algorithm is probabilistic. If the probability of getting the desired result
√
is P , then by quantum amplitude amplification[52] , it suffices to run the algorithm O(1/ P )
times, each time ending with measurement. This is already quadratic speedup over classical
probabilistic algorithms.
The universal gates (or elementary gates) is a set of unitary operators acting on one or two
qubits. It is required that any unitary operator can be approximated to some precision by a
finite composition of elementary gates. The number of elementary gates in the composition
measures the efficiency of the unitary operator.
The circuit complexity (or time complexity, or gate complexity) of a quantum algorithm
refers to the lower bound of the number of elementary gates in a quantum circuit to realize
the unitary operators in the quantum algorithm. A computation is said to be efficient, if the
number of gates is polynomial in the number of qubits used in the computation. A result of
Solovay and Kitaev[12, 222, 223] states that any unitary operator that can be realized efficiently
by a set of universal gates can also be realized efficiently by any other universal gates.
Besides circuit complexity, another evaluation of quantum algorithm is query complexity.
If in a quantum algorithm involving a given function f , the computation load concentrates on
the number of visits to f , then the number of visits to f in the algorithm is called the query
complexity. In a quantum walk algorithm, the query complexity is also referred to as the step
complexity (one query per step).
With the above terminology, some key concepts in designing quantum algorithms can be
re-introduced technically below:
(I) Quantum phase estimation Let U be a unitary operator. Then its eigenvalues are of
the form eiθj , where 0 ≤ θj < 2π. The θj are called the eigenphases of U .
Given unitary operator U and eigenvector |u, estimating the corresponding eigenphase
θ ∈ [0, 2π) is called quantum phase estimation.
(II) Quantum amplitude amplification Let |ψ = α|x + |x⊥ be a quantum state, where

α ∈ C is the amplitude of |ψ in basis state |x. By measuring |ψ, one gets state |x
with probability |α|2 , which can be a very small number.
With Grover search, by O(1/|α|) times of preparing |ψ and then making measurement,
state |x can be obtained with high probability. This subroutine of improving the prob-
ability of a component basis state in a quantum state by repetition following Grover’s
algorithm, is called quantum amplitude amplification.
(III) Block encoding Realizing linear transformation is a fundamental task in quantum com-
puting. A block-encoding of a square matrix A is a unitary matrix U such that the top-left
block of U is equal to A/t for some normalizing constant t ≥ Asp .
(IV) Linear combinations of unitaries (LCU) Any square matrix can be written as a
linear combination of unitary matrices. LCU algorithm is on quantum realization of a
linear transformation given in the form of LCU.

Let L = i αi Ui , where the Ui are unitary, and the αi ∈ C. A quantum realization of L
is a unitary transformation mapping an arbitrary state |φ|0 to
1
|ψ = L|φ|0 + (· · · )|0⊥ , (2.21)
t
where t is a know parameter satisfying t ≥ L|φ.
(V) Quantum preparation of classical vector Given a complex vector x = (x1 , · · · , xn )T ,

a quantum preparation of the unnormalized quantum state x |x of x is a unitary
transformation from initial state |0|0 to
x
|ψ = |x|0 + (· · · )|0⊥ , (2.22)
t
where t ≥ x is a know parameter.
(VI) Quantum eigenphase decomposition of unitary operator Let U be an n×n unitary

matrix with eigenvalues eiθj and corresponding eigenvectors uj for 0 ≤ j ≤ n − 1.
A quantum eigenphase decomposition of U with precision ε refers to a unitary transfor-
n
mation such that for any αj ∈ C satisfying j=1 |αj |2 = 1,

n−1
n−1
αj |uj |0 → αj |uj |θj , (2.23)
j=0 j=0
where θj is an ε-approximate of θj for all 0 ≤ j < n, and both θj , θj ∈ [0, 2π).
(VII) Quantum singular value estimation (SVE)

Let A be an m × n matrix. Recall that if the nonzero singular values of A are {σi >
0, i = 1, 2, · · · , r}, where r is the rank of A, then an SVD of A is A = U DV † , where
U = (u1 , · · · , um ) and V = (v1 , · · · , vn ) are unitary matrices, and D = (dij ) is an m × n
matrix whose only nonzero entries are dii = σi for all 1 ≤ i ≤ r. Obviously
Asp = max |σi |. (2.24)

i=1,2,··· ,r
In the special case when A is Hermitian, then m = n, the nonzero eigenvalues of A are
{θi = δi σi , i = 1, 2, · · · , r}, where δi ∈ {1, −1} is the sign of θi . For any 1 ≤ i ≤ r, ui and
vi are related by vi = δi ui , both of which are eigenvectors corresponding to eigenvalue
θi . The zero eigenvalues agree with the zero singular values, and ui = vi for r < i ≤ n.
When m = n, a quantum SVE of A is a unitary transformation with one of the following

n
properties: For any αi ∈ C satisfying i=1 |αi |2 = 1,

n
n
1) αi |vi |0 → αi |ui |
σi ,
i=1 i=1 (2.25)
n n
2) αi |ui |0 → αi |vi |
σi ,
i=1 i=1
i is an approximate of σi with error bound |

where σ σi − σi | ≤ εAsp .
(VIII) Quantum SVE for non-square matrix When m = n, the extended Hermitian matrix
of m × n matrix A is ⎡ ⎤
0 A
Aext := ⎣ ⎦. (2.26)
A† 0
The nonzero eigenvalues of Aext are {±σi , 1 ≤ i ≤ r}, the corresponding eigenvectors
i , ±vi ) . The orthogonal complement of the r-space spanned by {(ui , vi ) , 1 ≤
are (uT T T T T T
i ≤ r} in Cm+n is the eigenspace of Aext corresponding to eigenvalue 0, and is spanned

by the (uT j , 0) for all r < j ≤ m and the (0, vk ) for all r < j ≤ n.
T T T
A quantum SVE[110, 113, 119] of A can be deduced from that of Aext . It is a unitary
r
transformation such that for any αi , α−i ∈ C satisfying i=1 (|αi |2 + |α−i |2 ) = 1,

r

r

αi |ui , vi + α−i |ui , −vi |0 → αi |ui , vi | i ,
σi + α−i |ui , −vi |−σ (2.27)
i=1 i=1
i are approximates of σi , −σi respectively, with error bound εAsp .

i , −σ
where σ
(IX) Quantum linear solver For linear system Ax = b, a quantum linear solver outputs a
quantum state |x, such that

t|x − A+ |b ≤ εA+ sp (2.28)
for some unknown parameter t > 0, where A+ is the Moore-Penrose inverse of A.

Rescaling A does not influence (2.28). Usually A is rescaled to satisfy Asp = 1.
(X) Swap test For any two quantum states |x, |y, swap test is a technique to estimate the
inner product x|y = x · y of two unit vectors x, y.
Many quantum algorithms only return the quantum state of a classical vector. Swap test
is used to extract classical information from a quantum state.
3 Some Building Blocks in Quantum Algorithm Design

This section introduces two fundamental techniques in quantum algorithm design, together
with several key subroutines based on them. The two techniques are phase estimation and
LCU. The former is used to extract the coordinates from a unit vector given in the form of
a quantum state, and the latter is used to implement (non-unitary) linear maps and classical
vectors on quantum computer. They are counterparts of the interface between classical data
and quantum data.
3.1 Quantum Phase Estimation

Quantum phase estimation is among the most important techniques in quantum algorithm
design. It was first proposed by Kitaev[10] in 1995 as a generalization of a key technique in
Shor’s algorithm[9] . Currently, it is an important subroutine of many quantum algorithms,
such as quantum linear solver[99, 119] , quantum principal component analysis[128] , quantum
singular value decomposition[112, 113] , eigenvalue estimation of Hermitian matrix[224] , quantum
counting[51] , swap test[225] , Hamiltonian simulation based on quantum walk[89, 105] , etc.
Let U be a unitary transformation, and u be a unit eigenvector corresponding to eigenvalue
e2πiθ , where 0 ≤ θ < 1. Given U , the following algorithm returns a value θ ∈ [0, 1) such that
≤ 2−(n+1) for initial state |u, where integer n is introduced to represent the bit precision.
|θ− θ|
It is also the number of qubits needed by the algorithm to run on.
Algorithm 1 Quantum phase estimation[12]

1: Prepare the initial state |ψ1 = |0⊗n |u (assume the preparation is efficient).
2: Apply Hadamard transform to the first register |0⊗n of |ψ1 . Result:
n
2 −1
1
|ψ2 = |2n |u = √ |y|u. (3.1)
2n y=0
2n −1
3: Apply control transformation y=0 |y y| ⊗ U y to |ψ2 . The effect is that the y-th power
U y of U is applied to |u if the first register takes state value |y. The result is
n n
2 −1 2 −1
1 1 2πiθy
|ψ3 = √ |yU y |u = √ e |y|u. (3.2)
2n y=0 2n y=0
4: Apply inverse quantum Fourier transform to the first register |y of |ψ3 . Result:
n n
2 −1 2 −1 2 −1 n 2n −1
1 2πiθy−2πi xyn 1
2πiy(θ− 2xn )
|ψ4 = n e 2 |x|u = e |x|u. (3.3)
2 x=0 y=0 2n x=0 y=0
5: Perform measurement to |ψ4 .
The measurement returns a basis state |x|u for some 0 ≤ x < 2n , from which the value
of x in binary expression is obtained. With high probability, the rational number x/2n is an
approximate of θ to precision 2−(n+1) . This claim is established as follows[12] .
Denote the error function
x
δ(x) := θ − n , ∀x ∈ R. (3.4)
2
Since 0 ≤ θ < 1, θ can be written in binary expression form as

θ1 θn θ1 2n−1 + · · · + θn
θ= + · · · + n + rn = + rn , (3.5)
2 2 2n
where θi ∈ {0, 1} and 0 ≤ rn < 2−n . Denote integer
nθ := θ1 2n−1 + · · · + θn . (3.6)
It is the integer that one hopes the algorithm to output.

Case 1 If rn = 0, then δ(nθ ) = 0, and the amplitude of |ψ4 in |nθ |u is
n
2 −1
1 2πiy(θ− n2nθ )
e = 1. (3.7)
2n y=0
So |ψ4 = |nθ |u. The result nθ is obtained by measurement with probability 1, and the
algorithm is deterministic.
Case 2 If 0 < rn < 2−(n+1) , then δ(nθ ) = rn ∈ (0, 2−(n+1) ), and −δ(nθ + 1) = 2−n − rn ∈
(0, 2−n ). Between nθ /2n and (nθ + 1)/2n, only the former approximates θ to precision 2−(n+1) .
By inequalities
2 π π
|y| ≤ | sin(y)| ≤ |y|, ∀y ∈ − , , (3.8)
π 2 2
the probability of obtaining |nθ |u by measurement is
n 2 2 2
1 2πiyδ(nθ ) 1 e2πi2 δ(nθ ) − 1 1 sin(2n δ(nθ )π)
2 −1 n
4
e = 2n 2πiδ(nθ ) = 2n ≥ 2. (3.9)
22n y=0 2 e −1 2 sin(δ(nθ )π) π
Case 3 If 2−(n+1) ≤ rn < 2−n , then −δ(nθ + 1) = 2−n − rn ∈ (0, 2−(n+1) ]. Similar to
Case 2, one gets that between nθ /2n and (nθ +1)/2n , only the latter approximates θ to precision
2−(n+1) . The probability of obtaining |nθ + 1|u by measurement is ≥ 4/π 2 .
By the above analysis, with probability ≥ 4/π 2 ≈ 0.4, an approximate of θ to precision

−(n+1)
2 can be obtained. Since the probability is not close to 1, by running the algorithm
several times, the probability can be improved to be close to 1.
The following is another method to improve the success probability of the algorithm. Sup-
pose that the precision required is ε := 2−m for some 0 < m ≤ n − 2. (3.5) can be rewritten
as
θ1 2m−1 + · · · + θm mθ
θ= + rm =: m + rm , (3.10)
2m 2
where θi ∈ {0, 1} and 0 ≤ rm < 2−m . A similar analysis shows that all elements of {(2n−m mθ +
t)/2n | t = 0, 1, · · · , 2n−m − 1} are approximates of θ to precision 2−m . It is proved in [12,
Subsection 5.2] that the success probability to obtain one of these approximates is at least
1 − δ := 1 − 2(2n−m1
−2) .
Representing m, n as integer functions in ε, δ would result in

1 1 1
n = log + log 2 + = O log . (3.11)
ε 2δ εδ
Proposition 3.1 (see [10]) Let U be a unitary transformation with implementation com-
plexity O(T ), and let u be an eigenvector of U . Then the quantum phase estimation algorithm
returns the corresponding eigenvalue in time O(T /εδ) to precision ε, with probability at least
1 − δ.
A direct application of the above algorithm is quantum eigenphase decomposition of unitary
matrices, which is often taken as another form of quantum phase estimation. Let U be an M ×M
unitary matrix, with eigenvalues {e2πiθj | j = 1, 2, · · · , M } and corresponding unit eigenvectors
{uj | j = 1, 2, · · · , M }, where 0 ≤ θj < 1. Let c be an arbitrary nonzero vector of the M -space.
M
Then c = j=1 γj uj for some unknown parameters γj , as the uj form an orthonormal basis of
the M -space.
Suppose that U is given, but the uj are not, nor are the θj . In Proposition 3.1, choose n
by (3.11), and choose for Algorithm 1 the following initial state:

M
|0⊗n |c = γj |0⊗n |uj . (3.12)
j=1
The output of the algorithm is

M
γj |θj |uj , (3.13)
j=1
where θj is an approximate of θj for all 1 ≤ j ≤ M .

3.2 Application: Order Finding
Let M be a fixed natural number. Given an integer a ∈ Z∗M satisfying gcd(a, M ) = 1, the
smallest positive integer r such that ar ≡ 1 mod M , is called the order of a. The problem of
finding the order of an integer in Z∗M is called order finding.
Order finding is a problem where quantum phase estimation is a key technique. In the
following, we describe the order finding algorithm in Shor’s algorithm[9] . Denote m = log M .
Define unitary transformation
⎧
⎨ ax mod M, if 0 ≤ x ≤ M − 1,
U : x ∈ Z2m → (3.14)
⎩ x, else.
In [12], it was shown that for all 0 ≤ s < r,
1 −2πisk/r k
r−1
|us := √ e |a mod M (3.15)
r
k=0
is the quantum state of eigenvector us of U , and the corresponding eigenvalue is e2πis/r . Fur-
thermore,
1
r−1
√ |us = |0⊗(m−1) |1. (3.16)
r s=0
In Algorithm 1, choose the initial state |0⊗n |c = |0⊗n |0⊗(m−1) |1. Following the expres-

sion on the left side of (3.16), after Step 4 of the algorithm,
m
2 −1
m −1
r−1 2

1 i2πy( rs − 2x
|ψ4 = m √ e m)
|y|us . (3.17)
2 r x=0 s=0 y=0
According to the analysis of Algorithm 1, by running the algorithm several times, with
high probability a value 0 ≤ x < 2m can be obtained, such that s/r is a continued fraction
approximate of x/2m for two unknown integers s, r satisfying 0 ≤ s < r. The integer r is what
to be after.
To obtain r, first compute the continued fraction expansion of x/2m :
x 1
m
= c0 + 1 =: [c0 , c1 , · · · , cm ], (3.18)
2 c1 +
..
.+ 1
cm
where c0 , c1 , · · · , cm are positive integers. For every 0 ≤ k ≤ m, [c0 , c1 , · · · , ck ] is called the

k-th convergent of x/2m . Let [c0 , c1 , · · · , ck ] = sk /rk for 0 ≤ k ≤ m. Then for all 0 ≤ k ≤ m
such that rk ≤ M , check if any of rk , 2rk , · · · , M/rk rk is the order of a. When the procedure
terminates, the order r of a must be found. The complexity of the whole procedure for finding
r is O(poly log M ).
3.3 Swap Test

Swap test is a technique to estimate the inner product of two quantum states. In particular,
it can be used to estimate the amplitude of a quantum state in a basis state. The key idea in
this technique is quantum phase estimation.
Lemma 3.2 (see [52, 225]) Let |φ = sin(θ)|0|u + cos(θ)|1|v be a quantum state that
can be prepared in time T , where 0 ≤ θ < π, and |u, |v ∈ Cn . Then there is a quantum
algorithm that computes sin(θ), cos(θ) in time O(T /εδ) to precision ε with probability at least
1 − δ.
!
Proof Rotation −cos(2θ) sin(2θ)
sin(2θ) cos(2θ) in the 2-space spanned by |0|u, |1|v has the following
decomposition in the entire (2n)-space C2 ⊗ Cn :
Rcos(2θ),− sin(2θ) = (I − 2|φ φ|)(R|0 ⊗ I), (3.19)
where R|0 is the reflection with respect to |0 in the 2-space C2 spanned by |0, |1. The
eigenvalues of Rcos(2θ),− sin(2θ) are e±i2θ , and the corresponding eigenvectors are
1
|w± := √ (|0|u ± i|1|v). (3.20)
2
Since
i
|φ = − √ (eiθ |w+ − e−iθ |w− ), (3.21)
2
by Proposition 3.1, when choosing n according to (3.11), and choosing initial state |0n |c =
|0n |φ, then by applying Algorithm 1 to U = Rcos(2θ),− sin(2θ) , a value θ ∈ [0, π) satisfying
|θ − θ| ≤ ε can be obtained, with failure probability at most δ. Then sin(θ), cos(θ)
can be
− sin(θ)| ≤ ε, | cos(θ)
computed in negligible time, and | sin(θ) − cos(θ)| ≤ ε.
The proving procedure of the following proposition gives the swap test method.
Proposition 3.3 (see [52, 225]) Let |x, |y be two quantum states that can be prepared
simultaneously in time O(T ), then x|y can be estimated to precision ε in time O(T /ε).
Proof Consider the quantum state
1 " # 1" #
|φ = √ |+|x + |−|y = |0(|x + |y) + |1(|x − |y) . (3.22)
2 2
The probability of obtaining |0 by measuring the first register of |φ is (1 + Re x|y)/2, and
the probability of obtaining |1 is (1 − Re x|y)/2.
When both |x + |y and |x − |y are nonzero, set

sin(θ) = (1 + Re x|y)/2, cos(θ) = (1 − Re x|y)/2, (3.23)
and
|x + |y |x − |y
u= , v= . (3.24)
|x + |y |x − |y
Then θ ∈ [0, π/2], and
|φ = sin(θ)|0|u + cos(θ)|1|v. (3.25)
By Lemma 3.2, an ε -approximate θ of θ can be obtained in time O(T /ε), where ε is determined
as follows. By Re x|y = cos(2θ),

− Re x|y ≤ 2|θ − θ| ≤ 2ε .
cos(2θ) (3.26)

Setting ε = ε/2 would guarantee the precision ε of approximating Re x|y by cos(2θ).
By replacing |y with i|y in (3.22), Im x|y can be estimated similarly.
When |x = |y, (3.22) becomes |φ = |0|x = sin(π/2)|0|x, so an approximate θ ∈ [0, π)
of θ = π/2 can be obtained by Lemma 3.2. When |x = −|y, (3.22) becomes |φ = |1|x =
cos(0)|1|x, so an approximate θ ∈ [0, π) of θ = 0 can be obtained by Lemma 3.2.
One application of swap test is matrix multiplication computing. The multiplication of two
N × N matrices involves the evaluation of N 2 inner products of vector pairs. If the preparation
of the quantum states of the rows and columns of the two matrices are efficient, i.e., in time
T = O(poly log N ), then by Proposition 3.3, the matrix multiplication can be computed in time
O(N 2 (poly log N )/ε) to precision ε.
3.4 Linear Combination of Unitaries (LCU)

Given N nonzero complex numbers α0 , · · · , αN −1 , and N unitary operators U0 , · · · , UN −1
that can be implemented in time T in quantum computer, LCU is on implementing linear (but
N −1
not unitary) operator L = j=0 αj Uj .
LCU was first proposed by Long in 2006 as a basic operation of duality quantum computer[226] .
Later on, some other types of quantum algorithms to realize LCU were proposed[118, 222] . The
importance of LCU algorithms was recognized only in recent years, in the study of Hamilto-
nian simulation[105–107, 114, 227] , quantum linear solver[115] , quantum walk[114] , quantum state
preparation[118] , quantum gradient descent[228, 229] , quantum Newton’s method[229] , etc. In
the following, we describe the two LCU algorithms in [118, 222] respectively, and show the
application of LCU in the preparation of weighted superposition of quantum states.
To implement L, it suffices to construct a quantum algorithm to prepare L|φ for any
given initial state |φ. In the following algorithm[118] , t = 1/ maxj |αj | is assumed to be given.
Alternatively, t can be replaced by a relatively tight (but known) lower bound of the 1/|αj |.
For any 0 ≤ j < N , Rj := Rtαj ,√1−t2 |αj |2 is the complex rotation in the 2-space spanned

by |0, |1 such that Rj |0 = tαj |0 + 1 − t2 |αj |2 |1.
Algorithm 2 Linear combinations of unitaries (version 1)[118]

N −1
1: Prepare the initial state |ψ1 = |φ|N |0|0 = √1 j=0 |φ|j|0|0.
N
2: Use the second register |j of |ψ1 as the control register, generate state values |αj in the
third register of |ψ1 for all 0 ≤ j < N (control transformation). Result:
N −1
1
|ψ2 = √ |φ|j|αj |0. (3.27)
N j=0
N −1
3: Apply control transformation j=0 Uj ⊗ |j j| ⊗ I ⊗ Rj to |ψ2 . Result:
N −1 $
1
|ψ3 = √ Uj |φ|j|αj tαj |0 + 1 − t2 |αj |2 |1 . (3.28)
N j=0
4: Eliminate from the third register of |ψ3 the state values |αj for all 0 ≤ j < N (inverse of
the unitary transformation in Step 2). Result:
N −1 $
1
|ψ4 = √ Uj |φ|j|0 tαj |0 + 1 − t |αj | |1 .
2 2 (3.29)
N j=0
5: Apply Hadamard transform to the third register |j of |ψ4 . Result:

N −1
t t
|ψ5 = αj Uj |φ|0, 0, 0 + (· · · )|0, 0, 0⊥ = L|φ|0, 0, 0 + (· · · )|0, 0, 0⊥ . (3.30)
N j=0 N
6: Perform measurement to |ψ5 at the last three registers.
In the last step, the probability to get L|φ by measurement is L|φ2 t2 /N 2 . In Step 1
to Step 5, the running time is respectively O(log N ), O(1), O(T ), O(1), O(log N ). By quantum
amplitude amplification[52] , the time complexity of the algorithm is
" % #
O (T + log N )N max |αj | L|φ . (3.31)
j
One application of LCU is quantum state preparation. Given a vector x = (α0 , · · · , αN −1 ),

N −1
preparing unnormalized quantum state x |x = j=0 αj |j is called quantum state prepara-
tion, or the input problem. This problem can be a serious bottleneck[99, 113, 115, 124, 127, 129, 228] .
In the extreme case, the cost of quantum state preparation can dominate the cost of the whole
quantum algorithm[214, 216] . Quantum algorithms to solve the input problem can be found in
[118, 176, 230, 231].
Proposition 3.4 (see [118]) For any vector x = (α0 , · · · , αN −1 ), x |x can be prepared
&
in time O(κ log N ), where κ = maxj |αj | minj,αj
=0 |αj | is the condition number of vector x.
Proof Only the nonzero entries of x function in x |x. If there is any component of x
with zero value, then only the components with nonzero values are visited in the LCU algorithm,
under the assumption that in x, the components with zero value are given beforehand. Without
loss of generality, assume αj = 0 for all 0 ≤ j < N .
In Algorithm 2, by choosing |φ = |0, and Uj = I for all j, the result of Step 4 is (after
omitting common constant state values):
N −1
t tx
√ αj |j|0 + |0⊥ = √ |x|0 + |0⊥ . (3.32)
N j=0 N
By measuring (3.32) at the last register, x|x is obtained with probability t2 x2 /N ≥
1/κ2 . As T = 1 in (3.31), the complexity to prepare x |x is O(κ log N ).
A direct corollary of Proposition 3.4 is that the quantum state of a relatively uniformly
distributed vector can be prepared efficiently in quantum computer.
Next we introduce the LCU algorithm proposed in [222]. In the following,

N −1
αj
α := |αj |, eiθj := , (3.33)
j=0
|αj |
N −1
and V is a unitary transformation satisfying V |0 = √1
α j=0 |αj | |j.
Algorithm 3 Linear combination of unitaries (version 2)[222]

1: Prepare the initial state |ψ1 = |φ|0.
2: Apply I ⊗ V to |ψ1 . Result:
N −1 $
1
|ψ2 = √ |αj | |φ|j. (3.34)
α j=0
3: Use control transformation to insert the phase eiθj into the coefficient of |j, and then apply
Uj to |φ, with the last register |j of |ψ2 as the control register. Result:
N −1 $
1
|ψ3 = √ |αj |eiθj Uj |φ ⊗ |j. (3.35)
α j=0
4: Apply I ⊗ V −1 to |ψ3 . Result:

N −1
1 1
|ψ4 = αj Uj |φ|0 + (· · · )|0⊥ = L|φ|0 + (· · · )|0⊥ . (3.36)
α j=0 α
5: Perform measurement to |ψ4 at the last register.

&
The complexity of the above algorithm is O((T + CV )α L|φ), where O(CV ) is the com-
plexity to implement V in quantum computer. Since α ≤ N maxj |αj |, if O(CV ) = O(log N ),
then Algorithm 3 is more efficient than Algorithm 2.
4 Quantum Linear Solvers with Applications in Machine Learning

Solving linear equations is a fundamental problem in many disciplines of science and engi-
neering. A typical example is machine learning, which involves manipulating and classifying a
large number of vectors in a high dimensional space[232, 233] . Many machine learning tasks are
related to optimization problems that can be reduced to linear system solving[234] .
For linear system solving, one of the best classical algorithms – the conjugate gradient
√
method[117, 235, 236] , has complexity O(M s κ log 1/ε), where M is the maximum between the
number of equations and the number of variables, s, κ are the sparsity and the condition number
of the coefficient matrix respectively, and ε is the precision. In comparison, the quantum
algorithms in [99, 115, 116, 118, 119] achieve exponential speedup in parameter M .
4.1 The First Quantum Linear Solver: HHL Algorithm

Consider a linear system Ax = b, where A is an invertible M × M Hermitian matrix with
condition number κ. If this is not the case, then consider the following equivalent linear system:
⎡ ⎤⎡ ⎤ ⎡ ⎤
0 A 0 b
⎣ ⎦⎣ ⎦=⎣ ⎦. (4.1)
A† 0 x 0
Since A is Hermitian, e−itA is unitary, and can be efficiently implemented in quantum

computer when A is sparse. Assume that realizing e−itA in quantum computer has complexity
O(t log M ). Further assume that quantum state |b can be prepared efficiently.

Let A = M j=1 δj σj |uj uj | be an SVD of A, where the σj > 0, and for δj ∈ {1, −1}, the
M
δj σj are eigenvalues of A. Then |b = j=1 γj |uj for some unknown parameters γj such that
M
j=1 |γj | = 1.
2
By a suitable re-scaling of the original linear system, it can be assumed that Asp = 1.
Then A−1 sp = κ > 1, and
κ−1 ≤ σj ≤ 1, ∀1 ≤ j ≤ M. (4.2)
Assume that a lower bound K = Θ(1/κ) of the σj is given. Then K ≤ κ−1 < 1, and for all
1 ≤ j ≤ M,
K ≤ σj ≤ 1, K ≤ Kσj−1 ≤ 1. (4.3)
The quantum state |x of a solution x to Ax = b is proportional to

M
A−1 |b = γj δj σj−1 |uj . (4.4)
j=1
The following HHL algorithm is based on this observation.
Step 1 By quantum eigenphase decomposition (3.13), when choosing |0|b|0 as the initial

state, the following quantum state can be obtained in time O((log M )/ε ):

M
γj |δ'
j σj |uj |0, (4.5)
j=1
where |δ' '

j σj | ∈ [K, 1] and |δj σj − δj σj | ≤ ε for all 1 ≤ j ≤ M . The precision ε will be made
explicit in the analysis of the algorithm.
−1
Step 2 In order to put δ' j σj into the coefficient of (4.5) for 1 ≤ j ≤ M so that (4.4) can
be obtained, apply the 2-dimensional rotation
⎡ $ ⎤
−1 −2
K δ' σ − 1 − K 2 δ'σ
R ' −1 $ −2 =
⎣ $ j j j j
⎦, (4.6)
K δj σj , 1−K 2 δ' −2 −1
j σj
1 − K 2 δ'σ
j j K '
δ σ
j j
which is controlled by the first register |δ' j σj of (4.5), to the third register. Then (4.5) is
changed into

M $
−1 −2
γj |δ' ' |0 + 1 − K 2 δ'
j σj |uj K δj σj j σj |1 . (4.7)
j=1
Step 3 Undo the quantum eigenphase decomposition of Step 1 to eliminate from the first
register of (4.7) the state values |δ'
j σj for all 1 ≤ j ≤ M . The result from (4.7) is
$
M
−1 −2
γj |0|uj K δ'
j σj
2 '
|0 + 1 − K δj σj |1 = |0 Kt|x|0 + (· · · )|0⊥ , (4.8)
j=1
where

M
−1
t|x := γj δ'
j σj |uj . (4.9)
j=1
Step 4 By measuring (4.8) at the first and the last registers, the quantum state |x can
be obtained with probability
M
|γj |2
K 2 t2 = K2 2 ≥K .
2
(4.10)
j=1 '
δj σj
To improve the success probability by amplitude amplification, the algorithm needs to run
O(1/K) times.
By

M
−1 −1
−1
t|x − A |b = γj (δ'σ
j j − δ σ
j j
−1
)|u '
j ≤ max |δj σj − δj σj−1 |, (4.11)
j
j=1

to control the precision to ε in the sense of (2.28), i.e., t|x − A−1 |b ≤ εκ, it suffices to set
−1
max |δ'
j σj − δj σj−1 | ≤ εκ. (4.12)
j
By
−1 |δj σj − δ' j σj | ε
|δ'
j σj − δj σj−1 | = ≤ 2, (4.13)
|δj σj δ'
j σj |
K
It suffice to choose ε = εκK 2 ≤ ε/κ.
In the four steps of the algorithm, Step 2 has constant complexity, Step 1 and Step 3 have
the same complexity O((log M )/ε ), or equivalently, O(κ(log M )/ε). So the whole algorithm
has complexity O(κ2 (log M )/ε).
In 2012, Ambainis[116] made an improvement over HHL algorithm and reduced factor κ2 to
κ log3 κ in the complexity. In 2017, Childs, et al.[115] made a further improvement and reduced
factor 1/ε to log(1/ε).
Remark 4.1 The following properties of HHL algorithm can be found in [237–239]:
1) When Ax = b has more than one solution, HHL algorithm only returns one solution,
which is the least-square solution. More precisely, the algorithm solves A† Ax = A† b instead of
Ax = b.
2) HHL algorithm needs efficient preparation of the quantum state |b of b.
3) The output of HHL algorithm is a quantum state |x. Obtaining the classical solution
x up to normalization from |x takes at least O(M ) steps, which sacrifices the exponential
speedup of HHL algorithm.
4) The inner product of the solution state |x with any other quantum state can be estimated
by swap test. This is enough for many applications in machine learning.
5) HHL algorithm requires either A to be invertible, or b to lie in the well-conditioned
region of A: If singular value σj = 0 for some 1 ≤ j ≤ M , then in b, the component γj with
respect to the corresponding eigenvector uj is zero.
4.2 Quantum Linear Solving by Singular Value Estimation (SVE)

The efficiency of HHL algorithm relies on efficient implementation of Hamiltonian e−iAt .
However, Hamiltonian simulation is efficient only in some special cases. In 2017, Kerenidis and
Prakash[113] introduced a tree structure similar to QRAM[240, 241] to store a matrix in quantum
computer efficiently, and in this way discovered a fast algorithm for quantum SVE. Nowadays,
SVE has many important applications in machine learning[109, 113, 119, 228, 242] and Hamiltonian
simulation[109, 114] . In 2018, Wossnig, et al.[119] proposed a new quantum algorithm to solve
general dense linear systems based on SVE.
Below we first introduce Kerenidis, et al.’s quantum SVE, then introduce Wossnig, et al.’s
quantum linear solver.
Let A = (aij ) be an M × M matrix none of whose rows is composed of zeros. Denote the
i-th row of A by AT i−1 , where 1 ≤ i ≤ M . Then Ai = 0 for 0 ≤ i < M . Denote
A := (A0 , A1 , · · · , AM−1 )T . (4.14)

Then
1 1
M−1 M−1
|Ai = aij |j, |A = Ai |i. (4.15)
Ai j=0 A i=0
Define two linear operators LM and LN from CM to CM ⊗ CM as following: For all i, j ∈

{0, 1, · · · , M − 1},
LM : |i →
|i|Ai , LN : |j → |A |j. (4.16)
Then L†M LN = A−1 A. Furthermore, L†M LM = L†N LN = IM , the latter being the M × M
identity matrix.
Denote by VM , VN the M -spaces spanned respectively by the images of LM , LN in CM ⊗CM .
Let UM , UN be two unitary operators in CM ⊗ CM such that for all i, j ∈ {0, 1, · · · , M − 1},
UM : |i|0 → |i|Ai , UN : |0|j → |A |j. (4.17)
In [113], it was shown that there exist two unitary operators with the above property that can
be performed in time O(poly log M ).
In some sense, UM is a unitary realization of the normalized row vectors of matrix A,
with the first register |i labeling the rows, and the second register |Ai storing the normalized
row vectors in quantum form. On the other hand, UN takes down the “normalized” norm
information of the row vectors in the first register, leaving the second register for free.
Let RVM , RVN be the reflections in CM ⊗ CM with respect to VM , VN respectively. By
direct computation,
M−1
†
†
RVM = 2LM LM − IM 2 = UM 2 |i, 0 i, 0| − IM 2 UM ,
i=0
(4.18)

M−1
RV N = 2LN L†N − IM 2 = UN 2 |0, j 0, j| − IM 2 †
UN .
j=0
So RVM , RVN can be efficiently implemented in quantum computer. Denote
W = RVM RVN . (4.19)
Then unitary operator W can be implemented efficiently.

M−1
Let A = i=0 σi ui vi† be an (unknown) SVD of matrix A. Then
max σi = Asp ≤ A. (4.20)

i
For any fixed 0 ≤ k < M , denote the 2-space spanned by LM |uk , LN |vk in CM ⊗ CM as Vk2 .
By
2σk
W LN |vk = LM |uk − LN |vk ,
A
(4.21)
4σk2 2σk
W LM |uk = − 1 L |u
M k − L |v
N k ,
A2 A
Vk2 is invariant under W .

An orthonormal basis of the 2-space Vk2 is
|ek1 := LM |uk ,
LN |vk − ek1 |LN |vk |ek1 LN |vk − σk A−1 |ek1 (4.22)
|ek2 := = .
LN |vk − ek1 |LN |vk |ek1 1 − σk2 A−2
Substituting (4.22) into (4.21), we get

2σk2 2σk σ2
W |ek1 = − 1 |ek1 − 1 − k 2 |ek2 ,
A 2 A A

(4.23)
2σk σ2 2σk2
W |ek2 = 1 − k 2 |ek1 + − 1 |ek2 .
A A A2
So W is a 2-dimensional real rotation when restricted to Vk2 .

Denote the eigenvalues of the restriction of W on Vk2 by exp(±iθk ), where θk ∈ [0, π). Then
the corresponding eigenvectors are
1
|wk± := √ (|ek1 ± i|ek2 ). (4.24)
2
Furthermore,
2σk2 θk
cos θk = − 1, i.e., σk = A cos . (4.25)
A2 2
Simple calculation gives
1
M|uk = √ (|wk+ + |wk− ),
2
(4.26)
1 iθk /2 +
N |vk = √ (e |wk + e−iθk /2 |wk− ).
2
With the above notations, given an M × M matrix A together with its Frobenius norm A,
the algorithm given in [113] realizing the SVD of A in the form

M−1
M−1
αk |vk → αk |uk |
σk + O(ε), (4.27)
k=0 k=0
M−1
for all αk ∈ C satisfying k=0 |αk |2 = 1, such that |
σk − σk | ≤ εA for all k, can be described
as follows:
Algorithm 4 Quantum singular value estimation (SVE)[113]
1: (Preparation of an initial state for the eigenphase decomposition of W )

Choose an initial state |ψ0 ∈ CM , so that it can be formally written as M−1
k=0 αk |vk ,
where the (unknown) αk ∈ C. Apply UN to |ψ0 . Result:

M−1
M−1
1
|ψ1 = αk LN |vk = √ αk (eiθk /2 |wk+ + e−iθk /2 |wk− ). (4.28)
k=0 k=0
2
2: Perform quantum eigenphase decomposition to W , with |ψ1 as the initial state. The result
in the form of (3.13) is:

M−1
1
|ψ2 = √ αk eiθk /2 |wk+ |θk + e−iθk /2 |wk− | − θk , (4.29)
k=0
2
where θk is a (2ε)-approximate of θk for 0 ≤ k < M .

By (4.25),
σk = A cos(±θk /2), k := A cos(±θk /2),
σ (4.30)
σk − σk | ≤ εA.
and |
3: Use the second register | ± θk of |ψ2 as the control register, save values σ
k for 0 ≤ k < M
in a “new” register (an omitted register having constant state value before). Result:

M−1
1
|ψ3 = √ αk eiθk /2 |wk+ |θk + e−iθk /2 |wk− | − θk |
σk . (4.31)
k=0
2

4: Use the second register | ± θk of |ψ3 as the control register, put phase factor e∓iθk /2 in
each term. The purpose is to eliminate “approximately” the original phase factors e±iθk /2
for 0 ≤ k < M . Result:

M−1
1 θk −θk
θk −θ
√ αk ei 2 |wk+ |θk + e−i 2 |wk− | − θk |
k
|ψ4 = σk
k=0
2

M−1
1
= √ αk |wk+ |θk + |wk− | − θk |
σk + O(ε). (4.32)
k=0
2
In the second equality of (4.32),
1
M−1
2

|ψ4 − √ αk |wk+ |θk + |wk− | − θk |
σk
k=0
2

M−1
1 θk −θk
θk −θk
≤ |αk |2 |ei 2 − 1|2 + |e−i 2 − 1|2
2
k=0

M−1
1
≤ |αk |2 |θk − θk |2 ≤ ε2 . (4.33)
4
k=0
5: Undo the quantum eigenphase decomposition of Step 2. The purpose is to eliminate state
values | ± θk for 0 ≤ k < M from the second register of |ψ4 . Result (after omitting the
second register):

M−1
1
M−1
|ψ5 = √ αk (|wk+ + |wk− )|
σk + O(ε) = αk LM |uk |
σk + O(ε). (4.34)
k=0
2 k=0
−1
6: Apply UM . Result (after omitting a register of constant state value):

M−1
|ψ6 = αk |uk |
σk + O(ε). (4.35)
k=0
To be more accurate, in Step 2 of the above algorithm, −θk should be replaced by an εA-
approximate −θ k of −θk , and in general, −θ k = −θk . Accordingly, σ k /2)
k := A cos(−θ
should be introduced to distinguish with σ k . These minute distinctions contribute a total of
O(ε) to the final result.
M−1
The complexity of Algorithm 4 is O(ε−1 poly log(M )). Similarly, linear map k=0 αk |uk →
M−1
k=0 αk |vk |
σk can be realized with the same complexity.
The following quantum linear solver of Wossnig, et al.[119] is based on quantum SVE. Its
main difference in applicability from HHL algorithm, is that the algorithm is applicable to
any dense linear system with no assumption on Hamiltonian simulation. The algorithm has
complexity O(ε−1 κ2 Apoly log(M )). Remark 4.1 also holds for this algorithm.
Consider linear system Ax = b, where A is an M × M positive-definite Hermitian ma-
trix (such a matrix is selected for the purpose of illustration). Its SVD is of the form A =
M−1 †
k=0 σk uk uk , where the σk > 0.
Step 1 Choose an initial state formally in the form of

M−1
|b = αk |uk , (4.36)
k=0
M−1
where the αk ∈ C satisfy k=1 |αk |2 = 1, and run the SVE algorithm. Result:

M−1
αk |uk |
σk + O(ε). (4.37)
k=0
k−1 for 0 ≤ k < M , with

Step 2 Multiply each term of (4.37) separately with scalar σ
register |
σk as the control. Result up to normalization:

M−1
k−1 αk |uk |
σ σk + O(ε). (4.38)
k=0
σk . Then the solution state is obtained:

Step 3 Undo Step 1 to eliminate register |

M−1
k−1 αk |uk + O(ε).
σ (4.39)
k=0
4.3 Application: Boolean Equation Solving

A variable/solution is said to be Boolean, if it takes value only in {0, 1}. A Boolean polyno-
mial is an F2 -polynomial in n Boolean variables. The coefficients of a Boolean polynomial are
all 1, and any Boolean monomial is linear in each of its variables. Solving Boolean polynomial
system is an important task in many problems, such as the subset sum problem, and the graph
isomorphism problem.
In 2017, Faugère[46] proposed a quantum algorithm for solving Boolean quadratic equations,
by applying Grover’s algorithm in some step of the classical algorithm of Bardet, et al.[243] . The
complexity of this algorithm is O(20.462n ), where n is the number of indeterminates. It is better
than direct application of Grover’s algorithm, which would have complexity O(20.5n ).
In the same year, Chen and Gao[120] proposed a quantum algorithm to solve general Boolean
equations over F2 . The complexity of this algorithm is O((n 3.5 + T 3.5 )κ2 log(1/ε)), where T
is the total number of terms of the input polynomials, κ is the maximal condition number of
the converted complex linear systems, and ε is the precision. The key idea in Chen and Gao’s
algorithm is to convert a Boolean polynomial system into an equivalent sparse linear system
over the complex numbers, then solve it with HHL linear solver.
Below we introduce Chen and Gao’s algorithm[120] . Let the input Boolean polynomial
system be F. Since it is trivial to decide whether taking value 0 for all variables, or taking
value 1 for all variables, is a solution to F , we simply assume that none of (0, 0, · · · , 0) and
(1, 1, · · · , 1) is a solution to F .
Step 1 Convert the input Boolean polynomial system F into a projection-equivalent 3-

sparse Boolean polynomial system, denoted by F3 .
By introducing new Boolean variables to represent Boolean binomials, any Boolean poly-
nomial can be extended to a Boolean trinomial system, or 3-sparse polynomial system. In this
way, F is extended to a 3-sparse Boolean polynomial system, denoted by F3 . The projection
of the F2 -variety defined by F3 onto the component space of the original Boolean variables, is
just the F2 -variety of the input polynomial system F.
For example, if F = {x1 x2 + x2 + x3 + x4 }, by introducing new Boolean variable x5 :=
x1 x2 + x2 , F is extended to F3 = {x5 + x1 x2 + x2 , x5 + x3 + x4 }. The Boolean solutions of F3
when projected onto the components x1 , x2 , x3 , x4 , give all the Boolean solutions of F .
Step 2 Convert 3-sparse Boolean polynomial system F3 into an equivalent 6-sparse C-

polynomial system, denoted by F3,C .
A C-valued variable xi is Boolean if and only if
x2i − xi = 0, or equivalently, xi (xi − 1) = 0. (4.40)
A 3-sparse Boolean polynomial is a polynomial of at most three terms and each term has
coefficient 1. Any 3-sparse Boolean polynomial fj equals zero in F2 if and only if when fj is
taken as a C-polynomial, then either fj = 0 or fj = 2 when all its variables xi satisfy (4.40).
By replacing every polynomial fj ∈ F3 with the polynomial of
fj (fj − 2) = 0, (4.41)
then adding into F3 the polynomial of (4.40) for every variable xi of F3 , an enlarged C-
polynomial system is obtained, whose elements are 6-sparse, because if fj = a + b + c is a
trinomial, where monomials a, b, c take values in {0, 1}, then
fj (fj − 2) = a2 + b2 + c2 + 2ab + 2ac + 2bc − 2a − 2b − 2c = 2ab + 2ac + 2bc − a − b − c. (4.42)
The enlarged polynomial system is denoted by F3,C . The F2 -variety of the Boolean polynomial
system F3 is identical with the C-variety of its enlargement F3,C .
Step 3 Convert 6-sparse C-polynomial system F3,C into an equivalent sparse C-linear
system, denoted by F3,C,M .
The original Boolean polynomial system F has n variables and O(T ) polynomials, the
converted 3-sparse Boolean polynomial system F3 has O(n+T ) variables and O(T ) polynomials.
Suppose F3,C contains r polynomials in N variables, then r = O(n + T ) and N = O(n + T ).
Given an integer D > 0, all monomials of total degree ≤ D in the variables of F3,C span a

C-linear space of dimension M := D+N N . Observe that a solution to a polynomial equation
fi = 0 is always a solution to fi g = 0 for any monomial g. Any polynomial fi of F3,C can
generate a set of polynomials of degree ≤ D when multiplied with suitable monomials. Denote
by F3,C,M all the polynomials derived from the polynomials of F3,C in this way.
M−1
Each polynomial in F3,C,M , when set to be zero, is of the form i=1 λi mi = −λ0 , where
the mi are monomials of degree between 1 and D, and λ0 is the constant term of the polynomial.
Then polynomial system F3,C,M when taken as equations, can be written as a linear system of
the form
A(m1 , · · · , mM−1 )T = b, (4.43)

where b is a vector of dimension ri=1 D+n−degf n
i
, and the summation runs over all fi ∈ F3,C .
When D takes the complete solving degree [120]
of F3,C , then (4.43) is the Macaulay linear
system associated with F3,C , and solving the linear system gives all the C-solutions to F3,C . By
a delicate corollary of Lazard’s Lemma[120] , for polynomial system F3,C , its complete solving
degree is O(n + T ). Furthermore, the modified Macaulay matrix A has both row sparsity and
column sparsity O(n + T ).

Step 4 Solve linear system (4.43) by HHL linear solver within error bound ε/(n + T ).
The C-variety of F3,C is obviously 0-dimensional. Let all the zeros of F3,C be z1 , · · · , zw .
Then each zi is a (0, 1)-string of length M − 1. Since HHL algorithm returns the least-square
solution, a result of [120] shows that with high probability, the algorithm returns an approximate
of a state that can be written as

w
ηi |m1 (zi ), · · · , mM−1 (zi ) (4.44)
i=1
w
up to normalization, where the ηi ∈ C satisfy i=1 ηi = 1.
Step 5 Make measurement to the solution state to obtain a solution of value 1 for at least
one variable of F3,C .
For example, if ground state |1, 0, · · · , 0 is a measured result of (4.44), then m1 (zi ) = 1 for
some zero point zi of F3,C . Since m1 is a monomial in (0, 1)-valued variables, all its variables
must take value 1 at point zi . The variables in m1 are thus solved.
Step 6 Update polynomial system F3,C by substituting value 1 into solved variables.
Repeat the above procedure from Step 3 to Step 6, until no solution with value 1 is found
for F3,C . Then a complete solution is found for the original system F, where the variables
remaining unsolved take value 0.
Extending Chen and Gao’s algorithm to solve polynomial equations over a finite field is
straightforward[121] . Let the finite field be Fm . In Step 2 of the above algorithm, for any
variable Xi taking value in Fm , (4.40) is replaced by
Xi (Xi − 1) · · · (Xi − m + 1) = 0, (4.45)
and (4.41) for 3-sparse polynomial fj over Fm , is replaced by
fj (fj − m)(fj − 2m) · · · (fj − qm) = 0, where q < 3mdegfj . (4.46)
Furthermore, by introducing new variables, any polynomial equation can be replaced by a set
of quadratic ones. By the binary expression of integers, a variable taking value in Fm can be
replaced by a set of Boolean variables.
In [121], Chen, et al. also considered the following optimization problem over a finite field:
for variables X = {x1 , · · · , xn } and Y = {y1 , · · · , yt }, given functions f1 , · · · , fr ∈ Fm [X] and
h, g1 , · · · , gs ∈ Z[X, Y ], given positive integers b1 , · · · , bs and u1 , · · · , ut , solve for
⎧
⎪
⎪ i = 1, 2, · · · , r;
⎨ fi (X) = 0 mod m,
MinimizeX,Y h(X, Y ), subject to 0 ≤ gj (X, Y ) ≤ bj , j = 1, 2, · · · , s; (4.47)
⎪
⎪
⎩
0 ≤ yk ≤ u k , k = 1, 2, · · · , t.
Since set X and the range of values of the yk are both finite, so is the range of values of
function h. Finding minX,Y h(X, Y ) can be done by solving h(X, Y ) = hi , where hi ranges over
all possible values of function h, starting from the smallest one. Each inequality 0 ≤ gj ≤ bj
can be replaced by equality gj (gj − 1) · · · (gj − bj ) = 0. By introducing binary expressions
for bounded integer variables, the optimization problem over a finite field is reduced to C-
polynomial equation solving for Boolean variables.
4.4 Application in Machine Learning: Supervised Classification

Let there be two subsets (classes, or clusters) of vectors V = {v1 , · · · , vM } and W =
{w1 , · · · , wM } in RN . Problem: Given u ∈ RN , determine whether u should be assigned to V
or W , based on the distances from u to the means of V and W respectively:

1
M 1
M

dist(u, V ) := u − vj ; dist(u, W ) := u − wj . (4.48)
M M
j=1 j=1
This is the nearest-mean classifier, the simplest among multivariate parameter classifiers[232] .
Its complexity rests in the evaluation of (4.48). Classical methods to compute the distances
cost O(M N ).
In 2013, a quantum algorithm for the problem was proposed by Lloyd, et al.[127] , which
has complexity O((log M N )/ε), where ε is the precision. It achieves exponential speedup over
classical algorithms. Below we introduce this algorithm.
Consider evaluating dist2 (u, V ) by (4.48). In quantum computing, evaluating an inner
M
product can be done efficiently by swap test, as long as the classical vector u − M −1 j=1 vj
can be converted into its quantum state form, or more accurately, a quantum state of the form
⎛ ⎞
1
M
|ψ = t ⎝u |u − vj |vj ⎠ |0 + (· · · )|0⊥ , (4.49)
M j=1
where t > 0 is a known scalar.
Step 1 Prepare the initial state

⎡ ⎤
1 1 1 M
|ψ1 = √ |0 |0|0 − |1|M = √ ⎣|0|0|0 − √ |0|1|j⎦ . (4.50)
2 2 M j=1
Step 2 Use the last register to control in the first register of |ψ1 the preparation of u |u
when the register is in state |0, and vj |vj when the register is in state |j for 1 ≤ j ≤ M .
Let u = (u0 , · · · , uN −1 ) and vj = (vj0 , · · · , vj(N −1) ) for 1 ≤ j ≤ M . Denote
1
t= . (4.51)
maxj,k (|uk |, |vjk |)
Assume that t is given. t can be replaced by a known lower bound of the 1/|uk | and 1/|vjk |.
√ |u|0 + (· · · )|0⊥ is
In (3.32) of the proving procedure of Proposition 3.4, quantum state tu
N
tv
prepared efficiently. Similarly, √Nj |vj |0 + (· · · )|0⊥ can be prepared simultaneously.
The result of Step 2 is
⎡ ⎤
M
1 ⎣ tu 1 tv
√ |u|0 + (· · · )|0⊥ |0|0 − √ √ |vj |0 + (· · · )|0⊥ |1|j⎦ .
j
|ψ2 = √
2 N M j=1 N
(4.52)
The next to the last register of |ψ2 has one qubit, and takes state value |0 in the first part of
the expression, and state value |1 in the second part.
Step 3 To change |j in the last register of |ψ2 into |0 for all 1 ≤ j ≤ M , use the next
to the last register of |ψ2 as the control register, so that if the control register is in state |0,
then do nothing, else apply Hadamard gate to the last register.
Result:

1
M
t
|ψ3 = √ u |u|0|0|0 − vj |vj |0|1|0 + (· · · )|0⊥ |0|0
2N M j=1

+(· · · )|0|1|0⊥ + (· · · )|0⊥ |1|0 + (· · · )|0⊥ |1|0⊥ . (4.53)
Step 4 Apply Hadamard operator to the next to the last register of |ψ3 . Result:
⎡ ⎤
t 1 M
|ψ4 = √ ⎣u |u − vj |vj ⎦ |0, 0, 0 + (· · · )|0, 0, 0⊥ . (4.54)
2 N M j=1
M
Then quantum state u |u − M1
j=1 vj |vj is prepared.
Step 5 In (4.54), the probability of observing state |0, 0, 0 in the last three registers is
2
1
M
t2 t2
u− vj = dist2 (u, V ). (4.55)
4N M j=1 4N
Use swap test (Lemma 3.2) to estimate t2 dist2 (u, V )/(4N ), from which dist2 (u, V ) is obtained.
4.5 Application in Machine Learning: Linear Regression

Given a set of samples {(xi , yi ) | 1 ≤ i ≤ N }, where each xi ∈ CM is a column vector,
and each yi ∈ C is a data, linear regression aims at finding a vector c ∈ CM minimizing
N †
i=1 |xi c − yi | . By differentiation, the problem is reduced to solving the following linear
2
system:
X † Xc = X † y, (4.56)
where X † = (x1 , · · · , xN ), and y = (y1 , · · · , yN )T .

Linear regression plays an important role in (supervised) machine learning[244, 245] . The
purpose of linear regression is to find a linear function that reflects the global trend of the data
evolution, based on which a prediction can be made. Since HHL algorithm returns the least-
square solution of a linear system, it can be applied directly to linear regression[124] . Besides
HHL algorithm, other quantum algorithms for linear regression include [109, 125, 126, 228].
Linear regression is also an example in which the quantum state solution of a quantum
linear solver is sufficient to solve the problem. Suppose a solution state |c is obtained from a
quantum linear solver. For a new vector d ∈ CM , the prediction on the new data is done by
evaluating the inner product c|d, which can be estimated by swap test.
Regularization of ill-conditioned linear regression.
In solving linear system (4.56), if X † X is not invertible, then the linear solver may fail if
X y is not in the well-conditioned region of X † X, as mentioned in Remark 4.1.
†
One method to overcome this difficulty is regularization[245] . A new term λI is added to

†
X X, where λ is the regularization parameter, and I is the identity matrix. The linear system
is changed into (X † X + λI)

c = X † y for new vector variable c that is taken as an approximate
of c. The choice of parameter λ is technical.
Locally weighted linear regression.
In data fitting, a more prevalent method is locally weighted linear regression (or “piecewise”
linear regression)[246, 247] . In this method, linear regression is done locally based on the samples
close to the new vector whose data is to be predicted.
Locally weighted linear regression is equivalent to solving the following linear system:
X † W Xc = X † W y, (4.57)
where diagonal matrix W = diag(w0 , · · · , wN −1 ) serves as a filter, in which wi ≥ 0 for 0 ≤

i < N . A possible choice of wi is the Gauss kernel function[244, 248] . Usually W is a low-rank
matrix.
√ √
Set Xnew = W X, and ynew = W y. Then (4.57) can be written as
† †
Xnew Xnew c = Xnew ynew . (4.58)
Since W is low-rank, so is Xnew . According to [112, 127], low-rank Hermitian matrices can be
simulated efficiently. So HHL algorithm is efficient for locally weighted linear regression.
4.6 Application in Machine Learning: Least-Square Support Vector Machine

(SVM)
Given a set of training examples {xi ∈ RN , 1 ≤ i ≤ M }, each with a label yi ∈ {1, −1} for
1 ≤ i ≤ M to mark the example as belonging to one of two classes, the SVM problem is to find
a hyperplane that divides the points of separate classes with maximal margin[232, 245] .
Denote the hyperplane that divides the two classes by w·x−b = 0, where b ∈ R and w ∈ RN .
Formally, the hyperplane is constructed so that w · xj − b ≥ 1 if yj = 1, and w · xj − b ≤ −1 if
yj = −1. The points on the hyperplanes w · x − b = ±1 are called support points. The SVM
problem aims at finding a hyperplane w · x − b = 0 that maximizes the distance between the
two parallel hyperplanes w · x − b = ±1.
The distance from any support point to hyperplane w · x − b = 0 is 1/w. So the SVM
problem can be stated as the following quadratic convex optimization:
min w2 , s.t. yj (w · xj − b) ≥ 1, j = 1, 2, · · · , M. (4.59)

b∈R,w∈RN
When all the inequalities in (4.59) are replaced by equalities, the optimization problem is
called least-square SVM[249] :

M
min w + γ
2
ej , s.t. yj (w · xj − b) = 1 − ej , j = 1, 2, · · · , M,
2
(4.60)
b,ej ∈R,w∈RN
j=1
where γ > 0 is determined by the user, and the ej are slack variables that are indispensable if
the separating hyperplane does not exist: They measure the deviation of a data point from the
ideal condition of pattern separability.
The quadratic programming (4.60) can be reduced to a linear system by introducing La-
grange multipliers λ = (λ1 , · · · , λM )T . The Lagrange function is
w2 γ 2
M M !
L= + ej − λj (w · xj − b)yj − 1 + ej . (4.61)
2 2 j=1 j=1
In the optimization, the partial derivatives of L with respect to its arguments are all zero:
⎧
⎪
⎪ M
⎪
⎪ ∇ w L = w − λj yj xj = 0,
⎪
⎪
⎪
⎪
⎪
⎪
j=1
⎨ ∂L/∂e = γe − λ = 0,
j j j
(4.62)
⎪
⎪ M
⎪
⎪ ∂L/∂b = λj yj = 0,
⎪
⎪
⎪
⎪
⎪
⎪
j=1
⎩
∂L/∂λj = (w · xj − b)yj − 1 + ej = 0.
M
j=1 λj yj xj . Given a new vector z ∈ R , its
M
The first equation of (4.62) gives w =
classification by hyperplane w · x − b = 0 is determined by the sign of

M
w · z − b = −b + λj yj xj · z. (4.63)
j=1
Estimating the sign of the expression on the right side can be done in the same way as evaluating
dist2 (u, V ) by (4.48) in supervised classification. We sketch some details below.
Eliminating w and the ej from (4.62) leads to the following linear system:
⎡ ⎤⎡ ⎤ ⎡ ⎤
0 yT −b 0
⎣ ⎦⎣ ⎦ = ⎣ ⎦, (4.64)
−1
y K + γ IM λ 1
where
K = (yi yj xi · xj )i,j=1,2,··· ,M , y = (y1 , · · · , yM )T , 1 = (1, · · · , 1)T ∈ RM . (4.65)
Step 1 By HHL algorithm, a quantum state solution to (4.64) can be obtained, and is in
the form
1 M
| − b, λ := $ M − b|0 + λj |j . (4.66)
b2 + j=1 λ2j j=1
Step 2 Similar to the construction of (4.52), from (4.66) the following quantum state can
be constructed:

1 M
|ψ−b,λ = $ − b|0|0 + λj yj xj |j|xj . (4.67)
b2 + M λ
j=1 j
2 x 2
j j=1
Similar to the construction of (4.54), the following quantum state (“query state”) can be
constructed simultaneously with the construction of |ψ−b,λ :

1 M
|ψz = |0|0 + z |j|z . (4.68)
M z2 + 1 j=1
Step 4 By (4.67), (4.68) and (4.63),
ψ−b,λ |ψz = μ(−b + w · z), for some μ > 0. (4.69)
By swap test, the inner product of |ψ−b,λ and |ψz can be estimated, by whose sign z is
classified into the correct class.
Applying HHL algorithm to solve (4.64) needs efficient Hamiltonian simulation of the coef-
ficient matrix. In [129], a method was presented to do this. The method was inspired by the
work of [128] on quantum principal component analysis.
5 Quantum Walk
A quantum walk is the quantum counterpart of a random walk[95] . To introduce quantum
walk, first recall some basic facts of random walk[250, 251] .
5.1 Basic Terminology in Markov Chain

A Markov process is a random process that takes a distribution on some state space Ω ,
and maps it to another distribution on Ω , such that the distribution of the next state depends
only on the current state. A random walk (or Markov chain, or Markov diffusion) (Ω , P ), is a
Markov process with a stochastic transition matrix P = (puv ) defined on a discrete state space
Ω , such that for any u, v ∈ Ω , puv gives the probability of moving to state v from state u.
A Markov chain is symmetric if its transition matrix is symmetric. A Markov chain is state-
transitive if there is a transitive permutation group acting on the state space that leaves the
transition matrix invariant. A random walk is called a uniform diffusion if all entries of the
transition matrix are identical.
The period of state u is the minimal nonzero step to return to u when starting from u. A
Markov chain is said to be aperiodic if the GCD of all the periods of the states is 1. A Markov
chain is irreducible if every state is reachable from every other state. It is ergodic if it is both
irreducible and aperiodic.
A stationary distribution π T of Markov chain (Ω , P ) is a probability distribution on Ω such
that when π T is taken a row vector, then π T P = π T . As π T is a left eigenvector of matrix P
with eigenvalue 1, if the current state is distributed according to π T , the next state follows the
same distribution.
Any irreducible Markov chain has a unique stationary distribution. For any irreducible and
symmetric Markov chain, its stationary distribution is uniform.
For an irreducible Markov chain (Ω , P ), denote |Ω | = N , and denote the stationary distri-
bution by row vector
π T = (π T (u))u∈Ω := (π1 , · · · , πN ). (5.1)
The time-reversed Markov chain of (Ω , P ) is a Markov chain (Ω , P

), where P
= (p
uv )u,v∈Ω
is defined by
πv
p
uv := pvu . (5.2)
πu
(Ω , P ) is said to be reversible if P
= P , i.e., for every pair of states u, v ∈ Ω ,
πu Puv = πv Pvu . (5.3)
A random walk on an undirected graph is always reversible.

The discriminant matrix of matrix P is

D(P ) := ( puv p
vu )u,v∈Ω . (5.4)
√ √ √
By puv p
vu = πu puv πv −1 ,
$ $ −1
D(P ) = diag(π T )P diag(π T ) , (5.5)
where diag(π T ) is the diagonal matrix whose diagonal entries are the components of vector π T .
Matrix D(P ) is symmetric if and only if (Ω , P ) is reversible.
The distance between two distributions (row vectors) ρT = (ρu )u=1,2,··· ,N , ρ = (ρ u )u=1,2,··· ,N
T
on Ω , is measured by their total variation distance:

1
ρT − ρ tv := |ρu − ρ u |.
T
(5.6)
2
u∈Ω
The total variation distance between ρT , ρ is half the L1 -norm of their difference.
T
For an ergodic Markov chain (Ω , P ), the mixing time Tmix is the minimal number of steps
for any initial distribution to approximate the stationary distribution:

Tmix := min{t ∈ N ρT P t − π T tv ≤ 1/4, ∀ initial distribution ρT }. (5.7)
In (5.7), it seems more appropriate to measure the approximation of π T by ρT P t with some

ε 1, by defining the “ε-mixing time” Tε to be the minimal natural number t such that for
any initial distribution ρT , ρT P t − π T tv ≤ ε. In fact, Tmix ≤ Tε ≤ log2 (1/ε)Tmix. So
Tε = Θ (Tmix ), and the two mixing times can be taken to be equivalent.
An important concept in Markov chain is the spectral gap of the transition matrix P . Let
λ1 , · · · , λN be the multiset of all the eigenvalues of P in norm-decreasing order. It is a classical
result[252] that 1 = λ1 ≥ |λ2 | ≥ · · · ≥ |λN |. The spectral gap of P is defined as
δ := 1 − |λ2 | ≥ 0. (5.8)
If P is ergodic, then δ > 0.

The spectral gap is closely related to the mixing time Tmix . If (Ω , P ) is reversible and
ergodic, with spectral gap δ and stationary distribution π T = (πu )u∈Ω , then

1 3 1 3
− 1 log ≤ Tmix ≤ log . (5.9)
δ 2 δ minu∈Ω πu

When π T is the uniform distribution, then minu∈Ω πu = 1/N , and Tmix = Θ(1/δ).
The hitting time h(u, v) from state u to state v is the expected number of steps to hit v
when starting from u. If M is a set of states, the hitting time h(u, M) can be defined similarly.
The average hitting time from an initial distribution ρT = (ρu )u∈Ω to M is defined by

h := h(ρT , M) = ρu h(u, M). (5.10)
u∈Ω
It is related to the spectral gap as follows[253] :
1 1 |M|
≤ h ≤ , where ε = . (5.11)
ε εδ N
For random walk (Ω , P ), the absorbing walk of subset M ⊂ Ω is a random walk (Ω , PM ),
with ⎛ ⎞
P P
PM = ⎝ ⎠, (5.12)
0 I
where matrix P is obtained from P by deleting all rows and columns indexed by M, and P
is obtained from P by deleting all rows indexed by M and columns indexed by Ω \ M. The
walker PM behaves like P but is absorbed by the first state of M it hits. Absorbing walk is an
important tool in designing search algorithms, with M as the goal.
5.2 Discrete-Time Quantum Walk on the Line

Discrete-time quantum walk on the line is the most extensively studied model of quantum
walk. The simplest classical discrete-time random walk on the line consists of a walker and a line.
The walker starts in location 0, and moves left with probability 1/2 and right with probability
1/2. The straightforward counterpart would be a quantum process with basis states |n for all
n ∈ Z, and at each step, a unitary transformation is performed so that the move would be to
the left with amplitude a, staying in the same place with amplitude b, and moving to the right
with amplitude c, where |a|2 + |b|2 + |c|2 = 1. However, this is impossible. It is proved in [86]
that the only possible transformations are that at each step, the move is either always to the
left, or staying in the same place, or always to the right. The same thing happens for quantum
walks on general graphs.
To define discrete-time quantum walk on the line correctly, besides the position space
{|n, n ∈ Z} and the (unitary) evolution operators, an additional 1-qubit register called the
coin state must be introduced, so that the state space includes the coin besides the position.
The following is the basis states:

{|n, 0, |n, 1 n ∈ Z}. (5.13)
For the evolution operators, at each step there are two unitary operations: A coin flip transfor-
mation C deciding in which direction to move, and a shift operator S to make the move, so that
one step of quantum walk is the composition SC, for which there are a, b, c, d ∈ C satisfying
|a|2 + |b|2 = |c|2 + |d|2 = 1, such that
C|n, 0 = a|n, 0 + b|n, 1, S|n, 0 = |n − 1, 0,

(5.14)
C|n, 1 = c|n, 0 − d|n, 1, S|n, 1 = |n + 1, 1.
√
The most common choice for C is the Hadamard transform, where a = b = c = d = 1/ 2.
Consider the first three steps of such a quantum walk[87, 90] starting from state |0, 0:
C 1 S 1
|0, 0 → √ (|0, 0 + |0, 1) → √ (| − 1, 0 + |1, 1)
2 2
C 1 S 1
→ (| − 1, 0 + | − 1, 1 + |1, 0 − |1, 1) → (| − 2, 0 + |0, 1 + |0, 0 − |2, 1)
2 2
C 1
→ √ (| − 2, 0 + | − 2, 1 + 2|0, 0 − |2, 0 + |2, 1)
2 2
S 1
→ √ (| − 3, 0 + | − 1, 1 + 2| − 1, 0 − |1, 0 + |3, 1). (5.15)
2 2
If after the second step the state is measured, then n = −2 and n = 2 would be found with
probability 1/4 for each, and n = 0 be found with probability 1/2. This is exactly the case
in a classical random walk. From the third step on, quantum walk behaves differently from
random walk. In random walk, the left and right direction each have probability 1/2. In the
quantum case, due to quantum interference, the probability distribution is non-symmetric and
biased towards the left. The difference becomes more striking with the increase of the number
of steps.
There are two prominent distinctions of quantum walk from random walk, which exist for
almost all choices of coin transformation and initial state[87, 90] :
• In the evolution of the probability distribution of the states, after t steps, the maximum
√
probability is reached for n ≈ ± t/ 2. In contrast, in classical random walk, the maximum
probability is reached for n ≈ 0.
• There are Ω (t) locations of n for which the probability of measuring |n, 0 or |n, 1 is
Ω (1/t). This means that the expected distance between the starting location 0 and the
location to make measurement after t steps is Ω (t). So quantum walk spreads quadrati-
cally faster than its classical counterpart. This is key to fast quantum algorithm design.
5.3 Discrete-Time Quantum Walk on Undirected Graph

The following is a simple way to define discrete-time quantum walk on an undirected
graph[254–256] with vertices V and edges E: The basis states are

{|v, e v ∈ V, e ∈ E such that v is incident to e}. (5.16)
The evolution is the composition of a shift operator S and a coin flip transformation C. For
the shift operator, if edge e has endpoints v, v , then
S|v, e = |v , e, S|v , e = |v, e. (5.17)

For each vertex v, the coin flip transformation C is performed to all the states |v, e where e is
incident to v. A natural choice of C is Grover’s diffusion.
In designing fast quantum algorithms with quantum walk, Johnson graph is an important
tool. For any two positive integers n and r with r < n, the Johnson graph J(n, r) is the graph
whose vertices are all subsets of N = {1, 2, · · · , n} of cardinality r, and whose edges are such
that an edge connects two vertices if and only if the vertices as two subsets of N differ by
exactly one element.
The random walk on J(n, r) can be intuitively described as follows: at every step, if S is
the current vertex, then when moving to the next vertex S , since the two vertices must be the
two endpoints of an edge, one element of S (the unique element in S \ S ) is replaced by the
only element in S \ S. For any 2 < r < n, the stationary distribution of the random walk
on J(n, r) is unique and is the uniform distribution, because J(n, r) is a degree-regular graph.
Furthermore, the spectral gap of the transition matrix of the random walk on J(n, r) is ≥ 1/r.
For a special class of graphs called glued balanced binary trees, quantum walk gains expo-
nential speedup over all classical algorithms in hitting time. The simplest graph of this kind
is a graph obtained by identifying the leaves of a balanced binary tree with the corresponding
leaves of the mirror image of the tree. Suppose that the original tree T lies in the plane, whose
leaves are aligned along a vertical line L in the plane. Then the mirror image T of tree T with
respect to line L is another tree whose leaves are identified with those of T . Let the depth of
each tree be d, and let the walker go from the root of one tree to the root of the other. For a
classical random walker, it takes Ω (2d ) steps (hitting time) to reach one root from the other.
In contrast, Childs, et al.[94] showed that a continuous-time quantum walker can do so in O(d2 )
steps.
A more complicated graph is two balanced binary trees of depth d joined by a random cycle
of length 2d+1 that alternates between the leaves of the two trees. Classical random walkers
take O(2d ) steps to find one root from the other, but the quantum walkers in [93, 94] take
O(d2 ) steps to do so. Furthermore, in [93] it was shown that any classical algorithm (not just
classical random walk) requires an exponentially large number of steps.
5.4 Application: Search on Boolean Hypercube

In a Boolean hypercube, there are N = 2n vertices {vx , x = 0, 1, · · · , N − 1} indexed by
n-bit strings (binary expressions of the x). Two vertices vx and vy are connected by an edge if
and only if the corresponding string forms of x and y differ in exactly one bit. Suppose there
is only one marked vertex on the hypercube. Find it.
In quantum walk, the state space is spanned by the basis states
{|x|i, x = 0, 1, · · · , N − 1; i = 0, 1, · · · , n − 1}, (5.18)
where x ∈ {0, 1}n = {0, 1, · · · , N − 1} is used to index the vertices of the hypercube, and
i ∈ {1, 2, · · · , n} is used to index the edges by bits. The edge register serves as the coin, and the
vertex register serves as the walking space. The value of an n-bit string x at bit i is denoted by
xi . For x = (x0 , · · · , xn−1 ), where xi ∈ {0, 1}, flip(x, i) := (x0 , · · · , xi−1 , 1−xi , xi+1 , · · · , xn−1 ).
The distance between two vertices is the minimal number of edges connecting them. It
agrees with the Hamming distance between the two vertices taken as n-bit strings. For an n-bit
string x, its Hamming weight |x| is the number of nonzero bits, or the distance from 0-string.
Grover search can be used directly on the hypercube. However, due to the spatial structure,
a vertex in the hypercube is connected to only n = log N vertices. At each vertex, only the
local Grover’s diffusion Rn is available, and applying the diffusion for once only spreads the
superposition of vertex states to the neighbors of the vertex. In other words, the walker following
Grover’s diffusion goes only one step on the hypercube. To reach the farmost vertex, whose
distance from the current vertex is n, Grover’s diffusion Rn must be repeated n times, so
that all the N states in the superposition |N are accessed. Hence, a factor n is added to the
√
number of iterations O( N ) in Grover’s search algorithm, giving the step complexity ( minimal
√
number of steps a most unlucky walker needs to go to make the finding): O( N log N ).
In 2003, Shenvi, et al.[92] presented an algorithm to make the search by quantum walk in
√
O( N) steps. The following is their algorithm.
Algorithm 5 Quantum search on Boolean hypercube[92]

1: [Setup] Generate the superposition state
1
|N ×n := √ |x|i. (5.19)
N n x,i
√
2: Do the following steps O( N ) times:
(2.1) [Checking, and tossing coin] If vertex x is not marked, then apply Grover’s diffusion
Rn to register |i, else apply −I to register |i.
(2.2) [Walking, update of position] Apply shift S : |x|i → |flip(x, i)|i.
3: Measure the final state at the first register.
The algorithm itself is very simple, and is based on a quantum walk on the hypercube that
is taken as an undirected graph. However, the analysis of the correctness of the algorithm
is rather involved. Suppose there is a unique marked vertex m ∈ {0, 1, · · · , N − 1} on the
hypercube. The evolution operator U is the composition of the shift operator S and the coin
transformation C. With respect to the basis states (5.18),
C = 2(IN − |m m|) ⊗ |n n | − IN ⊗ In . (5.20)
A key idea in the analysis is to reduce the quantum walk on the hypercube to a quantum
walk on the line. For a line segment {0, 1, · · · , n} of n + 1 nodes, add a coin with two states
{R, L} to form the following 2n orthonormal basis states: For any 0 ≤ y < n and 0 < z ≤ n,
1 1
|y, R := $ n |x, i, |z, L := $ |x, i. (5.21)
(n − y) y |x|=y 0≤i<n, xi =0 z nz |x|=z 0≤i<n, xi =1
Denote by Ω the (2n)-space they span. Then

n−1
1 1
n−1 n−1
|N ×n = √ |0, R + √ |n, L + x−1
|x, L + x
|x, R . (5.22)
N N x=1
N N
Space Ω is invariant under Grover’s diffusion Rn when the latter acts on the edge space of
the hypercube. With respect to the basis states (5.21) supplemented with two “forbidden basis
states” |n, R and |0, L, Rn acts as
⎛ ⎞
n
cos ωy sin ωy
|y y| ⊗ ⎝ ⎠, (5.23)
y=0 sin ω y − cos ω y
where
2y 2
cos ωy = 1 −
, sin ωy = y(n − y). (5.24)
n n
So the new coin space is invariant under Rn .
Furthermore, space Ω is also invariant under the shift operator S and the evolution U = SC.
In Ω , the shift S acts as

n−1

y, R y + 1, L + y + 1, L y, R . (5.25)
y=0
By (5.20), the restriction of U to Ω depends on the specific value of |m. Let the marked state
be |m = |0 for simplicity. In space Ω , the evolution U acts as

n−1

U : = −2|1, L 0, R| + |x, R − cos ωx+1 x + 1, L| + sin ωx+1 x + 1, R|
x=0

n

+ |x, L sin ωx−1 x − 1, L| + cos ωx−1 x − 1, R| . (5.26)
x=1
So the quantum walk on the hypercube induces a quantum walk on the line segment, with
basis position states {|0, · · · , |n}, basis coin states {|R, |L}, and evolution operator U when
|m = |0. To show the correctness of the algorithm, check how the evolution U accumulates
the amplitudes towards the subspace of CN ⊗ Cn spanned by {|0|i, i = 0, 1, · · · , n − 1}, when
walking on line segment Ω .
For the initial state |N ×n ,
2
U |N ×n = |N ×n − √ |1, L. (5.27)
N
So N ×n |U |N ×n = 1 − 21−n, and |N ×n is almost an eigenvector of U with eigenvalue 1.
Define
-
.n/2−1

n/2−1
. % n − 1
|φ :=
1
$
1
|x, R − |x + 1, L , where c = / 1 . (5.28)
c x=0 n−1
x
2 x x=0
It is a unit vector orthogonal to |N ×n . If this state is available, then by measuring the first
register of |φ as in Step 3 of Algorithm 5, the probability of getting the marked vertex |0 is

1 2 1 2
n−1
1 1
0, i|φ = 0, R|φ ≥ − O , (5.29)
c i=0 c 2 n
where 1 < c2 < 1 + 2/n for sufficiently large n is used. The goal is thus to show that by starting
from |N ×n and making a number of iterations of U , state |φ can be prepared approximately.
It is easy to verify that
1
U |φ = |φ − $ (|n/2 − 1, R + |n/2 + 1, L). (5.30)
c 2 n−1
n/2
So
1 1
φ|U |φ = 1 − n−1 > 1 − , (5.31)
2c2 n/2 2(1 + n2 ) n−1
n/2
and |φ is almost another eigenvector of U with eigenvalue 1.

Shenvi, et al.[92] showed that in Ω , there are two orthonormal eigenvectors |w± of U , with
corresponding eigenvalues e±iθ satisfying cos(θ) > 1 − 2/(3n) ≈ 1. It turns out that the two
eigenvalues are the only eigenvalues of U satisfying the inequality. In the 2-space spanned by
|w± , U acts as a rotation of angle θ ∈ (0, π/2). In fact,

1 n3/2 1
θ= √ +O =O √ 1. (5.32)
c 2n−1 2n N
So the 2-space spanned by |N ×n , |φ almost agrees with the 2-space spanned by |w± .
According to the delicate estimations made in [92], the initial state |N ×n satisfies

|N ×n = a(|w+ + |w− ) + O( n/N ) |r, (5.33)
where 0 < a ≤ 1, and |r ∈ Ω is a unit vector orthogonal to |w± . After t iterations of U ,

&√
(U )t |N ×n = cos(tθ)|N ×n + sin(tθ)|φ + O(n3/4 2n ), (5.34)
each iteration being an angle-θ rotation approximately from |N ×n towards |φ.

In conclusion, starting from |N ×n , it suffices to reach |φ with high precision by t =
√
π/(2θ) = O( 2n ) iterations of U . The setup stage in Algorithm 5 has step complexity
O(log N ). In the checking stage, the flip operation has step complexity 1. So the total step
√
complexity of the algorithm is O( N ).
In 2008, Potocek, et al.[257] showed that if the first register is divided into two subspaces
for even and odd elements respectively, then they can evolve separately by the shift operator.
In this way the probability of finding the solution doubles to almost 1. In 2015, Tonchev[258]
obtained the same result by using a different coin transformation.
5.5 Quantization of Random Walk

The quantization of a random walk was defined by Szegedy[95] in 2004, and further refined
in [96]. In this paper, the given Markov chain (Ω , P ) is always assumed to be irreducible, and
N = |Ω |.
The state space of the quantization of (Ω , P ) is CN ⊗CN , whose basis states are the following
“directed edges” in Ω :

ΩQ := {|u, v u, v ∈ Ω , puv = 0}. (5.35)
Thus, the walker is on a graph whose vertices are the directed edges of Ω defined by the nonzero
entries of P . Alternatively, one can take the coin space to be a copy of the position space.
The evolution is the composition of two unitary operators. The first is the flip operation F
controlled by the position state, so that if the current position state is |x, and the coin state
√
is the superposition of all |y with probability pxy and amplitude pxy , then the coin state is
invariant under the flip operation, because it is exactly the probability distribution of the next
step that the classical random walker P makes, after leaving position |x.
For all x ∈ Ω , denote √
|px := pxy |y. (5.36)
y∈Ω
The |x, px for all x ∈ Ω span an N -space of CN ⊗ CN , denoted by

A := span {|x, px x ∈ Ω }. (5.37)
The reflection RA with respect to A can be selected as the flip operation F .

The second is the shift operation S controlled by the coin state, so that if the current
coin state is |x, and the position state is the superposition of all |y with probability p
xy and

amplitude p
xy , then the position state is invariant under the shift operation, because it is
exactly the probability distribution of the next step that the classical time-reversed random
walker P
makes, after leaving position |x.
Denote
|p
x := p
xy |y, (5.38)
y∈Ω
for all x ∈ Ω . The |p

x , x span another N -space of CN ⊗ CN , denoted by

B := span {|p
x , x x ∈ Ω }. (5.39)
The reflection RB with respect to B can be selected as the shift operation S.

The two N -subspaces A, B in the N 2 -dimensional state space CN ⊗ CN have nontrivial
intersection. For example,
√ √
|π := πu |u, pu = πv |p
v , v (5.40)
u∈Ω v∈Ω
is in A ∩ B.
The evolution operator is denoted by
W (P ) := RB RA . (5.41)
It is a rotation in the state space. (span(ΩQ ), W (P )) is called the quantization of random

walk (Ω , P ), or more accurately, of random walk (Ω , P ) in the coin space followed by the
time-reversed random walk (Ω , P
) in the position space.
Define matrix
√ √
P := ( pij )i,j=0,1,··· ,N −1 . (5.42)
√
Then its rows have norm 1, and itself has norm N . In the notation of (4.15),
−1 N −1
1
√ N √
√
|Pi = pij |j = |pi , |P = √ |i = |N . (5.43)
j=0
N i=0
So A is the image space VM of the linear map LM defined by (4.16), and RA = RVM in (4.18).
According to [113], the implementation of RA based on the unitary operator UM in (4.17)
has time complexity O(poly log N ). If furthermore (Ω , P ) is reversible, then in (5.38), |p
i = |pi
for all 0 ≤ i < N , so by (5.39), RB can also be implemented efficiently. Hence, W (P ) can be
efficiently implemented for all reversible (Ω , P ).
Recall that in (4.19), a unitary W = RVM RVN is defined, with the property that when
{σk = A cos(αk ), k = 0, 1, · · · , N − 1} (5.44)
are all the singular values of matrix A counting multiplicity, where αk ∈ [0, π/2), then (according
to (4.23) and (4.25)) a portion of the spectrum of W is
{e±2iαk , k = 0, 1, · · · , N − 1}. (5.45)
This relation lies the foundation of Algorithm 4 for quantum SVE.

√
In the current setting, matrix A = P , and “SVE unitary” W = RA RN , where RN is
the Grover diffusion. Notice the similarity between W and the quantum walk matrix W (P ) =
RB RA . The spectrum of W (P ) should be related to the singular values of matrix P , in a similar
way as (5.45) to (5.44). This relation is disclosed by the following theorem of Szegedy[95] .
Theorem 5.1 Let P be an irreducible Markov chain, and let cos θ1 , · · · , cos θm be the
multiset of singular values of D(P ) that lie in the open interval (0, 1), where θi ∈ (0, π/2).
Then the complete spectrum of W (P ) is:
• On A + B those eigenvalues of W (P ) that have nonzero imaginary part are exactly

e±2iθ1 , · · · , e±2iθm , with the same multiplicity.
• On A ∩ B the operator W (P ) acts as the identity I. A ∩ B is spanned by the left (and

right) singular vectors of D(P ) with singular value 1.
• On A ∩ B ⊥ and A⊥ ∩ B the operator W (P ) acts as −I. A ∩ B ⊥ (resp. A⊥ ∩ B) is spanned

by the left (resp. right) singular vectors of D(P ) with singular value 0.
• On A⊥ ∩ B ⊥ the operator W (P ) acts as I.
If (Ω , P ) is reversible, i.e., D(P ) is symmetric, then the singular values of D(P ) are equal
to the absolute values of the eigenvalues of P .
Corollary 5.2 (see [96]) Let P be an ergodic and reversible Markov chain. On A + B the
spectrum of W (P ) is:
• |π of (5.40) is the unique eigenvector corresponding to eigenvalue 1.
• e±2iθj are eigenvalues, for all singular value cos θj ∈ (0, 1) of D(P ).
• All the remaining eigenvalues are −1.
Given a subset M ⊂ Ω , for the absorbing walk (Ω , PM ) of M defined by (5.12), there is

a corresponding quantization W (PM ). The quantum hitting time[95] hQ of M refers to the
smallest t ∈ N for which

(W (PM ))t |π − |π ≥ 1/10. (5.46)
6 Frameworks of Search: From Classical to Quantum Algorithms

In a finite set of states Ω , assume that a subset M of states are marked. Given a procedure
C that, on input u ∈ Ω and an associated data structure d(u), checks whether the state u is
marked, the goal of search is either to find an element of M when promised that M = ∅ (called
the finding problem), or to determine whether M is nonempty (called the decision problem).
A typical search algorithm progresses in three stages[210] :
• In the setup stage, access some state of Ω (usually a random state).
• In the walk stage, move from state to state by performing a random walk or quantum
walk. The moves are called updates.
• In addition, perform checking in the walk stage to see if the current state is marked.
The algorithm is required to be correct with probability at least 2/3 in either case, the finding
or the decision problem.
The data structure (or data function) d stores some information of its argument, based on
which it can be determined whether the argument is marked or not. Creating and maintaining
the data structure incurs certain cost. The query complexity refers to the number of visits to
procedure C that determines whether an element is marked or not. In search algorithms, the
cost refers to the query complexity by default.
Corresponding to the three stages, there are three costs in a search algorithm[95] :
• Setup cost S In classical algorithms, S is the cost to sample from Ω and to construct
d(u) from sample u. In quantum algorithms, S is the cost to create a state that is the
superposition of all the states in the search space.
• Update cost U In classical algorithms, U is the cost to simulate a transition in Ω from

u to v, and to update d(u) to d(v). In quantum algorithms, U is the cost to create a state
that is a superposition of all the states adjacent to the current state.
• Checking cost C The cost of checking if u ∈ M by information d(u).
A naı̈ve algorithm to solve the search problem is to repeat the sampling from Ω uniformly
and checking the sample until a marked element is found. The quantum analogue of this naı̈ve
algorithm is Grover search.
6.1 Grover Search Revisited

Let N = 2n and Ω = ZN , let f be a map from Ω to Z2 , and assume that there is a unique
element x0 ∈ ZN such that f (x) = 1 if and only if x = x0 . The search problem is to find x0 .
In the quantum setting, the basis states are

{|x x = 0, 1, · · · , N − 1}. (6.1)
Map f is taken as an oracle. Define unitary operator
Of : |x → (−1)f (x) |x, ∀ x ∈ Ω . (6.2)
It is the reflection in space CN with respect to hyperspace |x0 ⊥ .

Call |x0 the “good” space, and hyperspace |x0 ⊥ the “bad” space. Suppose the initial state
is |ψ. Then
|ψ = a|ψgood + |ψbad , (6.3)
where |ψgood = |x0 , and |ψbad is the component in the bad space, and |a| ≤ 1.
If the initial state |ψ is chosen such that |a| = 1, then |x0 , and hence x0 , is found. If |a| < 1,
suppose an appropriate initial state |ψ is selected such that 0 < a < 1, then a = cos(θ/2) for
some 0 < θ < π, and θ/2 is the angle between vectors |ψ and |ψbad , as shown in Figure 1.
Figure 1 Geometric interpretation of Grover iteration
When θ 1, Grover’s idea[38] is to rotate vector |ψ in the plane spanned by |ψgood and
|ψbad towards vector |ψgood consistently, every time with fixed rotation angle θ, so that if θ
is small, then after some rounds of rotation towards |ψgood (called Grover iteration), the angle
θ between the updated state, denoted by |ψ , with |ψbad is almost π/2. By
|ψ = sin(θ )|ψgood + cos(θ )|ψbad , (6.4)
the probability of obtaining |ψgood by measurement is sin2 (θ ) ≈ 1, i.e., x0 can be found with
high probability by measuring |ψ .
Every rotation in the plane is the composition of two reflections. Figure 1 shows that the
angle-θ rotation towards |ψgood is simply the reflection Of followed by the reflection R|ψ .
Grover selected |N as the initial state |ψ. Then R|ψ is Grover’s diffusion, and
1
|ψbad = √ |x, (6.5)
N − 1 x
=x
0
and the rotation angle θ ∈ (0, π) satisfies

√
sin(θ/2) = N |x0 = 1/ N . (6.6)
√
When N is sufficiently large, θ ≈ 2/ N .
After t times of Grover iteration, the angle between the updated state and |ψbad becomes
θt := tθ + θ/2. (6.7)
As sin2 (θt ) is the probability of observing |ψgood in the updated state, to have sin2 (θt ) ≈ 1,
√ √
i.e., θt ≈ π/2, it suffices to select t ≈ π 4N − 12 = Θ ( N ).
Algorithm 6 Grover search[38]

1: [Setup] Prepare the initial state
√
1 N −1
|N = √ |ψgood + √ |ψbad . (6.8)
N N
√
2: Do the following O( N ) times:
2.1) [Checking] Apply Of (reflection with respect to |ψgood ⊥ ).
2.2) [Update] Apply RN (reflection with respect to |N ).
3: Measure the final state.
Denote M = {x0 }. Then |M| = 1. Let ε be the proportion of marked items M in state
space Ω . Then ε = 1/N .
If using the classical naı̈ve algorithm for the search problem, then the setup subroutine is a
sampling from Ω , the checking subroutine is a visit to f , and the update subroutine is another
sampling from Ω . The query occurs only in the checking subroutine. The checking-and-update
cycle needs to run O(N ) times to find x0 . The setup cost S and update cost U are both zero,
and the checking cost C = O(N ).
In Grover’s algorithm, the number of visits to f is zero in both the setup and the update
√ √
stages (so S = U = 0), and is O( N ) in the checking stage (so C = O( N )). The total costs of
the two algorithms are respectively:
1 1 √
classical naı̈ve : S + (U + C) = O(N ); Grover : S + √ (U + C) = O( N ). (6.9)
ε ε
Grover’s algorithm gains quadratic speedup over the naı̈ve algorithm in parameter 1/ε.
When |M| > 1, then ε = |M|/N . By modifying Step 2 of Grover’s algorithm such that the
√
checking-and-update cycle repeats 1/ ε times, the algorithm becomes valid for all |M| > 0. It
√
has query complexity O(1/ ε), and still achieves quadratic speedup over classical algorithms.
Remark 6.1 The following are some further extensions of Grover’s algorithm.
1) Denote k = |M| > 0. If k is not given beforehand, a quantum algorithm called quantum
counting was proposed by Brassard, et al.[51] in 1998 to get an estimate k of k. If the relative
√
error is τ , then the quantum counting algorithm has query complexity O(1/(τ ε)). This
overhead does not increase the complexity of Grover’s algorithm when k = O(1).
2) Suppose there is a quantum algorithm A that uses no intermediate measurement (so that
it remains a unitary operator), and has probability p 1 of finding a marked state when applied
to an initial state |φ. Now revise Grover’s algorithm as follows: Change the update unitary
√
operation to AR|φ A−1 , and change the number of checking-and-update cycles to O(1/ p).
Then with high probability a marked state can be found by the revised Grover’s algorithm.
The revision is well known as the amplitude amplification algorithm[52] .
3) The time complexity of Grover’s algorithm is O(1/ √ε). Suppose that f is no longer an
0 ≤ i < N . In 2010, Ambainis[259]
oracle, and the time cost for evaluating f (x) at x = i is ti for$
proposed an algorithm that solves the problem in time O( N −1 t2 ), and proved that this
i=0 i
time complexity is optimal.
4) If all the k elements i ∈ Ω such that f (i) = 1 are required to be found, by finding them
one by one, the query complexity is
√
O N/k + (N − 1)/(k − 1) + · · · + (N − k + 1)/1 = O( kN ). (6.10)
5) Grover’s algorithm can be modified to determine if M is empty, and the modified version
is called the randomized Grover’s algorithm[96] . Let ε = |M|/N . First sample from Ω a few
times to accommodate the case that ε ≥ 1/4. If no marked element is found, then proceed as if
√
ε < 1/4. Choose an integer T uniformly at random in [0, N ], make Grover iteration T times
to the initial state in Grover’s algorithm, and measure the final state. If M is not empty, a
marked state is found by measurement with probability ≥ 1/4 (Lemma 2 in [260]), otherwise
no marked element can be found.
6) The Grover iteration is cyclic, so the knowledge of k is necessary to stop it at the
right time to find a solution. To go beyond this restriction, in 2005 Grover proposed a fixed-
point search algorithm[261] , which converges monotonously to the good state, but no longer
has quadratic speedup. In 2014, Yoder, et al.[262] proposed a bounded-error quantum search
algorithm that varies the phase shift as a function of the iteration number, and can achieve
quadratic speedup.
6.2 Application: Collision Problem

A collision in a function f defined on {1, 2, · · · , n}, is composed of two distinct elements
i, j ∈ {1, 2, · · · , n} such that f (i) = f (j). Suppose function f is r-to-one (every image has
exactly r > 0 pre-images). Find a collision.
The problem is of particular interest to cryptology. Some functions such as hash functions
are used in various cryptographic protocols, and the security of these protocols depends crucially
on the presumed difficulty of finding collisions in such functions. When f is two-to-one, the
√
most efficient classical algorithms require Θ( n) evaluations of f .

In 1997, Brassard, et al.[263] proposed a quantum algorithm with query complexity O( 3 n/r),
which is also the complexity lower bound[54] . This algorithm is based on a smart use of Grover
search, and is presented below.
Algorithm 7 Brassard, et al.’s algorithm for function collision problem[263]

1: Choose an arbitrary subset K ⊂ {1, 2, · · · , n} of cardinality k.
2: Construct a table L where each item holds a distinct pair (i, f (i)) with i ∈ K, then sort L
according to the second entry in each item.
3: If L contains a collision, stop and output the collision.
4: Search for an index j ∈ / K such that there exists i ∈ K with f (j) = f (i).
Complexity analysis. The algorithm requires k queries in the first three steps. In the last
step, since K has no collision, in space Ω = {1, 2, · · · , n} \ K, the cardinality of the following
marked set

M = {j ∈ Ω ∃i ∈ K, s.t. f (j) = f (i)} (6.11)
$ n−k
is (r − 1)k, so Grover search needs O (r−1)k queries. The total number of queries is O(k) +
$ n−k x
O (r−1)k . Let k = O((n/r) ), where 0 < x < 1 is an unknown constant. Since r > 1,
1/(r − 1) ≤ 2/r. Then

n−k " 1−x
#
O(k) + O = O ((n/r)x ) + O (n/r) 2 , (6.12)
(r − 1)k
1−x
which takes the minimum O((n/r)1/3 ) when x = 2 .
Besides the function collision problem, there is also the graph collision problem. Given an
undirected graph of n vertices and an oracle access to a labeling of these vertices by 1 or 0, the
graph collision problem is to detect if there are two neighboring vertices that are both labeled
by 1, and if so, find such a couple. The best complexity lower bound is Ω (n1/2 ). In 2007,
Magniez, et al.[60] gave an O(n2/3 )-query quantum algorithm for collision search on general
graphs. This still remains the best result.
6.3 MNRS Quantum Walk Framework

In classical search, random walk can be used to improve the efficiency. Algorithm 8 below
follows this idea. It has complexity S + (U + C)/(εδ), where δ is the spectral gap of the transition
matrix P , and
ε= πu , (6.13)
u∈M
where π = (πu )u∈Ω is the stationary distribution of the random walk. If π T is the uniform
T
distribution, then ε = |M|/|Ω | is the proportion of marked items.
Algorithm 8 Classical search by one-step random walk

1: [Setup] Sample from Ω to get a sample u.
2: Do the following h = O(1/(εδ)) times, according to estimation (5.11):
2.1) [Checking] If u is marked, then return u and stop.
2.2) [Update] Start from u, simulate random walk P on Ω for one time step.
3: Return “no marked item”.
In Substep 2.2 of Algorithm 8, instead of simulating the random walk for once, one can make
the simulation several times, i.e., the walker can go several steps instead of just one step, with
the purpose of improving the efficiency of the search. This idea is embodied in the following
algorithm, which has complexity:
1 1
S + ( U + C). (6.14)
ε δ
Algorithm 9 Classical search by multi-step random walk[96, 250]

1: [Setup] Sample from Ω to get a sample u.
2: Do the following h(π T , M) = O(1/ε) times (it is the average hitting time starting from the
stationary distribution on Ω ):
2.1) [Checking] If u is marked, then return u and stop.
2.2) [Update] Start from u, simulate random walk P on Ω for Tmix = O(1/δ) time steps (to
reach the stationary distribution π T ).
3: Return “no marked item”.
The quantum analogues of Algorithm 8 include Szegedy’s quantum walk algorithm[95] , Falk’s
spatial search algorithm[264] , etc. The quantum analogues of Algorithm 9 include MNRS quan-
tum walk algorithm[96] , nested quantum walks, etc.
Below we introduce MNRS quantum walk algorithm, one of the most often used quantum
walk frameworks. In [96], the following theorem was proved: Let P = (puv ) be an ergodic
and reversible Markov chain on Ω with spectral gap δ, and let ε > 0 be a lower bound of
the probability that an element chosen from the stationary distribution π of P is marked.
If C is the cost to check if a state u ∈ Ω is marked using data information |d(u), S is the

cost to construct the superposition u∈Ω π(u)|u, d(u), and U is the cost to construct the
√
superposition v∈Ω puv |v, d(v) for any u ∈ Ω , then a marked state can be found with high
probability in the cost of
1 1
S+ √ √ U+C . (6.15)
ε δ
The algorithm gains quadratic speedup over Algorithm 9 in parameters 1/ε and 1/δ.
We investigate MNRS quantum walk algorithm with some detail, with the purpose to show
that in (6.15), the quadratic speedups in 1/ε and 1/δ come from Grover search and quantum
phase estimation respectively.
Consider the simple case when |M| = 1, |Ω | = N , and there is no need to construct data
function d on Ω . Since P = P
, (5.38) becomes
√
|p
x = pxy |y = |px . (6.16)
y∈Ω
Similar to (6.5), define

1 √ 1 √
|πgood = πu |u|pu , |πbad = $ πu |u|pu . (6.17)
u∈M πu πu u
∈M
u∈M u
∈M
The MNRS quantum walk algorithm has the same structure with Grover’s algorithm:
Algorithm 10 Search by MNRS quantum walk framework[96]

1: [Setup] Prepare the initial state (5.40):
√
|π = πu |u|pu = πu |πgood + πu |πbad . (6.18)
u∈Ω u∈M u
∈M
√
2: Do the following O(1/ ε) times:
2.1) [Checking] Make reflection R|πbad with respect to |πbad .
2.2) [Update] Make reflection R|π with respect to |π.
Reflection R|πbad has the effect that for any basis state in (6.18), if the first register is
marked, then a minus sign is added to the coefficient. This can be done by an oracle similar to Of
in Grover’s algorithm. Realizing reflection R|π is based on quantum eigenphase decomposition
of unitary operator W (P ) (quantization of random walk P ), which needs some elaboration.
Since (Ω , P ) is reversible, matrix P has only real eigenvalues, all of which are in interval
[−1, 1]. Let the multiset of singular values of D(P ) in the interval (0, 1) be {cos(θj ), j =
1, · · · , m}, where θj ∈ (0, π/2).
For the two N -spaces A, B defined by (5.37), (5.39) respectively, let the dimension of A + B
be n. By Theorem 5.1 and Corollary 5.2, when W (P ) = RB RA is restricted to the subspace
A + B of CN ⊗ CN , its eigenvalues are
1; {e2iθj , j = 1, · · · , m}; {e−2iθj , j = 1, · · · , m}; −1, · · · , −1. (6.19)

Furthermore, |π is the eigenvector corresponding to eigenvalue 1.

As the spectral gap of P is δ, for any 1 ≤ j ≤ m, δ ≤ 1−cos θj . By this and cos θj > 1−θj2 /2
for θj ∈ (0, π/2), one gets
√
θj ≥ 2δ, ∀1 ≤ j ≤ m. (6.20)
Let {wk , k = 0, · · · , n − 1} be unit eigenvectors of W (P ) corresponding to the eigenvalues

in the order of (6.19). Then |w0 = |π. Set θ0 := 0, and θm+j := −θj for 1 ≤ j ≤ m. The
eigenvalue corresponding to wk for k > 2m is −1. Set θk := π/2 for 2m < k < n. In this
way, for all 0 ≤ k < n, the eigenvalue of W (P ) corresponding to eigenvector wk is e2iθk , where
−π/2 < θk ≤ π/2.
The eigenphase decomposition of W (P ) gives: For all 0 ≤ k < n,
√ √

|wk |0 → |wk |θk → (−1) |θk |≤ δ/2 |wk |θk → (−1) |θk |≤ δ/2 |wk |0, (6.21)
√
where θk is a δ/2-approximate of θk , and L → [L] is a real-valued function in logic variable L
such that [L] = 0 if L is true, and [L] = 1 if L is false.
(6.21) is an implementation of the reflection R|π in space A + B, because state |π is
invariant, while any state in the orthogonal complement of |π is reversed, due to

√ 1 √ 1√
|θk | ≥ 2− δ> δ, ∀k = 0. (6.22)
2 2
√
By Proposition 3.1, the complexity of (6.21) is O(U/ δ), where U is the cost to implement
W (P ) by preparing RA , RB respectively. In the phase estimation procedure (3.2), quantum
√
walk W (P ) is executed O(1/ δ) times, which is determined by the phase estimation precision.
MNRS quantum walk algorithm is also valid when |M| > 0, but it is valid only when |M|
is known in advance. This assumption can be removed by some standard techniques, without
increasing the asymptotic complexity of the algorithm[260] .
Nested quantum walk.
In the checking subroutine or update subroutine of a quantum walk algorithm, another

graph can be constructed on which a new quantum walk can be made. This is the nested
quantum walk framework.
For example, let there be a nested MNRS quantum walk, where the inner MNRS quantum
walk is in the checking subroutine, and has complexity

1 1
C=S +√ √ U +C , (6.23)
ε δ
where (S , U , C , ε , δ ) are the costs and parameters associated with the inner walk. Then the
nested MNRS quantum walk has complexity:

1 1 1 1
S + √ √ U + S + √ √ U + C . (6.24)
ε δ ε δ
Jeffery, et al.[61] proposed a method to avoid repeated overhead of the setup cost, and decreased
the complexity (6.24) to

1 1 1 1
S+S + √ √ U+ √ √ U +C . (6.25)
ε δ ε δ
6.4 Application: Element Distinctness Problem

Given a set of integers {x1 , · · · , xn }, the element distinctness problem is to detect if there
exist two different indices i, j such that xi = xj , and if so, find such a pair. The best classical
algorithm requires O(n) queries, for example by sorting.
The first quantum algorithm, proposed by Buhrman, et al.[265] in 2005, achieves query com-
plexity O(n3/4 ) by using Grover’s search in a clever two-level construction. In 2007, Ambainis[78]
discovered a quantum algorithm with query complexity O(n2/3 ) and time complexity O(n 2/3 ).
This algorithm is optimal in that each complexity reaches the lower bound[54] .
Ambainis’ algorithm is based on a symmetric walk in the Johnson graph J(n, r). A vertex
A is a subset of Ω = {1, 2, · · · , n} with cardinality r. It is marked if there exist two different
elements i, j of subset A such that xi = xj . The probability for an arbitrary vertex A to be
marked is n−2
r(r − 1) r2
ε ≥ Prob(i, j ∈ A) = r−2 n = ≈ 2. (6.26)
r
n(n − 1) n
The data associated with vertex A is d(A) := {(u, xu ) : u ∈ A}.
Let A, A be two neighboring vertices of J(n, r). By definition, the two vertices when taken
as subsets of cardinality r, have exactly r − 1 elements in common, so the random walk on
1
J(n, r) has transition matrix P = (pA,A ), where pA,A = r(n−r) if A, A are neighbors. The
spectral gap is δ ≥ 1/r (see [250]).
In the MNRS quantum walk framework, the setup cost S is used to construct
1
$ |A|d(A), (6.27)
n
r A∈J(n,r)
so S = r queries. In the update subroutine, constructing d(A ) from d(A) is done by querying the
unique index in A \ A and “unquerying” the unique index in A \ A . Since all other information
of d(A ) are already in d(A), U = 2. In the checking subroutine, no additional query is needed,
√
so C = 0. The query complexity is thus O(r + n/ r), which achieves the minimum O(n2/3 )
at r = n2/3 . Furthermore, an appropriate data structure for d can be used to make the time
complexity equal to O(n 2/3 ).
A generalization of element distinctness problem is element k-distinctness: To decide if there
exist k different indices i1 , · · · , ik of {1, 2, · · · , n} such that xi1 = · · · = xik , and if so, find such
a k-tuple. The lower bound of the query complexity is Ω (n2/3 ).
Ambainis’ algorithm can be extended to solve the element k-distinctness problem, with
query complexity O(nk/(k+1) ), and time complexity O(n k/(k+1) ). In 2012, Belovs decreased the
k
query complexity to O(n0.75−1/(4(2 −1)) ) by using learning graphs[266] . This remains the best
query complexity result.
0.714 )
For the case k = 3, in 2013 Childs, et al.[97] proposed a quantum algorithm using O(n
queries. For k > 3, in 2014 Jeffery[267] proposed a quantum algorithm that achieves currently
(k−1)/k ).
the best time complexity: O(n
6.5 Other Frameworks of Quantum Walk Based Search

Szegedy’s quantum walk framework is another important algorithm for the detection prob-
lem, and for the finding problem when |M| = 1.
In the following algorithm for the detection problem, the absorbing quantum walk W (PM )
serves as a process of both update and checking, so its cost is U + C. It is applied repeatedly
to the initial state |π. If M is empty, then PM = P and the initial state is left invariant. If
M is nonempty, then the angle between vectors (W (PM ))t |π and (W (P ))t |π = |π gradually
increases for t not too large[95] .
Algorithm 11 Szegedy’s quantum walk algorithm to detect if |M| = 0[95]

1: [Setup] Prepare the initial state |π as (5.40).
√
2: Apply hQ = O( h) times the following walk:
[Simultaneous Checking and Update] W (PM ).
3: Construct the following state (up to normalization), the first register being the control one:
1 1
|0 |π + (W (PM ))t |π + |1 |π − (W (PM ))t |π . (6.28)
2 2
4: Measure the final state (at the control register).
When (Ω , P ) is ergodic and symmetric, then in the above algorithm, the quantum hitting
√
time hQ ≤ h, where h is the classical “hitting time” (the time steps to determine if M =
∅ by random walk (Ω , P ) in classical search algorithms). So Algorithm 11 has complexity
√
S + h(U + C).
If P is state-transitive and |M| = 1, then after deleting Step 3 of Algorithm 11, the modified
algorithm can be used to find the unique marked state with probability at least N/h with cost
√
S + h(U + C). The success probability can be increased to Θ (1) with h/N iterations of the
algorithm using quantum amplitude amplification.
In the framework of quantum walk, the finding problem for |M| > 1 is generally more
complicated than for |M| = 1. For the finding problem with information given that there are
multiple marked elements, in 2016, Krovi, et al.[268] introduced a novel idea called interpolating
quantum walk; in 2017, Dohotaru and Høyer[269] developed a new technique called controlled
quantum walk. None of them guarantees quadratic speedup over classical algorithms.
To deal with multiple marked elements, the concept of extended hitting time h+ for classical
random walk is important. In 2015, Ambainis and Kokainis[270] established the relation h ≤
h+ ≤ h/δ. In 2016, Krovi, et al.[268] proved h = h+ if |M| = 1, and h ≤ h+ if |M| > 1. In 2017,
Høyer and Komeili[253] established currently the best bound for h+ : 1/ε ≤ h ≤ h+ ≤ 1/(εδ).
Table 2 collects some typical frameworks of quantum walk based search.
Table 2 Frameworks for quantum walk based search and their costs
Algorithm Cost for case |M| = 1 Cost for case |M| > 1
$ √
[95] h
Szegedy (2004) N
(S + h(U + C)) —
MNRS[96] (2011) S+ √1 ( √1 U
ε δ
+ C) S+ 1 √
√
ε
( 1δ U + C)
√
Magniez, et al.[67] (2012) S+ h(U + C) —
[268]
√ √
Krovi, et al. (2016) S+ h(U + C) S+ h+ (U + C)
√ √
Dohotaru and Høyer[269] (2017) S+ hU + √1 C
ε
S + h+ (U + C)
6.6 Application: Spatial Search

For a physical region in which the moving of a quantum robot from one location to an
adjacent one takes unit time, the time needed to search the region could depend critically
on its spatial layout. For example, if the items are arranged on a one-dimensional line, simply
traveling from one end of the line to the other requires n moves, and no local algorithm, classical
or quantum, can find a marked item in less time than Ω (n).
√ √
Consider a 2-dimensional grid of size n × n, which has exactly one marked node. Direct
√ √
application of Grover search gives step complexity O( n × n) = O(n), because during each
√ √
of the O( n) Grover iterations, the algorithm needs O( n) steps to travel across the grid and
return to its starting point for the diffusion step.
In 2003, by using Grover’s algorithm recursively, Aaronson and Ambainis[68] gave an algo-
√
rithm with time complexity O( n log3/2 n). In 2004, Ambainis, et al.[65] presented an algorithm,
√
based on discrete-time quantum walk, that finishes the search in O( n log n) steps. In 2008,
√
Tulsi[66] improved the result to O( n log n) by modifying the quantum walk. In 2013, Falk[264]
√
used two kinds of quantum walks (diffusions) successively to reduce the complexity to O( n),
which is also the complexity lower bound. Below we introduce Falk’s algorithm.
Falk’s algorithm contains two key constructions and the corresponding diffusion operations.
The first is a tessellation of the grid into 4 × 4 blocks, and the associated diffusion within each
block. This diffusion takes local pieces of the grid and trades their amplitudes, so that if a
particular piece of the grid contains the marked item, it will act like Grover search and start
sending amplitudes to the marked node.
The second is another tessellation of the grid into 4 × 4 blocks, such that if two blocks of
different tessellations overlap, the overlap is a quadrant of each block. The associated diffusion
within a block B of the second tessellation disperses the amplitudes among the four blocks in
the first tessellation that overlap with B.
√
For simplicity, assume N = n/4 is an integer. The basis states are
Ω = {|i, j, 0 ≤ i, j < 4N }. (6.29)
The first tessellation is composed of the following states:
1
3
|uL (i, j) := |4i + x, 4j + y, ∀i, j = 0, 1, · · · , N − 1. (6.30)
4 x,y=0
Denote
L := span{|uL(i, j), i, j = 0, 1, · · · , N − 1}. (6.31)
The local diffusion operator associated with the tessellation is the reflection RL with respect
to L.
The second tessellation is composed of the following states:
1
3
|uA (i, j) := |4i + x + 2, 4j + y + 2. (6.32)
4 x,y=0
Denote
A := span{|uA (i, j), i, j = 0, · · · , N − 1}. (6.33)
The amplitude dispersion operator associated with the tessellation is the reflection RA with
respect to A.
Let |i0 , j0 be the marked state. As in Grover search, an oracle (a mark-checking function)
can be used to construct the reflection R|i0 ,j0 ⊥ with respect to the “bad” states. Falk’s al-
gorithm has similar structure with Grover’s algorithm, with the exception that there are two
walks/diffusions instead of one.
√ √
Algorithm 12 Search in a n × n grid for the unique marked node[264]
1: [Setup] Prepare the initial state
4N −1
1
|√n×√n = √ |i, j, (6.34)
n i,j=0
by walking along a horizontal and then a vertical.

√
2: Apply the following operator O( n) times:
[Update 1, Checking, Update 2, Checking] R|i0 ,j0 ⊥ RA R|i0 ,j0 ⊥ RL .

√
In the above algorithm, the setup cost S = O( n), the update and checking costs U + C =
O(1). The total complexity is
√ √
S + n(U + C) = O( n). (6.35)
Experiments[264] show that the actual probability of finding the marked node by the algorithm
is approximately 1/2.
Inspired by Falk’s work, in 2015 Portugal, et al.[271] presented a new framework of quantum
walk — Staggered quantum walk model, and proved its equivalence with Szegedy’s framework.
In 2017, Høyer and Komeili[253] proposed a quantum walk based algorithm for finding multiple
marked elements on the grid, which achieves quadratic speedup after ignoring logarithmic factor.
7 Some Open Problems and Emerging Directions

This section contains some famous open problems and new research directions in quantum
algorithm design.
7.1 Lattice Problems

Lattice problems have important applications in coding theory and cryptographic systems
due to their conjectured hardness. Since the invention of Shor’s algorithm, a number of post-
quantum public-key cryptosystems have been proposed, many of which are based on lattice
problems. Lattice-based cryptosystems are important candidates for post-quantum cryptogra-
phy, and are believed to be resistant to attacks from quantum computer.

Let {b1 , · · · , bn } be a basis of Rn . The lattice generated by them is L = { ni=1 λi bi : λi ∈
Z}. The shortest vector problem (SVP) is to find a nonzero vector of L with minimal L2 -norm.
SVP is the most famous and well studied computational problem on lattices. Let f (n) be a
polynomial in n. The f (n)-unique-SVP is to find the shortest nonzero vector that is shorter by
a factor of at least f (n) than any other nonparallel vector. This problem also has important
applications in cryptography[30, 31] .
To solve SVP, in the classical computing domain, in 2014 Aggarwal, et al.[272] proposed
an algorithm that has time complexity 2n+o(n) and space complexity 2n+o(n) . In 2018, Chen,
et al.[273] proposed another algorithm, with time complexity 22.05n+o(n) and space complexity
20.5n+o(n) .
In the quantum computing domain, in 2013 Laarhoven, et al.[45] proposed a quantum al-
gorithm based on Grover search. This algorithm has time complexity 21.799n+o(n) and space
complexity 21.286n+o(n) . In 2018, Chen, et al.[273] proposed a quantum algorithm with time
complexity 21.2553n+o(n) and space complexity 20.5n+o(n) .
Under certain heuristic assumptions, currently the best algorithm in the classical computing
domain to solve SVP was proposed by Becker, et al.[274] in 2016. It has time complexity
20.2925n+o(n) and space complexity 20.208n+o(n) .
Under the same heuristic assumptions but in the quantum computing domain, in 2013,
Laarhoven, et al.[45] proposed a quantum algorithm with time complexity 20.268n+o(n) and space
complexity 20.268n+o(n) . In 2015, Laarhoven[275] in his Ph.D. dissertation further improved the
result by decreasing both the time complexity and the space complexity to 20.265n+o(n) .
7.2 HSP of Dihedral Groups (Dihedral HSP)

This problem is also one of the most important mathematical problems that seem to resist
efficient quantum computing. An efficient algorithm for the HSP of dihedral groups would lead
to an efficient algorithm for several cryptographically significant lattice problems[32] .
Dihedral group DN := {x, y | xN = y 2 = yxyx = 1} is the symmetry group of the regular
N -gon in the plane, where x stands for the rotation with angle 2π/N about the center of the
regular N -gon, and y stands for the reflection with respect to one diagonal. It is not hard to
see that DN ∼ = ZN Z2 , with multiplication (a, r) ∗ (b, s) := (a + (−1)r b, r + s).
In 2000, Ettinger and Høyer[276] showed that the dihedral HSP can be reduced to the search
of a subgroup of the form H = {(0, 0), (d, 1)}. So the dihedral HSP can be reformulated as
follows: Let f be a map from ZN Z2 to a finite set S, with the property that (1) f (x, 0) is
injective from ZN to S, (2) there exists some d ∈ ZN such that f (x, 0) = f (x + d, 1) for all
x ∈ ZN . Find d.
The dihedral HSP is closely related to the following subset sum problem: Given m + 1
m
integers z, y1 , · · · , ym ∈ ZN , decide if there exist s1 , · · · , sm ∈ {0, 1} such that i=1 yi si = z.
m
It is called the average-case subset sum problem if the equation is replaced by i=1 yi si = z
mod N .
In 2004, Regev[32] proved that if there exists an efficient quantum algorithm to solve the
average-case subset sum problem, then there exists an efficient quantum algorithm to solve the
dihedral HSP. In 2006, Bacon, et al.[277] further specified that if the subset sum problem can
be efficiently solved and its solutions be efficiently quantum sampled, then the pretty good
measurement for the dihedral HSP can be efficiently implemented by quantum circuits, which
when combined with the standard method for the dihedral HSP, would lead to an efficient
quantum algorithm for solving the dihedral HSP.
The following procedure is known as the standard method for the dihedral HSP.
Step 1 Prepare the initial state
1 1
|ψ1 = √ |x|t|f (x, t) = √ (|x|0 + |x + d|1)|f (x, 0). (7.1)
2N x∈ZN ,t∈Z2
2N x∈ZN
Step 2 Apply quantum Fourier transform to the first register. Result:

1
|ψ2 = √ ω xy |y(|0 + ω dy |1)|f (x, 0), where ω = e2πi/N . (7.2)
2N x,y∈ZN
Step 3 Work on |ψ2 to get d (open problem).

In 2004, Regev[32] showed that if there exists an efficient quantum algorithm based on the
standard method for the dihedral HSP, then there exists an efficient quantum algorithm with
the same complexity that solves f (n)-unique-SVP. Also in this year, Kuperberg[18] proposed a
quantum algorithm to solve the dihedral HSP starting from the state (7.2), with time complexity
√
and space complexity both 2O( log N) . Later in the same year, Regev[278] improved the result
by reducing the space complexity to O(poly log N ). This is still the best result for the problem.
7.3 Graph Isomorphism Problem

Suppose Γ1 and Γ2 are two undirected graphs on the same vertices V = {1, 2, · · · , n}. The
graph isomorphism problem concerns whether there exists a one-to-one map σ : V → V such
that (i, j) is an edge of Γ1 if and only if (σ(i), σ(j)) is an edge of Γ2 . If Γ1 = Γ2 , such a σ is
called an automorphism. The graph automorphism problem is to determine whether a graph
has a non-trivial automorphism. The two problems have the same computational difficulty.
In the classical computing domain, currently the best algorithms for solving the graph
√ 1/3 2
isomorphism problem run in time eO( n log n) for general graphs[279] and eO(n (log n) ) for
strongly regular graphs[280] . In the quantum computing domain, the results are few and far
between.
The graph isomorphism problem is related to the HSP of symmetric groups. Let Γ be a
graph on n vertices, and define f (σ) = σ(Γ ) for all σ ∈ Sn . Then f is constant on every coset
of the automorphism group of Γ . Since the automorphism group of Γ is a subgroup of Sn ,
the construction of f reduces the graph automorphism problem to an HSP of Sn [281–284] . An

efficient algorithm for the HSP of the symmetric group would lead to an efficient algorithm for
graph isomorphism problem.
For symmetric groups, the standard method for HSP is insufficient[285, 286] , although circuit
implementations of quantum Fourier transform on symmetric groups are available[283, 287, 288] .
7.4 Triangle Finding

Let G = (V, E) be a graph. A triangle of G is composed of three vertices that are neighbors
to each other. Triangle finding is to detect if there is any triangle in a graph, and if so, find
one. Let A be the adjacency matrix of G. A triangle exists if and only if matrix A3 contains a
nonzero diagonal entry.
Triangle finding plays a key role in many problems. It is proved that faster algorithms for
triangle finding would lead to faster algorithms for matrix multiplication[81, 289] , the 3-SUM
problem[290] , the Max-2SAT problem[291] , etc.

Let n be the number of vertices of G. While classical algorithms have query cost n3 =
O(n3 ), Grover search reduces the query cost to O(n3/2 ). The first quantum algorithm outper-
forming Grover search for this problem was given by Magniez, et al.[60] in 2007, by considering
a quantum walk on Johnson graph J(n, r), and combining amplitude amplification with com-
binatorial arguments. This algorithm has query complexity O(n 13/10 ).
In 2012, Belovs[292] used learning graph to decrease the query complexity to O(n35/27 ) ≈
O(n1.296 ). In 2013, Lee, et al.[76] further decreased the query complexity to O(n9/7 ) ≈ O(n1.285 ),
again using learning graph. Both complexities can be achieved by nested quantum walks on
two Johnson graphs. In 2014, Le Gall[75] proposed an algorithm with currently the best query
complexity O(n1.25 ), using a 4-level nested MNRS quantum walk.
A known lower bound of the quantum query complexity of this problem is Ω (n). It is not
clear if the lower bound can be reached.
7.5 Quantum Optimization

Quantum optimization is an emerging research direction but still at its infancy. Two prob-
lems are concerned: Quantum semi-definite programming, and quantum convex optimization.
Quantum semi-definite programming.
Semi-definite program (SDP) is an important tool for designing efficient optimization and
approximation algorithms[293] . SDP generalizes the better-known linear program (LP), and
(like LP) is efficiently solvable.
The basic form of an SDP is the following: Given n × n Hermitian matrices C, A1 , · · · , Am ,
and real numbers b1 , · · · , bm , solve for
MaximizeX=Xn×n 0 Tr(CX), subject to Tr(Aj X) ≤ bj , j = 1, 2, · · · , m. (7.3)
An LP corresponds to the case where all matrices are diagonal.

In the classical computing domain, currently the best SDP-solvers such as the one in [294],
approximate the optimal value up to additive error ε with complexity:

O m(m2 + nω + mns)poly log(m, n, R, r, 1/ε) , (7.4)
where ω ∈ [2, 2.373) is the optimal exponent for matrix multiplication; s is the maximal sparsity
of the input matrices; R, r are respectively the upper bounds of the norm of the optimal primal
and dual solutions of the SDP.
In the quantum computing domain, in 2017 Brandão and Svore[295] discovered a quantum
algorithm that significantly outperforms classical SDP-solvers in certain problems. The com-

√mns2 (Rr/ε)32 , with speedup in parameters m, n, but speed-down in parameters
plexity is O
R, r, 1/ε.
Later in the same year, Apeldoorn, et al.[296] provided a quantum algorithm with complexity
√

O mns2 (Rr/ε)8 . In 2018, Apeldoorn and Gilyén[297] , Brandão, et al.[298] separately improved
the result to
√ √
( m + n(Rr/ε))s(Rr/ε)4 .
O (7.5)
The result is tight in the dependence on m, n, because there is a quantum lower bound[298]
√ √
Ω ( m + n) when R, r, s, ε are constant.
In August 2018, for the case m = O(n2 ), Kerenidis and Prakash[242] used quantum interior
point method to solve the SDP in time

n3.5 κ3 ξ −2 log(1/ε) ,
O (7.6)
where ξ, κ are respectively the error and maximal condition number of the Hessian matrices
used in the method.
Quantum convex optimization.
The following is a general convex minimization problem: Given a convex domain K ⊆ Rn

bounded by two balls B(0, r) and B(0, R), and given a bounded convex function f : K → R
whose upper bound and lower bound are both known, solve for
argminx∈K f (x). (7.7)
In the classical computing domain, the lower bounds of the query complexity are: Ω (n)
to the evaluation oracle for f , and Ω (n) to the membership oracle for K. Currently the best
algorithms such as the one in [299], solve the problem with O(n 2 ) queries of the evaluation

oracle for f , and O(n ) queries of the membership oracle for K.
2
In the quantum computing domain, in September 2018, Chakraborty, et al.[300] showed that
there is a quantum algorithm to solve the problem by O(n) queries of the evaluation oracle

for f , and O(n) queries of the membership oracle for K. They proved that the lower bounds
√ √
of the query complexity are: Ω ( n/ log n) to the evaluation oracle for f , and Ω ( n) to the
membership oracle for K. Similar results are obtained by Apeldoorn, et al.[301] in the same
month of the year.
7.6 Quantum Algorithms with Limitation on Quantum Computing Resources

The current status of quantum computer hardware is that there are only a few qubits
available for running a quantum algorithm. Designing quantum algorithms that outperform
classical algorithms with the fewest resources is an important task.
Take as an example the resources used by Grover’s algorithm in attacking cryptosystems.
In 2016, Grass, et al.[302] estimated the number of qubits nB , the number of elementary gates
nG , and the depth of circuits dC , to run Grover’s algorithm to attack AES. The resources for
attacking AES-128, AES-192, AES-256 are respectively:
(nB , nG , dC ) = (2953, 286 , 281 ); (4449, 2119 , 2113 ); (6681, 2151 , 2145 ). (7.8)
Due to the large circuit depth, it is challenging to implement this algorithm on an actual
physical quantum computer to break AES.
In the same year, Amy, et al.[303] also estimated the resources to run Grover’s algorithm to
attack SHA-2 and SHA-3. They assumed that the pre-image attack is run on a surface code
based fault-tolerant quantum computer. The resources for attacking SHA2-256 and SHA3-256
are respectively:
(dC , nB ) = (2153.8 , 6208); (2146 , 1048576). (7.9)
Executing these attacks is more expensive than one would expect from the simple query analysis,
which is 2128 queries in a quantum black-box model.
Recent researches on quantum algorithms with limited quantum computing resources, focus
on Hamiltonian simulation[213] , 3-SAT problem solving[304] , supervised classification[305] , etc.
References
[1] Benioff P, The computer as a physical system, Journal of Statistical Physics, 1980, 22: 563–591.
[2] Feynman R, Simulating physics with computers, International Journal of Theoretical Physics,
1982, 21: 467–488.
[3] Deutsch D, Quantum theory, the Church-Turing principle and the universal quantum computer,
Proc. R. Soc. A, 1985, 400: 97–117.
[4] Deutsch D, Quantum computational networks, Proc. R. Soc. A, 1989, 425: 73–90.
[5] Yao A C-C, Quantum circuit complexity, Proc. FOCS 1993, IEEE, Palo Alto, 1993, 352–361.
[6] Bernstein E and Vazirani U V, Quantum complexity theory, SIAM J. Comput., 1997, 26(5):
1411–1473.
[7] Deutsch D and Jozsa R, Rapid solution of problems by quantum computation, Proc. R. Soc. A,
1992, 439: 553–558.
[8] Simon D R, On the power of quantum computation, SIAM J. Comput., 1997, 26(5): 1474–1483.
[9] Shor P W, Polynomial-time algorithms for prime factorization and discrete logarithms on a
quantum computer, SIAM J. Comput., 1997, 26(5): 1484–1509.
[10] Kitaev A Y, Quantum measurements and the abelian stabilizer problem, arXiv: quant-ph
/9511026.
[11] Ettinger M, Høyer P, and Knill E, The quantum query complexity of the hidden subgroup problem
is polynomial, Information Processing Letters, 2004, 91(1): 43–48.
[12] Nielsen M A and Chuang I L, Quantum Computation and Quantum Information, Cambridge
University Press, Cambridge, 2000.
[13] Hallgren S, Polynomial-time quantum algorithms for Pell’s equation and the principal ideal prob-
lem, Proc. STOC 2002, ACM Press, New York, 2002, 653–658.
[14] Proos J and Zalka C, Shor’s discrete logarithm quantum algorithm for elliptic curves, Quantum
Information and Computation, 2003, 3: 317–344.
[15] Bacon D, Childs A M, and van Dam W, From optimal measurement to efficient quantum al-
gorithms for the hidden subgroup problem over semidirect product groups, Proc. FOCS 2005,
IEEE, Washington, 2005, 469–478.
[16] Chi D P, Kim J S, and Lee S, Notes on the hidden subgroup problem on some semi-direct product
groups, Phys. Lett. A, 2006, 359(2): 114–116.
[17] Inui Y and Le Gall G, Efficient quantum algorithms for the hidden subgroup problem over a class
of semi-direct product groups, Quantum Information and Computation, 2007, 7(5 & 6): 559–570.
[18] Kuperberg G, A subexponential-time quantum algorithm for the dihedral hidden subgroup prob-
lem, SIAM J. Comput., 2005, 35(1): 170–188.
[19] Moore C, Rockmore D, Russell A, et al., The power of basis selection in Fourier sampling: The
hidden subgroup problem in affine groups, Proc. SODA 2004, SIAM, Philadelphia, 2004, 1113–
1122.
[20] Gavinsky D, Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian-
groups, Quantum Information and Computation, 2004, 4: 229–235.
[21] Hallgren S, Russell A, and Ta-Shma A, Normal subgroup reconstruction and quantum computa-
tion using group representations, SIAM J. Comput., 2003, 32(4): 916–934.
[22] Ivanyos G, Magniez F, and Santha M, Efficient quantum algorithms for some instances of the
non-abelian hidden subgroup problem, SPAA 2001, ACM Press, New York, 2001, 263–270.
[23] Grigni M, Schulman L, Vazirani M, et al., Quantum mechanical algorithms for the nonabelian
hidden subgroup problem, Combinatorica, 2004, 24: 137–154.
[24] van Dam W, Hallgren S, and Ip L, Quantum algorithms for some hidden shift problems, SIAM
J. Comput., 2006, 36(3): 763–778.
[25] Boneh D and Lipton R J, Algorithms for black-box fields and their application to cryptography,
Advances in Cryptology — CRYPTO’96, Ed. by Koblitz N, LNCS 1109, 1996, 283–297.
[26] Kuwakado H and Morii M, Quantum distinguisher between the 3-round Feistel cipher and the
random permutation, Proc. ISIT 2010, IEEE, Austin, TX, 2010, 2682–2685.
[27] Kuwakado H and Morii M, Security on the quantum-type Even-Mansour cipher, Proc. ISITA
2012, IEEE, Honolulu, HI, 2012, 312–316.
[28] Santoli T and Schaffner C, Using Simon’s algorithm to attack symmetric-key cryptographic prim-
itives, arXiv: 1603.07856 [quant-ph].
[29] Kaplan M, Leurent G, and Leverrier A, Breaking symmetric cryptosystems using quantum period
finding, arXiv: 1602.05973v3 [quant-ph].
[30] Ajtai M and Dwork C, A public-key cryptosystem with worst-case/average-case equivalence,
Proc. STOC 1997, ACM Press, New York, 1997, 284–293.
[31] Regev O, New lattice-based cryptographic constructions, Journal of the ACM, 2004, 51(6): 899–
942.
[32] Regev O, Quantum computation and lattice problems, SIAM J. Comput., 2004, 33(3): 738–760.
[33] Galbraith S and Stolbunov A, Improved algorithm for the isogeny problem for ordinary elliptic
curves, Applicable Algebra in Engineering, Communication and Computing, 2013, 24(2): 107–
131.
[34] Couveignes J M, Hard Homogeneous Spaces, https://eprint.iacr.org/2006/291.pdf.
[35] Rostovtsev A and Stolbunov A, Public-key cryptosystem based on isogenies, https://eprint.
iacr.org/2006/145.pdf.
[36] Stolbunov A, Constructing public-key cryptographic schemes based on class group action on a
set of isogenous elliptic curves, Adv. Math. Commun., 2010, 4(2): 215–235.
[37] Childs A M, Jao D, and Soukharev V, Constructing elliptic curve isogenies in quantum subex-
ponential time, J. Mathematical Cryptology, 2014, 8: 1–29.
[38] Grover L K, A fast quantum mechanical algorithm for database search, Proc. STOC 1996, ACM
Press, New York, 1996, 212–219.
[39] Bennett C H, Bernstein E, Brassard G, et al., Strengths and weaknesses of quantum computing,
SIAM J. Comput., 1997, 26(5): 1510–1523.
[40] Zalka C, Grover’s quantum searching algorithm is optimal, Phy. Rev. A, 1999, 60: 2746–2751.
[41] Long G L, Grover algorithm with zero theoretical rate, Phys. Lett. A, 2001, 64: 022307.
[42] Ambainis A, Quantum search algorithms, SIGACT News, 2004, 35(2): 22–35.
[43] Campbell E, Khurana A, and Montanaro A, Applying quantum algorithms to constraint satis-
faction problems, arXiv: 1810.05582 [quant-ph].
[44] Liu W Z, Zhang J F, and Long G L, A parallel quantum algorithm for the satisfiability problem,
Common. Theor. Phys., 2008, 49(3): 629–630.
[45] Laarhoven T, Mosca M, and van de Pol J, Solving the shortest vector problem in lattices faster us-
ing quantum search, PQCrypto 2013, Ed. by Gaborit P, LNCS 7932, Springer, Berlin, Heidelberg,
2013, 83–101, also available: arXiv: 1301.6176v1 [cs.CR].
[46] Faugère J C, Horan K, Kahrobaei D, et al., Fast quantum algorithm for solving multivariate
quadratic equations, arXiv: 1712.07211 [cs.CR].
[47] He X Y, Sun X M, Yang G, et al., Exact quantum query complexity of weight decision problems,
arXiv: 1801.05717v1 [quant-ph].
[48] Le Gall F and Nishimura H, Quantum algorithms for matrix products over semirings, Chicago
Journal of Theoretical Computer Science, 2017, 1: 1–25.
[49] Dürr C and Høyer P, A quantum algorithm for finding the minimum, arXiv: quant-ph/9607014.
[50] Kowada L A B, Lavor C, Portugal R, et al., A new quantum algorithm for solving the minimum
searching problem, International Journal of Quantum Information, 2008, 6(3): 427–436.
[51] Brassard G, Høyer P, and Tapp A, Quantum Counting, Automata, Languages and Programming,
Eds. by Larsen K G, et al., LNCS 1443, Springer, Berlin, Heidelberg, 1998, 820–831.
[52] Brassard G, Høyer P, and Mosca M, Quantum amplitude amplification and estimation, Quantum
Computation and Quantum Information, 2002, 305: 53–74.
[53] Brassard G, Høyer P, and Tapp A, Quantum cryptanalysis of hash and claw-free functions,
LATIN’98: Theoretical Informatics, Eds. by Lucchesi C L and Moura A V, LNCS 1380, Springer,
Berlin, Heidelberg, 1998, 163–169.
[54] Aaronson S and Shi Y, Quantum lower bounds for the collision and the element distinctness
problems, Journal of the ACM, 2004, 51(4): 595–605.
[55] Wang X, Yao A, and Yao F, Cryptanalysis on SHA-1, http://csrc.nist.gov/groups/ST/hash/
documents/Wang SHA1-New-Result.pdf.
[56] Cochran M, Notes on the Wang, et al. 263 SHA-1 Differential Path, https://eprint.iacr.
org/2007/474.pdf.
[57] Hoffstein J, Pipher J, and Silverman J H, NTRU: A ring-based public key cryptosystem, Al-
gorithmic Number Theory, Ed. by Buhler J P, LNCS 1423, Springer, Berlin, Heidelberg, 1998,
267–288.
[58] Fluhrer S, Quantum cryptanalysis of NTRU, Cryptology ePrint Archive: Report 2015/676, 2015.
[59] Childs A M, Universal computation by quantum walk, Phys. Rev. Lett., 2009, 102: 180501.
[60] Magniez F, Santha M, and Szegedy M, Quantum algorithms for the triangle problem, SIAM J.
Comput., 2007, 37(2): 413–424.
[61] Jeffery S, Kothari R, and Magniez F, Nested quantum walks with quantum data structures, Proc.
SODA 2013, SIAM, Philadelphia, 2013, 1474–1485.
[62] Belovs A and Reichardt B W, Span programs and quantum algorithms for st-connectivity and
claw detection, European Symp. on Algorithms, Eds. by Epstein L, et al., LNCS 7501, Springer,
Berlin, Heidelberg, 2012, 193–204.
[63] Buhrman H, Cleve R, de Wolf R, et al., Bounds for small-error and zero-error quantum algorithms,
Proc. FOCS 1999, IEEE, New York, 1999, 358–368.
[64] Dürr C, Heiligman M, and Høyer P, Quantum query complexity of some graph problems, SIAM
J. Comput., 2006, 35(6): 1310–1328.
[65] Ambainis A, Kempe J, and Rivosh A., Coins make quantum walks faster, Proc. SODA 2005,
SIAM, Philadelphia, 2005, 1099–1108.
[66] Tulsi A, Faster quantum-walk algorithm for the two-dimensional spatial search, Phys. Rev. A,
2008, 78: 012310.
[67] Magniez F, Nayak A, Richter P C, et al., On the hitting times of quantum versus random walks,
Algorithmica, 2012, 63(1): 91–116.
[68] Aaronson S and Ambainis A, Quantum search of spatial regions, Theory of Computing, 2005, 1:
47–79.
[69] Childs A M, Cleve R, Jordan S P, et al., Discrete-query quantum algorithm for NAND trees,
Theory of Computing, 2009, 5: 119–123.
[70] Ambainis A, Childs A M, Reichardt B W, et al., Any AND-OR formula of size N can be evaluated
in time n1/2+o(1) on a quantum computer, SIAM J. Comput., 2010, 39(6): 2513–2530.
[71] Reichardt B W, Faster quantum algorithm for evaluating game trees, Proc. SODA 2011, SIAM,
Philadelphia, 2011, 546–559.
[72] Reichardt B W, Reflections for quantum query algorithms, Proc. SODA 2011, SIAM, Philadel-
phia, 2011, 560–569.
[73] Reichardt B W and Spalek R, Span-program-based quantum algorithm for evaluating formulas,
[74] Childs A M and Kothari R, Quantum query complexity of minor-closed graph properties, SIAM
Journal on Computing, 2012, 41(6): 1426–1450.
[75] Le Gall F, Improved quantum algorithm for triangle finding via combinatorial arguments, Proc.
FOCS 2014, IEEE, Philadelphia, 2014, 216–225.
[76] Lee T, Magniez F, and Santha M, Improved quantum query algorithms for triangle finding and
associativity testing, Algorithmica, 2017, 77: 459–486.
[77] Bernstein D J, Jeffery S, Lange T, et al., Quantum algorithms for the subset-sum problem,
Post-Quantum Cryptography, Ed. by Gaborit P, LNCS 7932, Springer, Berlin, Heidelberg, 2013,
16–33.
[78] Ambainis A, Quantum walk algorithm for element distinctness, SIAM J. Comput., 2007, 37:
210–239.
[79] Magniez F and Nayak A, Quantum complexity of testing group commutativity, Algorithmica,
2007, 48(3): 221–232.
[80] Buhrman H and Spalek R, Quantum verification of matrix products, Proc. SODA 2006, SIAM,
Philadelphia, 2006, 880–889.
[81] Le Gall F, Improved output-sensitive quantum algorithms for Boolean matrix multiplication,
Proc. SODA 2012, SIAM, Philadelphia, 2012, 1464–1476.
[82] Dorn S and Thierauf T, The quantum query complexity of algebraic properties, Fundamentals of
Computation Theory, Eds. by Csuhaj-Varjú E, et al, LNCS 4639, Springer, Berlin, Heidelberg,
2007, 250–260.
[83] Feynman R, Quantum mechanical computer, Optics News, 1985, 11: 11–20.
[84] Chase B A and Landhal A J, Universal quantum walks and adiabatic algorithms by 1d Hamilto-
nians, arXiv: 0802.1207 [quant-ph].
[85] Farhi E and Gutmann S, Quantum computation and decision trees, Phys. Rev. A, 1998, 58:
915–928.
[86] Meyer D, From quantum cellular automata to quantum lattice gases, J. Stat. Phys., 1996, 85:
551–574.
[87] Nayak A and Vishvanath A, Quantum walk on the line, arXiv: quant-ph/0010117.
[88] Strauch F W, Connecting the discrete and continuous-time quantum walks, Phys. Rev. A, 2006,
74: 030301.
[89] Childs A M, On the relationship between continuous- and discrete-time quantum walk, Commu-
nications in Mathematical Physics, 2010, 294(2): 581–603.
[90] Ambainis A, Bach E, Nayak A, et al., One-dimensional quantum walks, Proc. STOC 2001, ACM
Press, New York, 2001, 37–49.
[91] Kempe J, Discrete quantum walks hit exponentially faster, Probability Theory and Related Fields,
2005, 133(2): 215–235.
[92] Shenvi N, Kempe J, and Whaley K B, A quantum random-walk search algorithm, Phys. Rev. A,
2003, 67: 052307.
[93] Childs A M, Cleve R, Deotto E, et al., Exponential algorithmic speedup by quantum walk, Proc.
STOC 2003, ACM Press, New York, 2003, 59–68.
[94] Childs A M, Farhi E, and Gutmann S, An example of the difference between quantum and
classical random walks, Quantum Inf. Process, 2002, 1(1 & 2): 35–43.
[95] Szegedy M, Quantum speed-up of markov chain based algorithms, Proc. FOCS 2004, IEEE,
Rome, 2004, 32–41.
[96] Magniez F, Nayak A, Roland J, et al., Search via quantum walk, SIAM J. Comput., 2011, 40(1):
142–164.
[97] Childs A M, Jeffery S, Kothari R, et al., A time-efficient quantum walk for 3-distinctness using
nested updates, arXiv: 1302.7316 [quant-ph].
[98] Farhi E, Goldstone J, and Gutmann S, A quantum algorithm for the Hamiltonian NAND tree,
[99] Harrow A W, Hassidim A, and Lloyd S, Quantum algorithm for solving linear systems of equa-
tions, Phys. Rev. Lett., 2009, 103(15): 150502.
[100] Lloyd S, Universal quantum simulators, Science, 1996, 273(5278): 1073–1078.
[101] Suzuki M, General theory of fractal path integrals with applications to many-body theories and
statistical physics, Journal of Mathematical Physics, 1991, 32(2): 400–407.
[102] Aharonov D and Ta-Shma A, Adiabatic quantum state generation and statistical zero knowledge,
Proc. STOC 2003, ACM Press, New York, 2003, 20–29.
[103] Berry D W, Ahokas G, Cleve R, et al., Efficient quantum algorithms for simulating sparse Hamil-
tonians, Comm. Math. Phys., 2007, 270(2): 359–371.
[104] Childs A M and Kothari R, Simulating sparse Hamiltonians with star decompositions, Theory of
Quantum Computation, Communication, and Cryptography, Eds. by van Dam W, et al., LNCS
6519, Springer-Verlag Berlin Heidelberg, 2011, 94–103.
[105] Berry D W and Childs A M, Black-box Hamiltonian simulation and unitary implementation,
Quantum Information and Computation, 2012, 12: 29–62.
[106] Berry D W, Childs A M, Cleve R, et al., Simulating Hamiltonian dynamics with a truncated
Taylor series, Phys. Rev. Lett., 2015, 114: 090502.
[107] Berry D W, Childs A M, and Kothari R, Hamiltonian simulation with nearly optimal dependence
on all parameters, Proc. FOCS 2015, IEEE, Berkeley, 2015, 792–809.
[108] Low G H and Chuang I L, Hamiltonian simulation by qubitization, arXiv: 1610.06546v2 [quant-
ph].
[109] Chakraborty S, Gilyén A, and Jeffery S, The power of block-encoded matrix powers: Improved
regression techniques via faster Hamiltonian simulation, arXiv: 1804.01973v1 [quant-ph].
[110] Gilyén A, Su Y, Low G H, et al., Quantum singular value transformation and beyond: Exponential
improvements for quantum matrix arithmetics, arXiv: 1806.01838 [quant-ph].
[111] Childs A M and Kothari R, Limitations on the simulation of non-sparse Hamiltonians, Quantum
Information and Computation, 2010, 10: 669–684.
[112] Rebentrost P, Steffens A, and Lloyd S, Quantum singular value decomposition of non-sparse
low-rank matrices, Phys. Rev. A, 2018, 97: 012327.
[113] Kerenidis I and Prakash A, Quantum recommendation system, Proc. ITCSC 2017, Schloss
Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017, 49: 1–21.
[114] Wang C H and Wossnig L, A quantum algorithm for simulating non-sparse Hamiltonians, arXiv:
1803.08273v1 [quant-ph].
[115] Childs A M, Kothari R, and Somma R D, Quantum algorithm for systems of linear equations
with exponentially improved dependence on precision, SIAM J. Comput., 2017, 46: 1920–1950.
[116] Ambainis A, Variable time amplitude amplification and quantum algorithms for linear algebra
problems, Proc. STACS 2012, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl
Publishing, 2012, 636–647.
[117] Saad Y, Iterative Methods for Sparse Linear Systems, 2nd edition, Society for Industrial and
Applied Mathematics, 2003.
[118] Clader B D, Jacobs B C, and Sprouse C R, Preconditioned quantum linear system algorithm,
Phys. Rev. Lett., 2013, 110: 250504.
[119] Wossnig L, Zhao Z K, and Prakash A, Quantum linear system algorithm for dense matrices,
Phys. Rev. Lett., 2018, 120: 050502.
[120] Chen Y A and Gao X S, Quantum algorithms for Boolean equation solving and quantum algebraic
attack on cryptosystems, arXiv: 1712.06239v3 [quant-ph].
[121] Chen Y A, Gao X S, and Yuan C M, Quantum algorithms for optimization and polynomial
systems solving over finite fields, arXiv: 1802.03856v2 [quant-ph].
[122] Schuld M and Petruccione F, Supervised Learning with Quantum Computers, Springer, 2018.
[123] Wittek P, Quantum Machine Learning: What Quantum Computing Mean to Data Mining, Aca-
demic Press, 2014.
[124] Wiebe N, Braun D, and Lloyd S, Quantum algorithm for data fitting, Phys. Rev. Lett., 2012,
109(5): 050505.
[125] Schuld M, Sinayskiy I, and Petruccione F, Prediction by linear regression on a quantum computer,
Phys. Rev. A, 2016, 94: 022342.
[126] Wang G M, Quantum algorithm for linear regression, Phy. Rev. A, 2017, 96: 012335.
[127] Lloyd S, Mohseni M, and Rebentrost P, Quantum algorithms for supervised and unsupervised
machine learning, arXiv: 1307.0411v2 [quant-ph].
[128] Lloyd S, Rebentrost P, and Mohseni M, Quantum principal component analysis, Nature Physics,
2014, 10: 631–633.
[129] Rebentrost P, Mohseni M, and Lloyd S, Quantum support vector machine for big data classifi-
cation, Phys. Rev. Lett., 2014, 113(13): 130503.
[130] Rebentrost P, Bromley T R, Weedbrook C, et al., Quantum recurrent neural network, Phys. Rev.
A, 2018, 98: 042308.
[131] Altaisky M V, Quantum neural network, arXiv: quant-ph/0107012v2.
[132] Schuld M, Sinayskiy I, and Petruccione F, The quest for a quantum neural network, Quantum
Inf. Process, 2014, 13: 2567–2586.
[133] Schuld M, Sinayskiy I, and Petruccione F, Simulating a perceptron on a quantum computer,
Phys. Lett. A, 2015, 379: 660–663.
[134] Wan K H, Dahlsten O, Kristjánsson H, et al., Quantum generalisation of feedforward neural
networks, NPJ Quantum Information, 2017, 3(1): 36–43.
[135] Wiebe N, Kapoor A, and Svore K, Quantum perceptron models, Advances in Neural Information
Processing Systems, 2016, 29: 3999–4007.
[136] Yamamoto A Y, Sundqvist K M, Li P, et al., Simulation of a multidimensional input quantum
perceptron, Quantum Inf. Process, 2018, 17(6): 128–139.
[137] Schützhold R, Pattern recognition on a quantum computer, Phys. Rev. A, 2003, 67: 062311.
[138] Trugenberger C A, Quantum pattern recognition, Quantum Inf. Process, 2002, 1(6): 471–493.
[139] Ventura D and Martinez T, Quantum associative memory, Information Sciences, 2000, 124(1):
273–296.
[140] Low G H, Yoder T J, and Chuang I L, Quantum inference on Bayesian networks, Phys. Rev. A,
2014, 89: 062315.
[141] Sentı́s G, Calsamiglia J, Muñoz-Tapia R, et al., Quantum learning without quantum memory,
Scientific Reports, 2012, 2(708): 1–8.
[142] Barry J, Barry D T, and Aaronson S, Quantum POMDPs, Phys. Rev. A, 2014, 90: 032311.
[143] Clark L A, Huang W, Barlow T M, et al., Hidden quantum Markov models and open quantum
systems with instantaneous feedback, Interdisciplinary Symposium on Complex Systems, Eds. by
Sanayei A, et al., ECC 14, Springer, Cham, 2015, 143–151.
[144] Adachi S H and Henderson M P, Application of quantum annealing to training of deep neural
networks, arXiv: 1510.06356 [quant-ph].
[145] Wiebe N, Kapoor A, and Svore K, Quantum deep learning, arXiv: 1412.3489 [quant-ph].
[146] Amin M H, Andriyash E, Rolfe J, et al., Quantum Boltzmann machine, Phys. Rev. X, 2018, 8:
021050.
[147] Crawford D, Levit A, Ghadermarzy N, et al., Reinforcement learning using quantum Boltzmann
machines, arXiv: 1612.05695 [quant-ph].
[148] Kieferova M and Wiebe N, Tomography and generative data modeling via quantum Boltzmann
training, Phys. Rev. A, 2017, 96: 062327.
[149] Messiah A, Quantum Mechanics, Vol. II. Wiley, New Jersey, 1976.
[150] Farhi E, Goldstone J, Gutmann S, et al., Quantum computation by adiabatic evolution, arXiv:
quant-ph/0001106v1.
[151] Childs A M, Farhi E, and Preskill J, Robustness of adiabatic quantum computation, Phys. Rev.
A, 2001, 65: 012322.
[152] Roland J and Cerf N, Quantum search by local adiabatic evolution, Phys. Rev. A, 2002, 65:
042308.
[153] Aharonov D, van Dam W, Kempe J, et al., Adiabatic quantum computation is equivalent to
standard quantum computation, SIAM J. Comput., 2007, 37(1): 166–194.
[154] Childs A M, Farhi E, Goldstone J, et al., Finding cliques by quantum adiabatic evolution, Quan-
tum Information and Computation, 2002, 2(181): 181–191.
[155] Farhi E, Goldstone F, Gutmann S, et al., A quantum adiabatic evolution algorithm applied to
instances of an NP-complete problem, Science, 2001, 292(5516): 472–475.
[156] Hogg T, Adiabatic quantum computing for random satisfiability problems, Phys. Rev. A, 2003,
67: 022314.
[157] Reichardt B W, The quantum adiabatic optimization algorithm and local minima, Proc. STOC
2004, ACM Press, New York, 2004, 502–510.
[158] van Dam W and Vazirani U V, Limits on quantum adiabatic optimization, http:// cite-
seerx.ist.psu.edu/viewdoc/download?doi=10.1.1.394.2905&rep=rep1&type=pdf.
[159] Neven H, Denchev V S, Rose E, et al., Training a binary classifier with the quantum adiabatic
algorithm, arXiv: 0811.0416 [quant-ph].
[160] Pudenz K L and Lidar D A, Quantum adiabatic machine learning, Quantum Inf. Process, 2013,
12(5): 2027–2070.
[161] Gaitan F and Clark L, Ramsey numbers and adiabatic quantum computing, Phys. Rev. Lett.,
2012, 108: 010501.
[162] Gaitan F and Clark L, Graph isomorphism and adiabatic quantum computing, Phys. Rev. A,
2014, 89(2): 022342.
[163] Kitaev A Y, Fault-tolerant quantum computation by anyons, Annals of Physics, 2003, 303(1):
2–30.
[164] Freedman M H, Kitaev A, Larsen M J, et al., Topological quantum computation, Bull. Amer.
Math. Soc., 2003, 40: 31–38.
[165] Aharonov D, Jones V, and Landau Z, A polynomial quantum algorithm for approximating the
jones polynomial, Proc. STOC 2006, ACM Press, New York, 2006, 427–436.
[166] Aharonov D, Arad I, Eban E, et al., Polynomial quantum algorithms for additive approximations
of the potts model and other points of the tutte plane, arXiv: quant-ph/0702008.
[167] Wocjan P and Yard J, The Jones polynomial: Quantum algorithms and applications in quantum
complexity theory, Quantum Information and Computation, 2008, 8(1): 147–180.
[168] Arad I and Landau Z, Quantum computation and the evaluation of tensor networks, SIAM J.
Comput., 2010, 39(7): 3089–3121.
[169] Aaronson S, The limits of quantum computers, Scientific American, 2008, 298(3): 62–69.
[170] Aaronson S, BQP and the polynomial hierarchy, Proc. STOC 2010, ACM Press, New York, 2010,
141–150.
[171] Mahadev U, Classical Verification of Quantum Computations, arXiv: 1804.01082v2 [quant-ph].
[172] Cirac J and Zoller P, Quantum computation with cold trapped ions, Phys. Rev. Lett., 1995, 74:
4091–4094.
[173] Gershenfeld N and Chuang I L, Bulk spin resonance quantum computing, Science, 1997, 275:
350–356.
[174] Loss D and DiVincenzo D, Quantum computation with quantum dots, Phys. Rev. A, 1998, 57:
120–126.
[175] Vandersypen L M K, Steffen M, Breyta G, et al., Experimental realization of Shor’s quantum
factoring algorithm using nuclear magnetic resonance, Nature, 2001, 414(6866): 883–887.
[176] Zhao Z, Chen Y A, Zhang A N, et al., Experimental demonstration of five-photon entanglement
and open-destination teleportation, Nature, 2004, 430(6995): 54–58.
[177] 12-qubits reached in quantum information quest, https://www.sciencedaily.com/releases/2006/
05/060508164700.htm.
[178] World’s First 28 qubit Quantum Computer Demonstrated Online at Supercomputing 2007 Con-
ference, https://www.nanowerk.com/news/newsid=3274.php.
[179] Dwave System’s 128 qubit chip has been made, https://www.nextbigfuture.com/2008/12/ dwave-
systems-128-qubit-chip-has-been.html.
[180] Monz T, Schindler P, Barreiro J T, et al., 14-Qubit Entanglement: Creation and Coherence,
Phys. Rev. Lett., 2011, 106(13): 130506.
[181] D-wave systems breaks the 1000 qubit quantum computing barrier, https://www.dwavesys.
com/press-releases/d-wave-systems-breaks-1000-qubit-quantum-computing-barrier.
[182] O’Malley P J J, Babbush R, Kivlichan I D, et al., Scalable quantum simulation of molecular
energies, Phys. Rev. X, 2016, 6: 031007.
[183] IBM just made a 17 qubit quantum processor, its most powerful one yet, https://motherboard
.vice.com/en us/article/wnwk5w/ibm-17-qubit-quantum-processor -computer-google.
[184] Quantum inside: Intel manufactures an exotic new chip, https://www.technologyreview.com
/s/609094/quantum-inside-intel-manufactures-an-exotic-new-chip/.
[185] IBM Q Experience, https://quantumexperience.ng.bluemix.net/qx/experience.
[186] Coles P J, Eidenbenz S, Pakin S, et al., Quantum Algorithm Implementations for Beginners,
arXiv: 1804.03719v1 [cs.ET].
[187] China builds five qubit quantum computer sampling and will scale to 20 qubits by end of this year
and could any beat regular computer next year, https://www.nextbigfuture.com/2017/05/china-
builds-ten-qubit-quantum-computer-and-will-scale-to-20-qubits-by-end-of -this-year-and-could-
any-beat-regular-computer-next-year.html.
[188] IBM raises the bar with a 50-qubit quantum computer, https://www.technologyreview.
com/s/609451/ibm-raises-the-bar-with-a-50-qubit-quantum-computer/.
[189] D-wave announces d-wave 2000q quantum computer and first system order, https://
www.dwavesys.com/press-releases/d-wave-announces-d-wave-2000q-quantum-computer-and
-first-system-order.
[190] CES 2018: Intel’s 49-qubit chip shoots for quantum supremacy, https://spectrum.ieee.org/ tech-
talk/computing/hardware/intels-49qubit-chip-aims-for-quantum-supremacy.
[191] Google moves toward quantum supremacy with 72-qubit computer, https://www.sciencenews.
org/article/google-moves-toward-quantum-supremacy-72-qubit-computer.
[192] Lu C Y, Browne D E, and Yang T, Demonstration of a compiled version of Shor’s quantum
factoring algorithm Using Photonic Qubits, Phys. Rev. Lett., 2007, 99: 250504.
[193] Lanyon B P, Weinhold T J, Langford N K, et al., Experimental demonstration of a compiled
version of Shor’s algorithm with quantum entanglement, Phys. Rev. Lett., 2007, 99(25): 250505.
[194] Martin-Lopez E, Laing A, Lawson T, et al., Experimental realisation of Shor’s quantum factoring
algorithm using qubit recycling, Nat. Photon., 2012, 6: 773–776.
[195] Chuang I L, Gershenfeld N, and Kubinec M, Experimental implementation of fast quantum
searching, Phys. Rev. Lett., 1998, 80: 3408–3411.
[196] Vandersypen L M K, Steffen M, Sherwood M H, et al., Implementation of a three-quantum-bit
search algorithm, Appl. Phys. Lett., 2000, 76: 646–648.
[197] Barz S, Kassal I, and Ringbauer M, Solving systems of linear equations on a quantum computer,
Sci. Rep., 2014, 4: 115.
[198] Cai X D, Weedbrook C, Su Z E, et al., Experimental quantum computing to solve systems of
linear equations, Phys. Rev. Lett., 2013, 110(23): 230501.
[199] Pan J W, Cao Y D, Yao X W, et al., Experimental realization of quantum algorithm for solving
linear systems of equations, Phys. Rev. A, 2014, 89: 022313.
[200] Ambainis A, New Developments in Quantum Algorithms, Mathematical Foundations of Computer
Science, Eds. by Hlineny P, et al., LNCS 6281, Springer, Berlin, Heidelberg, 2010, 1–11.
[201] Cleve R, Ekert A, Macchiavello C, et al., Quantum algorithms revisited, Proc. R. Soc. A, 1997,
454(1969): 339–354.
[202] Montanaro A, Quantum algorithms: An overview, npj Quantum Information, 2016, 2: 15023.
[203] Shor P W, Progress in quantum algorithms, Quantum Inf. Process, 2004, 3: 5–13.
[204] Sun X M, A survey on quantum computing, Sci. China Inf. Sci., 2016, 8: 982–1002 (in Chinese).
[205] Dervovic D, Herbster M, Mountney P, et al., Quantum linear systems algorithms: A primer,
[206] Kaye P, Laflamme R, and Mosca M, An Introduction to Quantum Computing, Oxford University
Press, New York, 2007.
[207] Rieffel E and Polak W, Quantum Computing — A Gentle Introduction, The MIT Press, Cam-
bridge, Massachusetts London, England, 2011.
[208] Ambainis A, Quantum walks and their algorithmic applications, International Journal of Quan-
tum Information, 2003, 1: 507–518.
[209] Elı́as S, Venegas-Andraca S E, Quantum walks: A comprehensive review, Quantum Inf. Process,
2012, 11(5): 1015–1106.
[210] Nayak A, Richter P C, and Szegedy M, Quantum analogs of markov chains, Encyclopedia of
Algorithms, Ed. by Kao M Y, Springer, Berlin, Heidelberg, 2014, 1–10.
[211] Santha M, Quantum walk based search algorithms, Proc. TAMC 2008, Xi’an, 2008, 31–46.
[212] Kempe J, Quantum random walks - an introductory overview, Contemporary Physics, 2003,
44(4): 307–327.
[213] Childs A M, Maslov D, Nam Y, et al., Toward the first quantum simulation with quantum
speedup, Proceedings of the National Academy of Sciences, 2018, 115: 9456–9461.
[214] Adcock J C, Allen E, Day M, et al., Advances in quantum machine learning, arXiv: 1512.02900v1
[quant-ph].
[215] Arunachalam S and de Wolf R, A Survey of Quantum Learning Theory, arXiv:1701.06806v3
[quant-ph].
[216] Biamonte J, Wittek P, Pancotti N, et al., Quantum machine learning, Nature, 2017, 549: 195–
202.
[217] Ciliberto C, Herbster M, Ialongo A D, et al., Quantum machine learning: A classical perspective,
Proc. R. Soc. A, 2018, 474(2209): 20170551.
[218] Dunjko V and Briegel H J, Machine learning & artificial intelligence in the quantum domain,
[219] Schuld M, Sinayskiy I, and Petruccione F, An introduction to quantum machine learning, Con-
temporary Physics, 2015, 56(2): 172–185.
[220] Albash T and Lidar D A, Adiabatic quantum computing, Rev. Mod. Phys., 2018, 90: 015002.
[221] Quantum algorithm zoo, https://math.nist.gov/quantum/zoo/.
[222] Childs A M, Lecture notes on quantum algorithms, http://www.cs.umd.edu/ amchilds/qa/.
[223] Christopher M D and Nielsen A, The Solovay-Kitaev algorithm, Quantum Information and Com-
putation, 2006, 6(1): 81–95.
[224] Abrams D S and Lloyd S, Quantum algorithm providing exponential speed increase for finding
eigenvalues and eigenvectors, Phys. Rev. Lett., 1999, 83(24): 5162–5165.
[225] Buhrman H, Cleve R, Watrous J, et al., Quantum fingerprinting, Phys. Rev. Lett., 2001, 87(16):
167902.
[226] Long G L, General quantum interference principle and duality computer, Common. Theor. Phys.,
2006, 45: 825–844.
[227] Childs A M and Wiebe N, Hamiltonian simulation using linear combinations of unitary opera-
tions, Quantum Information and Computation, 2012, 12: 901–924.
[228] Kerenidis I and Prakash A, Quantum gradient descent for linear systems and least squares, arXiv:
1704.04992v3 [quant-ph].
[229] Rebentrost P, Schuld M, Wossnig L, et al., Quantum gradient descent and Newton’s method for
constrained polynomial optimization, arXiv: 1612.01789v2 [quant-ph].
[230] Grover L K and Rudolph T, Creating superpositions that correspond to efficiently integrable
probability distributions, arXiv: quant-ph/0208112.
[231] Soklakov A N and Schack R, Efficient state preparation for a register of quantum bits, Phys. Rev.
A, 2006, 73: 012307.
[232] Alpaydin E, Introduction to Machine Learning, 3rd Edition, The MIT Press, Massachusetts, 2015.
[233] Mackay D, Information Theory, Inference and Learning Algorithms, Cambridge University Press,
Cambridge, 2003.
[234] Sra S, Nowozin S, and Wright S J, Optimization for Machine Learning, The MIT Press, Mas-
sachusetts, 2011.
[235] Golub G H and Van Loan C F, Matrix Computations, 4th Edition, The John Hopkins University
Press, Baltimore, MD, 2013.
[236] Hestenes M R and Stiefel E, Methods of conjugate gradients for solving linear systems, J. Res.
Natl. Bur. Stand., 1952, 49: 409–436.
[237] Aaronson S, Quantum Machine Learning Algorithms: Read the Fine Print, Nature Physics, 2015,
11(4): 291–293.
[238] Childs A M, Quantum algorithms: Equation solving by simulation, Nature Physics, 2009, 5(5):
861.
[239] Harrow A W, Quantum algorithms for systems of linear equations, Encyclopedia of Algorithms,
Ed. by Kao M Y, Springer, Berlin, Heidelberg, 2016, 1680–1683.

[240] Giovannetti V, Lloyd S, and Maccone L, Architectures for a quantum random access memory,
Phys. Rev. A, 2008, 78: 052310.
[241] Giovannetti V, Lloyd S, and Maccone L, Quantum random access memory, Phys. Rev. Lett.,
2008, 100: 160501.
[242] Kerenidis I and Prakash A, A quantum interior point method for LPs and SDPs, arXiv:
1808.09266v1 [quant-ph].
[243] Bardet M, Faugère J C, Salvy B, et al., On the complexity of solving quadratic boolean systems,
Journal of Complexity, 2013, 29(1): 53–75.
[244] Hastie T, Tibshirani R, and Friedman J, The Elements of Statistical Learning, Springer, New
York, 2001.
[245] Haykin S, Neural Networks and Learning Machines, 3rd Edition, Pearson, 2009.
[246] Cleveland W S, Robust locally weighted regression and smoothing scatterplots, Journal of the
American Statistical Association, 1979, 74(368): 829–836.
[247] Cleveland W S and Devlin S J, Locally-weighted regression: An approach to regression analysis
by local fitting, Journal of the American Statistical Association, 1988, 83(403): 596–610.
[248] Ng A, Supervised learning, discriminative algorithms, http://cs229.stanford.edu/notes/ cs229-
notes1.pdf.
[249] Suykens J A K and Vandewalle J, Least squares support vector machine classifiers, Neural Pro-
cessing Letters, 1999, 9(3): 293–300.
[250] Levin D A, Peres Y, and Wilmer E L, Markov Chains and Mixing Times, American Mathematical
Society, Providence, Rhode Island, 2009.
[251] Lovász L, Random walks on graphs — A survey, Combinatorics, 1993, 1–46.
[252] Gerschgorin S, Über die Abgrenzung der Eigenwerte einer Matrix, Izv. Akad. Nauk. USSR Otd.
Fiz.-Mat. Nauk, 1931, 7: 749–754.
[253] Høyer P and Komeili M, Efficient quantum walk on the grid with multiple marked elements,
STACS 2017, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017,
42:1–42:14.
[254] Watrous J, Quantum simulations of classical random walks and undirected graph connectivity,
Journal of Computer and System Sciences, 2001, 62(2): 376–391.
[255] Aharonov D, Ambainis A, Kempe J, et al., Quantum walks on graphs, Proc. STOC 2001, ACM
[256] Kendon V, Quantum walks on general graphs, Int. J. Quantum Inf., 2006, 4(5): 791–805.
[257] Potocek V, Gabris A, Kiss T, et al., Optimized quantum random-walk search algorithms on the
hypercube, Phys. Rev. A, 2009, 79: 012325.
[258] Tonchev H, Alternative coins for quantum random walk search optimized for a hypercube, Journal
of Quantum Information Science, 2015, 5: 6–15.
[259] Ambainis A, Quantum search with variable times, Theory of Computing Systems, 2010, 47(3):
786–807.
[260] Boyer M, Brassard G, Høyer P, et al., Tight bounds on quantum searching, Fortsch. Phys. Prog.
Phys., 1998, 46(4–5): 493–505.
[261] Grover L K, Fixed-point quantum search, Phys. Rev. Lett., 2005, 95: 150501.
[262] Yoder T J, Low G H, Chuang I L, Optimal fixed-point quantum amplitude amplification using
Chebyshev polynomials, Phys. Rev. Lett., 2014, 113: 210501.
[263] Brassard G, Høyer P, and Tapp A, Quantum algorithm for the collision problem, ACM SIGACT
News, 1997, 28: 14–19.
[264] Falk M, Quantum search on the spatial grid, arXiv: 1303.4127 [quant-ph].
[265] Buhrman H, Dürr C, Heiligman M, et al., Quantum algorithms for element distinctness, SIAM
J. Comput., 2005, 34(6): 1324–1330.
[266] Belovs A, Learning-graph-based quantum algorithm for k-distinctness, Proc. FOCS 2012, IEEE,
New Brunswick, 2012, 207–216.
[267] Jeffery S, Frameworks for quantum algorithms, PhD thesis, University of Waterloo, 2014.
[268] Krovi H, Magniez F, Ozols M, et al., Quantum walks can find a marked element on any graph,
Algorithmica, 2016, 74(2): 851–907.
[269] Dohotaru C and Høyer P, Controlled quantum amplification, Proc. ICALP 2017, Schloss Dagstuhl
– Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017, 18: 1–13.
[270] Ambainis A and Kokainis M, Analysis of the extended hitting time and its properties, Proc. QIP
2015, Philadelphia, 2012.
[271] Portugal R, Santos R A M, Fernandes T D, et al., The staggered quantum walk model, Quantum
Information Processing, 2016, 15: 85–101.
[272] Aggarwal D, Dadush D, and Regev O, et al., Solving the shortest vector problem in 2n time via
discrete Gaussian sampling, Proc. STOC 2014, ACM Press, New York, 2014, 733–742.
[273] Chen Y, Chung K, and Lai C, Space-efficient classical and quantum algorithms for the shortest
vector problem, Quantum Information and Computation, 2018, 18(3 & 4): 285–307.
[274] Becker A, Ducas L, and Gama N, et al., New directions in nearest neighbor searching with
applications to lattice sieving, Proc. SODA 2016, SIAM, Philadelphia, 2016, 10–24.
[275] Laarhoven T, Search problems in cryptography, PhD dissertation, Eindhoven University of Tech-
nology, Eindhoven, 2015.
[276] Ettinger M and Høyer P, On quantum algorithms for noncommutative hidden subgroups, Ad-
vances in Applied Mathematics, 2000, 25(3): 239–251.
[277] Bacon D, Childs A M, and van Dam W, Optimal measurements for the dihedral hidden subgroup
problem, Chicago Journal of Theoretical Computer Science, 2006, article 2.
[278] Regev O, A subexponential time algorithm for the dihedral hidden subgroup problem with poly-
nomial space, arXiv: quant-ph/0406151.
[279] Babai L, On the complexity of canonical labeling of strongly regular graphs, SIAM J. Comput.,
1980, 9: 212–216.
[280] Spielman D A, Faster isomorphism testing of strongly regular graphs, Proc. STOC 1996, ACM
Press, New York, 576–584.
[281] Wang F, The Hidden Subgroup Problem, Master’s Project, Aarhus Universitet, 2010.
[282] Ettinger M and Høyer P, A quantum observable for the graph isomorphism problem, arXiv:
quant-ph/9901029.
[283] Beals R, Quantum computation of Fourier transforms over symmetric groups, Proc. STOC 1997,
ACM Press, New York, 1997, 48–53.
[284] Boneh D and Lipton R J, Quantum cryptanalysis of hidden linear functions, Advances in Cryptol-
ogy CRYPTO’95, Ed. by Coppersmith D, LNCS 963, Springer-Verlag Berlin, Heidelberg, 1995,
424–437.
[285] Hallgren S, Moore C, Roetteler M, et al., Limitations of quantum coset states for graph isomor-
phism, J. ACM, 2010, 57(6): 1–33.
[286] Moore C, Russell A, and Schulman L J, The symmetric group defies strong fourier sampling,
SIAM J. Comput., 2008, 37(6): 1842–1864.
[287] Kawano Y and Sekigawa H, Quantum fourier transform over symmetric groups, Proc. ISSAC
2013, ACM Press, New York, 2013, 227–234.
[288] Kawano Y and Sekigawa H, Quantum Fourier transform over symmetric groups - improved result,
J. Symb. Comp., 2016, 75: 219–243.
[289] Williams V V and Williams R, Subcubic equivalences between path, matrix and triangle problems,
Proc. FOCS 2010, IEEE, Las Vegas, 2010, 645–654.
[290] Williams V V and Williams R, Finding, minimizing, and counting weighted subgraphs, SIAM J.
Comput., 2013, 42(3): 831–854.
[291] Williams R, A new algorithm for optimal 2-constraint satisfaction and its implications, Theor.
Comput. Sci., 348(2–3): 357–365.
[292] Belovs A, Span programs for functions with constant-sized 1-certificates, Proc. STOC 2012, ACM
[293] Grötschel M, Lovász L, and Schrijver A, Geometric Algorithms and Combinatorial Optimization,
Springer, New York, 1988.
[294] Lee Y T, Sidford A, and Wong S C, A faster cutting plane method and its implications for
combinatorial and convex optimization, Proc. FOCS 2015, IEEE, Berkeley, 2015, 1049–1065.
[295] Brandão F G S L and Svore K M, Quantum speed-ups for solving semidefinite programs, Proc.
FOCS 2017, IEEE, Berkeley, 2017, 415–426.
[296] Apeldoorn J van, Gilyén A, Gribling S, et al., Quantum SDP-solvers: Better upper and lower
bounds, Proc. FOCS 2017, IEEE, Berkeley, 2017, 403–414.
[297] Apeldoorn J van and Gilyén A, Improvements in quantum SDP-solving with applications, arXiv:
1804.05058 [quant-ph].
[298] Brandão F G S L, Kalev A, Li T Y, et al., Quantum SDP solvers: Large speed-ups, optimality,
and applications to quantum learning, arXiv: 1710.02581v2 [quant-ph].
[299] Lee Y T, Sidford A, and Vempala S S, Efficient convex optimization with membership oracles,
arXiv: 1706.07357 [cs.DS].
[300] Chakraborty S, Childs A M, Li T Y, et al., Quantum algorithms and lower bounds for convex
optimization, arXiv: 1809.01731 [quant-ph].
[301] Apeldoorn J van, Gilyén A, Gribling S, et al., Convex optimization using quantum oracles, arXiv:
1809.00643v1 [quant-ph].
[302] Grassl M, Langenberg B, and Roetteler M, et al., Applying Grover’s Algorithm to AES: Quantum
Resource Estimates, PQCrypto 2016, Ed. by Takagi T, LNCS 9606, Springer, Cham 2016, 29–43.
[303] Amy M, Di Matteo O, and Gheorghiu V, et al., Estimating the cost of generic quantum pre-image
attacks on SHA-2 and SHA-3, Selected Areas in Cryptography, Eds. by Avanzi R and Heys H,
LNCS 10532, Springer, Cham, 2017, 317–337.
[304] Dunjko V, Ge Y M, and Cirac I, Computational speedups using small quantum devices, arXiv:
1807.08970 [quant-ph].
[305] Schuld M, Bocharov A, Svore K, et al., Circuit-centric quantum classifiers, arXiv: 1804.00633
[quant-ph].
View publication stats

Quantum Algorithm Design Techniques and Applications

Uploaded by

Copyright:

Available Formats

Quantum Algorithm Design Techniques and Applications

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Quantum Algorithm Design Techniques and Applications

Uploaded by

Copyright:

Available Formats

See discussions, stats, and author profiles for this publication at: https://www.researchgate.

Quantum Algorithm Design: Techniques and Applications

Article in Journal of Systems Science and Complexity · February 2019

Quantum computing View project

The user has requested enhancement of the downloaded file.

Quantum Algorithm Design: Techniques and

1 Overview: Development of Quantum Algorithms

1.1 Early History

1.2 Hidden Subgroup Problem

1.3 (Sub-)Exponential Speedup Quantum Algorithms for Breaking Cryptosys-

putational diﬃculty of this problem. By assuming the correctness of Generalized Riemann

1.4 Grover’s Search Algorithm

1.5 Quantum Walk

1.6 Hamiltonian Simulation

Asp := max Ax. (1.1)

In 2003, Aharonov and Ta-Shma[102] generalized Lloyd’s algorithm substantially to simu-

1.7 Quantum Linear Solver

1.8 Quantum Machine Learning

1.9 Robust Quantum Computing and Quantum Complexity Theory

One important application of topological quantum computing is a polynomial-time quan-

1.10 Hardware Development and Quantum Algorithm Demonstration

a 2000-qubit quantum annealing computer[189] .

Table 1 Experimental demonstration of quantum algorithms

Algorithm Problem solved # qubits: Technology

2 Basic Terminology in Quantum Algorithms

• f = Θ (g) if both f = O(g) and f = Ω (g).

• poly(n) (or poly n) refers to a polynomial in n.

• log(n1 , · · · , nk ) refers to a product of logarithmic factors in n1 , · · · , nk respectively.

(ai bj )i=1,2,··· ,m,j=1,2,··· ,n

is denoted by |a b|. When m = n, then a|b denotes a · b. The tensor product a ⊗ b is a

|ab = |a, b := |a ⊗ |b (2.1)

when representing a quantum state.

|φ = α|0 + β|1 = α|0 + |0 ⊥ , (2.2)

where |0 ⊥ is a shorthand notation of a linear combination of quantum states orthogonal to |0 .

|0 ⊗ |φ = (x1 , · · · , xN , 0, · · · , 0)T , |1 ⊗ |φ = (0, · · · , 0, x1 , · · · , xN )T . (2.5)

|ψ1 ψ2 · · · ψk = |ψ1 |ψ2 · · · |ψk , (2.6)

where |i := |ei represents the basis state by its subscript.

(ii) Reﬂection with respect to a subspace of CN .

where I is the identity matrix. The reﬂection with respect to W ⊥ is RW ⊥ = −RW .

(iii) Quantum Fourier transform: the matrix form is

of the binary expressions of integers x, y taken as vectors of dimension n.

(v) Grover’s diﬀusion: R|2n  , with |2n given by (2.13).

(vi) Elimination of register.

(vii) Quantum implementation of classical map.

The quantum implementation can be realized by Uf H, in which H is the Hadamard

Uf : |x, y → |x, y ⊕ f (x) , ∀x ∈ Z2n , y ∈ Z2m , (2.17)

where ⊕ denotes the bit-wise XOR.

(viii) Control transformation

where each Cj is a unitary operator.

(II) Quantum amplitude amplification Let |ψ = α|x + |x ⊥ be a quantum state, where

(V) Quantum preparation of classical vector Given a complex vector x = (x1 , · · · , xn )T ,

(VI) Quantum eigenphase decomposition of unitary operator Let U be an n×n unitary

(VII) Quantum singular value estimation (SVE)

Asp = max |σi |. (2.24)

When m = n, a quantum SVE of A is a unitary transformation with one of the following

i is an approximate of σi with error bound |

i ≤ r} in Cm+n is the eigenspace of Aext corresponding to eigenvalue 0, and is spanned

 i are approximates of σi , −σi respectively, with error bound εAsp .

for some unknown parameter t > 0, where A+ is the Moore-Penrose inverse of A.

3 Some Building Blocks in Quantum Algorithm Design

|φ = α|0 + β|1 = α|0 + |0⊥ , (2.2)

where |0⊥ is a shorthand notation of a linear combination of quantum states orthogonal to |0.

(v) Grover’s diﬀusion: R|2n , with |2n given by (2.13).

Uf : |x, y → |x, y ⊕ f (x), ∀x ∈ Z2n , y ∈ Z2m , (2.17)

(II) Quantum amplitude amplification Let |ψ = α|x + |x⊥ be a quantum state, where

i is an approximate of σi with error bound |

i are approximates of σi , −σi respectively, with error bound εAsp .

where θj is an approximate of θj for all 1 ≤ j ≤ M .

In Algorithm 1, choose the initial state |0⊗n |c = |0⊗n |0⊗(m−1) |1. Following the expres-

Rcos(2θ),− sin(2θ) = (I − 2|φ φ|)(R|0 ⊗ I), (3.19)

Step 1 By quantum eigenphase decomposition (3.13), when choosing |0|b|0 as the initial

UM : |i|0 → |i|Ai , UN : |0|j → |A |j. (4.17)

where θk is a (2ε)-approximate of θk for 0 ≤ k < M .

k−1 for 0 ≤ k < M , with

is changed into (X † X + λI)