Given the ability to apply an unknown quantum channel acting on a $d$-dimensional system, we develop a quantum algorithm for transforming its singular values. The spectrum of a quantum channel as a superoperator is naturally tied to its Liouville representation, which is in general non-Hermitian. Our key contribution is an approximate block-encoding scheme for this representation in a Hermitized form, given only black-box access to the channel; this immediately allows us to apply polynomial transformations to the channel's singular values by quantum singular value transformation (QSVT). We then demonstrate an $O(d^3/δ)$ upper bound and an $Ω(d/δ)$ lower bound for the query complexity of constructing a quantum channel that is $δ$-close in diamond norm to a block-encoding of the unnormalized Hermitized Liouville representation. We show our method applies practically to the problem of learning the $q$-th singular value moments of unknown quantum channels for arbitrary $q>2, q\in \mathbb{R}$, which has implications for testing if a quantum channel is entanglement breaking. Our results establish a general framework for manipulating black-box quantum channels with QSVT and related methods, enabling direct evaluation of the channel's spectral properties without tomography or significant classical post-processing.
Given the ability to apply an unknown quantum channel acting on a d-dimensional system, we develop a quantum algorithm for transforming its singular values. The spectrum of a quantum channel as a superoperator is naturally tied to its Liouville representation, which is in general non-Hermitian. Our key contribution is an approximate block-encoding scheme for this representation in a Hermitized form, given only black-box access to the channel; this immediately allows us to apply polynomial transformations to the channel's singular values by quantum singular value transformation (QSVT). We then demonstrate an O(d3/δ) upper bound and an Ω(d/δ) lower bound for the query complexity of constructing a quantum channel that is δ-close in diamond norm to a block-encoding of the unnormalized Hermitized Liouville representation. We show our method applies practically to the problem of learning the q-th singular value moments of unknown quantum channels for arbitrary q>2,q∈R, which has implications for testing if a quantum channel is entanglement breaking. Our results establish a general framework for manipulating black-box quantum channels with QSVT and related methods, enabling direct evaluation of the channel's spectral properties without tomography or significant classical post-processing.
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 embeds a matrix as a sub-block of a unitary matrix and serves as a fundamental input model for quantum algorithms based on quantum singular value transformation, enabling polynomial transformations of matrices encoded in unitary operators. Block encoding of unknown quantum states can be useful for quantum learning; however, the fundamental limits on converting between unknown quantum states and their block-encoding unitary channels remain poorly understood. In this paper, we investigate this convertibility in both directions. First, we prove that implementing an ε-approximate block-encoding unitary channel of an unknown quantum state requires Ω(1/ε) copies of the state, matching known upper bounds up to logarithmic factors. Second, we show that recovering a rank-r, d-dimensional quantum state ρ given query access to its block-encoding unitary channel generally requires Ω((1/λmax(ρ))d/r) queries, where λmax(ρ) is the maximum eigenvalue of ρ, revealing an unavoidable dependence on the dimension of the state. Our results identify inherent limitations of block encoding as a representation of unknown quantum states and reveal a separation between learning properties of a quantum state and generating the state itself. Using our techniques, we further establish lower bounds for specific state-generation tasks, including ground-state preparation and Gibbs-state preparation.
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.
We develop new algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework that encapsulates most known quantum algorithms and serves as the foundation for new ones. Existing implementations of QSVT rely on block encoding, incurring an intrinsic O(logL) ancilla overhead and circuit depth O(Ldλ) for polynomial transformations of a Hamiltonian H=∑k=1LHk, where d is the polynomial degree and λ=∑k∥Hk∥. We introduce a simple yet powerful approach that utilizes only basic Hamiltonian simulation techniques, namely, Trotter methods, to: (i) eliminate the need for block encoding, (ii) reduce the ancilla overhead to only a single qubit, and (iii) still maintain near-optimal complexity. Our method achieves a circuit depth of O(L(dλcomm)1+o(1)), without requiring any complicated multi-qubit controlled gates. Moreover, λcomm depends on the nested commutators of the terms of H and can be substantially smaller than λ for many physically relevant Hamiltonians, a feature absent in standard QSVT. To achieve these results, we make use of Richardson extrapolation in a novel way, systematically eliminating errors in any interleaved sequence of arbitrary unitaries and Hamiltonian evolution operators, thereby establishing a general framework that encompasses QSVT but is more broadly applicable. As applications, we develop end-to-end quantum algorithms for solving linear systems and estimating ground state properties of Hamiltonians, both achieving near-optimal complexity without relying on oracular access. Overall, our results establish a new framework for quantum algorithms, significantly reducing hardware overhead while maintaining near-optimal performance, with implications for both near-term and fault-tolerant quantum computing.
Quantum Singular Value Transformation (QSVT) provides a unified framework for applying polynomial functions to the singular values of a block-encoded matrix. QSVT prepares a state proportional to $\bA^{-1}\bb$ with circuit depth O(d⋅polylog(N)), where d is the polynomial degree of the 1/x approximation and N is the size of $\bA$. Current polynomial approximation methods are over the continuous interval [a,1], giving $d = O(\sqrt{\kap}\log(1/\varepsilon))$, and make no use of any properties of $\bA$.
We observe here that QSVT solution accuracy depends only on the polynomial accuracy at the eigenvalues of $\bA$. When all N eigenvalues are known exactly, a pure spectral polynomial pS can interpolate 1/x at these eigenvalues and achieve unit fidelity at reduced degree. But its practical applicability is limited. To address this, we propose a spectral correction that exploits prior knowledge of K eigenvalues of $\bA$. Given any base polynomial p0, such as Remez, of degree d0, a K×K linear system enforces exact interpolation of 1/x only at these K eigenvalues without increasing d0. The spectrally corrected polynomial pSC preserves the continuous error profile between eigenvalues and inherits the parity of p0.
QSVT experiments on the 1D Poisson equation demonstrate up to a 5× reduction in circuit depth relative to the base polynomial, at unit fidelity and improved compliance error. The correction is agnostic to the choice of base polynomial and robust to eigenvalue perturbations up to 10% relative error. Extension to the 2D Poisson equation suggests that correcting a small fraction of the spectrum may suffice to achieve fidelity above 0.999.