Quantum Algorithms and the Fourier Transform

Abstract

The quantum algorithms of Deutsch, Simon and Shor are described in a way which highlights their dependence on the Fourier transform. The general construction of the Fourier transform on an Abelian group is outlined and this provides a unified way of understanding the efficacy of these algorithms. Finally we describe an efficient quantum factoring algorithm based on a general formalism of Kitaev and contrast its structure to the ingredients of Shor's algorithm.

18 pages Latex. Submitted to Proceedings of Santa Barbara Conference on Quantum Coherence and Decoherence

Cited by in corpus (43)

• On the role of entanglement in quantum computational speed-up
• Information and Computation: Classical and Quantum Aspects
• Implementation of the Quantum Fourier Transform
• Quantum Algorithms: Entanglement Enhanced Information Processing
• The problem of equilibration and the computation of correlation functions on a quantum computer
• Quantum Computing with NMR
• Quantum Process Tomography of the Quantum Fourier Transform
• General Methods for Digital Quantum Simulation of Gauge Theories
• Optimal Control-Based Efficient Synthesis of Building Blocks of Quantum Algorithms Seen in Perspective from Network Complexity towards Time Complexity
• Yao.jl: Extensible, Efficient Framework for Quantum Algorithm Design
• Quantum factoring, discrete logarithms and the hidden subgroup problem
• Noisy intermediate-scale quantum computers
• Using Quantum Computers for Quantum Simulation
• Calculating the Thermal Rate Constant with Exponential Speed-Up on a Quantum Computer
• Quantum computing of fluid dynamics using the hydrodynamic Schrödinger equation
• Five measurement bases determine pure quantum states on any dimension
• Quantum Template Matching
• Gradient Flows for Optimisation and Quantum Control: Foundations and Applications
• Versatile microwave-driven trapped ion spin system for quantum information processing
• Quantum fast Fourier transform using multilevel atoms
• Entangled Quantum States Generated by Shor's Factoring Algorithm
• Constructive Quantum Shannon Decomposition from Cartan Involutions
• Quantum circuit for the fast Fourier transform
• Hamiltonian symmetries in auxiliary-field quantum Monte Carlo calculations for electronic structure
• Applications of Multi-Valued Quantum Algorithms
• The Significance of the $C$-Numerical Range and the Local $C$-Numerical Range in Quantum Control and Quantum Information
• Networked Quantum Services
• Efficient implementations of the Quantum Fourier Transform: an experimental perspective
• On Quantum Algorithms for Noncommutative Hidden Subgroups
• Entanglement of Periodic States, the Quantum Fourier Transform and Shor's Factoring Algorithm
• Design of quantum Fourier transforms and quantum algorithms by using circulant Hamiltonians
• Simulated Quantum Computation of Global Minima
• Query complexity of generalized Simon's problem
• Coherence Fraction in Grover Search Algorithm
• Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization
• Efficient Light Propagation Algorithm using Quantum Computers
• Deterministic Algorithms for the Hidden Subgroup Problem
• Quantum compiling with a variational instruction set for accurate and fast quantum computing
• Non-maximally entangled mixed states of X and non-X types as teleportation channels
• Simon's Period Finding on a Quantum Annealer
• Coupling modifies the quantum fluctuations of entangled oscillators
• An Approach by Representation of Algebras for Decoherence-Free Subspaces
• Entanglement groups