Quantum algorithms for algebraic problems

Abstract

Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation, and in particular, on problems with an algebraic flavor.

52 pages, 3 figures, to appear in Reviews of Modern Physics

References in corpus (46)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Mechanics helps in searching for a needle in a haystack
• Strengths and Weaknesses of Quantum Computing
• Simulated Quantum Computation of Molecular Energies
• Quantum Algorithms Revisited
• Quantum Computation and Decision Trees
• A Quantum Random Walk Search Algorithm
• Two-Bit Gates are Universal for Quantum Computation
• Reliable Quantum Computers
• On the Power of One Bit of Quantum Information
• Exponential algorithmic speedup by quantum walk
• Spatial search by quantum walk
• Efficient Simulation of Quantum Systems by Quantum Computers
• Bounds for the adiabatic approximation with applications to quantum computation
• Resilient Quantum Computation: Error Models and Thresholds
• An approximate Fourier transform useful in quantum factoring
• Reversing quantum dynamics with near-optimal quantum and classical fidelity
• Simulation of topological field theories by quantum computers
• Quantum Algorithm for the Collision Problem
• Approximate Quantum Fourier Transform and Decoherence
• Complexity limitations on quantum computation
• The quantum query complexity of the hidden subgroup problem is polynomial
• Spatial search and the Dirac equation
• Approximation by Quantum Circuits
• A Simple Proof that Toffoli and Hadamard are Quantum Universal
• Simulations of Many-Body Quantum Systems by a Quantum Computer
• Efficient Discrete Approximations of Quantum Gates
• The BQP-hardness of approximating the Jones Polynomial
• Quantum query complexity of some graph problems
• On Universal and Fault-Tolerant Quantum Computing
• Efficient Quantum Transforms
• Fast parallel circuits for the quantum Fourier transform
• Quantum algorithms for hidden nonlinear structures
• Trading inverses for an irrep in the Solovay-Kitaev theorem
• A 2 rebit gate universal for quantum computing
• Counting points on varieties over finite fields of small characteristic
• Efficient Quantum Algorithms for Estimating Gauss Sums
• Quantum Algorithms for Weighing Matrices and Quadratic Residues
• A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
• The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem
• Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer
• Quantum Algorithms for Matching and Network Flows
• On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group
• Optimal phase estimation in quantum networks
• Sharp Quantum vs. Classical Query Complexity Separations
• Quantum computation and the evaluation of tensor networks

Cited by in corpus (123)

• Quantum Chemistry in the Age of Quantum Computing
• Quantum algorithms: an overview
• Quantum walks: a comprehensive review
• Quantum computing with defects
• Quantum Random Number Generators
• Semiconductor Spin Qubits
• The Expressive Power of Parameterized Quantum Circuits
• Synthesis and Optimization of Reversible Circuits - A Survey
• Stabilizer Rényi entropy
• Hybrid Quantum-Classical Approach to Quantum Optimal Control
• Mitigation of readout noise in near-term quantum devices by classical post-processing based on detector tomography
• Coherence depletion in the Grover quantum search algorithm
• Robust encoding of a qubit in a molecule
• Quantum Algorithm Implementations for Beginners
• Machine learning method for state preparation and gate synthesis on photonic quantum computers
• Experimental Quantum Fast Hitting on Hexagonal Graphs
• Efficiently computable bounds for magic state distillation
• Theory for Equivariant Quantum Neural Networks
• Recent advances for quantum classifiers
• Quantum algorithm for non-homogeneous linear partial differential equations
• Open Quantum Walks on Graphs
• A quantum algorithm to solve nonlinear differential equations
• Generation of stable entanglement between two cavity mirrors by squeezed-reservoir engineering
• Primitive Quantum Gates for an SU(2) Discrete Subgroup: BT
• Search for supersymmetry in pp collisions at sqrt(s) = 7 TeV in events with a single lepton, jets, and missing transverse momentum
• Primitive Quantum Gates for Dihedral Gauge Theories
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory
• Control by quantum dynamics on graphs
• Dissipative preparation of large W states in Optical Cavities
• Validating Quantum-Classical Programming Models with Tensor Network Simulations
• Machine learning \& artificial intelligence in the quantum domain
• Self-calibrating Quantum State Tomography
• Neural-network states for the classical simulation of quantum computing
• Provably Trainable Rotationally Equivariant Quantum Machine Learning
• Mean Field Analysis of Quantum Annealing Correction
• Quantum Computing for Fusion Energy Science Applications
• Pretty good state transfer of entangled states through quantum spin chains
• Models of quantum computation and quantum programming languages
• Quantum gates and architecture for the quantum simulation of the Fermi-Hubbard model
• Experimental Realization of a One-way Quantum Computer Algorithm Solving Simon's Problem
• A quantum-walk-inspired adiabatic algorithm for graph isomorphism
• Quantum computation of discrete logarithms in semigroups
• A brief introduction to quantum algorithms
• Qunity: A Unified Language for Quantum and Classical Computing (Extended Version)
• Six-electron semiconductor double quantum dot qubits
• Analyzing the impact of time-correlated noise on zero-noise extrapolation
• Quantum algorithm for obtaining the energy spectrum of a physical system
• A Quantum Model for Autonomous Learning Automata
• Primitive Quantum Gates for an SU(3) Discrete Subgroup: $\Sigma (36\times 3)$
• Factorization of numbers with Gauss sums: I. Mathematical background
• Quantum state transfer via Bloch oscillations
• On the role of dealing with quantum coherence in amplitude amplification
• Bloch-Landau-Zener dynamics induced by a synthetic field in a photonic quantum walk
• Quantum Undergraduate Education and Scientific Training
• Universal quantum gates between nitrogen-vacancy centers in a levitated nanodiamond
• Quantum algorithm for total least squares data fitting
• Enhanced entanglement and controlling quantum steering in a Laguerre-Gaussian cavity optomechanical system with two rotating mirrors
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• Quantum algorithms for scientific computing
• Hidden Translation and Translating Coset in Quantum Computing
• Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search
• Fourier Transform of the Orbital Angular Momentum of a Single Photon
• Decoherence enhances performance of quantum walks applied to graph isomorphism testing
• Dissipative preparation of generalised Bell states
• Expressivity of Variational Quantum Machine Learning on the Boolean Cube
• Universal quantum computing with thermal state bosonic systems
• Optimizing Quantum Adiabatic Algorithm
• Quantum-walk search in motion
• Quantum Advantages in (n,d)->1 Random Access Codes
• Limitations of Classically-Simulable Measurements for Quantum State Discrimination
• Abstract structure of unitary oracles for quantum algorithms
• Easy and hard functions for the Boolean hidden shift problem
• Symmetry and localization of quantum walk induced by extra link in cycles
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations
• Quantum search degeneration under amplitude noise in queries to the oracle
• Quantum Hypothesis Testing with Group Structure
• Multiple Network Alignment on Quantum Computers
• The computational power of normalizer circuits over black-box groups
• Characterizations of symmetrically partial Boolean functions with exact quantum query complexity
• Quantum Algorithm For Estimating Eigenvalue
• Observability of fidelity decay at the Lyapunov rate in few-qubit quantum simulations
• Quantum mutual information and quantumness vectors for multi-qubit systems
• Purification-based metric to measure the distance between quantum states and processes
• tqix: A toolbox for Quantum in X: Quantum measurement, quantum tomography, quantum metrology, and others
• ChemiQ: A Chemistry Simulator for Quantum Computer
• Quantum algorithms for problems in number theory, algebraic geometry, and group theory
• Modular quantum signal processing in many variables
• Normalizer Circuits and Quantum Computation
• Resource optimization for fault-tolerant quantum computing
• Deterministic Algorithms for the Hidden Subgroup Problem
• Benchmarks for quantum computers from Shor's algorithm
• Solution to the Hidden Subgroup Problem for a Class of Noncommutative Groups
• Einstein-Podolsky-Rosen steering paradox "2=1'' for $N$ qubits
• Momentum space magic for the transverse field quantum Ising model
• Unification of Finite Symmetries in Simulation of Many-body Systems on Quantum Computers
• Abelian Hypergroups and Quantum Computation
• A quantum algorithm for solving some discrete mathematical problems by probing their energy spectra
• Individual attacks with generalized discrimination and inadequacy of some information measures
• The Abstract Structure of Quantum Algorithms
• Classical simulations of Abelian-group normalizer circuits with intermediate measurements
• Analytical solutions for quantum walks on 1D chain with different shift operators
• Bosonic quantum Fourier codes
• Quantum Arnoldi and conjugate gradient iteration algorithm
• Physics and computer science: quantum computation and other approaches
• Exact solutions and symmetry analysis for the limiting probability distribution of quantum walks
• Decoder for Nonbinary CWS Quantum Codes
• Classical Simulation of Quantum Adiabatic Algorithms using Mathematica on GPUs
• Randomness-free Detection of Non-projective Measurements: Qubits & beyond
• On the distinguishability of geometrically uniform quantum states
• Quantum Learning Algorithms and Post-Quantum Cryptography
• Multi-step quantum algorithm for solving the 3-bit exact cover problem
• The abelian state hidden subgroup problem: Learning stabilizer groups and beyond
• A Quantum Approach to the Unique Sink Orientation Problem
• Non-normality and dissipation in Markovian quantum dynamics: Implications for quantum simulation
• General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography
• Quantum speedup to some types of polynomial equations
• Generalization of Quantum Fourier Transformation
• An Efficient Deterministic Quantum Algorithm for the Integer Square-free Decomposition Problem
• Toward an Optimal Quantum Algorithm for Polynomial Factorization over Finite Fields
• A reduction from LWE problem to dihedral coset problem
• Phase Space Entanglement Spectrum
• On zeros of exponential polynomials and quantum algorithms
• Non-Pauli Observables for CWS Codes