Block Encoding of Sparse Matrices via Coherent Permutation
It addresses a key bottleneck in quantum algorithms (Hamiltonian simulation, QSVT, linear solvers) by providing practical circuit implementations for general sparse matrices, bridging theory and hardware.
This work introduces a unified framework for block encoding of sparse matrices that reduces multi-controlled X gate overhead and circuit depth, enabling hardware-efficient implementations with explicit gate-level constructions.
Block encoding of sparse matrices underpins powerful quantum algorithms such as quantum singular value transformation, Hamiltonian simulation, and quantum linear solvers, yet its efficient gate-level realization for general sparse matrices remains a major challenge. We introduce a unified framework that addresses key obstacles including the overhead of multi-controlled X (MCX) gates, amplitude reordering, and hardware connectivity, enabling simplified block encoding constructions with explicit gate-level implementations. Central to our approach is a connection to combinatorial optimization, which enables systematic assignment of control qubits to satisfy nearest-neighbor connectivity constraints, along with coherent permutation operators that preserve superposition while enabling structured amplitude reordering. We demonstrate our methods on structured sparse matrices, achieving systematic reductions in control overhead and circuit depth. Our framework bridges the gap between theoretical formulations and hardware-efficient quantum circuit implementations.