Block-encoding structured matrices for data input in quantum computing

Abstract

The cost of data input can dominate the run-time of quantum algorithms. Here, we consider data input of arithmetically structured matrices via block encoding circuits, the input model for the quantum singular value transform and related algorithms. We demonstrate how to construct block encoding circuits based on an arithmetic description of the sparsity and pattern of repeated values of a matrix. We present schemes yielding different subnormalisations of the block encoding; a comparison shows that the best choice depends on the specific matrix. The resulting circuits reduce flag qubit number according to sparsity, and data loading cost according to repeated values, leading to an exponential improvement for certain matrices. We give examples of applying our block encoding schemes to a few families of matrices, including Toeplitz and tridiagonal matrices.

References in corpus (30)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Surface codes: Towards practical large-scale quantum computation
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Strong quantum computational advantage using a superconducting quantum processor
• Quantum random access memory
• Hamiltonian Simulation by Qubitization
• Synthesis of Quantum Logic Circuits
• Roads towards fault-tolerant universal quantum computation
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Circuits for General Multiqubit Gates
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Halving the cost of quantum addition
• Quantum computing enhanced computational catalysis
• Is there evidence for exponential quantum advantage in quantum chemistry?
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• A perspective on the current state-of-the-art of quantum computing for drug discovery applications
• Quantum arithmetic with the Quantum Fourier Transform
• Quantum computation with realistic magic state factories
• Efficient phase-factor evaluation in quantum signal processing
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Resilience of quantum random access memory to generic noise
• Realization of quantum signal processing on a noisy quantum computer
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• FABLE: Fast Approximate Quantum Circuits for Block-Encodings
• Quantum Computation for Periodic Solids in Second Quantization
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• Efficient quantum circuits for Toeplitz and Hankel matrices

Cited by in corpus (24)

• Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition
• Circuit complexity of quantum access models for encoding classical data
• Quantum algorithms for scientific computing
• Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems
• Quantum Computing Simulation of a Mixed Spin-Boson Hamiltonian and Its Performance for a Cavity Quantum Electrodynamics Problem
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Time-dependent Hamiltonian Simulation via Magnus Expansion: Algorithm and Superconvergence
• The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts
• Randomized semi-quantum matrix processing
• Thermalization in open many-body systems and KMS detailed balance
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
• Encoding of linear kinetic plasma problems in quantum circuits via data compression
• Quantum state preparation via piecewise QSVT
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics
• Quantum algorithm for solving generalized eigenvalue problems with application to the Schrödinger equation
• Measurement Schemes for Quantum Linear Equation Solvers
• On Modifying the Variational Quantum Singular Value Decomposition Algorithm
• Quantum Simulation-Based Optimization for Cooling System Design
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs
• Vortex Detection from Quantum Data
• Block encoding the 3D heterogeneous Poisson equation with application to fracture flow
• Block Encoding of Sparse Matrices via Coherent Permutation
• Preconditioned Block Encodings for Quantum Linear Systems