Approximate Quantum Fourier Transform with T gates
arXiv:1803.04933 · doi:10.1038/s41534-020-0257-5
Abstract
The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer facilitates the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, solving systems of linear equations, and phase estimation, to name a few. The standard fault-tolerant implementation of an -qubit unitary QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+T gates, incurring the T-count complexity of . In this paper, we show how to obtain approximate QFT with the T-count of . Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.
arXiv comment7 pages, improved gate counts
References in corpus (22)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum algorithm for solving linear systems of equations
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
- Quantum computers can search rapidly by using almost any transformation
- A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
- Semiclassical Fourier Transform for Quantum Computation
- Simulating chemistry using quantum computers
- Halving the cost of quantum addition
- Automated optimization of large quantum circuits with continuous parameters
- Novel constructions for the fault-tolerant Toffoli gate
- Addition on a Quantum Computer
- Approximate Quantum Fourier Transform and Decoherence
- Quantum arithmetic with the Quantum Fourier Transform
- Efficient synthesis of universal Repeat-Until-Success circuits
- Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures
- Quantum Algorithm for Molecular Properties and Geometry Optimization
- Scalability of Shor's algorithm with a limited set of rotation gates
- Use of global interactions in efficient quantum circuit constructions
- General-Purpose Parallel Simulator for Quantum Computing
- Approximating Fractional Time Quantum Evolution
- Scaling laws for Shor's algorithm with a banded quantum Fourier transform
Cited by in corpus (31)
- Generalization in quantum machine learning from few training data
- Grover Adaptive Search for Constrained Polynomial Binary Optimization
- Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
- Constrained Optimization via Quantum Zeno Dynamics
- Low cost quantum circuits for classically intractable instances of the Hamiltonian dynamics simulation problem
- The Efficient Preparation of Normal Distributions in Quantum Registers
- Shorter quantum circuits via single-qubit gate approximation
- Universal quantum multi-qubit entangling gates with auxiliary spaces
- Noisy intermediate-scale quantum simulation of the one-dimensional wave equation
- Resource-Optimized Fermionic Local-Hamiltonian Simulation on Quantum Computer for Quantum Chemistry
- Polylogarithmic-depth controlled-NOT gates without ancilla qubits
- On efficient quantum block encoding of pseudo-differential operators
- Large-scale quantum hybrid solution for linear systems of equations
- A quantum algorithm for the direct estimation of the steady state of open quantum systems
- Power-optimal, stabilized entangling gate between trapped-ion qubits
- The Present and Future of Discrete Logarithm Problems on Noisy Quantum Computers
- Single-step high-fidelity three-qubit gates by anisotropic chiral interactions
- Quantum Multiplication Algorithm Based on the Convolution Theorem
- Quantum Fully Homomorphic Encryption by Integrating Pauli One-time Pad with Quaternions
- Roadmap for quantum simulation of the fractional quantum Hall effect
- Implementation of Quantum Fourier Transform and Quantum Hashing for a Quantum Device with Arbitrary Qubits Connection Graphs
- Quantum Circuit Distillation and Compression
- Susceptibility of Trapped-Ion Qubits to Low-Dose Radiation Sources
- Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation
- Invested and Potential Magic Resources in Measurement-Based Quantum Computation
- Q-gen: A Parameterized Quantum Circuit Generator
- Quantum Simulation of QED in Coulomb Gauge
- Quadratic speed-ups in quantum kernelized binary classification
- Tradeoff between noise and banding in a quantum adder with qudits
- Quantum Simulation of Nuclear Dynamics in First Quantization
- Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits