REVIEW 3 major objections 3 minor 22 references
A Solovay-Kitaev theorem for quantum signal processing
T0 review · 3 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read For quantum signal processing, density of an ansatz in a compact function class guarantees short approximating protocols with $O(\log^c(1/\varepsilon))$ phases.
desk verdict A genuinely novel QSP/SKT bridge, but the load-bearing surjectivity claim fails at the endpoints, so the main theorem does not follow as written. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the nested commutator of Lemma III.4: for four planar QSP protocols related by $U_2=U_0^\dagger$ and $U_3=U_1^\dagger$, the product $[[U_0,U_1],[U_2,U_3]]$ is again an XZ-planar protocol near the SU(2) identity, and to leading order in $\varepsilon$ it acts like an $\varepsilon^4$ rotation whose $\sigma_z$ and $\sigma_x$ coefficients are products of the $\Im[P]$ and $\Im[Q]$ components of the input protocols. This shrinking step converts an $\varepsilon$-net for functions of norm at most $\varepsilon^{1/4}$ into an $\varepsilon^{5/4}$-net with length multiplied by a constant factor. Around it, Definition III.5 abstracts the needed properties—surjectivity on balls about the identity, closeness under the projection implying closeness in the ambient group, and error self-correction—into a 'compatible commutator,' so the net-refinement theorem can be transferred to other QSP-like ansätze once such a commutator is supplied.
What would settle it
Restrict Theorem III.1 to a constant-Lipschitz function space and inspect the leading-order image (50) of the nested commutator. For a candidate low-degree target such as $g(x)=\varepsilon x^2\sqrt{1-x^2}$ in the ball $S_{\varepsilon^{1/4}}(F(X,\xi))$, solve the coupled equations for symmetric-QSP polynomials $P_0,Q_0,P_1,Q_1$ implied by (46)–(49) and (50); if no definite-parity, norm-bounded solutions exist, the claimed surjectivity fails and the recursion stops. A simpler numerical version: sample low-degree Chebyshev targets in the ball, run the preimage construction, and check whether the image covers the ball to leading order.
Extended reading notes
Core claim
The central discovery is that density under a projection $\Pi$ in a compact function space $F(X)$ is enough to guarantee efficient uniform approximation of functions, not just pointwise approximation of gates. The paper constructs a compatible commutator for symmetric QSP: a nested group commutator $[[U_0,U_1],[U_2,U_3]]$ of four planar protocols near the identity, with $U_2=U_0^\dagger$ and $U_3=U_1^\dagger$, which is again planar, shrinks distance to the identity from $\varepsilon$ to $\varepsilon^{5/4}$, and self-corrects approximation error better than naively expected. Iterating this refinement step converts a constant-precision net into nets of exponentially improving precision, yielding protocols of length $O(\log^c(1/\varepsilon))$ for a constant $c$; for the symmetric QSP instance, $c=\log 17/\log(5/4)\approx 12.7$.
Load-bearing premise
The recursion depends on the claim that the nested commutator can hit every function in a small ball about the identity—with the unmonitored $\sigma_x$ component freely redefined at each step—but this surjectivity is only sketched, and if it fails the net refinement cannot continue.
Editorial extensions
If this is right
- If Theorem III.2 is correct, then for any QSP-like ansatz one can replace the hard task of exactly characterizing achievable functions with an easier density check: density in the relevant compact function space automatically yields $O(\log^c(1/\varepsilon))$ approximating protocols under the chosen projection.
- The theorem gives a formal rationale for numerical phase-finding: existence of short phases is guaranteed by net refinement, while actual phases can be computed by stable numerical optimization, decoupling proof of existence from construction.
- For symmetric QSP, density follows for absolutely summable Chebyshev expansions (Theorem IV.3) and for analytic functions via a constant-space LCU construction (Theorem IV.4), both supplying the preconditions of the main theorem in settings where standard completion-and-layer-stripping proofs fail.
- The method yields 'QSP without phases' and 'QSP without polynomials': replacing the continuous phase set by any SU(2)-dense instruction set (plus a $\pi/2$ rotation) or replacing the oracle by any smooth invertible $f(x)\sigma_x$ oracle leaves the density conclusions unchanged (Theorem IV.5).
- For the symmetric QSP instantiation, the length exponent is $c=\log 17/\log(5/4)\approx 12.7$, worse than the standard Solovay-Kitaev exponent because the nested commutator self-corrects errors less efficiently ($\varepsilon\mapsto\varepsilon^{5/4}$, not $\varepsilon\mapsto\varepsilon^{3/2}$).
Reading between the lines
- The 'retroactive definition' of the uncontrolled $\sigma_x$ component suggests a general recipe: when approximating a single matrix element, one can absorb all uncontrolled components into the target at each refinement step. This may let similar theorems be proved for other projections $\Pi$, such as real parts or off-diagonal elements, by finding any planar-preserving commutator rather than the s
- The same proof skeleton should transplant to G-QSP or multivariable QSP: one needs only a density statement plus a compatible commutator preserving the ansatz's planarity. Constructing such commutators is the bottleneck the paper leaves open.
- For target functions that are only once-differentiable, the paper's average-case counting argument suggests unavoidable length growth of order $\xi/\varepsilon$; the $\operatorname{polylog}(1/\varepsilon)$ guarantee is essentially reserved for analytic targets on a Bernstein ellipse. A testable prediction is that any efficient variant must either exploit smoothness or accept a smoothness-dependent
- If a better compatible commutator with error amplification $\varepsilon\mapsto\varepsilon^{1+b}$ for $b>1/4$ exists, the length exponent $c$ would drop toward the standard SKT value; systematically searching over planar protocol products with larger $b$ is a concrete route to improving Theorem III.2.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a lifted Solovay–Kitaev theorem for quantum signal processing. It defines QSP instruction sets, a common QSP function space, planar QSP protocols, a nested group commutator, and a notion of compatible commutators. The main theorem (Thm. III.2) claims that if an instruction set is Π-dense in a compact function space, then every target function has an ε-uniform approximation with phase and oracle length O(log^c(1/ε)). The proof is built on a shrinking lemma (Thm. III.1) that requires the nested commutator to be surjective on balls about the identity function, together with a 'retroactive definition' step to pass from component-wise closeness to operator-norm closeness. Section IV provides density results for several ansätze, including an LCU-based construction and a constant-space QSVT result.
Significance. If correct, the proposed framework would be a valuable new proof technique for QSP/QSVT: it would decouple the existence of short good protocols from constructive phase-finding, and it would extend naturally to modified ansätze for which standard QSP proofs fail. The paper is clearly written, and the definitions of QSP instruction sets, the common function space, and compatible commutators are useful organizational devices. The density statements in Section IV, especially the LCU-based and constant-space constructions, are creative and potentially interesting in their own right. However, the central net-refinement step contains a load-bearing gap, and the main theorem is not established by the arguments given.
major comments (3)
- [Sec. III, Eq. (50); Thm. III.1; Def. III.5(1)] The surjectivity assertion in Thm. III.1 step (1), encoded as property (1) of Def. III.5, is false for the nested commutator constructed in Lem. III.4. In the leading-order formula (50), both the σz and σx coefficients carry an explicit factor √(1−x²); consequently the Π-image of every nested commutator vanishes at x=±1. The ball S_{ε^{1/4}}(F(X,ξ)) contains constant functions such as h(x)=ε^{1/4}/2, which have h(±1)≠0. No element of the commutator image can approximate such an h to better than Ω(ε^{1/4}) at the endpoints, whereas the refinement step claims accuracy ε^{5/4}. The remark that these boundary conditions can be removed by 'shifting by a constant of order ε' does not repair the argument, because the shift is not part of the commutator map G whose surjectivity Def. III.5(1) requires, and the endpoint discrepancy is O(ε^{1/4}), not O(ε). Therefore the net-refinement step cannot be continued for general f∈F(X), and Thm. III.2 does not follow from the given lemmas.
- [Sec. III, Def. III.5(2); Thm. III.1 step (2); Thm. III.2 step (2)] Property (2) of Def. III.5 is load-bearing for translating Π-closeness into operator-norm closeness, but it is not proved and as stated it appears false for natural choices of the planar protocol space. The justification in Thm. III.1 step (2) claims that ℑ[P(x)] uniquely determines the off-diagonal element iQ(x)√(1−x²); this is incorrect, since near the identity the unitary has independent σz and σx components to first order, and ℑ[P] controls only the σz component. The proof of Thm. III.2 step (2) simply assumes ∥I−A0(U0 U R0)^†∥<ε0, which is not a consequence of Π-density alone. A repair would require either a genuinely stronger approximation statement or a revised commutator that controls both components; as it stands, the translation step is unjustified.
- [Sec. IV, Thm. IV.3 and Thm. IV.4] Several of the density results claimed as preconditions for the main theorem do not produce elements of the QSP instruction set Σ* as defined in Def. I.3. Thm. IV.3 uses LCU with additional qubits and a QSVT protocol to isolate the desired matrix element, and Thm. IV.4 explicitly concerns QSVT protocols with 'constant additional space'; neither is a finite pointwise product of the oracle and phase unitaries only. Thus these theorems do not establish Π-density of a QSP instruction set in the sense required by Thm. III.2, and the applications section does not currently supply the claimed instruction sets.
minor comments (3)
- [Sec. III, Eq. (78)] The complexity formula in Eq. (78) is garbled: the displayed expression for n should be cleaned up, and the exponent should follow explicitly from ε_n=ε_{n-1}^{5/4} and ℓ_n=17ℓ_{n-1}.
- [Sec. III, Thm. III.1 step (2)] The term 'retroactive definition' is used repeatedly but never formally defined; a precise definition of when and how unspecified matrix elements are chosen would improve the presentation and could clarify the intended repair of the translation step.
- [Sec. III, Lem. III.7] The proof of Lem. III.7 is a sketch: the constant 32∆δ is obtained by adding contributions from four commutators without displaying the second-order terms. Since this lemma is used with ∆=ε^{1/4}, a fully detailed proof would help.
Circularity Check
No significant circularity: the main result is a conditional theorem over an explicitly defined compatible-commutator hypothesis, and the derivation does not reuse its conclusion as an input.
full rationale
The paper's central claim (Thm. III.2) is conditional: given a QSP instruction set that is Π-dense and a compatible commutator satisfying the three properties of Def. III.5, the net-refinement argument yields short approximations. This is a standard theorem-with-hypotheses structure, not a circular reduction: the conclusion is not used to define the hypotheses, and the proof of Lem. III.7 verifies the shrinking property by direct expansion rather than importing it. The concrete symmetric-QSP case is argued in Thm. III.1, where property (1), surjectivity of the nested commutator on balls about the identity, is asserted via Lem. III.8 and the 'retroactive definition' step; this is the weakest point of the paper. In particular, the √(1−x²) factor in Eq. (50) means the leading-order commutator image vanishes at x=±1, so the surjectivity claim needs additional endpoint-moving shifts; the paper acknowledges this and invokes 'shifting by a constant of order ε' in the discussion after Thm. III.1. Whether that repair is valid is a correctness risk, not a circularity: no equation is reused as its own input, no fitted parameter is relabeled as a prediction, and the few self-citations (e.g., [Ros24] for elementary phase-reversal identities) are peripheral and externally checkable algebraic facts. The derivation is therefore self-contained in the sense relevant to this circularity review.
Assumptions & free parameters
assumptions (4)
- domain assumption Standard QSP main theorem (Theorem I.1) characterizing achievable polynomials
- domain assumption Known density of symmetric QSP in the common function space (Remark IV.3)
- standard math Arzela-Ascoli theorem for compactness of function spaces
- ad hoc to paper Existence of a compatible commutator satisfying properties in Definition III.5
invented entities (1)
-
Nested group commutator for QSP protocols
Cite this review
Pith. "Pith review of A Solovay-Kitaev theorem for quantum signal processing." pith.science (2026). https://pith.science/paper/3DMGA5G4
@misc{pith2026250505468,
author = {Pith},
title = {Pith review of: A Solovay-Kitaev theorem for quantum signal processing},
year = {2026},
howpublished = {\url{https://pith.science/paper/3DMGA5G4}},
note = {Machine review of arXiv:2505.05468}
}
read the original abstract
Quantum signal processing (QSP) studies quantum circuits interleaving known unitaries (the phases) and unknown unitaries encoding a hidden scalar (the signal). For a wide class of functions one can quickly compute the phases applying a desired function to the signal; surprisingly, this ability can be shown to unify many quantum algorithms. A separate, basic subfield in quantum computing is gate approximation: among its results, the Solovay-Kitaev theorem (SKT) establishes an equivalence between the universality of a gate set and its ability to efficiently approximate other gates. In this work we prove an 'SKT for QSP,' showing that the density of parameterized circuit ans\"atze in classes of functions implies the existence of short circuits approximating desired functions. This is quite distinct from a pointwise application of the usual SKT, and yields a suite of independently interesting 'lifted' variants of standard SKT proof techniques. Our method furnishes alternative, flexible proofs for results in QSP, extends simply to ans\"atze for which standard QSP proof methods fail, and establishes a formal intersection between QSP and gate approximation.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[3]
[BCK15] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pages 792–809. IEEE,
work page 2015
-
[10]
Quantum signal processing over SU(N)
[Lan24] Lorenzo Laneve. Quantum signal processing over SU(N). arXiv preprint, arXiv:2311.03949 ,
-
[11]
Generalized Quantum Signal Processing and Non-Linear Fourier Transform are equivalent
[Lan25] Lorenzo Laneve. Generalized Quantum Signal Processing and Non-Linear Fourier Transform are equivalent. arXiv preprint, arXiv:2503.03026 ,
-
[13]
[LS24] Guang Hao Low and Yuan Su. Quantum eigenvalue processing. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , page 1051–1062. IEEE,
work page 2024
-
[14]
Comment on "Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle"
[MFM23] Hitomi Mori, Keisuke Fujii, and Kaoru Mizuta. Comment on “Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle”. arXiv preprint arXiv:2310.00918 ,
-
[17]
Fast phase factor finding for quantum signal processing
[NY24] Hongkang Ni and Lexing Ying. Fast phase factor finding for quantum signal processing. arXiv preprint, arXiv:2410.06409,
-
[19]
https://publications.ias.edu/sites/default/files/Letter%20-%20golden%20gates%20march_ 0.pdf. [TLTC23] Andrew K. Tan, Yuan Liu, Minh C. Tran, and Isaac L. Chuang. Error correction of quantum algorithms: Arbitrarily accurate recovery of noisy quantum signal processing. arXiv preprint arXiv:2301.08542 ,
-
[22]
Yoder, Guang Hao Low, and Isaac L
[YLC14] Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang. Fixed-point quantum search with an optimal number of queries. Phys. Rev. Lett., 113(21):210501, 2014
work page 2014
Show all 22 references
-
[1983]
Multivariable QSP and bosonic quantum simulation using iterated quantum signal processing
[GLW24] Niladri Gomes, Hokiat Lim, and Nathan Wiebe. Multivariable QSP and bosonic quantum simulation using iterated quantum signal processing. arXiv preprint, arXiv:2408.03254 ,
-
[1988]
On the length of the shortest non-trivial element in the derived and the lower central series
[ET13] Abdelrhman Elkasapy and Andreas Thom. On the length of the shortest non-trivial element in the derived and the lower central series. arXiv preprint, arXiv:1311.0138 ,
-
[1995]
Martyn, Jasmine Sinanan-Singh, Kevin C
[LMSS+24] Yuan Liu, John M. Martyn, Jasmine Sinanan-Singh, Kevin C. Smith, Steven M. Girvin, and Isaac L. Chuang. Toward mixed analog-digital quantum signal processing: Quantum AD/DA conversion and the Fourier transform. arXiv preprint, arXiv:2408.14729 ,
-
[2002]
Breaking the cubic barrier in the Solovay-Kitaev algorithm
[Kup23] Greg Kuperberg. Breaking the cubic barrier in the Solovay-Kitaev algorithm. arXiv preprint, arXiv:2306.13158,
-
[2011]
On variants of multivariate quantum signal processing and their characterizations
[NKK+23] Bal´ azs N´ emeth, Blanka K¨ ov´ er, Bogl´ arka Kulcs´ ar, Roland Botond Mikl´ osi, and Andr´ as Gily´ en. On variants of multivariate quantum signal processing and their characterizations. arXiv preprint arXiv:2312.09072 ,
-
[2012]
A CS guide to the quantum singular value transformation
[TT23] Ewin Tang and Kevin Tian. A CS guide to the quantum singular value transformation. arXiv preprint arXiv:2302.14324,
-
[2015]
Efficient universal quantum compilation: An inverse-free Solovay- Kitaev algorithm
[BGT21] Adam Bouland and Tudor Giurgica-Tiron. Efficient universal quantum compilation: An inverse-free Solovay- Kitaev algorithm. arXiv preprint, arXiv:2112.02040 ,
-
[2019]
Nonlinear Fourier analysis
[TT12] Terence Tao and Christoph Thiele. Nonlinear Fourier analysis. arXiv preprint, arXiv:1201.5129 ,
-
[2020]
Silva, Mario Berta, and Leandro Aolita
[CWS+24] Santiago Cifuentes, Samson Wang, Thais L. Silva, Mario Berta, and Leandro Aolita. Quantum computa- tional complexity of matrix functions. arXiv preprint, arXiv:2410.13937 ,
-
[2021]
Finding angles for quantum signal processing with machine precision
[CDG+20] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, and Mario Szegedy. Finding angles for quantum signal processing with machine precision. arXiv preprint arXiv:2003.02831 ,
2003 arXiv
-
[2022]
Rossi, Jack L
[RCC23] Zane M. Rossi, Jack L. Ceroni, and Isaac L. Chuang. Modular quantum signal processing in many variables. arXiv preprint, arXiv:2309.16665 ,
-
[2023]
24 They even have a variant of what in standard QSP is solved by the Fej´ er-Riesz lemma [PS98], which Ross and Selinger recognize as a Diophantine equation
23 Limited work has been done in the coherently noisy setting, where QSP can self-correct certain errors [TLTC23]. 24 They even have a variant of what in standard QSP is solved by the Fej´ er-Riesz lemma [PS98], which Ross and Selinger recognize as a Diophantine equation. 37 [...
-
[2024]
Quantum signal processing and nonlinear Fourier analysis
[AMT23] Michel Alexis, Gevorg Mnatsakanyan, and Christoph Thiele. Quantum signal processing and nonlinear Fourier analysis. arXiv preprint, arXiv:2310.12683 ,
-
[2025]
Martyn, Zane M
[MRC+24] John M. Martyn, Zane M. Rossi, Kevin Z. Cheng, Yuan Liu, and Isaac L. Chuang. Parallel quantum signal processing via polynomial factorization. arXiv preprint, arXiv:2409.19043 ,
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.