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.
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.
Polynomial transformations are basic primitives in quantum algorithms: quantum signal processing and singular value transformation compile univariate polynomials into circuits with query complexity essentially set by degree. Multivariable transformations of noncommuting matrices, however, lack a comparable synthesis theory. We develop a complete constructive theory under joint block access for all polynomials contractive on the prescribed matrix domain. Given a compact finite-state description of a degree-D polynomial P and 0<τ<1, we synthesize P with (1+τ)-optimal normalization using O(D/τ) queries, and exactly D under row-block access, matching a degree lower bound. The complete circuit realization is classically computable in polynomial time with polylogarithmic dependence on accuracy. The key to our construction is a finite algorithmic Schur--Agler theorem: the coefficient recurrence defines a polynomial-dimensional continuation space supporting a complete semidefinite certificate for contractivity on the prescribed domain. Factoring this certificate yields the contractive realization underlying the query algorithm.
Beyond matrix transformations, our framework lifts multivariable polynomial synthesis to quantum channel transformations. Given coherent Kraus access K={Ka}a, we synthesize any finite jointly contractive family of noncommutative polynomial maps K↦{Fb(K)}b as completely positive operations, allowing coherent interference among Kraus histories. Furthermore, channel-level transformations specified by causal Choi data can be synthesized explicitly as fixed-order quantum combs. Collectively, these results point to a broader program: multivariable approximation as a language for multi-operator quantum algorithms and higher-order quantum information processing.
We develop Multivariate Quantum Signal Processing for designing matrix-valued transformations of multiple noncommuting nonnormal block-encoded matrices. Our framework equips quantum transducers with the analytic structure of multiport Infinite-Impulse-Response (IIR) filters and establishes a transfer-function methodology for designing quantum query algorithms. Efficiently computable analytic bounds that hold uniformly across the oracle promise yield efficient quantum circuits with logarithmic error dependence and near-unity success probability, paralleling the approximation-theoretic guarantees of univariate QSP/QSVT. We provide a complete characterization of achievable transfer functions and a principled library of analytic IIR components. Our modular designs greatly improve or resolve the per-oracle query complexity of open multi-oracle problems: (1) Hamiltonian simulation under H=∑jHj with weighted quasinorm cost ≈t⟨λ,C⟩1/2+O(∥C∥1log(1/ε)) for block-encoding normalizations λ and costs C; (2) sparse simulation with optimal time--norm Θ(d∥H∥1→2t) and additive error dependence; (3) solving linear systems and (4) differential equations under minimal matrix assumptions with optimal weighted state-preparation and multi-term cost; (5) ground-state preparation and energy estimation; (6) generalized eigenvalue problems. We apply these to exactly simulate downfolded Hamiltonians with leading cost t⟨λeff,Ceff⟩1/2 further reduced by fractional dynamic correlation energy contributions from coarse-grained Hamiltonians, and show similar classical-data-input-reduction results for multiscale graph classification via Kron reduction. We also show the online generalization with anisotropic Kalman filtering of streaming quantum data.
We achieve query-optimal quantum simulations of non-Hermitian Hamiltonians Heff=HR+iHI, where HR is Hermitian and HI⪰0, using a bivariate extension of quantum signal processing (QSP) with non-commuting signal operators. The algorithm encodes the interaction-picture Dyson series as a polynomial on the bitorus, implemented through a structured multivariable QSP (M-QSP) circuit. A constant-ratio condition guarantees scalar angle-finding for M-QSP circuits with arbitrary non-commuting signal operators. A degree-preserving sum-of-squares spectral factorization permits scalar complementary polynomials in two variables. Angles are deterministically calculated in a classical precomputation step, running in O(dR⋅dI) classical operations. Operator norms αR,βI contribute additively with query complexity O((αR+βI)T+log(1/ε)/loglog(1/ε)) matching an information-theoretic lower bound in the separate-oracle model, where HR and HI are accessed through independent block encodings. The postselection success probability is e−2βIT∥e−iHeffT∣ψ0⟩∥2⋅(1−O(ε)), decomposing into a state-dependent factor ∥e−iHeffT∣ψ0⟩∥2 from the intrinsic barrier and an e−2βIT overhead from polynomial block-encoding.
In the absence of error correction, noisy intermediate-scale quantum devices are operated by training parametrized quantum circuits (PQCs) so as to minimize a suitable loss function. Finding the optimal parameters of those circuits is a hard optimization problem, where global guarantees are known only for highly structured cases of limited practical relevance, and first-order methods can fail to find even local minima due to the presence of barren plateaus. In this work, we study the training of practical classes of PQCs, namely polynomial-depth circuits with a constant number of trainable parameters. This captures widely used PQC families, including fixed-depth QAOA, hardware-efficient ansätze, and Fixed Parameter Count QAOA. Our main technical result is a fully polynomial randomized approximation scheme (FPRAS), which, for every ε>0, returns an ε-approximate solution to the problem's global optimum with high probability, and has runtime and query complexity polynomial in 1/ε and the number of qubits. Unlike the standard hybrid quantum-classical training loop in variational algorithms, where the quantum device is queried repeatedly throughout the training, our approach separates the computation into two distinct stages: (1) an initial quantum data-acquisition phase, followed by (2) a classical global-optimization phase based on the trigonometric moment/sum-of-squares hierarchies. Under a standard flat-extension condition, which can be checked numerically, the method also supports the extraction of optimal circuit parameters. The existence of an FPRAS implies that the promise problem associated with the optimization of poly-depth constant-parameter PQC is in BQP. This imposes a limitation on the expressive power of the class, namely, it cannot encode combinatorial optimization problems whose objective values are separated by an inverse-polynomial gap.
Multivariate quantum signal processing (M-QSP) has recently been shown to be applicable for non-Hermitian Hamiltonian simulation, opening several problems regarding the optimization landscape, angle-finding, and constant-factor analysis. We resolve several of these problems here. We find the anti-Hermitian query complexity $d_I = Θ(\betaI T + \log(1/\varepsilon)/\log\log(1/\varepsilon))$ to be tight, established via Chebyshev coefficient bounds, modified Bessel function asymptotics, and Lambert~W inversion. Fast-forwarding to $d_I = \mathcal{O}(\sqrt{\betaI T})$ is impossible in the bivariate polynomial model, though a linear state-dependent improvement to dI=OβeffT+log(1/ε)/loglog(1/ε)) is achievable. The optimization landscape of M-QSP admits spurious local minima, but a warm-start basin guarantee ensures the two-stage algorithm converges. CRC-exploiting block peeling reduces angle-finding from O(d3) to O(d2) classical operations, and optimized error allocation yields a leading constant of approximately~2 relative to the information-theoretic lower bound. A constant-ratio condition extends to non-identical signal operators, enabling time-dependent non-Hermitian simulation with query complexity $\mathcal{O}(\int_0^T(\alphaR(s) + \betaI(s))\,ds + \log(1/\varepsilon)/\log\log(1/\varepsilon))$. Block-encoding overhead $e^{-2\betaI T}$ holds across all function classes within the walk-operator oracle model, and dilational methods (Schrödingerization) achieve the walk-operator barrier. A precisely characterized direct-access construction achieves the intrinsic barrier e−2ωT (with $ω< \betaI$ for non-commuting Hamiltonians) on a restricted domain, though extension to the full bitorus remains open.
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 state conversion problem in this space precisely identifies all and only the QSP protocols in the univariate case. Motivated by this first result, we extend the formalism to several variables: the existence of a feasible solution to the adversary bound implies the existence of a M-QSP protocol, and the computation of a protocol of minimal space is reduced to a rank minimization problem involving the feasible solution space of the adversary bound.