Block Encoding of Sparse Matrices via Coherent Permutation

Abstract

Block encoding of sparse matrices underpins quantum algorithms such as quantum singular value transformation, Hamiltonian simulation, and quantum linear system solvers, yet its efficient gate-level realization remains challenging, with index-mapping oracles constituting one important source of overhead. We introduce a block-encoding framework that focuses on the index-mapping component, where coherent permutation is used as the central mechanism to optimize shift, delete, and insert operations. This provides a unified treatment of index mapping and reduces local multicontrolled X control complexity through structured compression. We further connect coherent amplitude permutation to combinatorial optimization, enabling systematic assignment of control states under hardware connectivity constraints. The resulting construction supports entry-wise block encoding for general sparse matrices, with efficiency gains in structured cases. We demonstrate the approach on representative examples and provide resource analysis using IBM superconducting backends, showing significant reductions in circuit depth.

16 pages, 8 figures. Published in Physical Review Research

References in corpus (14)

• Quantum algorithm for solving linear systems of equations
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Experimental Comparison of Two Quantum Computing Architectures
• Quantum Circuits for General Multiqubit Gates
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Quantum Circuits for Isometries
• Efficient Distributed Quantum Computing
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Quantum SDP-Solvers: Better upper and lower bounds
• Quantum K-nearest neighbor classification algorithm based on Hamming distance
• Block-encoding structured matrices for data input in quantum computing
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth