Quantum Algorithms for Multivariable Polynomial Transformations: From Efficient Synthesis to Quantum Channel Transformations
Abstract
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.
Related
- Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability
- Polynomial-time classical algorithms for mean-field models up to the glass transition
- Quantum algorithms for orthogonal polynomial transforms
- Efficient Eccentric Effective-One-Body Dynamics via Near-Identity Averaging Transformations
- Efficient Eccentric and Quasicircular Effective-One-Body Waveforms via Near-Identity Averaging Transformations
BibTeX
@misc{shen2026quantum,
title = {{Quantum Algorithms for Multivariable Polynomial Transformations: From Efficient Synthesis to Quantum Channel Transformations}},
author = {Zheyu Shen and Yusen Wu and Xiao Yuan and Xiao-Ming Zhang and Yukun Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08714},
eprint = {2610.08714},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08714},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Algorithms for Multivariable Polynomial Transformations: From Efficient Synthesis to Quantum Channel Transformations
AU - Zheyu Shen
AU - Yusen Wu
AU - Xiao Yuan
AU - Xiao-Ming Zhang
AU - Yukun Zhang
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08714
UR - https://arxiv.org/abs/2610.08714
AB - 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={K_a}_a, we synthesize any finite jointly contractive family of noncommutative polynomial maps K↦{F_b(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.
ER -