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.
arXiv preprint arXiv:2510.10967 , year=
8 Pith papers cite this work. Polarity classification is still indexing.
8
Pith papers citing it
citation-role summary
background 3
citation-polarity summary
years
2026 8roles
background 3polarities
background 3representative citing papers
A quantum decoder for LDPC codes with coherent errors outperforms belief propagation on average-case D-regular max-k-XORSAT for several k and D, matching an enhanced version of Prange's algorithm.
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.
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
-
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.
-
Optimization Using Locally-Quantum Decoders
A quantum decoder for LDPC codes with coherent errors outperforms belief propagation on average-case D-regular max-k-XORSAT for several k and D, matching an enhanced version of Prange's algorithm.
-
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.
-
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.