arXiv:2610.03393
Multivariate quantum signal processing with optimal query complexity
Mingrui Jing, Xin Wang, Zhan Yu, Lei Zhang
Abstract
Polynomial transformations of data encoded in quantum operations are a building block of quantum algorithms, and their query complexity measures how often those operations are used. For multiple variables, existing methods either realize restricted polynomial families or implement monomials separately at a query cost exponential in the number of variables. We present a quantum circuit that implements every multivariate trigonometric polynomial up to an explicit normalization. The circuit processes one variable coherently over the frequency components of the remaining variables, allowing all components to share the same signal queries. Each variable is queried exactly as many times as its degree in the polynomial, and we prove that this query complexity is optimal. We further extend the construction to commuting unitaries. The resulting circuit applies the multivariate polynomial simultaneously across their shared eigenbasis, using the minimum numbers of forward and inverse queries to each unitary. We also study trainable rotations with fixed preparation and a local readout of the last input. At query depth at least two, independent uniform initialization gives every active readout gradient a variance lower bound set by its squared branch weight and the inverse square root of the depth, uniformly over data states and dimensions. For supervised squared loss, retaining sample correlations gives an initialization gradient-variance bound in terms of targets and input spectra. This also bounds the expected loss decrease after the first exact gradient step with a specified step size. These results provide a scalable and practical solution for developing multivariate quantum algorithms and quantum learning models.
AI Summary
The paper asks whether general multivariate polynomial transformations can attain degree-matched query counts. It constructs exact block encodings of trigonometric polynomials with prescribed parity and coefficient norm $\|P\|_{c,1}\leq1$, using exactly $L_j$ plain $R_z(x_j)$ queries per variable. Frequency labels for the first $N-1$ variables coherently control univariate QSP sequences in the last variable, sharing signal queries across branches. With $L_N=\max_jL_j$ and $\ell=\prod_{j<N}(L_j+1)$, the construction uses at most $2(L_N+2)\ell-2$ polynomial-dependent rotation parameters. Exponent bookkeeping proves matching exact-query lower bounds. For commuting unitaries accessed through controlled forward and inverse oracles, the construction implements Laurent polynomials using respectively $\deg_j^+(P)$ and $\deg_j^-(P)$ queries, simultaneously attaining both lower bounds. An appendix characterizes optimal normalization at a fixed scalar-query order by an SDP, with circuit recovery and dual certificates, and exhibits a target whose optimal normalization changes from $1$ to $\sqrt2$ when query order changes. For fixed preparation and a local $Z$ readout, direct two-copy gate averaging gives initialization gradient variance at least $|a_\mu|^4/(64\sqrt{2L_N})$ for every active coordinate when $L_N\geq2$; the depth exponent is sharp. Related squared-loss bounds retain sample correlations. The normalization requirement is stronger than supremum-norm boundedness, and parameter counts remain exponential in variable number for dense polynomials. Unitary inputs must commute. The learning readout depends only on the last input; uniform branch weights produce exponentially small coordinate variances in the number of inputs. Zero-loss convergence requires an additional trajectory-wide Jacobian condition, not established by initialization bounds.
Central claim may not hold: The abstract claims implementation of every multivariate trigonometric polynomial up to normalization, but the stated scalar query model cannot implement mixed-parity targets such as (1+e^{ix/2})/2 at any fixed query count, even after nonzero constant rescaling. The preliminaries incorrectly dismiss parity as a restriction on realizable functions: doubling integer-frequency exponents does not encompass the mixed-parity polynomials included in the paper's definition.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 30 pages including appendix