Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates

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 $n$-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 $O(n{\log }^2(n))$. In this paper, we show how to obtain approximate QFT with the T-count of $O(n\log (n))$. 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.

7 pages, improved gate counts

References in corpus (9)

• Quantum algorithm for solving linear systems of equations
• 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
• 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
• Scalability of Shor's algorithm with a limited set of rotation gates
• Approximating Fractional Time Quantum Evolution

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