The quantum singular value transformation is a powerful quantum algorithm that allows one to apply a polynomial transformation to the singular values of a matrix that is embedded as a block of a unitary transformation. This paper shows how to perform the quantum singular value transformation for a matrix that can be embedded as a block of a Hamiltonian. The transformation can be implemented in a purely Hamiltonian context by the alternating application of Hamiltonians for chosen intervals: it is an example of the Quantum Alternating Operator Ansatz (generalized QAOA). We also show how to use the Hamiltonian quantum singular value transformation to perform inverse block encoding to implement a unitary of which a given Hamiltonian is a block. Inverse block encoding leads to novel procedures for matrix multiplication and for solving differential equations on quantum information processors in a purely Hamiltonian fashion.
The quantum singular value transformation is a powerful quantum algorithm that allows one to apply a polynomial transformation to the singular values of a matrix that is embedded as a block of a unitary transformation. This paper shows how to perform the quantum singular value transformation for a matrix that can be embedded as a block of a Hamiltonian. The transformation can be implemented in a purely Hamiltonian context by the alternating application of Hamiltonians for chosen intervals: it is an example of the Quantum Alternating Operator Ansatz (generalized QAOA). We also show how to use the Hamiltonian quantum singular value transformation to perform inverse block encoding to implement a unitary of which a given Hamiltonian is a block. Inverse block encoding leads to novel procedures for matrix multiplication and for solving differential equations on quantum information processors in a purely Hamiltonian fashion.
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(λ).
The quantum singular value transformation has revolutionised quantum algorithms. By applying a polynomial to an arbitrary matrix, it provides a unifying picture of quantum algorithms. However, polynomials are restricted to definite parity and real coefficients, and finding the circuit (the phase factors) has proven difficult in practice. Recent work has removed these restrictions and enabled faster computation of phase factors, yet only for unitary matrices. Here we propose two generalisations. The generalised quantum singular value transformation allows complex polynomials for arbitrary matrices. For Hermitian matrices, we propose the generalised quantum eigenvalue transformation that even allows polynomials of indefinite parity. While we find that the polynomial might have to be downscaled compared to the quantum singular value transformation, the higher expressivity of polynomials and faster computation of phase factors can sometimes result in advantages. The results are achieved with various block encoding (or projected unitary encoding) techniques, including qubitisation, Hermitianisation, and multiplication. We show how to multiply block-encoded matrices with only one extra qubit, and introduce measure-early multiplication to further avoid the extra qubit and decrease average circuit length.
Quantum signal processing and quantum singular value transformation are powerful tools to implement polynomial transformations of block-encoded matrices on quantum computers, and has achieved asymptotically optimal complexity in many prominent quantum algorithms. We propose a framework of quantum signal processing and quantum singular value transformation on U ( N ) , which realizes multiple polynomials simultaneously from a block-encoded input, as a generalization of those on U ( 2 ) in the original frameworks. We provide a comprehensive characterization of achievable polynomial matrices and give recursive algorithms to construct the quantum circuits that realize desired polynomial transformations. As three example applications, we propose a framework to realize bi-variate polynomial functions, demonstrate N -interval decision achieving O ( d ) query complexity with a log 2 N improvement over iterative U ( 2 ) -QSP requiring O ( d log 2 N ) queries, and present a quantum amplitude estimation algorithm achieving the Heisenberg limit without adaptive measurements.
Abstract. Many problems in linear algebra—such as those arising from non-Hermitian physics, transcorrelated quantum chemistry, and differential equations—can be solved on a quantum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited for this task because eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum superposition of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generate [Formula: see text] Fourier coefficients with [Formula: see text] gates compared to prior approaches with linear cost.
Many problems in linear algebra-such as those arising from non-Hermitian physics, transcorrelated quantum chemistry and differential equations-can be solved on a quan-tum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited to this task, as eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators, and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum super-position of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generatenFourier coefficients with 0 (poly log (n)) gates compared to prior approaches with linear cost.
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.