Skip to content
Preprint

Quantum Algorithms for Multivariable Polynomial Transformations: From Efficient Synthesis to Quantum Channel Transformations

Oct 2026 · 0 citations
Physics

TL;DR

The framework lifts multivariable polynomial synthesis to quantum channel transformations, and synthesizes any finite jointly contractive family of noncommutative polynomial maps as completely positive operations, allowing coherent interference among Kraus histories.

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<\tau<1$, we synthesize $P$ with $(1+\tau)$-optimal normalization using $O(D/\sqrt{\tau})$ 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\mapsto\{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.

View source

Similar papers

Preprint Oct 2026

Quantum algorithms for orthogonal polynomial transforms

A quantum orthogonal polynomial transform (QOPT) is an algorithmic primitive that maps a superposition of standard basis states $\sum_k \alpha_{k} \ket{k}$ coherently to a basis of normalized univariate polynomials orthogonal with respect to a probability measure $\mu(x)$. We provide new discrete and continuous QOPTs f...

A. Prakash, S. Sureshbabu, Dylan Herman et al. · 0 citations
Preprint Oct 2026

Multivariate Quantum Signal 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 methodolo...

Guang Hao Low · 0 citations
Preprint Sep 2026

Resource-Tunable Quantum Circuit Implementation of Nonlinear Element-Wise Transformations

Nonlinear transformations are important in quantum machine learning and other quantum numerical applications, which can be reduced to the implementation of element-wise polynomials through polynomial approximation. Existing works establish the feasibility of transformations and improve query or auxiliary-space efficien...

Chun-Lin Yang, Yu-Qi Li, Hong-Mei Yao et al. · 0 citations
Preprint Oct 2026

Multivariate quantum signal processing with optimal query complexity

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 e...

Ming-Rui Jing, Xin Wang, Zhan Yu et al. · 0 citations
Preprint Sep 2026

From Simple Sources to Quantum Advantage: Homomorphic Polynomial Transduction via Relative Decoding

Decoded quantum interferometry (DQI) and its Hamiltonian extension (HDQI) prepare states whose amplitudes are low-degree polynomials of an objective, using Fourier transforms and coherent decoding. We recast and generalize this approach as quantum state transduction through algebra homomorphisms. We transfer an efficie...

Zhong-Xia Shang, Daniel Stilck França · 0 citations
Preprint Oct 2026

The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight

Quantum algorithms for linear algebra that access a matrix $A$ through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems. Dequantized classical algorithms, when given sampling and query access to $A$, return sampling and query access to an ap...

Shouvanik Chakrabarti, Dylan Herman, J. Kim et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.