Quantum algorithms for algebraic problems
From MaRDI portal
Publication:3077033
DOI10.1103/REVMODPHYS.82.1zbMATH Open1205.81057arXiv0812.0380OpenAlexW1972883454WikidataQ27350179 ScholiaQ27350179MaRDI QIDQ3077033FDOQ3077033
Authors: Andrew M. Childs, Wim van Dam 
Publication date: 21 February 2011
Published in: Reviews of Modern Physics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0812.0380
Recommendations
Quantum computation (81P68) Software, source code, etc. for problems pertaining to quantum theory (81-04)
Cites Work
- Title not available (Why is that?)
- A hierarchy of polynomial time lattice basis reduction algorithms
- A polynomial invariant for knots via von Neumann algebras
- Quantum field theory and the Jones polynomial
- Simulation of topological field theories by quantum computers
- Universal Quantum Simulators
- A method for obtaining digital signatures and public-key cryptosystems
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Simulating quantum systems on a quantum computer
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Computability
- Title not available (Why is that?)
- State models and the Jones polynomial
- Factoring polynomials with rational coefficients
- A modular functor which is universal for quantum computation
- Statistical decision theory for quantum systems
- Quantum complexity of testing group commutativity
- A new universal and fault-tolerant quantum basis
- Quantum search of spatial regions
- Title not available (Why is that?)
- Quantum computational networks
- Integer Programming with a Fixed Number of Variables
- Spatial search and the Dirac equation
- Bounds for the adiabatic approximation with applications to quantum computation
- New directions in cryptography
- Optimum testing of multiple hypotheses in quantum detection theory
- Quantum algorithms revisited
- Reliable quantum computers
- Quantum computations: algorithms and error correction
- Title not available (Why is that?)
- On the Power of Quantum Computation
- Quantum Complexity Theory
- Strengths and Weaknesses of Quantum Computing
- Title not available (Why is that?)
- On the computational complexity of the Jones and Tutte polynomials
- Topological quantum computation
- Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
- Quantum Algorithms for the Triangle Problem
- Quantum Walk Algorithm for Element Distinctness
- A polynomial quantum algorithm for approximating the Jones polynomial
- Quantum simulations of classical random walks and undirected graph connectivity
- Probabilistic algorithm for testing primality
- PRIMES is in P
- Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
- Rapid solution of problems by quantum computation
- Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
- The query complexity of order-finding
- Group-theoretic algorithms and graph isomorphism
- Reversing quantum dynamics with near-optimal quantum and classical fidelity
- Algebraic aspects of cryptography. With an appendix on hyperelliptic curves by Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato
- Title not available (Why is that?)
- Fast Monte Carlo algorithms for permutation groups
- Title not available (Why is that?)
- Fault-Tolerant Quantum Computation with Constant Error Rate
- Quantum Computation and Lattice Problems
- A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- The Symmetric Group Defies Strong Fourier Sampling
- Title not available (Why is that?)
- A ‘Pretty Good’ Measurement for Distinguishing Quantum States
- Quantum algorithms for weighing matrices and quadratic residues
- Noise-tolerant learning, the parity problem, and the statistical query model
- Quantum lower bounds by polynomials
- Quantum Query Complexity of Some Graph Problems
- EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS
- Quantum mechanical algorithms for the nonabelian hidden subgroup problem
- Counting points on curves and Abelian varieties over finite fields
- Counting curves and their projections
- Sharp quantum versus classical query complexity separations
- Quantum Algorithms for Some Hidden Shift Problems
- The Hidden Subgroup Problem and Quantum Computation Using Group Representations
- New lattice-based cryptographic constructions
- Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
- On quantum algorithms for noncommutative hidden subgroups
- The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts
- Random measurement bases, quantum state distinction and applications to the hidden subgroup problem
- The shortest vector in a lattice is hard to approximate to within some constant
- Optimal phase estimation in quantum networks
- The quantum query complexity of the hidden subgroup problem is polynomial
- Efficient discrete approximations of quantum gates
- Efficient Computation of the Fourier Transform on Finite Groups
- Fast generalized Fourier transforms
- On the computational complexity of the general discrete Fourier transform
- Title not available (Why is that?)
- Quantum computation of zeta functions of curves
- EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
- Approximate Counting and Quantum Computation
- Fast Fourier analysis for abelian group extensions
- The Relationship Between Breaking the Diffie--Hellman Protocol and Computing Discrete Logarithms
- Hardness of approximating the shortest vector problem in lattices
- Fast quantum algorithms for computing the unit group and class group of a number field
- The quantum query complexity of the abelian hidden subgroup problem
- Is code equivalence easy to decide?
- Quantum computation in algebraic number theory: Hallgren's efficient quantum algorithm for solving Pell's equation.
- Classical and quantum function reconstruction via character evaluation
- Title not available (Why is that?)
Cited In (58)
- Effective implementation of nonadiabatic geometric quantum gates of cat-state qubits using an auxiliary qutrit
- Quantum algorithm for total least squares data fitting
- Quantum computing: survey and analysis
- Title not available (Why is that?)
- Finding shortest lattice vectors faster using quantum search
- Quantum circuits for \(\mathbb F_{2^n}\)-multiplication with subquadratic gate count
- Leveraging the hardness of dihedral coset problem for quantum cryptography
- An encryption protocol for NEQR images based on one-particle quantum walks on a circle
- On the role of dealing with quantum coherence in amplitude amplification
- A novel quantum representation for log-polar images
- Quantum search degeneration under amplitude noise in queries to the oracle
- Individual attacks with generalized discrimination and inadequacy of some information measures
- Quantum algorithm for estimating largest eigenvalues
- Quantum algorithms for a set of group theoretic problems
- Quantum computation in algebraic number theory: Hallgren's efficient quantum algorithm for solving Pell's equation.
- Computing primitive idempotents in finite commutative rings and applications
- An Arbitrated Quantum Signature Scheme without Entanglement *
- Quantum computation: algorithms and applications
- Quantum mechanical algorithm for solving quadratic residue equation
- Quantum algorithms for typical hard problems: a perspective of cryptanalysis
- Quantum speedup and categorical distributivity
- Quantum Implementation of Numerical Methods for Convection-Diffusion Equations: Toward Computational Fluid Dynamics
- Factorization of numbers with Gauss sums. I: Mathematical background
- Pretty good state transfer of entangled states through quantum spin chains
- Models of quantum computation and quantum programming languages
- Efficient algebraic representation of quantum circuits
- Quantum computers: the fundamentals and algorithms (a brief review)
- Analytical solutions for quantum walks on 1D chain with different shift operators
- Quantum walks: a comprehensive review
- Quantum mutual information and quantumness vectors for multiqubit systems
- \texttt{tqix}: a toolbox for quantum in \texttt{x}. \texttt{x}: quantum measurement, quantum tomography, quantum metrology, and others
- Quantum algorithm for solving hyperelliptic curve discrete logarithm problem
- Reduction of the semigroup-action problem on a module to the hidden-subgroup problem
- Algebraic Methods in Quantum Informatics
- Phase space entanglement spectrum
- Multiple network alignment on quantum computers
- General linear group action on tensors: a candidate for post-quantum cryptography
- Efficient quantum algorithm for the parity problem of a certain function
- Non-Pauli observables for CWS codes
- Some open problems related to quantum computing
- Physical quantum algorithms
- SPDH-Sign: Towards Efficient, Post-quantum Group-Based Signatures
- Progress in quantum algorithms
- Vibration analysis of cyclic symmetrical systems by quantum algorithms
- Using small-scale quantum devices to solve algebraic equations
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Exact solutions and symmetry analysis for the limiting probability distribution of quantum walks
- Single channel quantum color image encryption algorithm based on HSI model and quantum Fourier transform
- On quantum algorithm for exptime problem
- Quantum circuits for hyperelliptic curve discrete logarithms over the mersenne prime fields
- Quantum Algorithms for Some Hidden Shift Problems
- Post-quantum \(\kappa\)-to-1 trapdoor claw-free functions from extrapolated dihedral cosets
- Quantum Algorithms
- SCALLOP: scaling the CSI-FiSh
- Optimal cloning with respect to the relative error
- Why haven't more quantum algorithms been found?
- On the complexity of the hidden subgroup problem
- Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem
This page was built for publication: Quantum algorithms for algebraic problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3077033)
