arXiv:2609.35101
From Simple Sources to Quantum Advantage: Homomorphic Polynomial Transduction via Relative Decoding
Zhong-Xia Shang, Daniel Stilck França
Abstract
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 this approach as quantum state transduction through algebra homomorphisms. We transfer an efficiently preparable operator state of a degree-$D$ polynomial in a source Hamiltonian $H_A$ to the corresponding polynomial state of a target Hamiltonian $H_B=π(H_A)$, where $π$ is a unital $*$-homomorphism between the finite-dimensional source and target $C^*$-algebras. The transduction uses operator Fourier transforms and relative decoding to recover source operators rather than individual term-selection labels. The relative distance $d_{\mathrm{rel}}$ is the first degree at which source and target traces disagree. We prove that $2D<d_{\mathrm{rel}}$ is equivalent to preserving all inner products between degree-$D$ polynomials. Moreover, $d_{\mathrm{rel}}\ge d_{\mathrm{ord}}$, where $d_{\mathrm{ord}}$ is the ordinary distance used in (H)DQI, and we give families with $d_{\mathrm{ord}}=O(1)$ but $d_{\mathrm{rel}}=Θ(n)$ and efficient decoders. Our framework replaces the complicated pilot state preparation by the more modular task of preparing a source polynomial state. DQI and HDQI arise as relation-free special cases. The framework accommodates nonuniform coefficients and noncommuting interactions and extends to fermionic, qudit, and bosonic systems, with applications to approximate optimization and Gibbs sampling. As evidence of advantages, for a nonlinear pairwise variant of optimal polynomial intersection where constant $d_{\mathrm{ord}}$ limits DQI-style preparations, relative decoding yields an ideal quantum score of 0.643 versus 0.606 for the best tested classical heuristic, a gap exceeding 3 percentage points.
AI Summary
Decoded quantum interferometry (DQI) prepares polynomially filtered objective states using Fourier transforms and coherent decoding. This paper asks how to extend this mechanism when marked interaction terms satisfy relations that obstruct ordinary term-selection decoding. It formulates polynomial-state transfer from a source algebra to a target algebra through a unital $*$-homomorphism $\pi$, replacing recovery of term-selection labels with recovery of the source operator they represent. The relative distance $d_{\mathrm{rel}}$ is the first marked degree at which source and target normalized traces disagree. A word-splitting argument proves that $2D<d_{\mathrm{rel}}$ is equivalent to preserving every inner product between degree-$D$ operators. With compatible operator bases, efficient source-state preparation, Fourier transforms, label maps, and relative decoding, a four-step circuit deterministically transfers polynomial states. Explicit constructions have $d_{\mathrm{ord}}=O(1)$ but $d_{\mathrm{rel}}=\Theta(n)$ with efficient decoders. The framework includes optimization and Gibbs-state preparation, with Majorana and Weyl formulations for fermions, qudits, and finite bosonic encodings. For a nonlinear pairwise variant of optimal polynomial intersection, Reed–Solomon decoding supports degree-$D$ guides when $4D\le n$; a tridiagonal eigenproblem determines their optimal mean score when $4D+2\le n$. At $p=2053$, $n=205$, and $D=50$, the ideal quantum mean is $0.64313$, versus a classical benchmark median of $0.60666$ after roughly $5\times10^6$ candidates per deep run. This is not a classical lower bound or hardware demonstration. Efficient source preparation and decoding remain separate requirements; low-degree target expectations are already source-accessible, and particle-number postselection can dominate some implementations.
The same models were also used for proofreading. We used ChatGPT 6 Astra to find the nonlinear-chain example in Section~\ref{sec:applications} and ChatGPT 5.6 Sol to code the benchmarks.
Error found: The abstract states d_rel ≥ d_ord without qualification, although the body's comparison requires an additional scalar-or-traceless-words assumption and the inequality can fail for general represented finite-dimensional C*-algebra quotients.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 84 pages, 1 figure, comments are welcome!