Random linear codes over finite fields satisfy near-optimal discrepancy properties, enabling list-decoding and zero-error list-recovery above capacity that match random codes.
Verifiable quantum advantage via optimized dqi circuits
13 Pith papers cite this work. Polarity classification is still indexing.
13
Pith papers citing it
citation-role summary
background 3
citation-polarity summary
years
2026 13roles
background 3polarities
background 3representative citing papers
Multivariate DQI uses N-variable polynomials for weighted Max-LINSAT, derives closed-form asymptotics for expectation and concentration, provides a single-decoder preparation circuit, and shows outperformance over weighted Prange for some OPI cases while extending to Hamiltonian DQI.
Existence of asymptotically better solutions than the semicircle law for worst-case OPI over prime fields when n/m exceeds thresholds like 0.6225 for rho approximately 1/2, via connection to local leakage resilience of secret sharing.
Optimal affine filtering measurements for group-covariant pure-state codewords reduce to an LP, and SPC-based affine-filtering+GE decoding can outperform symbol-wise USD and PGM on i.i.d. pure-state channels.
Locally-quantum decoding of LDPC codes under coherent bit-flip superpositions outperforms BP and sometimes Prange/SA on Gallager max-k-XORSAT, but an enhanced Prange algorithm ties it.
Extends NP-hardness of exceeding r/q + O(1/sqrt(D)) for bounded-degree max-Ek-LINSAT(q,r) over F_q and shows quantum decoding is required for DQI to achieve the hardness-optimal 1/sqrt(D) scaling.
Decoded quantum interferometry is generalized to translation association schemes, reducing analysis to tridiagonal eigenvalue problems, with a finite-field matrix rank-difference protocol that produces constant-probability residual-rank bounds but no additive optimality guarantee.
Explicit quantum circuits for elliptic-curve point addition achieve 6.5-10% fewer Toffoli gates and 1.5% more qubits than Babbush et al. for secp256k1, plus a generic prime-field version.
DQI-Kit automates encoding of objectives and constraints into Max-LINSAT instances and estimates expected DQI performance on the resulting problems.
Regev's reduction on Cheng-Wan DLOG instances does not yield an efficient quantum algorithm for discrete log because decoders fall short of the threshold and the Pretty Good Measurement is inefficient.
A space-efficient quantum ECDLP algorithm uses 5n + 4⌊log₂n⌋ + O(1) logical qubits and O(n³) Toffoli gates, lowering the 256-bit estimate from 2124 to 1333 qubits.
Large qLDPC blocks in distributed quantum computing enable Pauli-based computation to run up to 10x faster than surface codes for optimization algorithms by using spare nodes to bypass serialization bottlenecks.
A review describing the Decoded Quantum Interferometry algorithm for quantum speedups in max-LINSAT optimization, with claimed superpolynomial advantage in the OPI problem.
citing papers explorer
-
Discrepancy for Random Linear Codes
Random linear codes over finite fields satisfy near-optimal discrepancy properties, enabling list-decoding and zero-error list-recovery above capacity that match random codes.
-
Multivariate Decoded Quantum Interferometry for Weighted Optimization
Multivariate DQI uses N-variable polynomials for weighted Max-LINSAT, derives closed-form asymptotics for expectation and concentration, provides a single-decoder preparation circuit, and shows outperformance over weighted Prange for some OPI cases while extending to Hamiltonian DQI.
-
On Worst-Case Optimal Polynomial Intersection
Existence of asymptotically better solutions than the semicircle law for worst-case OPI over prime fields when n/m exceeds thresholds like 0.6225 for rho approximately 1/2, via connection to local leakage resilience of secret sharing.
-
Affine Filtering Measurements and Their Applications to Quantum Decoding
Optimal affine filtering measurements for group-covariant pure-state codewords reduce to an LP, and SPC-based affine-filtering+GE decoding can outperform symbol-wise USD and PGM on i.i.d. pure-state channels.
-
Optimization Using Locally-Quantum Decoders
Locally-quantum decoding of LDPC codes under coherent bit-flip superpositions outperforms BP and sometimes Prange/SA on Gallager max-k-XORSAT, but an enhanced Prange algorithm ties it.
-
Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry
Extends NP-hardness of exceeding r/q + O(1/sqrt(D)) for bounded-degree max-Ek-LINSAT(q,r) over F_q and shows quantum decoding is required for DQI to achieve the hardness-optimal 1/sqrt(D) scaling.
-
Decoded Quantum Interferometry Beyond Hamming: Rank-Metric and Translation Association Schemes
Decoded quantum interferometry is generalized to translation association schemes, reducing analysis to tridiagonal eigenvalue problems, with a finite-field matrix rank-difference protocol that produces constant-probability residual-rank bounds but no additive optimality guarantee.
-
Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms
Explicit quantum circuits for elliptic-curve point addition achieve 6.5-10% fewer Toffoli gates and 1.5% more qubits than Babbush et al. for secp256k1, plus a generic prime-field version.
-
From Constraint to Code: DQI-Kit -- A Software Framework for Decoded Quantum Interferometry
DQI-Kit automates encoding of objectives and constraints into Max-LINSAT instances and estimates expected DQI performance on the resulting problems.
-
Regev's reduction as a candidate quantum algorithm for the discrete logarithm problem in finite abelian groups
Regev's reduction on Cheng-Wan DLOG instances does not yield an efficient quantum algorithm for discrete log because decoders fall short of the threshold and the Pretty Good Measurement is inefficient.
-
Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation
A space-efficient quantum ECDLP algorithm uses 5n + 4⌊log₂n⌋ + O(1) logical qubits and O(n³) Toffoli gates, lowering the 256-bit estimate from 2124 to 1333 qubits.
-
Space-Time Tradeoffs of Pauli-Based Computation in Distributed qLDPC Architectures
Large qLDPC blocks in distributed quantum computing enable Pauli-based computation to run up to 10x faster than surface codes for optimization algorithms by using spare nodes to bypass serialization bottlenecks.
-
Quantum Decoding Algorithms: Quantum Speedups in Optimization
A review describing the Decoded Quantum Interferometry algorithm for quantum speedups in max-LINSAT optimization, with claimed superpolynomial advantage in the OPI problem.