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.
We introduce Unitaria, a Python library that brings the simplicity of classical linear algebra toolkits such as NumPy and SciPy to the implementation of quantum algorithms based on block encodings, a general-purpose abstraction in which a matrix is embedded as a sub-block of a larger unitary operator. Their implementation has so far required deep knowledge of low-level circuit construction, which Unitaria aims to eliminate. The library provides a composable, array-like interface through which users can define block encodings of matrices and vectors, combine them through standard operations such as addition, multiplication, tensor products, and the Quantum Singular Value Transformation, and extract the resulting quantum circuits automatically. A key feature is a matrix-arithmetic evaluation path in which every operation can be computed directly on encoded vectors and matrices without dependence on ancilla qubits or circuit simulation. This enables correctness verification and classical simulation that scale well beyond what state vector simulation permits and also allows resource estimation, including gate counts, qubit counts, and normalization constants, without executing any circuit. Together, these capabilities allow researchers to develop, verify, and analyze quantum linear algebra algorithms today, ahead of the availability of error-corrected hardware. Unitaria is open source and available at https://github.com/tequilahub/unitaria.
The cost of data input can dominate the run-time of quantum algorithms. Here, we consider data input of arithmetically structured matrices via block encoding circuits, the input model for the quantum singular value transform and related algorithms. We demonstrate how to construct block encoding circuits based on an arithmetic description of the sparsity and pattern of repeated values of a matrix. We present schemes yielding different subnormalisations of the block encoding; a comparison shows that the best choice depends on the specific matrix. The resulting circuits reduce flag qubit number according to sparsity, and data loading cost according to repeated values, leading to an exponential improvement for certain matrices. We give examples of applying our block encoding schemes to a few families of matrices, including Toeplitz and tridiagonal matrices.
Quantum Signal Processing (QSP) and Quantum Singular Value Transformation (QSVT) provide an efficient framework for implementing polynomials of block-encoded matrices, and thus offer a systematic approach to quantum algorithm design. However, despite a number of recent advances, important limitations remain. In particular, QSP can only transform unitary matrices, by applying a polynomial to their eigenvalues, while QSVT is a singular-value transformation and thus one can only obtain the polynomial of Hermitian matrices. As a consequence, these techniques do not directly apply to an arbitrary non-Hermitian matrix that is not diagonalizable. In this work, we propose a simple yet powerful method to extend these ideas to arbitrary square matrices by acting on their eigenvalues. To this end, we introduce the notion of an
n-regular block encoding, namely, a block encoding whose
k-th power reproduces the
k-th power of the encoded matrix for every
0<k<n. We show that applying QSP to any unitary with this property is equivalent to applying a polynomial of degree at most
n to the block-encoded matrix, independently of its internal structure. Moreover, we provide a simple construction that transforms any block encoding into an
n-regular one using only
O(logn) ancillary qubits and operations. Finally, we show that this construction induces the desired transformation on the eigenvalues associated with the Jordan normal form of the matrix; for non-diagonalizable matrices this yields the full matrix function
P(A), whose action on each Jordan block involves the derivatives of
P, and not merely the map
λ↦P(λ).
Block encoding of non-unitary matrices in a quantum framework is a transformative technique for broadening the capabilities of quantum algorithms, allowing them to address a wider range of computational challenges. This paper introduces a novel embedding method to construct unitary matrices from non-unitary matrices, enabling their efficient encoding into quantum circuits. Utilizing the Gram-Schmidt process, the proposed approach embeds an
n×nnon-unitary matrix
Ainto a
2n×2nunitary matrix
UA. When Compared to conventional methods such as Singular Value Decomposition (SVD), our approach achieves a 20 % faster execution time while maintaining high accuracy. Block encoding method has the potential to significantly advance quantum computing applicability by building unitary matrices from non-unitary ones in areas like optimization, quantum machine learning, and large-scale quantum simulations.
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.