Efficient Quantum Transforms

Abstract

Quantum mechanics requires the operation of quantum computers to be unitary, and thus makes it important to have general techniques for developing fast quantum algorithms for computing unitary transforms. A quantum routine for computing a generalized Kronecker product is given. Applications include re-development of the networks for computing the Walsh-Hadamard and the quantum Fourier transform. New networks for two wavelet transforms are given. Quantum computation of Fourier transforms for non-Abelian groups is defined. A slightly relaxed definition is shown to simplify the analysis and the networks that computes the transforms. Efficient networks for computing such transforms for a class of metacyclic groups are introduced. A novel network for computing a Fourier transform for a group used in quantum error-correction is also given.

30 pages, LaTeX2e, 7 figures included

References in corpus (9)

• Elementary gates for quantum computation
• Good Quantum Error-Correcting Codes Exist
• Strengths and Weaknesses of Quantum Computing
• A Class of Quantum Error-Correcting Codes Saturating the Quantum Hamming Bound
• Quantum Error Correction and Orthogonal Geometry
• Quantum Networks for Elementary Arithmetic Operations
• Simple Quantum Error Correcting Codes
• Quantum measurements and the Abelian Stabilizer Problem
• Semiclassical Fourier Transform for Quantum Computation

Cited by in corpus (25)

• Quantum algorithms for algebraic problems
• Asymptotically Optimal Quantum Circuits for d-level Systems
• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• The Hidden Subgroup Problem - Review and Open Problems
• Quantum interference as a resource for quantum speedup
• The Symmetric Group Defies Strong Fourier Sampling: Part II
• Optimal measurements for the dihedral hidden subgroup problem
• The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling
• Quantum advantage for differential equation analysis
• Efficient Quantum Algorithm for All Quantum Wavelet Transforms
• The Optimal Single Copy Measurement for the Hidden Subgroup Problem
• Easy and hard functions for the Boolean hidden shift problem
• Local Search Methods for Quantum Computers
• On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems
• Single-Step Quantum Search Using Problem Structure
• Explicit Multiregister Measurements for Hidden Subgroup Problems
• Tight Results on Multiregister Fourier Sampling: Quantum Measurements for Graph Isomorphism Require Entanglement
• How a Clebsch-Gordan Transform Helps to Solve the Heisenberg Hidden Subgroup Problem
• The Study of Entangled States in Quantum Computation and Quantum Information Science
• Simon's Algorithm, Clebsch-Gordan Sieves, and Hidden Symmetries of Multiple Squares
• Quantum Algorithms Using the Curvelet Transform
• Adaptive Quantum Image Encryption Method Based on Wavelet Transform
• Generalization of Quantum Fourier Transformation
• Shor's Algorithm from the Mindset of Quantum Oracles
• Quantum Measurements for Graph Isomorphism Require Entanglement: Tight Results on Multiregister Fourier Sampling (Withdrawn)