Trading T gates for dirty qubits in state preparation and unitary synthesis

Abstract

Efficient synthesis of arbitrary quantum states and unitaries from a universal fault-tolerant gate-set e.g. Clifford+T is a key subroutine in quantum computation. As large quantum algorithms feature many qubits that encode coherent quantum information but remain idle for parts of the computation, these should be used if it minimizes overall gate counts, especially that of the expensive T-gates. We present a quantum algorithm for preparing any dimension-$N$ pure quantum state specified by a list of $N$ classical numbers, that realizes a trade-off between space and T-gates. Our scheme uses $\mathcal{O}(\log (N/\epsilon ))$ clean qubits and a tunable number of $\sim (\lambda \log (\frac{\log N}{\epsilon }))$ dirty qubits, to reduce the T-gate cost to $\mathcal{O}(\frac{N}{\lambda }+\lambda \log \frac{N}{\epsilon }\log \frac{\log N}{\epsilon })$. This trade-off is optimal up to logarithmic factors, proven through an unconditional gate counting lower bound, and is, in the best case, a quadratic improvement in T-count over prior ancillary-free approaches. We prove similar statements for unitary synthesis by reduction to state preparation. Underlying our constructions is a T-efficient circuit implementation of a quantum oracle for arbitrary classical data.

19 pages, 2 figures. Version published in Quantum

References in corpus (26)

• Elementary gates for quantum computation
• Quantum algorithm for solving linear systems of equations
• Quantum principal component analysis
• Hamiltonian Simulation by Qubitization
• Quantum algorithms for quantum chemistry and quantum materials science
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Synthesis of Quantum Logic Circuits
• Toward the first quantum simulation with quantum speedup
• Quantum Data Fitting
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Halving the cost of quantum addition
• Quantum computing enhanced computational catalysis
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits
• Lower bounds on the non-Clifford resources for quantum computations
• Efficient Discrete Approximations of Quantum Gates
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Fault tolerant resource estimation of quantum random-access memories
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Resilience of quantum random access memory to generic noise
• Algorithmic complexity and entanglement of quantum states
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications

Cited by in corpus (39)

• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Fault-Tolerant Quantum Simulations of Chemistry in First Quantization
• Quantum Algorithms for Jet Clustering
• Quantum Computing: An Overview Across the System Stack
• Initial state preparation for quantum chemistry on quantum computers
• No-go theorems for quantum resource purification II: new approach and channel theory
• Rapid initial state preparation for the quantum simulation of strongly correlated molecules
• Systems Architecture for Quantum Random Access Memory
• Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries
• Quantum algorithms for scientific computing
• Faster quantum chemistry simulations on a quantum computer with improved tensor factorization and active volume compilation
• Exponentially faster implementations of Select(H) for fermionic Hamiltonians
• Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
• Quantum state preparation for multivariate functions
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis
• Fast quantum simulation of electronic structure by spectrum amplification
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• QRAM: A Survey and Critique
• Hardware-Efficient Quantum Random Access Memory Design with a Native Gate Set on Superconducting Platforms
• Quantum Computation of Electronic Structure with Projector Augmented-Wave Method and Plane Wave Basis Set
• Resource Analysis of Low-Overhead Transversal Architectures for Reconfigurable Atom Arrays
• Windowed quantum arithmetic
• Reducing Circuit Depth in Quantum State Preparation for Quantum Simulation Using Measurements and Feedforward
• Multireference error mitigation for quantum computation of chemistry
• Simulating optically-active spin defects with a quantum computer
• A quantum random access memory (QRAM) using a polynomial encoding of binary strings
• Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
• Quantum state preparation via piecewise QSVT
• Discontinuous Galerkin discretization for quantum simulation of chemistry
• Fat-Tree QRAM: A High-Bandwidth Shared Quantum Random Access Memory for Parallel Queries
• Halving the cost of quantum multiplexed rotations
• Unified Architecture for Quantum Lookup Tables
• Quantum Circuit Design for Decoded Quantum Interferometry
• Synthesis of Single Qutrit Circuits from Clifford+R
• Benchmarking Quantum Simulation of Chemical Hamiltonians using the Sorted-List Encoding
• Robust and optimal loading of general classical data into quantum computers
• Quantum phase estimation with optimal confidence interval using three control qubits
• Formal Verification of Quantum Ancilla Safety
• A quantum eigenvalue solver based on tensor networks