Quantum algorithms for algebraic problems
From MaRDI portal
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
- 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 Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- 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 Computation of the Fourier Transform on Finite Groups
- Efficient discrete approximations of quantum gates
- EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
- Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
- EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS
- Factoring polynomials with rational coefficients
- Fast Fourier analysis for abelian group extensions
- Fast generalized Fourier transforms
- Fast Monte Carlo algorithms for permutation groups
- 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
- 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?)
- 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 computational complexity of the general discrete Fourier transform
- On the computational complexity of the Jones and Tutte polynomials
- On the Power of Quantum Computation
- Optimal phase estimation in quantum networks
- Optimum testing of multiple hypotheses in quantum detection theory
- 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
- PRIMES is in P
- Probabilistic algorithm for testing primality
- Quantum Algorithms for Some Hidden Shift Problems
- Quantum Algorithms for the Triangle Problem
- Quantum algorithms for weighing matrices and quadratic residues
- Quantum algorithms revisited
- Quantum complexity of testing group commutativity
- Quantum Complexity Theory
- Quantum Computability
- Quantum Computation and Lattice Problems
- 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 Query Complexity of Some Graph Problems
- 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
- Quantum Walk Algorithm for Element Distinctness
- 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 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 Relationship Between Breaking the Diffie--Hellman Protocol and Computing Discrete Logarithms
- The shortest vector in a lattice is hard to approximate to within some constant
- The Symmetric Group Defies Strong Fourier Sampling
- Topological quantum computation
- Universal Quantum Simulators
Cited in
(66)- Quantum computation in algebraic number theory: Hallgren's efficient quantum algorithm for solving Pell's equation.
- Physical quantum algorithms
- 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
- Efficient quantum algorithm for the parity problem of a certain function
- Quantum walks: a comprehensive review
- On the role of dealing with quantum coherence in amplitude amplification
- Leveraging the hardness of dihedral coset problem for quantum cryptography
- Quantum search degeneration under amplitude noise in queries to the oracle
- An encryption protocol for NEQR images based on one-particle quantum walks on a circle
- Individual attacks with generalized discrimination and inadequacy of some information measures
- General linear group action on tensors: a candidate for post-quantum cryptography
- Models of quantum computation and quantum programming languages
- Vibration analysis of cyclic symmetrical systems by quantum algorithms
- Quantum computing: survey and analysis
- Progress in quantum algorithms
- Non-Pauli observables for CWS codes
- Quantum circuits for \(\mathbb F_{2^n}\)-multiplication with subquadratic gate count
- Quantum algorithms for typical hard problems: a perspective of cryptanalysis
- Quantum algorithm for solving hyperelliptic curve discrete logarithm problem
- Quantum mutual information and quantumness vectors for multiqubit systems
- Using small-scale quantum devices to solve algebraic equations
- Some open problems related to quantum computing
- On quantum algorithm for exptime problem
- Analytical solutions for quantum walks on 1D chain with different shift operators
- Quantum Algorithms
- Optimal cloning with respect to the relative error
- Quantum computers: the fundamentals and algorithms (a brief review)
- Pretty good state transfer of entangled states through quantum spin chains
- Efficient algebraic representation of quantum circuits
- Quantum Algorithms for Some Hidden Shift Problems
- Why haven't more quantum algorithms been found?
- Algebraic Methods in Quantum Informatics
- A novel quantum representation for log-polar images
- Quantum algorithms revisited
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- scientific article; zbMATH DE number 1464668 (Why is no real title available?)
- An Arbitrated Quantum Signature Scheme without Entanglement *
- Phase space entanglement spectrum
- Multiple network alignment on quantum computers
- Quantum speedup and categorical distributivity
- Factorization of numbers with Gauss sums. I: Mathematical background
- On the complexity of the hidden subgroup problem
- Quantum algorithms for a set of group theoretic problems
- Quantum Implementation of Numerical Methods for Convection-Diffusion Equations: Toward Computational Fluid Dynamics
- Quantum algorithm for estimating largest eigenvalues
- SCALLOP: scaling the CSI-FiSh
- Computing primitive idempotents in finite commutative rings and applications
- \texttt{tqix}: a toolbox for quantum in \texttt{x}. \texttt{x}: quantum measurement, quantum tomography, quantum metrology, and others
- Quantum circuits for hyperelliptic curve discrete logarithms over the mersenne prime fields
- Quantum computation: algorithms and applications
- SPDH-Sign: Towards Efficient, Post-quantum Group-Based Signatures
- Post-quantum \(\kappa\)-to-1 trapdoor claw-free functions from extrapolated dihedral cosets
- Effective implementation of nonadiabatic geometric quantum gates of cat-state qubits using an auxiliary qutrit
- 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
- On the distinguishability of geometrically uniform quantum states
- Faster SCALLOP from non-prime conductor suborders in medium sized quadratic fields
- Non-static axisymmetric structures embedded in an asymptotically CDM universe
- A subexponential quantum algorithm for the semidirect discrete logarithm problem
- Fixation in fluctuating populations
- Efficient post-quantum commutative group actions from orientations of large discriminant
- Quantum algorithm for total least squares data fitting
- Quantum mechanical algorithm for solving quadratic residue equation
- Finding shortest lattice vectors faster using quantum search
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)
