In recent years, quantum algorithms have been proposed which use quantum phase estimation (QPE) coherently as a subroutine without measurement. In order to do this effectively, the routine must be able to distinguish eigenstates with success probability close to unity. In this paper, we provide the first systematic comparison between two approaches towards maximizing this success probability, one using the quantum singular value transform and the other leveraging window functions, which have been previously studied as priors of the phase value distribution. We find that the quantum singular value transform is significantly outclassed by the window function approach, with the latter able to achieve between 3 and 5 orders of magnitude improvement in the success probability with approximately 1/4 the query cost. Our circuit simulation results indicate that QPE is not a domain which benefits from the integration of QSVT and we show that the use of the Kaiser window function is currently the most practical choice for realizing QPE with high success probability.
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 generate
nFourier coefficients with 0 (poly log (
n)) gates compared to prior approaches with linear cost.
Efficiently uploading data into quantum states is essential for many quantum algorithms to achieve advantage across various applications. In this paper, we address this challenge by developing a method to upload a polynomial function f ( x ) on the interval x ∈ [ − 1 , 1 ] into a pure quantum state consisting of qubits, where a discretized f ( x ) is the amplitude of this state. The preparation cost has O ( n log n ) scaling in the number of qubits n and linear scaling with the degree of the polynomial Q . This efficiency allows the preparation of states whose amplitudes correspond to high-degree polynomials (up to 10 4 ), enabling accurate approximation of functions that admit efficient polynomial series representations and whose amplitude profiles are not extremely localized. We provide a fully explicit circuit realization, based on four real polynomials that meet specific parity and boundedness conditions. We extend this construction to cover piecewise polynomial functions, a case not previously addressed explicitly in the literature, the algorithm scaling linearly with the number of piecewise parts. Our method achieves efficient quantum circuit implementation and we present detailed gate counting and resource analysis.
We introduce shadow quantum singular value transformation (Shadow QSVT): given an initial state
∣ψ⟩, a Hermitian matrix
H, a polynomial
f, and a set of observables
{O1,…,Om}, the goal is to estimate
⟨ψ∣f(H)†Ojf(H)∣ψ⟩ for all
j∈{1,…,m}. Shadow QSVT provides a systematic route to reduce the quantum resources required by standard QSVT, which constructs a unitary block-encoding of
f(H). It uses structure in the input state and observables, together with the fact that many applications require only observable estimates rather than synthesizing the full unitary.
We present three algorithms that exploit structure in the initial state and observables to reduce quantum circuit depth. First, we develop a state-aware QSVT algorithm that prepares the target state with low circuit depth when the Krylov subspace associated with
H and
∣ψ⟩ is low-dimensional or admits an accurate low-dimensional approximation. Second, we introduce an observable-aware Shadow QSVT algorithm that combines a new observable-aware Krylov subspace with history states to further reduce circuit depth and gate complexity. Finally, we develop Classical Shadow QSVT, which constructs a classical representation from
H,
f, and
∣ψ⟩ without prior knowledge of the observables or explicit preparation of the target state proportional to
f(H)∣ψ⟩. This representation enables estimation of the target quantities for observables specified after the quantum computation. Together, these three algorithms provide tools for reducing the circuit depth of QSVT-based computations across a range of settings.
We introduce a versatile method for preparing a quantum state whose amplitudes are given by some known function. Unlike existing approaches, our method does not require handcrafted reversible arithmetic circuits, or quantum table reads, to encode the function values. Instead, we use a template quantum eigenvalue transformation circuit to convert a low-cost block encoding of the sine function into the desired function. Our method uses only four ancilla qubits (three if the approximating polynomial has definite parity), providing order-of-magnitude qubit count reductions compared to state-of-the-art approaches, while using a similar number of gates if the function can be well represented by a polynomial or Fourier approximation. We demonstrate the algorithmic utility of our method, including preparing Gaussian and Kaiser window states.
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.