Introduction to Quantum Algorithms

Abstract

These notes discuss the quantum algorithms we know of that can solve problems significantly faster than the corresponding classical algorithms. So far, we have only discovered a few techniques which can produce speed up versus classical algorithms. It is not clear yet whether the reason for this is that we do not have enough intuition to discover more techniques, or that there are only a few problems for which quantum computers can significantly speed up the solution.

17 pages, latex, notes for talk given for the short course at the January 2000 American Math Society meeting, minor errors corrected in version 2

References in corpus (12)

• Fault-tolerant quantum computation by anyons
• Quantum Mechanics helps in searching for a needle in a haystack
• Elementary gates for quantum computation
• Good Quantum Error-Correcting Codes Exist
• The Physical Implementation of Quantum Computation
• Strengths and Weaknesses of Quantum Computing
• A Class of Quantum Error-Correcting Codes Saturating the Quantum Hamming Bound
• Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
• Efficient Simulation of Quantum Systems by Quantum Computers
• An Introduction to Quantum Error Correction
• Fast versions of Shor's quantum factoring algorithm
• Limitations of Noisy Reversible Computation

Cited by in corpus (26)

• Information and Computation: Classical and Quantum Aspects
• The Hidden Subgroup Problem - Review and Open Problems
• Quantum advantage and noise reduction in distributed quantum computing
• Decoherence in Discrete Quantum Walks
• Combinatorial Optimization on Gate Model Quantum Computers: A Survey
• The Early Universe as a Quantum Growing Network
• Theory of quasi-exact fault-tolerant quantum computing and valence-bond-solid codes
• Quantum information processing: The case of vanishing interaction energy
• Simulation of Quantum Algorithms with a Symbolic Programming Language
• Countinuous Quantum Hidden Subgroup Algorithms
• Application of a Quantum Search Algorithm to High- Energy Physics Data at the Large Hadron Collider
• From Monte Carlo to Quantum Computation
• Quantum Hidden Subgroup Algorithms: The Devil Is in the Details
• Quantum Approximation I. Embeddings of Finite Dimensional L_p Spaces
• An integral version of Shor's factoring algorithm
• A Review of Procedure to Evolve Quantum Procedures
• Quantum Integration in Sobolev Classes
• The zero energy quantum informtaiton processing
• Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers
• Symbolic Arithmetic and Integer Factorization
• Linear algebra and quantum algorithm
• Quantum Algorithms in Cybernetics
• The Quantum Query Complexity of Elliptic PDE
• On a Problem in Quantum Summation
• Quantum Summation with an Application to Integration
• Zeno machines and hypercomputation