Quantum Resources Required to Block-Encode a Matrix of Classical Data

Abstract

We provide modular circuit-level implementations and resource estimates for several methods of block-encoding a dense $N\times N$ matrix of classical data to precision $\epsilon$; the minimal-depth method achieves a $T$-depth of $\mathcal{O}(\log (N/\epsilon )),$ while the minimal-count method achieves a $T$-count of $\mathcal{O}(N\log (1/\epsilon ))$. We examine resource tradeoffs between the different approaches, and we explore implementations of two separate models of quantum random access memory (QRAM). As part of this analysis, we provide a novel state preparation routine with $T$-depth $\mathcal{O}(\log (N/\epsilon ))$, improving on previous constructions with scaling $\mathcal{O}({\log }^2(N/\epsilon ))$. Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.

References in corpus (33)

• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Quantum random access memory
• Hamiltonian Simulation by Qubitization
• Surface code quantum computing by lattice surgery
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• A Grand Unification of Quantum Algorithms
• Quantum-state preparation with universal gate decompositions
• Architectures for a quantum random access memory
• Halving the cost of quantum addition
• Creating superpositions that correspond to efficiently integrable probability distributions
• Efficient decomposition of quantum gates
• Quantum circuits of T-depth one
• Novel constructions for the fault-tolerant Toffoli gate
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• The methodology of resonant equiangular composite quantum gates
• On the robustness of bucket brigade quantum RAM
• Black-box quantum state preparation without arithmetic
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Fault tolerant resource estimation of quantum random-access memories
• Lattice Surgery with a Twist: Simplifying Clifford Gates of Surface Codes
• Universal quantum computing with twist-free and temporally encoded lattice surgery
• Fault-Tolerant Postselected Quantum Computation: Schemes
• Resilience of quantum random access memory to generic noise
• A Robust Quantum Random Access Memory
• Quantum algorithms and lower bounds for convex optimization
• Parallelising the Queries in Bucket Brigade Quantum RAM
• Fast Black-Box Quantum State Preparation
• Quantum Interior Point Methods for Semidefinite Optimization
• Fast Black-Box Quantum State Preparation Based on Linear Combination of Unitaries

Cited by in corpus (15)

• Challenges and Opportunities in Quantum Optimization
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Block-encoding structured matrices for data input in quantum computing
• Efficient Hamiltonian Simulation for Solving Option Price Dynamics
• Circuit complexity of quantum access models for encoding classical data
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• QRAM: A Survey and Critique
• Randomized semi-quantum matrix processing
• Encoding of linear kinetic plasma problems in quantum circuits via data compression
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
• Phase Estimation with Compressed Controlled Time Evolution
• Preconditioned Block Encodings for Quantum Linear Systems
• Robust and optimal loading of general classical data into quantum computers