Quantum algorithms for algebraic problems
From MaRDI portal
Publication:3077033
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5899272 (Why is no real title available?)
- scientific article; zbMATH DE number 3164227 (Why is no real title available?)
- scientific article; zbMATH DE number 4077312 (Why is no real title available?)
- scientific article; zbMATH DE number 44579 (Why is no real title available?)
- scientific article; zbMATH DE number 1318047 (Why is no real title available?)
- scientific article; zbMATH DE number 475434 (Why is no real title available?)
- scientific article; zbMATH DE number 1131801 (Why is no real title available?)
- scientific article; zbMATH DE number 1978496 (Why is no real title available?)
- scientific article; zbMATH DE number 1776257 (Why is no real title available?)
- scientific article; zbMATH DE number 3099224 (Why is no real title available?)
- A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- A hierarchy of polynomial time lattice basis reduction algorithms
- A method for obtaining digital signatures and public-key cryptosystems
- A modular functor which is universal for quantum computation
- A new universal and fault-tolerant quantum basis
- A polynomial invariant for knots via von Neumann algebras
- A polynomial quantum algorithm for approximating the Jones polynomial
- A ‘Pretty Good’ Measurement for Distinguishing Quantum States
- Algebraic aspects of cryptography. With an appendix on hyperelliptic curves by Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato
- Approximate Counting and Quantum Computation
- Bounds for the adiabatic approximation with applications to quantum computation
- Classical and quantum function reconstruction via character evaluation
- Counting curves and their projections
- Counting points on curves and Abelian varieties over finite fields
- Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
- EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
- EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS
- Efficient Computation of the Fourier Transform on Finite Groups
- Efficient discrete approximations of quantum gates
- Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
- Factoring polynomials with rational coefficients
- Fast Fourier analysis for abelian group extensions
- Fast Monte Carlo algorithms for permutation groups
- Fast generalized Fourier transforms
- Fast quantum algorithms for computing the unit group and class group of a number field
- Fault-Tolerant Quantum Computation with Constant Error Rate
- Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
- Group-theoretic algorithms and graph isomorphism
- Hardness of approximating the shortest vector problem in lattices
- Integer Programming with a Fixed Number of Variables
- Is code equivalence easy to decide?
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- New directions in cryptography
- New lattice-based cryptographic constructions
- Noise-tolerant learning, the parity problem, and the statistical query model
- On quantum algorithms for noncommutative hidden subgroups
- On the Power of Quantum Computation
- On the computational complexity of the Jones and Tutte polynomials
- On the computational complexity of the general discrete Fourier transform
- Optimal phase estimation in quantum networks
- Optimum testing of multiple hypotheses in quantum detection theory
- PRIMES is in P
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
- Probabilistic algorithm for testing primality
- Quantum Algorithms for Some Hidden Shift Problems
- Quantum Algorithms for the Triangle Problem
- Quantum Complexity Theory
- Quantum Computability
- Quantum Computation and Lattice Problems
- Quantum Query Complexity of Some Graph Problems
- Quantum Walk Algorithm for Element Distinctness
- Quantum algorithms for weighing matrices and quadratic residues
- Quantum algorithms revisited
- Quantum complexity of testing group commutativity
- Quantum computation in algebraic number theory: Hallgren's efficient quantum algorithm for solving Pell's equation.
- Quantum computation of zeta functions of curves
- Quantum computational networks
- Quantum computations: algorithms and error correction
- Quantum field theory and the Jones polynomial
- Quantum lower bounds by polynomials
- Quantum mechanical algorithms for the nonabelian hidden subgroup problem
- Quantum search of spatial regions
- Quantum simulations of classical random walks and undirected graph connectivity
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Random measurement bases, quantum state distinction and applications to the hidden subgroup problem
- Rapid solution of problems by quantum computation
- Reliable quantum computers
- Reversing quantum dynamics with near-optimal quantum and classical fidelity
- Sharp quantum versus classical query complexity separations
- Simulating quantum systems on a quantum computer
- Simulation of topological field theories by quantum computers
- Spatial search and the Dirac equation
- State models and the Jones polynomial
- Statistical decision theory for quantum systems
- Strengths and Weaknesses of Quantum Computing
- The Hidden Subgroup Problem and Quantum Computation Using Group Representations
- The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts
- The Relationship Between Breaking the Diffie--Hellman Protocol and Computing Discrete Logarithms
- The Symmetric Group Defies Strong Fourier Sampling
- The quantum query complexity of the abelian hidden subgroup problem
- The quantum query complexity of the hidden subgroup problem is polynomial
- The query complexity of order-finding
- The shortest vector in a lattice is hard to approximate to within some constant
- Topological quantum computation
- Universal Quantum Simulators
Cited in
(59)- Why haven't more quantum algorithms been found?
- Quantum algorithm for total least squares data fitting
- On the complexity of the hidden subgroup problem
- Quantum computing: survey and analysis
- Finding shortest lattice vectors faster using quantum search
- Effective implementation of nonadiabatic geometric quantum gates of cat-state qubits using an auxiliary qutrit
- scientific article; zbMATH DE number 1464668 (Why is no real title available?)
- 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 computation in algebraic number theory: Hallgren's efficient quantum algorithm for solving Pell's equation.
- Quantum algorithms for a set of group theoretic problems
- Quantum mechanical algorithm for solving quadratic residue equation
- An Arbitrated Quantum Signature Scheme without Entanglement *
- Computing primitive idempotents in finite commutative rings and applications
- Quantum algorithms for typical hard problems: a perspective of cryptanalysis
- Quantum computation: algorithms and applications
- 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
- Quantum algorithm for solving hyperelliptic curve discrete logarithm problem
- \texttt{tqix}: a toolbox for quantum in \texttt{x}. \texttt{x}: quantum measurement, quantum tomography, quantum metrology, and others
- Reduction of the semigroup-action problem on a module to the hidden-subgroup problem
- Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem
- Algebraic Methods in Quantum Informatics
- Multiple network alignment on quantum computers
- Phase space entanglement spectrum
- 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
- Physical quantum algorithms
- Some open problems related to quantum computing
- 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
- Quantum algorithms revisited
- On quantum algorithm for exptime problem
- Quantum Algorithms for Some Hidden Shift Problems
- Quantum Algorithms
- Quantum circuits for hyperelliptic curve discrete logarithms over the mersenne prime fields
- Post-quantum \(\kappa\)-to-1 trapdoor claw-free functions from extrapolated dihedral cosets
- Optimal cloning with respect to the relative error
- SCALLOP: scaling the CSI-FiSh
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)
