PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Algorithms

Michele Mosca

arXiv:0808.0369v1quant-ph

TL;DR

This survey addresses what quantum computers can solve more efficiently than classical algorithms and why those possibilities matter for cryptography and other applications. It synthesizes representative black-box and non-black-box algorithms, reporting results such as a quadratic quantum speedup for search, while noting that worst-case adiabatic complexity remains difficult to establish.

  • Problem

    Quantum computation raises the question of which important problems quantum algorithms can solve more efficiently than the best known classical algorithms, including problems central to public-key cryptography.

    Source: §1 · pp. 3–4

  • Method

    The article surveys a representative sample of black-box and non-black-box quantum algorithms, organized by problem, technique, and algorithmic paradigm.

    Source: §2 · p. 7

  • Results

    The survey reports an Abelian hidden-subgroup algorithm using O(l) evaluations with an Ω(l) worst-case query lower bound, and Grover’s search algorithm gives a quadratic speedup over the best possible classical algorithm.

    Source: Quantum algorithms for the Abelian… · p. 18, §5 · p. 18

  • Takeaways & Limitations

    Shor’s factoring and discrete-logarithm results imply that sufficiently capable quantum computers could compromise public-key cryptography based on those problems, while the broader application implications remain unknown.

    Source: §1 · p. 4

    Worst-case complexity for adiabatic algorithms on NP-hard problems is unknown because rigorous or convincing heuristic bounds on the minimum gap are difficult to establish.

    Source: §9 · p. 48

Abstract

from arXiv · show

This article surveys the state of the art in quantum computer algorithms, including both black-box and non-black-box results. It is infeasible to detail all the known quantum algorithms, so a representative sample is given. This includes a summary of the early quantum algorithms, a description of the Abelian Hidden Subgroup algorithms (including Shor's factoring and discrete logarithm algorithms), quantum searching and amplitude amplification, quantum algorithms for simulating quantum mechanical systems, several non-trivial generalizations of the Abelian Hidden Subgroup Problem (and related techniques), the quantum walk paradigm for quantum algorithms, the paradigm of adiabatic algorithms, a family of ``topological'' algorithms, and algorithms for quantum tasks which cannot be done by a classical computer, followed by a discussion.

Glossary

The glossary distinguishes computational cost from the number of oracle queries and defines the standard circuit and black-box models.

Quantum Circuit Model

  • The quantum circuit model generalizes classical acyclic circuits and is commonly used to represent quantum computation.For problems with infinitely many possible inputs, circuit families are often required to be uniform: the circuit for size n must be efficiently generated from n.Source: Glossary · p. 2

Black Box Model; Query Complexity

  • A black-box model exposes an oracle only through queries, and its query complexity counts the applications needed to solve the problem.An oracle may, for example, return selected bits of a string.Source: Glossary · p. 2

Computational Complexity

  • Computational complexity measures an algorithm’s resource use as a function of input size, while problem complexity is the minimum resources any algorithm requires.The algorithm measure is usually worst-case over inputs of a given size.Source: Glossary · p. 2

1 Definition of the Subject and Its Importance

Quantum mechanics challenges the Strong Church-Turing thesis’s classical framework and motivates asking whether quantum computers can solve important problems more efficiently. The survey frames this question through cryptographic risks and broader potential applications.

Origins of quantum computation

  • Quantum mechanics challenged the Strong Church-Turing thesis’s claim that probabilistic Turing machines efficiently simulate realistic computation, prompting proposals for quantum computation.Feynman proposed quantum computers for simulating quantum systems; Deutsch defined quantum models and gave the first quantum algorithm.Source: §1 · pp. 2–3

Quantum computation models

  • Quantum algorithms are studied in realistic quantum-computation models, most commonly uniform quantum circuits, which can efficiently simulate other developed models.The circuit model closely resembles many current approaches to scalable quantum computers.Source: §1 · p. 3

Cryptographic significance

  • Shor’s efficient factoring and discrete-logarithm algorithms [165] threaten public-key cryptography, which relies on the believed difficulty of those problems.The passage warns that a sufficiently capable quantum computer could compromise previously recorded ciphertexts and public keys.Source: §1 · pp. 3–4

Broader applications

  • Quantum algorithms are motivated by the possibility that quantum computers can efficiently solve problems lacking known or possible efficient classical algorithms.Searching, optimization, and physical-system simulation are cited as known application areas, while broader implications remain uncertain.Source: §1 · p. 4

2 Introduction and Overview

The introduction outlines a representative survey of quantum algorithms, their models, techniques, and the limits of black-box conclusions. It connects reversible computation and oracle algorithms to concrete implementations while noting where coverage or guarantees remain incomplete.

Continuous and discrete models

  • Continuous-time algorithms are useful when efficiently simulable by universal discrete models, while continuous problems require discretization and error analysis.The survey describes continuous-time quantum walks and adiabatic algorithms, and notes that approximation scaling must be quantified as error decreases.Source: §2 · p. 5

Reversible computation

  • A classical circuit of size C can be converted into O(C) reversible gates that compute f(x) into an output register while resetting ancilla workspace.This construction underlies the reversible implementation of classical heuristic algorithms used in quantum search.Source: §2 · pp. 5–6

Black-box algorithms

  • Replacing each of T oracle calls with a B-gate subcircuit yields TB + A gates when the algorithm uses A other steps, so polynomial T and A preserve efficiency for polynomial-time computable functions.The survey notes that Shor’s factoring algorithm can be viewed as an oracle algorithm whose oracle is implemented by modular exponentiation.Source: §2 · p. 6

Limits of black-box lower bounds

  • A black-box query lower bound of T implies an Ω(T) gate lower bound only for algorithms that treat the implemented subcircuit as a black box, not for algorithms exploiting its internal structure.A stronger gate lower bound would require a lower bound on the cost of implementing the black box itself.Source: §2 · p. 6

Survey scope

  • The survey covers representative black-box and non-black-box algorithms, comparing quantum and classical performance where information is available, but acknowledges gaps in query and operation counts or lower bounds.Its sections group algorithms by problem type, technique, or paradigm, including early algorithms, hidden subgroups, search, simulation, quantum walks, adiabatic methods, and topological algorithms.Source: §2 · p. 7

Input conventions

  • The survey represents real inputs and outputs by finite descriptions that enable polynomial-time approximations to error at most 1/2^n.Source: §2 · p. 7

3 Early Quantum Algorithms

The early algorithms show how quantum queries can distinguish promised functions and recover hidden structure, culminating in Simon’s algorithm and its computational bounds. Together, these results connect foundational black-box work to later practical quantum algorithms.

3 Early Quantum Algorithms

  • Deutsch’s one-query algorithm distinguishes whether a two-input Boolean function is constant or balanced by computing f(0)⊕f(1), and guesses correctly with probability 2/3 when the measurement is inconclusive.Source: §3 · pp. 7–8
  • Deutsch-Jozsa extends the constant-versus-balanced promise to n-bit inputs; its quantum query count is two, reducible to one for the standard oracle, versus 2^(n−1)+1 deterministic classical evaluations.A classical randomized algorithm can decide with error ε using O(log(1/ε)) queries.Source: §3 · pp. 8–9
  • Bernstein and Vazirani recover the hidden vector with one standard-oracle query, and recursive Fourier sampling was the first black-box problem shown to give an exponential quantum improvement over bounded-error randomized classical algorithms.The affine-map generalization recovers an m × n matrix using m queries, potentially fewer than n+1 when m<n, though no practical application was developed.Source: §3 · p. 9

Simon’s problem

  • Simon’s problem asks for the hidden string s such that f(x)=f(y) exactly when x⊕y is 0 or s; s=0 gives a one-to-one function and nonzero s a two-to-one function.Source: Simon’s problem · p. 9

Simon’s algorithm

  • Simon’s algorithm samples vectors orthogonal to s and uses linear algebra to recover it from n+O(1) samples with high probability.The algorithm prepares a coset state, applies Hadamard gates, measures samples, and solves a linear system.Source: Simon’s algorithm · p. 10

Classical algorithms for Simon’s problem

Quantum algorithms for Simon’s problem

  • Simon’s algorithm finds hidden s with bounded error using n+O(1) oracle evaluations, O(n) quantum operations, and O(n^3) classical operations.Brassard and Høyer combined it with amplitude amplification to make the algorithm exact.Source: Quantum algorithms for Simon’s problem · p. 11

4 Factoring, Discrete Logarithms and the Abelian Hidden Subgroup Problem

The section presents factoring and discrete logarithms through quantum order- and period-finding, then places these algorithms within the Abelian Hidden Subgroup Problem. It describes quantum methods, their complexity bounds, and applications of hidden-subgroup algorithms.

Integer factorization problem

  • Factoring reduces in classical probabilistic polynomial time to O(l) order-finding instances, and order finding can be solved efficiently on a quantum computer.Here l is O(log N).Source: Integer factorization problem · p. 12

Eigenvalue estimation problem

Period finding problem

  • Shor’s order-finding methods estimate a random integer multiple of 1/r, then use continued fractions to recover r.For period finding, the quantum Fourier transform estimates the period; the same algorithm applies beyond f(x) = ax mod N when the stated distinct-value assumption holds.Source: Period finding problem · p. 12, Sampling estimates · p. 13

Phase estimation problem

  • Kitaev’s phase-estimation algorithm uses O(n) state copies and estimates the phase with error at most 1/2^n with high probability.It does not require a quantum Fourier transform.Source: Phase estimation problem · pp. 13–14

Quantum algorithms for order finding

  • For groups with unique encodings, quantum order finding uses O(log r) black-box multiplications and O(n + log^2 r) other elementary operations.The supplied passage also gives a quantum complexity bound for order finding modulo N, but its expression is incomplete in context.Source: Quantum algorithms for order finding · p. 14

The discrete logarithm problem

The Abelian hidden subgroup problem

  • Finite and finitely generated Abelian hidden-subgroup problems are efficiently solvable by generalizations of factoring, discrete-log, and Simon algorithms.The framework includes period finding, discrete logarithms, and self-shift-equivalences of polynomials as hidden-subgroup instances.Source: The Abelian hidden subgroup problem · pp. 16–17

Quantum algorithms for the Abelian Hidden Subgroup Problem

5 Algorithms based on Amplitude Amplification

This section presents Grover search and amplitude amplification as quantum methods for increasing the chance of finding a solution. It also surveys their query-complexity guarantees and applications, including amplitude estimation and collision finding.

5 Algorithms based on Amplitude Amplification

  • Grover’s search algorithm permits constructive amplitude growth, and amplitude amplification generalizes the approach to algorithms that guess a solution with probability p.With an initial success probability p, amplification uses O(1/√p) applications of the oracle and unitary versions of A and A^-1.Source: Search problem · pp. 19–20

Search problem

  • With probability at least 2/3, quantum search finds a solution if one exists using O(√(2^n)) oracle applications; Ω(√(2^n)) are necessary.The lower bound applies even when there is at most one solution; the algorithm also works with a small bounded error in the oracle.Source: Search problem · p. 20

5.1 Other applications of Amplitude Amplification

  • Amplitude estimation supports approximate and exact counting and estimating a function’s mean, with up to a quadratic speed-up over classical algorithms.The section also discusses local searching, whose speed-up depends on spatial dimension, and ordered-list search, which takes Θ(log N) queries with an unknown constant factor.Source: §5.1 · p. 21, Search problem · p. 21

Quantum Algorithms for Collision Finding

  • For an r-to-1 function, the quantum collision algorithm outputs a collision with probability at least 2/3 when r > 1, and otherwise outputs “NO COLLISION”.The section states that a lower bound on oracle applications is needed, but the supplied passage gives no complete bound.Source: Quantum Algorithms for Collision Finding · p. 22

Classical Algorithms for Collision Finding

  • A classical probabilistic collision algorithm likewise outputs a collision with probability at least 2/3 when r > 1, and otherwise outputs “NO COLLISION”.The section also states that a lower bound on oracle applications is needed, but the supplied passage gives no complete bound.Source: Classical Algorithms for Collision… · p. 22

6 Simulation of quantum mechanical systems

The survey focuses on simulating quantum-system evolution from an initial state and Hamiltonian, considering both Hamiltonian-sum and sparse-oracle formulations. It describes algorithmic bounds in terms of the evolution scale and discusses ground-state preparation and continuous-time algorithms as applications.

6 Simulation of quantum mechanical systems

  • Motivated by simulation of quantum systems, the section studies evolution from an initial state and Hamiltonian, restricting attention to discrete spaces and time-independent Hamiltonians.Continuous state spaces are approximated by discrete ones with accumulated error below a desired threshold; well-behaved time-dependent evolution can be approximated by a sequence of time-dependent evolutions.Source: §6 · pp. 22–23

Hamiltonian Simulation Problem 1

  • The sum formulation assumes each simple component can be simulated, treating that simulation as exact and unit-cost for convenience.For local terms acting on a fixed number of subsystems, the component can be simulated on those relevant subsystems.Source: §6 · p. 23, Hamiltonian Simulation Problem 1 · p. 24
  • Hamiltonian Simulation Problem 1 takes a sum H = ΣHk, an initial n-qubit state, time t, and error ε, and outputs a state approximating eiHt|ψ⟩.The formulation supplies black boxes for the component evolutions.Source: Hamiltonian Simulation Problem 1 · p. 23
  • Commuting component Hamiltonians make simulation straightforward, while noncommuting terms can be approximated using Trotter formulas and improved variants.Product Hamiltonians such as tensor products of Pauli operators also admit efficient simulation, and the cited discussion notes the number of factors need not be constant.Source: Hamiltonian Simulation Problem 1 · pp. 24–25

Quantum complexity of Hamiltonian Simulation Problem 1

  • The Hamiltonian-sum algorithm achieves trace-distance error at most ε with running time polynomial in n when each exponential term is simulable in polynomial time; some cases require Ω(τ) time.Here τ = ||H||t.Source: Quantum complexity of Hamiltonian… · p. 25

Hamiltonian Simulation Problem 2

Quantum complexity of Hamiltonian Simulation Problem 2

  • For sparse Hamiltonians, an algorithm achieves trace-distance error at most ε with a stated black-box query bound, while some cases require Ω(τ) evaluations.The query bound is stated for any positive integer k; τ = ||H||t.Source: Quantum complexity of Hamiltonian… · p. 26
  • Simulation can support ground-state preparation by combining dynamics simulation, eigenvalue estimation, and amplitude amplification when a procedure prepares the ground state with probability p.The discussion also identifies implementation of continuous-time algorithms in a discrete-time model as an application.Source: Quantum complexity of Hamiltonian… · pp. 26–27

7 Generalizations of the Abelian Hidden Subgroup Problem

This section surveys extensions of Abelian Hidden Subgroup methods, including non-Abelian and lattice-based approaches, hidden nonlinear structures, and hidden shifts and translations. It covers related quantum algorithms and results, along with query bounds and limitations or partial progress on several techniques.

7.1 Non-Abelian Hidden Subgroup Problem

  • For graph automorphism, the hidden subgroup is the graph’s automorphism group, and no substantially better quantum algorithm for graph isomorphism is known.Graph isomorphism reduces to graph automorphism.Source: §7.1 · p. 27

Query complexity of the non-Abelian Hidden Subgroup Problem

  • For any finite group, the non-Abelian HSP takes O(log |G|) oracle queries with high probability, but whether the full algorithm can be efficient remains open.The efficiency question includes both black-box queries and other elementary operations.Source: Query complexity of the non-Abelian… · pp. 27–28

7.1.1 Quantum Fourier transform approaches

  • Non-Abelian quantum Fourier transforms are sometimes efficient to implement, but are not known to be efficient in general and appear useful for HSP only in special cases, such as normal subgroups.The approach starts from a random coset state and seeks information about the hidden subgroup through a Fourier transform.Source: §7.1.1 · pp. 28, 30

7.1.2 “Pretty Good Measurements”

  • For the dihedral HSP, the pretty good measurement is optimal but not known to be efficiently implementable; it is implementable for the Heisenberg-group HSP.For certain semidirect-product groups, these measurements are also optimal and their implementation relates to matrix-sum problems and average-case algebraic problems. The cited families include Z_p^r ⋊ Z_p for constant r and Z_N ⋊ Z_p when p is prime and N/p is polynomial in log N.Source: §7.1.2 · pp. 31–32

7.1.3 “Sieving”

Classical algorithms for the dihedral HSP

7.1.4 Other methods and results

  • For nil-2 groups, standard HSP instances reduce non-trivially to Abelian HSP instances, and generators can be found in polynomial time using O(log |G|) hiding samples.The result uses a generalized hiding procedure whose states are identical within a left coset and orthogonal across different left cosets.Source: §7.1.4 · pp. 33–34

7.2 Lattice and Number Field Problems

  • Lattice methods yield quantum algorithms for Pell’s equation and the Principal Ideal Problem, and polynomial-time algorithms for computing unit groups of number fields.A logarithmic embedding represents the unit group as a lattice; approximating its generators supports unit-group computation and a simpler solution to the Principal Ideal Problem in constant-degree fields.Source: §7.2 · pp. 34–35
  • Under the Generalized Riemann Hypothesis, the tools also find unique quantum representatives of class-group elements in constant-degree number fields, enabling class-group computation.Source: §7.2 · p. 35

7.3 Hidden Non-Linear Structures

  • The hidden-radius problem generalizes the Abelian HSP by hiding sets defined by nonlinear equations, such as circles over finite fields.In the described construction, points on a circle are encoded using randomly permuted offsets and centers.Source: §7.3 · p. 36, Hidden Radius Problem · p. 36

Quantum Algorithms for the Hidden Radius Problem

  • For odd d, a bounded-error quantum algorithm finds the hidden radius with polylog(q) queries, while another uses polylog(q) total operations to determine whether it is a quadratic residue.The radius-finding algorithm has no known polynomial bound on its non-query operations.Source: Quantum Algorithms for the Hidden… · p. 36

Classical Algorithms for the Hidden Radius Problem

7.4 Hidden shifts and translations

  • Hidden shifts include polynomial shift-equivalence; quantum algorithms solve finite-field character shifts efficiently and imply a method to break a class of algebraically homomorphic cryptosystems.The more general orbit-equivalence problem can be hard even for quantum computers.Source: §7.4 · p. 37
  • For smoothly solvable groups, quantum algorithms solve hidden translation with polynomial queries and operations, and also solve the hidden subgroup problem for those groups.The translation algorithm builds on an orbit-coset problem that is self-reducible to quotient and normal-subgroup instances.Source: §7.4 · pp. 37–38
  • For any fixed ε > 0, the generalized hidden shift problem is solvable in time polynomial in log N when M ≥ N^ε.Its algorithm uses a pretty good measurement involving a matrix-sum problem; M = 2 recovers the dihedral HSP, while M = N yields an Abelian HSP instance.Source: §7.4 · pp. 38–39

7.5 Other related algorithms

  • A quantum algorithm estimates the phase γ of a finite-field Gauss sum to error below ε in time O(1/ε polylog(pr)).The problem is not black-box, and solving it is at least as hard as the discrete logarithm problem in the field’s multiplicative group.Source: §7.5 · p. 40

8 Quantum walk algorithms

Quantum walks model computation as evolution over graph states, with unitary and continuous-time variants. The survey highlights applications to element distinctness, glued-trees, and NAND-tree evaluation, while noting that the relationship between walk models remains unsettled.

8 Quantum walk algorithms

  • A coined walk adds a coin register of dimension at least the graph's maximum degree, allowing unitary transitions where a walk on the original graph may not be unitary.The coin indicates which neighbor to move to; alternatively, the walk can use directed-edge states.Source: §8 · p. 42
  • Quantum walks can offer at most quadratic speedups in mixing time, while some examples achieve exponentially faster hitting times.A unitary walk does not reach equilibrium; averaging over time is one way to define effective mixing time.Source: §8 · p. 42

Element Distinctness Problem

  • Quantum walks provide an algorithm for element distinctness, whereas classical bounded-error algorithms require N − O(1) oracle applications on worst-case instances.The quantum algorithm uses a walk over subsets of size ⌈N/3⌉, with adjacent subsets differing in two elements; its detailed analysis is beyond this survey's scope.Source: Quantum Algorithms for Element… · p. 43, Classical Algorithms for Element… · p. 43

8 Quantum walk algorithms

  • Quantum-walk algorithms have been applied to element distinctness, triangle finding, commutativity testing, and other problems, and some of the best known algorithms use walks.The relationship between continuous-time and discrete-time walk models is not fully understood.Source: §8 · p. 41, Classical Algorithms for Element… · p. 43

“Glued-trees” problem

  • For glued-trees, a continuous-time walk finds the EXIT label with probability at least 1 − 2^-n(1 − ε), while any classical algorithm making 2^(n/6) queries succeeds with probability at most 4 · 2^−n/6.The walk starts at ENTRANCE, evolves under the graph's adjacency-matrix Hamiltonian, and is efficiently simulatable with polynomially many oracle calls.Source: Quantum Algorithms for the… · p. 44, Classical Algorithms for the… · p. 44

NAND-tree evaluation

9 Adiabatic algorithms

Adiabatic algorithms encode a problem in a target Hamiltonian's ground state and evolve an initially prepared ground state toward it. Their worst-case complexity for problems such as 3-SAT is unknown because rigorous or convincing heuristic bounds on the minimum gap are difficult to establish.

Adiabatic algorithms

  • Adiabatic algorithms interpolate from an easy-to-prepare ground state of H0 to the ground state of a problem Hamiltonian H1, relying on sufficiently slow evolution to remain in the ground state.The interpolation is H(t) = (1 − t/T)H0 + (t/T)H1.Source: §9 · p. 47
  • The required evolution time depends on the minimum gap between the two lowest eigenvalues, the Hamiltonian norm, and norms of its derivatives.Scaling the Hamiltonian can speed up its evolution but incurs resource overhead in realistic implementations.Source: §9 · p. 48
  • For 3-SAT with a unique satisfying assignment w, the described problem Hamiltonian has |w⟩⟨w| as its unique ground state.Its fΦ(x) term counts clauses violated by assignment x.Source: §9 · p. 48
  • The worst-case complexity of these algorithms on NP-hard problems is unknown because useful rigorous or convincing heuristic bounds on the minimum gap have proved difficult to obtain.The survey notes a widespread belief that these algorithms will not solve an NP-hard problem in polynomial time.Source: §9 · p. 48
  • Adiabatic computation, a generalization that need not end with a Hamiltonian diagonal in the computational basis, is polynomially equivalent to general quantum computation.Source: §9 · pp. 48–49

10 Topological algorithms

Topological quantum algorithms use quantum computation to approximate quantities such as the Jones and Tutte polynomials. The survey describes a construction through planar medial graphs and linear transformations, while noting that known approximations do not solve the associated NP-hard problem.

10 Topological algorithms

  • Topological quantum algorithms approximate the Jones polynomial at certain points more efficiently than any known classical algorithm, but the known approximations are insufficient to solve an NP-hard problem.The corresponding topological quantum field theory model is equivalent in power to the standard quantum-computation model.Source: §10 · p. 49
  • Exact Jones-polynomial evaluation is #P-hard at primitive rth roots of unity for r ≥ 5, while certain approximations are not known to be #P-hard.Source: §10 · pp. 49–50

Quantum Algorithms for Approximating the Tutte Polynomial

  • A quantum algorithm approximates the Tutte-polynomial value in time polynomial in n, with additive approximation Δ_alg/poly(m), where Δ_alg depends on the graph embedding.The survey says comparison with classical algorithms is difficult, though special cases are BQP-hard.Source: Quantum Algorithms for Approximating… · pp. 50–51

Classical Algorithms for Approximating the Tutte Polynomial

  • For certain parameter ranges, approximating the Tutte polynomial is BQP-hard, so a classical algorithm is not expected to match the quantum approximation unless classical computers efficiently simulate quantum computers.Source: Classical Algorithms for Approximating… · p. 51

10.1 Sketch of the structure of the algorithm

  • The algorithm maps a planar graph to its medial graph and represents that graph as a linear operation whose matrix element gives the Kauffman bracket and thus a generalized Tutte polynomial.The medial graph is decomposed into basic elements represented by transformations on finite-dimensional Hilbert spaces; ancillas and unitaries implement non-unitary transformations for the inner-product estimate.Source: §10 · p. 50, §10.1 · pp. 51–52

11 Quantum algorithms for quantum tasks

The survey broadens quantum algorithms beyond classical inputs and outputs, covering quantum subroutines, state transformations, and tasks such as compression and entanglement distillation. It also describes estimating an inner product as a basic subroutine for topological algorithms.

11 Quantum algorithms for quantum tasks

  • Some quantum algorithms take quantum inputs or produce quantum outputs rather than solving a classical-input, classical-output problem.Amplitude amplification can search for a marked quantum state, and amplitude estimation can estimate a unitary's transition probability.Source: §11 · p. 52
  • The Hadamard test estimates the real part of an inner product involving U|00...0⟩, using repeated trials or amplitude estimation; a similar procedure estimates the imaginary part.The survey identifies inner-product estimation as a subroutine for topological algorithms.Source: §11 · pp. 52–53
  • The coset orbit problem asks whether a group action maps one supplied quantum state to another and, if so, returns a representative and generators for the stabilizer subgroup.Its solution was an important part of the solution to the hidden translation problem.Source: §11 · p. 53
  • Quantum tasks also include data compression, entanglement concentration and distillation, and basis transformations such as the Clebsch-Gordan transformation.Source: §11 · p. 53

12 Future directions

Developments across quantum algorithms have made a comprehensive survey impractical, while open directions range from extending existing paradigms to finding new ones. Future progress may also clarify when large-scale quantum computers can test conjectured running times.

Outlook

  • The field’s progress has made a full survey impractical, and large-scale quantum computers could eventually test conjectured running times on interesting instances.The section anticipates that a survey will be harder to write in another decade and hopes for clearer expectations about when such computers may arrive.Source: §12 · pp. 54–56

Non-Abelian hidden subgroup problem

  • A quantum polynomial-time algorithm for graph isomorphism remains an open question; confidence that none exists could support quantum computationally secure cryptography.The passage notes that proving no such algorithm exists would imply P̸ = PSPACE.Source: §12 · p. 54

Amplitude amplification

  • Amplitude amplification has sped up classical algorithms in non-trivial ways, and further such applications may exist.The passage distinguishes these applications from simply treating a classical algorithm as a guessing algorithm and applying amplitude amplification.Source: §12 · p. 54

Quantum walks

  • Quantum walks have become a standard algorithm-design approach, with black-box results applicable to actual functions such as cryptographic hash functions.The passage also calls for a unified theory spanning continuous and discrete, coined and non-coined, and quantum and classical walks.Source: §12 · pp. 54–55

Adiabatic algorithms

  • No adiabatic algorithm is yet proven to run more than quadratically faster than the best known classical algorithm, partly because worst-case complexity is hard to analyze.The section asks whether adiabatic algorithms can do better.Source: §12 · p. 55

Topological algorithms

  • Topological algorithms have received limited attention partly because early work required substantial familiarity with topological quantum field theory, but recent work suggests the approach could mature into a fruitful paradigm.Source: §12 · p. 55

Measurement-based computation and globally controlled architectures

  • Measurement-based computation has mostly been studied as a possible way to implement scalable fault-tolerant quantum computers; algorithms may be developed directly in this and globally controlled architectures.Source: §12 · p. 55

Computational problems in physics

  • Work on physics problems includes Hamiltonian-simulation complexity, QMA-hardness of some ground-state computations, and identifying quantum systems efficiently simulable classically.The passage suggests that cross-disciplinary exchange may help define candidate simulation problems and yield quantum algorithms or reusable primitives.Source: §12 · pp. 55–56
Loading 0808.0369v1…