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 (16)

• Simulated Quantum Computation of Molecular Energies
• Exponential algorithmic speedup by quantum walk
• Spatial search by quantum walk
• Bounds for the adiabatic approximation with applications to quantum computation
• Spatial search and the Dirac equation
• A Simple Proof that Toffoli and Hadamard are Quantum Universal
• Quantum algorithms for hidden nonlinear structures
• Trading inverses for an irrep in the Solovay-Kitaev theorem
• A 2 rebit gate universal for quantum computing
• Efficient Quantum Algorithms for Estimating Gauss Sums
• Counting points on varieties over finite fields of small characteristic
• A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
• The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem
• Quantum Algorithms for Matching and Network Flows
• Optimal phase estimation in quantum networks
• Quantum computation and the evaluation of tensor networks

Cited by in corpus (122)

• 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
• Quantum gates and architecture for the quantum simulation of the Fermi-Hubbard model
• Models of quantum computation and quantum programming languages
• Pretty good state transfer of entangled states through quantum spin chains
• 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
• On the role of dealing with quantum coherence in amplitude amplification
• Quantum state transfer via Bloch oscillations
• 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
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• Quantum algorithms for scientific computing
• Enhanced entanglement and controlling quantum steering in a Laguerre-Gaussian cavity optomechanical system with two rotating mirrors
• Quantum algorithm for total least squares data fitting
• Fourier Transform of the Orbital Angular Momentum of a Single Photon
• Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search
• 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
• Easy and hard functions for the Boolean hidden shift problem
• Abstract structure of unitary oracles for quantum algorithms
• Symmetry and localization of quantum walk induced by extra link in cycles
• Limitations of Classically-Simulable Measurements for Quantum State Discrimination
• Quantum Advantages in (n,d)->1 Random Access Codes
• Quantum-walk search in motion
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations
• Quantum Hypothesis Testing with Group Structure
• Characterizations of symmetrically partial Boolean functions with exact quantum query complexity
• Multiple Network Alignment on Quantum Computers
• The computational power of normalizer circuits over black-box groups
• Quantum search degeneration under amplitude noise in queries to the oracle
• 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
• tqix: A toolbox for Quantum in X: Quantum measurement, quantum tomography, quantum metrology, and others
• ChemiQ: A Chemistry Simulator for Quantum Computer
• Purification-based metric to measure the distance between quantum states and processes
• Quantum algorithms for problems in number theory, algebraic geometry, and group theory
• Resource optimization for fault-tolerant quantum computing
• Normalizer Circuits and Quantum Computation
• Deterministic Algorithms for the Hidden Subgroup Problem
• Modular quantum signal processing in many variables
• 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
• The Abstract Structure of Quantum Algorithms
• Analytical solutions for quantum walks on 1D chain with different shift operators
• Individual attacks with generalized discrimination and inadequacy of some information measures
• Classical simulations of Abelian-group normalizer circuits with intermediate measurements
• Exact solutions and symmetry analysis for the limiting probability distribution of quantum walks
• Physics and computer science: quantum computation and other approaches
• Decoder for Nonbinary CWS Quantum Codes
• Classical Simulation of Quantum Adiabatic Algorithms using Mathematica on GPUs
• Quantum Arnoldi and conjugate gradient iteration algorithm
• Bosonic quantum Fourier codes
• Multi-step quantum algorithm for solving the 3-bit exact cover problem
• The abelian state hidden subgroup problem: Learning stabilizer groups and beyond
• 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
• A Quantum Approach to the Unique Sink Orientation Problem
• Quantum Learning Algorithms and Post-Quantum Cryptography
• Non-Pauli Observables for CWS Codes
• Phase Space Entanglement Spectrum
• Toward an Optimal Quantum Algorithm for Polynomial Factorization over Finite Fields
• A reduction from LWE problem to dihedral coset problem
• On zeros of exponential polynomials and quantum algorithms
• Randomness-free Detection of Non-projective Measurements: Qubits & beyond
• On the distinguishability of geometrically uniform quantum states