On efficient quantum block encoding of pseudo-differential operators

Abstract

Block encoding lies at the core of many existing quantum algorithms. Meanwhile, efficient and explicit block encodings of dense operators are commonly acknowledged as a challenging problem. This paper presents a comprehensive study of the block encoding of a rich family of dense operators: the pseudo-differential operators (PDOs). First, a block encoding scheme for generic PDOs is developed. Then we propose a more efficient scheme for PDOs with a separable structure. Finally, we demonstrate an explicit and efficient block encoding algorithm for PDOs with a dimension-wise fully separable structure. Complexity analysis is provided for all block encoding algorithms presented. The application of theoretical results is illustrated with worked examples, including the representation of variable coefficient elliptic operators and the computation of the inverse of elliptic operators without invoking quantum linear system algorithms (QLSAs).

arXiv comment28 pages, 9 figures, v3 accepted by Quantum

References in corpus (25)

• Quantum algorithm for solving linear systems of equations
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• An approximate Fourier transform useful in quantum factoring
• Creating superpositions that correspond to efficiently integrable probability distributions
• Quantum algorithms and the finite element method
• Quantum algorithm and circuit design solving the Poisson equation
• High-precision quantum algorithms for partial differential equations
• Quantum Algorithm for Simulating the Wave Equation
• Efficient phase-factor evaluation in quantum signal processing
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Linear-depth quantum circuits for multiqubit controlled gates
• Finding Angles for Quantum Signal Processing with Machine Precision
• FABLE: Fast Approximate Quantum Circuits for Block-Encodings
• Stable factorization for phase factors of quantum signal processing
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices
• Efficient quantum circuits for Toeplitz and Hankel matrices
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations
• Decomposition of Multi-controlled Special Unitary Single-Qubit Gates

Cited by in corpus (8)

• Efficient quantum amplitude encoding of polynomial functions
• Explicit block encodings of boundary value problems for many-body elliptic operators
• 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
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
• Efficient explicit circuit for quantum state preparation of piecewise continuous functions
• Quantum Signal Processing and Quantum Singular Value Transformation on $U(N)$
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs