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 entrywise 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.
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 entrywise 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.
Block encoding is a successful technique used in several powerful quantum algorithms. In this work we provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure. The proposed methodology is based on the linear combination of unitaries (LCU) framework and on an efficient unitary operator used to project the complex exponential at a frequency ω multiplied by the computational basis into its real and imaginary components. We demonstrate a distinct computational advantage with a O(poly(n)) gate complexity, where n is the number of qubits, in the worst-case scenario used for banded matrices, and O(n) when dealing with a simple diagonal matrix, compared to the exponential scaling of general-purpose methods for dense matrices. Various applications for the presented methodology are discussed in the context of solving differential problems such as the advection-diffusion-reaction (ADR) dynamics, using quantum algorithms with optimal scaling, e.g., quantum singular value transformation (QSVT). Numerical results are used to validate the analytical formulation.
Abstract. Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest [Formula: see text] in a larger unitary transformation [Formula: see text] that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such a gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of [Formula: see text], which is difficult in general, and not trivial even for well structured sparse matrices. In this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB.
Modern quantum algorithms are increasingly formulated as coherent procedures for implementing polynomial transformations of operators and singular values. This perspective provides a powerful and unifying language for quantum algorithm design, connecting a wide range of distinct problems through five closely related key tools: block-encoding, qubitization, QSP, QSVT and GQSP. Block-encoding embeds non-unitary matrices into larger unitaries; qubitization converts block-encodings into structured operators; QSP, QSVT and GQSP enable polynomial transformations with near-optimal query complexity. Together, these techniques form a general toolkit for transforming matrix functions into implementable quantum circuits. This paper develops these techniques from first principles as a unified framework for constructing quantum algorithms. We apply this framework to representative applications to highlight design principles and demonstrate how distinct algorithms can be constructed from a unified sequence of operator transformations.
A central contribution is a systematic decision workflow for selecting the appropriate approach according to the operator structure and the desired transformation polynomial. This perspective clarifies when direct GQSP or through qubitization, or Laurent expansion, or QSVT is most appropriate. We organize algorithmic design into an end-to-end pipeline: identifying the target matrix function, constructing an appropriate block-encoding, determining the relevant spectral domain, designing a polynomial or Laurent-polynomial approximation, synthesizing the phase factors, and translating the transformation into an executable quantum circuit. By applying this unified framework to example applications, we showcase a practical methodology for reasoning, designing, and implementing quantum algorithms based on polynomial transformations.
Implementing polynomial functions of Hermitian matrices on quantum hardware is a foundational task in quantum computing, critical for accurate Hamiltonian simulation, quantum linear system solving, high-fidelity state preparation, machine learning kernels, and other advanced quantum algorithms. Existing state-of-the-art techniques, including Qubitization, Quantum Singular Value Transformation (QSVT), and Quantum Signal Processing (QSP), rely heavily on block-encoding the Hermitian matrix. These methods are often constrained by the complexity of preparing the block-encoded state, the overhead associated with the required ancillary qubits, or the challenging problem of angle synthesis for the polynomial's phase factors, which limits the achievable circuit depth and overall efficiency. In this work, we propose a novel and resource-efficient approach to implement arbitrary polynomials of a Hermitian matrix by leveraging the Generalized Quantum Signal Processing (GQSP) framework. Our method circumvents the need for block-encoding and avoids the compounding post-selection overheads characteristic of LCU-based constructions, achieving a stable, degree-independent success probability. We derive closed-form expressions for symmetric polynomial expansions and demonstrate how linear combinations of GQSP circuits can realize the desired transformation. This approach reduces resource overhead and opens new pathways for quantum algorithm design for functions of Hermitian matrices, particularly in settings where the Hermitian operator arises naturally from symmetric combinations of unitaries.
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 {U(2), CNOT} gate set, the protocol queries a 2n×2n sparse matrix with s non-zero elements at a circuit depth of O(log(ns)) , utilizing O(n2s) 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 O(n) . Moreover, in our protocol, the subnormalization, a scaled factor that influences the measurement probability of ancillary qubits, is minimized to ∑l=0s0|Al| , where s0 denotes the number of classifications in the dictionary and Al 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.
While quantum algorithms for solving large scale systems of linear equations offer potentially exponential speedups, their application has largely been confined to sparse matrices. This work extends the scope of these algorithms to a broad class of structured dense matrices arise in potential theory, covariance modeling, and computational physics, namely, hierarchically block separable (HBS) matrices. We develop two distinct methods to make these systems amenable to quantum solvers. The first is a pre-processing approach that transforms the dense matrix into a larger but sparse format. The second is a direct block encoding scheme that recursively constructs the necessary oracles from the HBS structure. We provide a detailed complexity analysis and rigorous error bounds for both methods. Numerical experiments are presented to validate the effectiveness of our approaches.