Source-linked AI summary
Shadow Quantum Singular Value Transformation with Shallow Quantum Circuits
Nai-Hui Chia, Hyunseong Kim, Chia-Ying Lin
TL;DR
QSVT-based algorithms can be difficult to implement on early fault-tolerant quantum computers with limited coherent circuit depth. Shadow QSVT uses input-state and observable structure to estimate target quantities or prepare a target state with shallow circuits. Under invariant Krylov-space conditions, the state-aware and observable-aware algorithms achieve depths scaling as O(rDH) and O(sDH), respectively.
Problem
Early fault-tolerant quantum computers are expected to have limited logical qubits, quantum memory, and coherent circuit depth, making many QSVT-based algorithms difficult to implement.
Source: §1 · p. 4Method
Shadow QSVT exploits input-state and observable structure, including reduced Krylov and history-space representations, to prepare target states or evaluate observables without coherently preparing the polynomially transformed state.
Source: §1 · p. 4, §1.2.2 · pp. 8–9Results
For invariant Krylov spaces, state-aware preparation has depth O(rDH), while observable-aware estimates have depth O(sDH) when the observable-visible dimension is s≤r.
Source: §1.1 · pp. 5–6Takeaways & Limitations
The framework suggests a route to shallow state preparation or observable statistics under suitable instance-dependent assumptions on input states and target observables.
Source: §1.3 · p. 10Current gate- and sample-complexity bounds still depend polynomially on deg(f), so the algorithms primarily reduce circuit depth under their structural promises.
Source: §1.3 · p. 11
Abstract
from arXiv · showhide
We introduce shadow quantum singular value transformation (Shadow QSVT): given an initial state $|{\psi}\rangle$, a Hermitian matrix $H$, a polynomial $f$, and a set of observables $\{O_1,\dots,O_m\}$, the goal is to estimate $\langle{\psi}|f(H)^{\dagger}O_j f(H)|{\psi}\rangle$ for all $j\in\{1,\dots,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 $|\psi\rangle$ 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 $|\psi\rangle$ without prior knowledge of the observables or explicit preparation of the target state proportional to $f(H)|\psi\rangle$. 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.
1 Introduction
The introduction motivates instance-aware QSVT methods that exploit input-state and observable structure to estimate needed quantities under limited coherent depth, rather than implement full operators. It also discusses complexity limitations, discloses the use of AI tools during the research, and notes that further end-to-end resource reductions without stronger input assumptions remain open.
1.1 Main result
- Shadow QSVT formalizes estimation of observable expectations for a specified input state and offers three algorithms designed to reduce quantum circuit depth.The algorithms are state-aware QSVT, observable-aware Shadow QSVT, and Classical Shadow QSVT.Source: §1.1 · pp. 4–6
1.2.1 State-aware QSVT
- Under H-invariance and a degree-(r−1) polynomial representation of f(H)|ψ⟩, state-aware QSVT prepares the normalized target state with depth O(rDH).The theorem bounds the state-preparation error by ϵ and does not require prior knowledge of the spectral measure.Source: §1.1 · p. 5
1.2.2 Observable-aware Shadow QSVT
- When the observable-visible dimension is s ≤ r, observable-aware Shadow QSVT estimates observables at depth O(sDH) without coherently preparing the transformed state.It uses an observable-relevant quotient Krylov space and history states; it also removes the bounded-normalization-ratio assumption required by the state-aware method.Source: §1.1 · p. 6, §1.2.2 · pp. 8–9
1.2.3 Classical Shadow QSVT
- When observables are unspecified during data collection, Classical Shadow QSVT builds reusable data in depth O(rDH) and estimates later queries through classical postprocessing.Its quantum data acquisition depends on H, |ψ⟩, and Krylov indices, not observable identities.Source: §1.1 · p. 6, §1.2.3 · pp. 9–10
1.3 Discussion
- The discussion leaves quantum advantage conditional on hardness and precision assumptions, notes regimes where sparse inputs and constant Krylov dimension allow classical computation, and identifies state-dependent fast-forwarding as a potential application.It highlights finding physically relevant instances with manageable total resource costs as an important next step.Source: §1.3 · p. 10
- The algorithms’ gate and sample complexity still depend polynomially on deg(f), so their main benefit is reducing circuit depth under structural promises.Further total-complexity reductions are open; accurate moment-matrix access could help but shifts computational burden to the input model and faces precision and error-propagation barriers.Source: §1.3 · p. 11
1.4 Disclosure of AI usage
- The authors report using ChatGPT to check arguments, improve error analysis, identify Cayley-Hamilton for Algorithm 3, and explore references for Algorithm 1 with Claude; they wrote and independently verified the final proof and calculation.The disclosure says both tools were accessed in September 2026.Source: §1.4 · p. 11
2 Preliminary
The preliminaries establish Krylov subspaces and their Lanczos representation, then review block-encoding, QSVT, and Hadamard-test tools used in the algorithms.
2.1 Krylov subspace and Lanczos basis
- The Krylov subspace is spanned by successive powers of H applied to a starting vector, and Lanczos yields an orthonormal basis; invariance is equivalent to β_r = 0.The Lanczos basis is generated from the initial vector and the Hermitian matrix H.Source: §2.1 · pp. 11–12
2.2 Block-encoding
- The paper assumes ∥H∥s ≤ 1 and access to a (1, l, ϵ)-block-encoding; block-encodings compose, enabling polynomial constructions from H.The product of block-encodings represents the product of their encoded operators, with additive circuit depth.Source: §2.2 · p. 13
2.3 Quantum Singular Value Transformation
- QSVT block-encodes a polynomial of H with depth scaling with its degree, and postselection succeeds with probability approximately ∥Pr(H)|ψ⟩∥².For a degree-(r−1) polynomial, the circuit uses repeated applications of UH and U†H.Source: §2.3 · pp. 14–15
2.4 Hadamard test
- The Hadamard test estimates the real or imaginary part of ⟨ψ|U|ψ⟩, while multiple estimators jointly achieve error ϵ with failure probability at most lδ.The joint guarantee follows by allocating failure probability across the l tests.Source: §2.4 · pp. 15–16
3 State-aware QSVT with shallow quantum circuit
State-aware QSVT exploits an invariant, low-dimensional Krylov subspace to prepare the target state using a polynomial of degree at most r−1. It estimates Krylov information, computes coefficients classically, and uses QSVT for final state preparation.
3 State-aware QSVT with shallow quantum circuit
- When f(H)|ψ⟩ lies in an H-invariant r-dimensional Krylov subspace, a degree-(r−1) polynomial reproduces the target state.The theorem prepares the normalized polynomial-transformed state with error ε and success probability 1−δ.Source: §3 · pp. 17–18
3.1 State-Aware QSVT Algorithm
- The algorithm estimates Gram-matrix moments, computes polynomial coefficients classically, then prepares the target state using LCU or QSVT.The coefficient calculation takes place in an r × r classical computation.Source: §3 · p. 18, §3.1.2 · p. 21
3.1.1 Gram matrix estimation complexity
- The two Hankel Gram matrices have only 2r independent entries, which are estimated from Hadamard tests of powers of the block encoding.Their entries are moments ⟨ψ|H^k|ψ⟩.Source: §3.1.1 · p. 20
3.1.2 Coefficient vector calculation
- Coefficient recovery avoids constructing the Lanczos basis matrix, but errors in estimated Gram matrices propagate to the prepared state.The error bound depends on the function’s Lipschitz constant and the minimum eigenvalue of the Gram matrix.Source: §3.1.2 · pp. 21–22
3.1.3 Sample complexity of Hadamard test
- The analysis sets Hadamard-test sample requirements to control the error in the final state preparation.The Gram-matrix estimates are the inputs to coefficient recovery.Source: §3.1.3 · pp. 23–24
3.1.4 Proof of Theorem 3.1
- The overall circuit depth scales with the Krylov dimension r and the block-encoding depth D_H.The proof combines the Hadamard-estimation and degree-(r−1) QSVT depths.Source: §3.1.4 · p. 24
4 Classical-Shadow S-QSVT
Classical-Shadow S-QSVT replaces coherent target-state preparation with estimation of Krylov coefficients and observable-dependent Krylov matrices. Shadow data can be collected independently of the observables and processed classically for later queries.
4 Classical-Shadow S-QSVT
- When only observable estimates are needed, the procedure can bypass final preparation of the transformed state.Instead, it estimates the Krylov coefficients and observable Krylov matrices.Source: §4 · p. 25
4.1 Classical-shadow access model
- Classical-shadow measurements provide data for estimating the observable Krylov matrices without preparing P_r(H)|ψ⟩.The matrices contain Krylov cross moments.Source: §4 · p. 25
4.2 Algorithm procedure
- The quantum data-acquisition stage produces a reusable shadow dataset that depends on H, |ψ⟩, the Krylov pair, and the measurement ensemble—not on the observables.Observable-dependent processing can be run later on the stored dataset.Source: §4.2 · p. 26
18 Step 4: Compute the observable estimates.
The observable-estimation procedure reuses shadow data for post-hoc observable families when the stored sample count is sufficient. Its guarantees bound estimation error under an exact block encoding, and the local-Pauli specialization gives logarithmic dependence on the number of bounded-weight Pauli observables.
18 Step 4: Compute the observable estimates.
- A later observable family can be evaluated from stored data without new quantum measurements when the dataset has enough samples for its shadow-norm bound and target precision.Otherwise, additional samples are required.Source: §18 · p. 28
4.3 Main observable-estimation guarantee
- Under the theorem’s conditions, estimates meet the target observable precision with probability at least 1−δ, without preparing the transformed state.The guarantee assumes an exact block encoding; the stated analysis excludes bias from approximate block encoding.Source: §4.3 · pp. 29–30
4.4 Observable Krylov matrix estimation
- Observable identities do not affect quantum data acquisition; they affect the sample count needed for classical post-processing.The observable Krylov matrices are estimated from the stored datasets.Source: §4.4 · p. 30
4.5 Local Pauli specialization
- For bounded-weight Pauli observables, the dependence on the number M of observables is logarithmic under local Pauli shadows.The cited specialization assumes each Pauli string has weight at most k.Source: §4.5 · p. 31
5 Observable-Aware S-QSVT
Observable-Aware S-QSVT reduces dynamics to the part of the state-Krylov space visible to prescribed observables and uses observable histories to recover observable estimates. The section analyzes the algorithm’s end-to-end guarantees and resource requirements, and presents a more efficient construction of the matrices used in Algorithm 7.
5.1 The observable-aware Krylov subspace
- The method quotients out state-Krylov directions invisible to every observable after every future application of H, leaving an observable-relevant space of dimension s.The invisible subspace is invariant under H, so the Hamiltonian induces dynamics on the quotient.Source: §5 · p. 32, §5.1 · p. 32
5.2 Observable-aware Krylov reduction
- When the observable-relevant quotient has dimension s, its first s quotient Krylov vectors form a basis, and every higher vector is a linear combination of them.Consequently, any polynomial acting on the initial state can be reduced, without changing the observables, to a polynomial of degree at most s −1.Source: §5.2 · p. 33
5.3 History-space representation
- The first s observable histories characterize invisible directions and realize the quotient as an s-dimensional history space with a basis formed by the first s history vectors.The induced Hamiltonian dynamics can be represented in that generally nonorthogonal basis and reconstructed from history-vector inner products; its coefficient matrix need not be Hermitian in the standard Euclidean inner product.Source: §5.3 · pp. 34–36
5.4 Algorithm procedure
- The algorithm estimates history Gram matrices, reconstructs the effective history-space dynamics, computes observable-aware Krylov coefficients and reduced observable matrices, then estimates the observables.Source: §5.4 · p. 37
5.5 Correctness analysis
- Proposition 5.7 establishes exact observable reconstruction for every polynomial and each prescribed observable.For Hermitian H with ∥H∥2 ≤1, the effective dynamics matrix is similar to a Hermitian contraction.Source: §5.5 · pp. 38, 40
5.6 End-to-end error analysis
- The end-to-end error analysis fixes the polynomial P and studies estimation error relative to a specified reference quantity.The supplied passage gives the setup but not the resulting error bound.Source: §5.6 · p. 41
- Under its stated block-encoding and precision assumptions, Theorem 5.10 gives a probability-at-least-1−δ guarantee that Algorithm 6 avoids failure and satisfies a simultaneous guarantee for every i.The supplied theorem passage truncates before specifying the quantity or bound guaranteed for each i.Source: §5.6 · p. 42
- The analysis accounts for estimation of history matrices and observable Krylov matrices over O(s^2) Krylov pairs, with all M observables estimated simultaneously for each pair.The supplied passages omit the displayed sample-count formulas, so no total sample bound can be stated here.Source: §5.6 · p. 45
- The maximum quantum circuit depth is O(Dψ + sDH + Dsh), with each shadow sample requiring O(s) sequential applications of UH or controlled-UH.All remaining steps are classical.Source: §5.6 · p. 46
A.1.1 Correctness of Algorithm 7
- Algorithm 7 constructs Ur and Jr together using their relationship, reducing the stated total computational complexity from O(r^3) for Gaxpy’s Cholesky algorithm to O(r^2).The given data can be used with Algorithm 2 to calculate Ur and Jr together.Source: §A.1.1 · pp. 49, 51
A.2 Proof of QR factor-Lanczos equivalent
The proof establishes the equivalence by induction over the Krylov basis: it verifies the one-dimensional base case and extends the correspondence at each added direction.
A.2 Proof of QR factor-Lanczos equivalent
- The base case identifies the first Krylov subspace as the span of the initial state.The passage also derives this from the unit norms of the vectors used in the construction.Source: §A.2 · p. 51
- At each induction step, the new basis vectors lie in the one-dimensional extension orthogonal to the preceding Krylov subspace.The proof uses this shared one-dimensional space to relate the two vectors up to a phase.Source: §A.2 · p. 51
- The argument is stated to hold throughout the process when the initial state is the first basis vector and each new basis vector is orthogonal to the previous Krylov space.Source: §A.2 · p. 51
A.3 Minor Claims for Theorem 3.1
These appendix passages collect technical claims and subroutines for the state-aware and classical-shadow methods, including controlled Krylov branches and weighted shadow samples.
A.3 Minor Claims for Theorem 3.1
- The appendix’s perturbation claims frame reduced-matrix and Lanczos-coefficient errors using Lipschitz conditions and a shared eigenbasis.The coefficient-error claim defines the perturbations as differences between estimated and reference quantities.Source: §A.3 · pp. 52–53
B.1 Median-of-means subroutine
- The median-of-means subroutine partitions samples into groups and returns the median of their group estimates.The appendix identifies this as a statistical subroutine used in the classical-shadow technical details.Source: §B.1 · p. 53, Appendix B · p. 53
B.2.1 Controlled Krylov branches
- A controlled Krylov-branch implementation uses at most max{a, b} queries to the block encoding or its controlled version.Failed block-encoding rounds are retained with zero weight, so the stated sample complexity has no additional postselection factor.Source: §B.2.1 · p. 54
B.2.2 Weighted classical snapshots
- The good-branch operator has trace p_a,b, and the corresponding shadow outcome follows a classical-shadow measurement of the good-branch state.When p_a,b is zero, the weighted estimators vanish identically.Source: §B.2.2 · p. 54, §B.2.3 · p. 55
B.3 Proof of observable Krylov matrix estimation and its resources
The proof assembles estimates across Krylov pairs and shadow rounds, using median-of-means bounds for simultaneous accuracy and sequential block-encoding layers for resource accounting.
B.3 Proof of observable Krylov matrix estimation and its resources
- With probability at least 1 − η, median-of-means estimates all 2M real quantities to the stated accuracy.The guarantee follows by taking medians over groups and applying a union bound.Source: §B.3 · p. 56
- The proof allocates failure probability across the r(r + 1)/2 upper-triangular Krylov pairs and sums their sample and query costs.The passages refer to the resulting bounds as Eqs. (121), (122), and (124), without giving their formulas here.Source: §B.3 · pp. 56–57
- For a Krylov pair (a, b), the controlled implementation uses max{a, b} sequential block-encoding layers, with at most one query per layer.The preparation depth is counted from these sequential layers.Source: §B.3 · p. 56
B.4 Proof of end-to-end observable estimation
The proof combines coefficient and observable-Krylov-matrix estimates to establish end-to-end observable accuracy and bound the total quantum resources. The two estimation stages contribute additive query and gate costs, while overall depth is their maximum.
B.4 Proof of end-to-end observable estimation
- The coefficient and observable-Krylov-matrix events together give success probability at least 1 −δ and accuracy ϵO.The coefficient-estimation event fails with probability at most δ/2, and the observable-Krylov-matrix event fails with probability at most δ/2.Source: §B.4 · pp. 57–58
- Total sample complexity is Nobs = Nλ(ϵλ, δ/2) + NB.Source: §B.4 · p. 58
- Query and gate costs add across the two estimation stages, whereas total circuit depth is the larger stage-wise depth.The resource totals are Qobs = Qλ + QB, Dobs = max{Dλ, DB}, and Gobs = Gλ + GB.Source: §B.4 · p. 58
B.5 Local Pauli classical shadows
The local Pauli specialization uses independently randomized single-qubit measurement bases and exploits observable weight bounds. This allows the full snapshot matrix to be avoided and yields a weight-dependent bound for the shadow observables.
B.5 Local Pauli classical shadows
- Each qubit is measured in an independently and uniformly chosen X, Y, or Z basis.The computational-basis outcome is encoded as mj := (−1)bj.Source: §B.5 · p. 58
- The full snapshot matrix need not be constructed explicitly.The passage states that the full 2n+1 × 2n+1 snapshot matrix is avoided.Source: §B.5 · p. 59
- When each observable is a Pauli string of weight at most k, the two shadow observables have weight at most k + 1.The local Pauli specialization gives the stated bound O ≤ 3k+1.Source: §B.5 · p. 59
Appendix C: Technical Details for Observable-Aware S-QSVT
The appendices establish the observable-aware history-space construction and describe related measurement and factorization tools. The history map removes observable-invisible directions and realizes the observable-relevant quotient dynamics in an s-dimensional space.
Appendix C: Technical Details for Observable-Aware S-QSVT
- The finite history map removes exactly the observable-invisible directions, yielding an s-dimensional realization of the observable-relevant quotient dynamics.When dim QO = s, the history space has dimension s and the mapped vectors form a basis.Source: Appendix C · pp. 59–60
Appendix D: Hadamard test with block-encoded operator
- The block-encoded Hadamard test provides a way to measure ⟨ψ|A|ψ⟩ for a block-encoded operator without additional measurement.The passage identifies the circuit as a Hadamard test and relates its first-register outcome probability to the measurement.Source: Appendix D · pp. 61, 63
Appendix E: Cholesky factorization
- A Hermitian positive-definite matrix has a unique Cholesky factorization U†U with an upper-triangular factor having positive real diagonal entries.Source: Appendix E · p. 63
E.1 Error propagation
The section analyzes how perturbations to a positive-definite matrix affect its Cholesky factor. It expresses the perturbed factor through a relative factor perturbation and establishes identities that preserve positive definiteness.
E.1 Error propagation
- The error analysis assumes a Hermitian perturbation and a positive-definite estimate; relative error bounds can provide tighter upper bounds in some matrices using U.Source: §E.1 · pp. 64, 66
- For a Hermitian estimate G~ = G + δG, the relative factor perturbation Γ gives U~ = (1 + Γ)U and 1 + A = (1 + Γ)†(1 + Γ).The section defines A := U−†δGU−1 and Γ := (U~ − U)U−1.Source: §E.1 · p. 66
- The factor perturbation Γ is upper triangular with real diagonal entries greater than −1, so 1 + A and G~ remain positive definite.Source: §E.1 · p. 66