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

Quantum List Recovery and Decoding: Achievability and Limitations

Fernando Granha Jeronimo, Xiaojuan Ma

Quantum list recovery (QLR) and quantum list decoding (QLD) seek short lists of logically distinct Pauli corrections consistent with a syndrome and prescribed error constraints. For CSS codes, two issues arise: treating the \(X\)- and \(Z\)-sectors separately can multiply their output list sizes, while distinct classical candidates can collapse after stabilizer quotienting. We study combinatorial upper and lower bounds for balanced folded quantum Reed--Solomon (FQRS) codes and balanced random CSS codes, both studied by Bergamaschi, Golowich, and Gunn (STOC 24). Let \(R\in(0,1)\) be the quantum rate and \(R_1=(1+R)/2\) the common component rate. As the radius \(ρ=(1-R)/2-γ\) approaches the quantum Singleton bound, we have, deterministically for FQRS codes and w.h.p. for balanced random CSS codes, \[ L^\star_{\rm QLR} = \ell^{Θ(R_1/γ)}, \qquad L^\star_{\rm QLD} = Θ\!\left(\frac{1-R}γ\right) \qquad (γ\downarrow0). \] The asymptotically exact QLD radius tradeoff is \[ ρ_L^\star = \frac{L}{L+1}\frac{1-R}{2}. \] These conclusions extend to the average-radius setting. For achievability, building on the work of Brakensiek, Chen, Dhar, and Zhang (STOC 2026), we establish a pairing lemma for joint \(X/Z\) candidate lists that preserves the one-sector coefficient and avoids a product loss in list size. For the QLD converse, we prove a quantum generalized Singleton bound based on the classical projection-and-patching argument with stabilizer distinctness. For the QLR lower bounds, we adapt the folded Reed--Solomon construction of Chen and Zhang (STOC 2025) so that the candidates remain stabilizer distinct. For random CSS codes, we show classical bad lists survive the stabilizer quotient with high probability.

quant-pharXiv:2609.40262•Oct 1, 2026•0 citations

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

The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem

Yuhan Liu, Jose Carrasco, Jens Eisert +1 more

In the quest to identify further quantum algorithms exhibiting superpolynomial speed-ups, a recurring theme is that the complexity of a problem is largely shaped by the input access model. Here, we study this phenomenon for the state hidden subgroup problem (StateHSP), a quantum generalization of the hidden subgroup problem in which the goal is to identify the symmetries of an unknown quantum state. For finite abelian groups, existing Fourier-sampling algorithms use $O(\log(|G|)/ε)$ copies of the state, but whether this scaling is optimal has remained open. We settle the complexity of the abelian StateHSP in both the previously studied sample model and a new query model, which is a stronger and operationally natural generalization that provides access to the state-preparation unitary and its inverse. In the query model, we give a time-efficient quantum algorithm using $O(\log(|G/H|)/\sqrtε)$ forward and inverse queries, and prove a matching $Ω(\log(|G/H|)/\sqrtε)$ lower bound which holds even in the stronger conjugate-query and controlled-query settings. By contrast, we show that in the sample model, $Θ(\log(|G/H|)/ε)$ copies are both sufficient and information-theoretically necessary, even if one allows for arbitrary collective measurements. Thus, the quadratic improvement in $ε$ genuinely arises from coherent access to the preparation circuit. As applications, we obtain faster algorithms for learning stabilizer groups, locating unentanglement, and identifying hidden translation symmetries.

quant-pharXiv:2609.35656•Sep 29, 2026•1 citation

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

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

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•1 citation
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.
Quantum list recovery (QLR) and quantum list decoding (QLD) seek short lists of logically distinct Pauli corrections consistent with a syndrome and prescribed error constraints. For CSS codes, two issues arise: treating the XXX- and ZZZ-sectors separately can multiply their output list sizes, while distinct classical candidates can collapse after stabilizer quotienting. We study combinatorial upper and lower bounds for balanced folded quantum Reed--Solomon (FQRS) codes and balanced random CSS codes, both studied by Bergamaschi, Golowich, and Gunn (STOC 24). Let R∈(0,1)R\in(0,1)R∈(0,1) be the quantum rate and R1=(1+R)/2R_1=(1+R)/2R1​=(1+R)/2 the common component rate. As the radius ρ=(1−R)/2−γρ=(1-R)/2-γρ=(1−R)/2−γ approaches the quantum Singleton bound, we have, deterministically for FQRS codes and w.h.p. for balanced random CSS codes, LQLR⋆=ℓΘ(R1/γ),LQLD⋆=Θ ⁣(1−Rγ)(γ↓0). L^\star_{\rm QLR} = \ell^{Θ(R_1/γ)}, \qquad L^\star_{\rm QLD} = Θ\!\left(\frac{1-R}γ\right) \qquad (γ\downarrow0). LQLR⋆​=ℓΘ(R1​/γ),LQLD⋆​=Θ(γ1−R​)(γ↓0). The asymptotically exact QLD radius tradeoff is ρL⋆=LL+11−R2. ρ_L^\star = \frac{L}{L+1}\frac{1-R}{2}. ρL⋆​=L+1L​21−R​. These conclusions extend to the average-radius setting. For achievability, building on the work of Brakensiek, Chen, Dhar, and Zhang (STOC 2026), we establish a pairing lemma for joint X/ZX/ZX/Z candidate lists that preserves the one-sector coefficient and avoids a product loss in list size. For the QLD converse, we prove a quantum generalized Singleton bound based on the classical projection-and-patching argument with stabilizer distinctness. For the QLR lower bounds, we adapt the folded Reed--Solomon construction of Chen and Zhang (STOC 2025) so that the candidates remain stabilizer distinct. For random CSS codes, we show classical bad lists survive the stabilizer quotient with high probability.
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.
In the quest to identify further quantum algorithms exhibiting superpolynomial speed-ups, a recurring theme is that the complexity of a problem is largely shaped by the input access model. Here, we study this phenomenon for the state hidden subgroup problem (StateHSP), a quantum generalization of the hidden subgroup problem in which the goal is to identify the symmetries of an unknown quantum state. For finite abelian groups, existing Fourier-sampling algorithms use O(log⁡(∣G∣)/ε)O(\log(|G|)/ε)O(log(∣G∣)/ε) copies of the state, but whether this scaling is optimal has remained open. We settle the complexity of the abelian StateHSP in both the previously studied sample model and a new query model, which is a stronger and operationally natural generalization that provides access to the state-preparation unitary and its inverse. In the query model, we give a time-efficient quantum algorithm using O(log⁡(∣G/H∣)/ε)O(\log(|G/H|)/\sqrtε)O(log(∣G/H∣)/ε​) forward and inverse queries, and prove a matching Ω(log⁡(∣G/H∣)/ε)Ω(\log(|G/H|)/\sqrtε)Ω(log(∣G/H∣)/ε​) lower bound which holds even in the stronger conjugate-query and controlled-query settings. By contrast, we show that in the sample model, Θ(log⁡(∣G/H∣)/ε)Θ(\log(|G/H|)/ε)Θ(log(∣G/H∣)/ε) copies are both sufficient and information-theoretically necessary, even if one allows for arbitrary collective measurements. Thus, the quadratic improvement in εεε genuinely arises from coherent access to the preparation circuit. As applications, we obtain faster algorithms for learning stabilizer groups, locating unentanglement, and identifying hidden translation symmetries.
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.
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
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.