Decoded Quantum Interferometry Requires Structure

• URL: http://arxiv.org/abs/2509.14509v1
• Date: Thu, 18 Sep 2025 00:51:36 GMT
• Title: Decoded Quantum Interferometry Requires Structure
• Authors: Eric R. Anschuetz, David Gamarnik, Jonathan Z. Lu,
• Abstract summary: We study the performance of Decoded Quantum Interferometry (DQI) on typical instances of MAX-$k$-XOR-SAT.<n>We prove that DQI is approximately Lipschitz under the quantum Wasserstein metric over many standard ensembles of codes.
• Score: 1.121518046252855
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the performance of Decoded Quantum Interferometry (DQI) on typical instances of MAX-$k$-XOR-SAT when the transpose of the constraint matrix is drawn from a standard ensemble of LDPC parity check matrices. We prove that if the decoding step of DQI corrects up to the folklore efficient decoding threshold for LDPC codes, then DQI is obstructed by a topological feature of the near-optimal space of solutions known as the overlap gap property (OGP). As the OGP is widely conjectured to exactly characterize the performance of state-of-the-art classical algorithms, this result suggests that DQI has no quantum advantage in optimizing unstructured MAX-$k$-XOR-SAT instances. We also give numerical evidence supporting this conjecture by showing that approximate message passing (AMP)--a classical algorithm conjectured to saturate the OGP threshold--outperforms DQI on a related ensemble of MAX-$k$-XOR-SAT instances. Finally, we prove that depth-$1$ QAOA outperforms DQI at sufficiently large $k$ under the same decoding threshold assumption. Our result follows by showing that DQI is approximately Lipschitz under the quantum Wasserstein metric over many standard ensembles of codes. We then prove that MAX-$k$-XOR-SAT exhibits both an OGP and a related topological obstruction known as the chaos property; this is the first known OGP threshold for MAX-$k$-XOR-SAT at fixed $k$, which may be of independent interest. Finally, we prove that both of these topological properties inhibit approximately Lipschitz algorithms such as DQI from optimizing MAX-$k$-XOR-SAT to large approximation ratio.

Related papers

• Verifiable Quantum Advantage via Optimized DQI Circuits [2.149968465453488]
  Decoded Quantum Interferometry (DQI) provides a framework for superpolynomial quantum speedups.<n>We apply DQI to the Optimal Polynomial Intersection (OPI) problem, whose code is Reed-Solomon (RS)<n>We establish that DQI for OPI is the first known candidate for verifiable quantum advantage with optimal speedup.
  arXiv  Detail & Related papers  (2025-10-13T03:19:28Z)
• Optimization of Quadratic Constraints by Decoded Quantum Interferometry [0.0]
  We extend Decoded Quantum Interferometry (DQI) to optimization problems involving quadratic constraints.<n>We give an efficient algorithm to prepare the DQI state for max-QUADSAT.<n>We show that quadratic-OPI is an instance of max-QUADSAT and use our algorithm to optimize it.
  arXiv  Detail & Related papers  (2025-10-09T10:49:17Z)
• The Geometry of LLM Quantization: GPTQ as Babai's Nearest Plane Algorithm [52.89358421626026]
  GPTQ emerged as one of the standard methods for one-shot post-training quantization at LLM scale.<n>We show that GPTQ is mathematically identical to Babai's nearest plane algorithm for the classical closest vector problem.
  arXiv  Detail & Related papers  (2025-07-24T16:22:18Z)
• IGMaxHS -- An Incremental MaxSAT Solver with Support for XOR Clauses [0.0]
  We introduce IGMaxHS, which is based on the solvers iMaxHS and GaussMaxHS, but poses fewer restrictions on the XOR constraints than GaussMaxHS. IGMaxHS is the only solver that reported neither incorrect unsatisfiability verdicts nor invalid models nor incoherent cost model combinations. We show that IGMaxHS is capable of decoding quantum color codes through simulation with the Munich Quantum Toolkit.
  arXiv  Detail & Related papers  (2024-10-21T11:21:21Z)
• Optimization by Decoded Quantum Interferometry [42.169154389732036]
  We introduce a quantum algorithm called Decoded Quantum Interferometry (DQI)<n>For approximating to data over finite fields, DQI achieves a better approximation ratio than any time known to us.
  arXiv  Detail & Related papers  (2024-08-15T17:47:42Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• The Overlap Gap Property limits limit swapping in the QAOA [5.578103948136372]
  The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for Combinatorial Optimization Problem (COP)<n>We show that if a local algorithm is limited in performance at logarithmic depth for a spin glass type COP with an underlying Erd"os--R'enyi hypergraph, then a random regular hypergraph is similarly limited in as well.
  arXiv  Detail & Related papers  (2024-04-09T07:45:06Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models [45.14286976373306]
  We establish optimal Statistical Query (SQ) lower bounds for robustly learning certain families of discrete high-dimensional distributions. Our SQ lower bounds match the error guarantees of known algorithms for these problems, providing evidence that current upper bounds for these tasks are best possible.
  arXiv  Detail & Related papers  (2022-06-09T16:10:23Z)
• DPMS: An ADD-Based Symbolic Approach for Generalized MaxSAT Solving [45.21499915442282]
  We propose a novel dynamic-programming approach for solving generalized MaxSAT problems with hybrid constraints. Our versatile framework admits many generalizations of CNF-MaxSAT, such as MaxSAT, Min-MaxSAT, and MinSAT with hybrid constraints. Empirical results indicate that DPMS is able to solve certain problems quickly, where other algorithms based on various techniques all fail.
  arXiv  Detail & Related papers  (2022-05-08T00:31:53Z)
• Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit [0.05076419064097732]
  We present an explicit algorithm to evaluate the performance of QAOA on MAX-CUT applied to random Erdos-Renyi graphs of expected degree $d$. This analysis yields an explicit mapping between QAOA parameters for MAX-CUT on Erdos-Renyi graphs, and the Sherrington-Kirkpatrick model.
  arXiv  Detail & Related papers  (2021-10-20T17:58:53Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  We show how to apply the quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph. We construct an efficient classical simulation algorithm which simulates level-$1$ QAOA and level-$1$ RQAOA for arbitrary graphs.
  arXiv  Detail & Related papers  (2020-11-26T18:22:21Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.