An adversary bound for quantum signal processing
Lorenzo Laneve · 2025
Read An adversary bound for quantum signal processing by Lorenzo Laneve (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-20484.txt.
Introduction
Lorenzo Laneve finds the exact limits of quantum signal processing through an adversary argument. His twenty twenty-five paper recasts the method, a core trick for turning matrix functions into quantum circuits, as a state conversion task. In that frame, a classic lower-bound tool from query complexity can bite.
The bound matches, precisely, the set of protocols that work in the single-variable case: nothing more, nothing less. The multivariate extension, where several matrices transform at once, has resisted a clean rule. A sharp one-variable yardstick gives that hunt a firm base camp. Quantum algorithm designers learn exactly which polynomial tricks are possible before building them.
Catalog record
| CREATOR | Lorenzo Laneve |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 84 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-20484
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An adversary bound for quantum signal processing Lorenzo Laneve Abstract Quantum signal processing (QSP) and quantum singular value transformation (QSVT), have emerged as unifying frameworks in the context of quantum algorithm design. These techniques allow to carry out efficient polynomial transformations of matrices block-encoded in unitaries, involving a single ancilla qubit. Recent efforts try to extend QSP to the multivariate setting (M-QSP), where multiple matrices are transformed simultaneously. However, this generalization faces problems not encountered in the univariate counterpart: in particular, the class of polynomials achievable by M-QSP seems hard to characterize. In this work we borrow tools from query complexity, namely the state conversion problem and the adversary bound: we first recast QSP as a state conversion problem over the Hilbert space of square-integrable functions. We then show that the adversary bound for a | 0 ⟩ ↦ ( P , Q ) \ket{0}\mapsto(P,Q) state conversion in this space precisely identifies all and only the QSP protocols over S U ( 2 ) SU(2) in the univariate case. Motivated by this result, we extend the formalism to M-QSP: the computation of a M-QSP protocol of minimal space is thus reduced to a rank minimization problem involving the feasible solution space of the adversary bound. 1 Introduction One of the main tasks in quantum computation involves quantum algorithm design: given some computational problem, how can we devise procedures that offer provable speed-up compared to classical models? To solve this task effectively, we need a set of generally applicable techniques that we can combine to construct useful algorithms. For this purpose, many different approaches were proposed throughtout the years including amplitude amplification schemes [ 1 ] , linear combination of unitaries [ 2 , 3 , 4 , 5 ] , phase estimation [ 6 ] , matrix inversion [ 7 ] and quantum walks [ 8 , 9 , 10 , 11 , 12 ] . More recently, a technique called quantum signal processing (QSP) was developed which — along with its lift to the quantum singular value transformation (QSVT) [ 13 ] — was proven to unify and simplify a vast number of the aforementioned techniques and beyond [ 14 , 15 , 16 , 17 , 18 , 19 ] . QSP/QSVT involves the application of a polynomial transformation to matrices that are block-encoded in a unitary. The major advantage of this ansatz is that it requires a single ancilla qubit to work and the class of implementable polynomials implementable gives great freedom. Moreover, numerical algorithms for the computation of QSP protocols starting from a desired transformation are efficient and well-understood [ 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 ] . Notable mentions across the QSP literature include randomized QSP [ 32 ] , parallel QSP [ 33 ] , recursive QSP [ 34 ] , composable QSP [ 35 ] and protocol synthesis through a Solovay-Kitaev-like approximation [ 36 ] . Given the success of QSP, which involves the eigenvalue or singular value transformation of a matrix, recent research tries to generalize the ansatz to multiple signals (we call this multivariate quantum signal processing , or M-QSP [ 37 , 38 , 39 ] ), which in turn allows the joint transformation of multiple matrices. Unfortunately, the flexibility of univariate QSP — in terms of achievable polynomials — does not carry over to more than one variable, and some impossibility results were found [ 40 , 41 ] . Some approaches combine QSP with linear combination of unitaries [ 42 ] , giving up the single-qubit structure, while others go for a modular, bottom-up approach [ 35 , 43 ] , which requires a bit of engineering to achieve a desired transformation — as opposed to the original top-down approach, where the target polynomial can be algorithmically compiled into an implementing protocol. On the other hand, the theory of quantum query complexity is more mature and well-understood: the query complexity, i.e., the number of calls to an oracle needed for an algorithm to solve a certain task — was studied in terms of lower bounds. A first example of the application of this theory is to prove that Grover’s search is optimal [ 44 ] . Two main techniques to derive lower bounds for quantum query complexity include the polynomial method [ 45 , 46 ] and the adversary bound [ 47 , 48 , 49 , 50 , 51 ] . While the former was already used in the context of lower bounds for matrix functions, where QSP/QSVT are protagonists [ 52 ] , the latter was proven to be stronger [ 53 , 54 , 55 ] : in particular, the adversary bound not only constitutes a lower bound, but also gives an upper bound, i.e., from a feasible solution to the adversary bound, one can construct a quantum query algorithm. A central task in the theory of query complexity is state conversion [ 56 , 57 , 58 ] , where we are given one copy of some state \ket{\xi_x} which needs to be converted into some final state \ket{\tau_x} , extracting information on x only from the oracle. In this work we show that (M-)QSP can be seen as an instance of state conversion over the Hilbert space L^{2}(\mathbb{T}^{m}) of m -variate square-integrable functions. In particular, the adversary bound — which already characterizes the original state conversion problem — also characterizes QSP: in the case of univariate single-qubit QSP, we find a perfect correspondence between the feasible solutions of the adversary bound and the SU(2) -QSP protocols, which motivates the use of this formalism to explore M-QSP. Moreover, we find that, for a given desired polynomial transformation P (either univariate or multivariate), the feasible solution space of the adversary bound is a convex set of all the possible protocols implementing P , for which we ideally want to find a minimal-rank solution to optimize space. The remainder of this work is structured as follows: Section 2 is a review of the theory of state conversion over finite label sets, mainly taken from [ 57 , 58 ] , and introduces a new variant called partial state conversion . Section 3 gives an overview of QSP, defining QSP protocols in both univariate and multivariate case. Section 4 is devoted to the merge of these two theories, defining polynomial state conversion and characterizing the structure of the feasible solution space of the corresponding adversary bound. Section 5 concludes with remarks and outlook for future directions. The full technical proofs for Section 4 can be found in Appendix A . 1.1 Preliminaries and notation Given vectors v_{1},v_{2},\ldots,v_{n} , the direct sum can be defined as \displaystyle v_{1}\oplus\cdots\oplus v_{n}:=\sum_{k=0}^{n-1}\ket{k}\ket{v_k}\ . The vectors might be of different lengths, and in this case the second register is taken large enough so that it can contain all the v_{k} ’s. A polynomial vector is a vector whose entries are polynomials or, equivalently, a polynomial whose coefficients are vectors in some Hilbert space \displaystyle v(z)=\sum_{j}P_{j}(z)\ket{j}=\sum_{k}v_{k}z^{k}\ . The vector space \operatorname{span}\{v(z)\}_{z} , which coincides with \operatorname{span}\{v_{k}\}_{k} is the range of v(z) . We call