Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Translation-invariant Fourier covariance and path-correlated codeword search

Sungsoo Na

Published Sep 12, 2026• 0 citations
Publisher

Abstract

Translation-invariant second moments on a finite abelian group have diagonal Fourier spectrum. We observe that this standard diagonalization equates the expected coherent bad mass after subgroup addition with the ordinary bad mass, for any fixed subgroup and bad-error set. The identity applies to translation-equivariant ensembles generated by local constraints, independently of the constraint graph. We apply it to path-correlated codeword search for folded Reed-Solomon codes under an independent-row, exactly half-balanced random bit oracle. For every integer λ ≥ λ0 := 3604, a uniform quantum circuit uses exactly 2(n − 1) queries to the same bit oracle available classically, poly(λ) gates and qubits, and exact finite-gate synthesis. Its average success is at least 1 − 4bλ, while every adaptive classical strategy making at most ⌊2λ1/4⌋ queries has success at most e−n/2000; here n = 2⌊log2 λ⌋ − 1 and bλ ≤ 3e−n/800. Conditioning on an explicit event of probability at least 1 − 2√bλ yields a worst-case bounded-error promise separation. The algorithmic framework and general decoding comparison are those of Yamakawa-Zhandry. The path application supplies the correlated error law, adaptive pair-query bound, and resource assembly. Complexity is measured in unary λ; complete algorithms and lower bounds for general constraint graphs remain open. MSC 2020: 81P68; 68Q12; 94B35. The package contains the paper PDF, LaTeX source, vector figures, figure data, resource ledger, and checksums.

DOI
10.5281/zenodo.22715703

Related papers

Graph-correlated codeword search: A technical note in the random-oracle model

Sungsoo Na

We extend Yamakawa-Zhandry codeword search to graph-correlated predicates in one iid bit oracle. Sequential preparation replaces independent-coordinate preparation; classical list recovery counts active vertices. The scalar theorem has jointly polynomial quantum cost and exp(Ω(λ/log λ)) classical queries for fixed parameters. A folded-dual block refinement replaces the squared-rate restriction by a linear-rate margin, improving the sufficient cutoff and real cap exponent. Its full cost is λO(D+1) poly(Lin+|Γ|), polynomial for fixed degree D; jointly polynomial growing-D time remains open, and its cutoff-boundary classical cap is polynomial. Large-alphabet normalization is a small-error check. These are purely asymptotic results. MSC 2020: 68Q12, 68Q17, 94B35. The accompanying package contains the manuscript source, figures, and integrity manifests.

•Sep 14, 2026•0 citations

Single-Query Exact Discrimination of Phase-Modified Permutation Oracles

Owen Root

Abstract I consider a promise problem for an unknown unitary acting on an \((n)\)-qubit register. The oracle is promised to implement either a fixed permutation of computational basis states or the same permutation accompanied by a conditional sign change determined by a designated input qubit. I show that the two cases can be distinguished exactly with a single query to the oracle and a measurement on only one qubit, and that the query complexity of this task is exactly one. The protocol uses no ancilla qubits and requires only \((n+1)\) Hadamard gates in addition to the oracle call. The promise is intrinsically quantum because the two cases differ only through relative phases. MSC Classification: 81P68 , 68Q12

•Oct 14, 2026•0 citations

Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability

Seyoon Ragavan, Noah Shutty

Regev's reduction quantumly finds codewords satisfying nonlinear constraints by decoding the dual code. To date, applications that have not been dequantized have relied on efficient classical decoders and coordinate-wise constraints. We overcome these restrictions separately. Our first contribution uses a quantum decoder to find solutions $\mathbf{y}\in(\mathbb{F}_q\setminus\{0\})^m$ to $\mathbf{B}\mathbf{y}=0$, where $\mathbf{B}\in\mathbb{F}_q^{n\times m}$. For fixed prime $q>2$, Chen, Liu, and Zhandry solve this problem for random matrices with $m=Ω(n^2)$, a regime now covered by classical algorithms. We adapt their template to codes (spanned by the rows of $\mathbf{B}$) that satisfy a "two-fold multiplication property": the coordinate-wise products of pairs of codewords span a space of dimension smaller than $m$. Under suitable distance conditions, this allows us to solve instances with $m\leq n^{2-Ω(1)}$, beyond the established guarantees of classical algorithms. We also give an efficient classical algorithm under a stronger three-fold multiplication property, leaving intermediate regimes as candidates for quantum advantage. For Reed-Muller codes punctured at random points, our algorithm finds a word in the unpunctured dual code supported exactly on those points. This works beyond known efficient classical decoding regimes. Our second contribution retains classical decoding but allows global constraints on symbol frequencies. We study "histogram-local" constraints, which specify the allowed numbers of occurrences of each symbol. For broad families, stability under resampling one coordinate yields efficient quantum algorithms for variants of optimal polynomial intersection (OPI) combining coordinate-wise and histogram-local constraints. Adapting Yamakawa-Zhandry, we prove a quantum-classical separation for these problems relative to a classical random oracle.

quant-pharXiv:2610.00502•Oct 2, 2026•0 citations

Pixel-Translation-Equivariant Quantum Convolutional Neural Networks via Fourier Multiplexers

Dmitry Chirkov, Igor Lobanov

Convolutional neural networks owe much of their success to hard-coding translation equivariance. Quantum convolutional neural networks (QCNNs) have been proposed as near-term quantum analogues, but the relevant notion of translation depends on the data encoding. For address/amplitude encodings such as FRQI, a pixel shift acts as modular addition on an index register, whereas many MERA-inspired QCNNs are equivariant only under cyclic permutations of physical qubits. We formalize this mismatch and construct QCNN layers that commute exactly with the pixel cyclic shift (PCS) symmetry induced by the encoding. Our main technical result is a constructive characterization of all PCS-equivariant unitaries: conjugation by the quantum Fourier transform (QFT) diagonalizes translations, so any PCS-equivariant layer is a Fourier-mode multiplexer followed by an inverse QFT (IQFT). Building on this characterization, we introduce a deep PCS-QCNN with measurement-induced pooling, deferred conditioning, and inter-layer QFT cancellation. We also analyze trainability at random initialization and prove a lower bound on the expected squared gradient norm that remains constant in a depth-scaling regime, ruling out a depth-induced barren plateau in that sense.

quant-pharXiv:2604.06094•Apr 8, 2026•0 citations

Exchange Realization of Relational Coherence: Exact Synthesis and Resource Bounds

Qingchun Zhang

This preprint studies a cycle-reflection operation on a supplied six-qubit realization of paired trigram configurations. A four-matched-pulse identity and a minimum within its stated serial grammar are separated from an ordinary-exchange endpoint construction. The raw full-source reflection and its full domain-safe alternative are different tasks: the latter is excluded by a collective-symmetry obstruction in the admitted source-only exchange model. Strict preservation of the addressable sector throughout the path is also excluded for the full task, while finite-action lower bounds quantify peak no-address population and time-integrated exposure. The paper presents an explicit low-excursion balanced word and a conditional joint clock–amplitude error certificate. Root settings and trajectory inputs remain tied to their supplied computer-assisted certificates. The second internal review reproduced all ten advertised numerical routes and twenty-four outputs using the original programs; this is same-program reproducibility, not independent implementation or external peer review. A separate Lean supplement covers the finite raw/safe operator algebra and the obstruction for arbitrary finite words of the declared algebraic factors. It does not formalize the numerical roots, matrix exponentials, continuous-time dynamics or resource theorems. No global pulse optimum, measured hardware feasibility, general noise tolerance, or automatic connection to the companion recovery code is claimed.

•Sep 10, 2026•0 citations

Efficient Exact Quantum Sampling from the Sun-Wootters Distribution for Optimal Polynomial Intersection

Sunghyeon Jo

Optimal Polynomial Intersection (OPI) is a structured optimization problem for which Decoded Quantum Interferometry (DQI) attains a satisfaction guarantee governed by the semicircle law. Sun and Wootters recently showed that, for balanced OPI over prime fields, a Fourier-defined distribution $P_u$ gives a strict worst-case improvement from limiting rate $0.6225$ onward and asymptotically perfect solutions from rate $0.7496$ onward, and asked whether $P_u$ can be sampled efficiently. We answer this question for Reed--Solomon OPI parameters satisfying their exponent condition strictly below the dual Johnson radius. Under coherent membership-oracle access, we give a bounded-error polynomial-time quantum sampler for $P_u$. The ideal circuit samples $P_u$ exactly conditioned on success, while a finite-precision implementation achieves any prescribed inverse-polynomial total-variation error. Consequently, every fixed limiting rate $0.6225\le r<1$ admits a strict worst-case improvement over the DQI semicircle value, and every limiting rate $r\ge 3/4$ admits solutions of satisfaction $1-o(1)$ with high probability. The algorithm coherently sums the amplitudes of all low-weight errors in each syndrome class using deterministic complete list decoding. Complete Reed--Solomon list decoding and the Sun--Wootters denominator estimate make the list size and postselection overhead polynomial. In concurrent and independent work, Horinaga and Yamakawa obtain worst-case OPI algorithms over prime-power fields and exact satisfaction at every fixed rate strictly above $3/4$.

quant-pharXiv:2607.16541•Jul 21, 2026•0 citations
Translation-invariant second moments on a finite abelian group have diagonal Fourier spectrum. We observe that this standard diagonalization equates the expected coherent bad mass after subgroup addition with the ordinary bad mass, for any fixed subgroup and bad-error set. The identity applies to translation-equivariant ensembles generated by local constraints, independently of the constraint graph. We apply it to path-correlated codeword search for folded Reed-Solomon codes under an independent-row, exactly half-balanced random bit oracle. For every integer λ ≥ λ0 := 3604, a uniform quantum circuit uses exactly 2(n − 1) queries to the same bit oracle available classically, poly(λ) gates and qubits, and exact finite-gate synthesis. Its average success is at least 1 − 4bλ, while every adaptive classical strategy making at most ⌊2λ1/4⌋ queries has success at most e−n/2000; here n = 2⌊log2 λ⌋ − 1 and bλ ≤ 3e−n/800. Conditioning on an explicit event of probability at least 1 − 2√bλ yields a worst-case bounded-error promise separation. The algorithmic framework and general decoding comparison are those of Yamakawa-Zhandry. The path application supplies the correlated error law, adaptive pair-query bound, and resource assembly. Complexity is measured in unary λ; complete algorithms and lower bounds for general constraint graphs remain open. MSC 2020: 81P68; 68Q12; 94B35. The package contains the paper PDF, LaTeX source, vector figures, figure data, resource ledger, and checksums.
We extend Yamakawa-Zhandry codeword search to graph-correlated predicates in one iid bit oracle. Sequential preparation replaces independent-coordinate preparation; classical list recovery counts active vertices. The scalar theorem has jointly polynomial quantum cost and exp(Ω(λ/log λ)) classical queries for fixed parameters. A folded-dual block refinement replaces the squared-rate restriction by a linear-rate margin, improving the sufficient cutoff and real cap exponent. Its full cost is λO(D+1) poly(Lin+|Γ|), polynomial for fixed degree D; jointly polynomial growing-D time remains open, and its cutoff-boundary classical cap is polynomial. Large-alphabet normalization is a small-error check. These are purely asymptotic results. MSC 2020: 68Q12, 68Q17, 94B35. The accompanying package contains the manuscript source, figures, and integrity manifests.
Abstract I consider a promise problem for an unknown unitary acting on an (n)(n)(n)-qubit register. The oracle is promised to implement either a fixed permutation of computational basis states or the same permutation accompanied by a conditional sign change determined by a designated input qubit. I show that the two cases can be distinguished exactly with a single query to the oracle and a measurement on only one qubit, and that the query complexity of this task is exactly one. The protocol uses no ancilla qubits and requires only (n+1)(n+1)(n+1) Hadamard gates in addition to the oracle call. The promise is intrinsically quantum because the two cases differ only through relative phases. MSC Classification: 81P68 , 68Q12
Regev's reduction quantumly finds codewords satisfying nonlinear constraints by decoding the dual code. To date, applications that have not been dequantized have relied on efficient classical decoders and coordinate-wise constraints. We overcome these restrictions separately. Our first contribution uses a quantum decoder to find solutions y∈(Fq∖{0})m\mathbf{y}\in(\mathbb{F}_q\setminus\{0\})^my∈(Fq​∖{0})m to By=0\mathbf{B}\mathbf{y}=0By=0, where B∈Fqn×m\mathbf{B}\in\mathbb{F}_q^{n\times m}B∈Fqn×m​. For fixed prime q>2q>2q>2, Chen, Liu, and Zhandry solve this problem for random matrices with m=Ω(n2)m=Ω(n^2)m=Ω(n2), a regime now covered by classical algorithms. We adapt their template to codes (spanned by the rows of B\mathbf{B}B) that satisfy a "two-fold multiplication property": the coordinate-wise products of pairs of codewords span a space of dimension smaller than mmm. Under suitable distance conditions, this allows us to solve instances with m≤n2−Ω(1)m\leq n^{2-Ω(1)}m≤n2−Ω(1), beyond the established guarantees of classical algorithms. We also give an efficient classical algorithm under a stronger three-fold multiplication property, leaving intermediate regimes as candidates for quantum advantage. For Reed-Muller codes punctured at random points, our algorithm finds a word in the unpunctured dual code supported exactly on those points. This works beyond known efficient classical decoding regimes. Our second contribution retains classical decoding but allows global constraints on symbol frequencies. We study "histogram-local" constraints, which specify the allowed numbers of occurrences of each symbol. For broad families, stability under resampling one coordinate yields efficient quantum algorithms for variants of optimal polynomial intersection (OPI) combining coordinate-wise and histogram-local constraints. Adapting Yamakawa-Zhandry, we prove a quantum-classical separation for these problems relative to a classical random oracle.
Convolutional neural networks owe much of their success to hard-coding translation equivariance. Quantum convolutional neural networks (QCNNs) have been proposed as near-term quantum analogues, but the relevant notion of translation depends on the data encoding. For address/amplitude encodings such as FRQI, a pixel shift acts as modular addition on an index register, whereas many MERA-inspired QCNNs are equivariant only under cyclic permutations of physical qubits. We formalize this mismatch and construct QCNN layers that commute exactly with the pixel cyclic shift (PCS) symmetry induced by the encoding. Our main technical result is a constructive characterization of all PCS-equivariant unitaries: conjugation by the quantum Fourier transform (QFT) diagonalizes translations, so any PCS-equivariant layer is a Fourier-mode multiplexer followed by an inverse QFT (IQFT). Building on this characterization, we introduce a deep PCS-QCNN with measurement-induced pooling, deferred conditioning, and inter-layer QFT cancellation. We also analyze trainability at random initialization and prove a lower bound on the expected squared gradient norm that remains constant in a depth-scaling regime, ruling out a depth-induced barren plateau in that sense.
This preprint studies a cycle-reflection operation on a supplied six-qubit realization of paired trigram configurations. A four-matched-pulse identity and a minimum within its stated serial grammar are separated from an ordinary-exchange endpoint construction. The raw full-source reflection and its full domain-safe alternative are different tasks: the latter is excluded by a collective-symmetry obstruction in the admitted source-only exchange model. Strict preservation of the addressable sector throughout the path is also excluded for the full task, while finite-action lower bounds quantify peak no-address population and time-integrated exposure. The paper presents an explicit low-excursion balanced word and a conditional joint clock–amplitude error certificate. Root settings and trajectory inputs remain tied to their supplied computer-assisted certificates. The second internal review reproduced all ten advertised numerical routes and twenty-four outputs using the original programs; this is same-program reproducibility, not independent implementation or external peer review. A separate Lean supplement covers the finite raw/safe operator algebra and the obstruction for arbitrary finite words of the declared algebraic factors. It does not formalize the numerical roots, matrix exponentials, continuous-time dynamics or resource theorems. No global pulse optimum, measured hardware feasibility, general noise tolerance, or automatic connection to the companion recovery code is claimed.
Optimal Polynomial Intersection (OPI) is a structured optimization problem for which Decoded Quantum Interferometry (DQI) attains a satisfaction guarantee governed by the semicircle law. Sun and Wootters recently showed that, for balanced OPI over prime fields, a Fourier-defined distribution PuP_uPu​ gives a strict worst-case improvement from limiting rate 0.62250.62250.6225 onward and asymptotically perfect solutions from rate 0.74960.74960.7496 onward, and asked whether PuP_uPu​ can be sampled efficiently. We answer this question for Reed--Solomon OPI parameters satisfying their exponent condition strictly below the dual Johnson radius. Under coherent membership-oracle access, we give a bounded-error polynomial-time quantum sampler for PuP_uPu​. The ideal circuit samples PuP_uPu​ exactly conditioned on success, while a finite-precision implementation achieves any prescribed inverse-polynomial total-variation error. Consequently, every fixed limiting rate 0.6225≤r<10.6225\le r<10.6225≤r<1 admits a strict worst-case improvement over the DQI semicircle value, and every limiting rate r≥3/4r\ge 3/4r≥3/4 admits solutions of satisfaction 1−o(1)1-o(1)1−o(1) with high probability. The algorithm coherently sums the amplitudes of all low-weight errors in each syndrome class using deterministic complete list decoding. Complete Reed--Solomon list decoding and the Sun--Wootters denominator estimate make the list size and postselection overhead polynomial. In concurrent and independent work, Horinaga and Yamakawa obtain worst-case OPI algorithms over prime-power fields and exact satisfaction at every fixed rate strictly above 3/43/43/4.