Decoded Quantum Interferometry for Weighted Optimization Problems

• URL: http://arxiv.org/abs/2605.10666v1
• Date: Mon, 11 May 2026 14:45:46 GMT
• Title: Decoded Quantum Interferometry for Weighted Optimization Problems
• Abstract summary: Decoded Quantum Interferometry (DQI) is a recently introduced quantum optimization to decoding.<n>In its original formulation, DQI treats all constraints uniformly and cannot exploit the weight structure present in most optimization problems of interest.<n>We develop a theory of DQI for weighted optimization problems, focusing on the weighted Max-LINSAT problem.
• Score: 6.4675604105664
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decoded Quantum Interferometry (DQI) is a recently introduced quantum algorithm that reduces discrete optimization to decoding with potential advantages over the best known polynomial-time classical algorithms for certain Max-LINSAT problems. In its original formulation, however, DQI treats all constraints uniformly and cannot exploit the weight structure present in most optimization problems of interest. In this work, we develop a theory of DQI for weighted optimization problems, focusing on the weighted Max-LINSAT problem over a prime field. Grouping constraints into $N$ blocks by distinct weights, we introduce \emph{multivariate DQI states} built from $N$-variable polynomials of bounded total degree, and derive a closed-form asymptotic expression for both their optimal expectation value and their concentration behavior. We give an explicit preparation circuit using a single decoder call, and extend the analysis to imperfect decoding. We also show that, for certain weighted OPI problems, multivariate DQI outperforms a natural weighted analogue of Prange's algorithm, which serves as the weighted counterpart of the classical benchmark used in the unweighted setting. Finally, we extend the ideas to Hamiltonian DQI, obtaining approximate Gibbs states for commuting Pauli Hamiltonians with block structure.

Related papers

• A nearly linear-time Decoded Quantum Interferometry algorithm for the Optimal Polynomial Intersection problem [0.0]
  Recently, Jordan et al. introduced a novel quantum-algorithmic technique called Decoded Quantum Interferometry (DQI)<n>They presented a constraint-satisfaction problem called Optimal Polynomial Intersection (OPI) and showed that a DQI algorithm running in time can satisfy a larger fraction of constraints than any known-time classical algorithm.<n>We show how these improvements result in a nearly linear-time DQI algorithm for the OPI problem.
  arXiv  Detail & Related papers  (2026-01-21T16:48:05Z)
• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  The tutorial begins by outlining variational quantum circuits and QUBO problems.<n>Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications.<n>The tutorial extends these concepts to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
  arXiv  Detail & Related papers  (2025-11-23T09:54:20Z)
• A Rigorous Quantum Framework for Inequality-Constrained and Multi-Objective Binary Optimization [0.4753535328327316]
  In this letter, we show that including inequality constraints is equivalent to solving a multi-objective optimization.<n>This insight motivates the Multi-Objective Quantum Approximation (MOQA) framework, which approximates the maximum via smaller $p$-norms.
  arXiv  Detail & Related papers  (2025-10-15T18:05:27Z)
• 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)
• No Quantum Advantage in Decoded Quantum Interferometry for MaxCut [0.08122270502556375]
  Decoded Quantum Interferometry (DQI) is a framework for approxing special kinds of discrete optimization problems.<n>We show that the instances of MaxCut on which DQI attains a nontrivial guarantee are solvable exactly in classical time.
  arXiv  Detail & Related papers  (2025-09-24T10:21:31Z)
• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  We develop a variational approach that creates an equal superposition of quantum states that satisfy constraints in a QCBO.<n>The resulting equal superposition can be used as an initial state for quantum algorithms that solve QUBOs/QCBOs.
  arXiv  Detail & Related papers  (2025-08-04T16:44:53Z)
• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  Branch-and-bound algorithms effectively solve convex optimization problems, relying on the relaxation the objective function to obtain tight lower bounds.<n>We propose a branch-and-bound digitized counterdiabatic quantum optimization (BB-DCQO) algorithm that addresses the relaxation difficulties.
  arXiv  Detail & Related papers  (2025-04-21T18:19:19Z)
• Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
  We show that VarQITE achieves significantly lower mean optimality gaps compared to other conventional methods.<n>We demonstrate that scaling the Hamiltonian can further reduce optimization costs and accelerate convergence.
  arXiv  Detail & Related papers  (2025-04-17T03:09:37Z)
• Optimization by Decoded Quantum Interferometry [38.063836468778895]
  We introduce Decoded Quantum Interferometry (DQI), a quantum algorithm that uses the quantum Fourier transform to reduce optimization problems to decoding problems.<n>For approximating optimal fits over finite fields, DQI achieves a superpolynomial speedup over known classical algorithms.
  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)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• 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)
• Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
  arXiv  Detail & Related papers  (2022-03-23T18:00:03Z)
• 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)

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.