Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth

Abstract

Block encoding severs as an important data input model in quantum algorithms, enabling quantum computers to simulate non-unitary operators effectively. In this paper, we propose an efficient block-encoding protocol for sparse matrices based on a novel data structure, called the dictionary data structure, which classifies all non-zero elements according to their values and indices. Non-zero elements with the same values, lacking common column and row indices, belong to the same classification in our block-encoding protocol's dictionary. When compiled into the \{\rm U(2), CNOT\} gate set, the protocol queries a $2^n\times 2^n$ sparse matrix with $s$ non-zero elements at a circuit depth of $\mathcal{O}(\log (ns))$, utilizing $\mathcal{O}(n^{2}s)$ ancillary qubits. This offers an exponential improvement in circuit depth relative to the number of system qubits, compared to existing methods~\cite{clader2022quantum,zhang2024circuit} with a circuit depth of $\mathcal{O}(n)$. Moreover, in our protocol, the subnormalization, a scaled factor that influences the measurement probability of ancillary qubits, is minimized to ${\sum }_{l=0}^{s_0}|A_l|$, where $s_0$ denotes the number of classifications in the dictionary and $A_l$ represents the value of the $l$-th classification. Furthermore, we show that our protocol connects to linear combinations of unitaries (LCU) and the sparse access input model (SAIM). To demonstrate the practical utility of our approach, we provide several applications, including Laplacian matrices in graph problems and discrete differential operators.

26 pages, 8 figures

References in corpus (14)

• Quantum algorithm for solving linear systems of equations
• Third quantization: a general method to solve master equations for quadratic open Fermi systems
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Simulating sparse Hamiltonians with star decompositions
• Exponential quantum speedup in simulating coupled classical oscillators
• Block-encoding structured matrices for data input in quantum computing
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
• FABLE: Fast Approximate Quantum Circuits for Block-Encodings
• Lecture Notes on Quantum Algorithms for Scientific Computation
• Circuit complexity of quantum access models for encoding classical data
• On efficient quantum block encoding of pseudo-differential operators
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• S-FABLE and LS-FABLE: Fast approximate block-encoding algorithms for unstructured sparse matrices

Cited by in corpus (1)

• Block Encoding of Sparse Matrices via Coherent Permutation