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).

28 pages, 9 figures, v3 accepted by Quantum

References in corpus (8)

• Quantum algorithm for solving linear systems of equations
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Creating superpositions that correspond to efficiently integrable probability distributions
• Quantum algorithm and circuit design solving the Poisson equation
• Linear-depth quantum circuits for multiqubit controlled gates
• FABLE: Fast Approximate Quantum Circuits for Block-Encodings
• Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices
• 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