FABLE: Fast Approximate Quantum Circuits for Block-Encodings

Abstract

Block-encodings of matrices have become an essential element of quantum algorithms derived from the quantum singular value transformation. This includes a variety of algorithms ranging from the quantum linear systems problem to quantum walk, Hamiltonian simulation, and quantum machine learning. Many of these algorithms achieve optimal complexity in terms of black box matrix oracle queries, but so far the problem of computing quantum circuit implementations for block-encodings of matrices has been under-appreciated. In this paper we propose FABLE, a method to generate approximate quantum circuits for block-encodings of matrices in a fast manner. FABLE circuits have a simple structure and are directly formulated in terms of one- and two-qubit gates. For small and structured matrices they are feasible in the NISQ era, and the circuit parameters can be easily generated for problems up to fifteen qubits. Furthermore, we show that FABLE circuits can be compressed and sparsified. We provide a compression theorem that relates the compression threshold to the error on the block-encoding. We benchmark our method for Heisenberg and Hubbard Hamiltonians, and Laplacian operators to illustrate that they can be implemented with a reduced gate complexity without approximation error.

References in corpus (15)

• Elementary gates for quantum computation
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum computers can search rapidly by using almost any transformation
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Circuits for General Multiqubit Gates
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A Grand Unification of Quantum Algorithms
• Digitization of Scalar Fields for Quantum Computing
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Quantum pixel representations and compression for $N$-dimensional images
• Efficient quantum circuits for Szegedy quantum walks
• Lecture Notes on Quantum Algorithms for Scientific Computation
• Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

Cited by in corpus (15)

• Exact and efficient Lanczos method on a quantum computer
• Block-encoding structured matrices for data input in quantum computing
• Realization of quantum signal processing on a noisy quantum computer
• Adaptive variational simulation for open quantum systems
• On efficient quantum block encoding of pseudo-differential operators
• Block encoding bosons by signal processing
• An Early Investigation of the HHL Quantum Linear Solver for Scientific Applications
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
• Ladder Operator Block-Encoding
• Quantum Iterative Methods for Solving Differential Equations with Application to Computational Fluid Dynamics
• Short-time quantum Fourier transform processing
• A quantum algorithm for linear autonomous differential equations via Padé approximation
• On Modifying the Variational Quantum Singular Value Decomposition Algorithm
• Efficient Simulation of Open Quantum Systems on NISQ Trapped-Ion Hardware
• Co-Designing Spectral Transformation Oracles with Hybrid Oscillator-Qubit Quantum Processors: From Algorithms to Compilation