Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems

• URL: http://arxiv.org/abs/2508.02590v1
• Date: Mon, 04 Aug 2025 16:44:53 GMT
• Title: Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems
• Authors: Anthony Wilkie, Alexander DeLise, Andrew Del Real, Rebekah Herrman, James Ostrowski,
• Abstract summary: 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.
• Score: 41.23247424467223
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum computing approaches excel at solving quadratic unconstrained binary optimization (QUBO) problems, however solving quadratic constrained binary optimization problems (QCBOs) is more challenging. In this work, we develop a variational approach that creates an equal superposition of quantum states that satisfy constraints in a QCBO. The method relies on flag qubits, one per constraint, to identify when a constraint is violated or not. The resulting equal superposition can be used as an initial state for quantum algorithms that solve QUBOs/QCBOs such as Grover's search algorithm or the quantum approximate optimization algorithm (QAOA). We test the approach on sets of one and two linear inequality constraints and find that it is able to generate an equal superposition of feasible states with a .98 AR on average. We then use the approach to generate initial states for Grover-mixer QAOA (GM-QAOA) and find that GM-QAOA with the constraint gadgets yields significantly higher probability of measuring the optimal solution than random guessing.

Related papers

• A Quantum Constraint Generation Framework for Binary Linear Programs [0.0]
  We propose a new approach to utilize quantum computers for binary linear programming (BLP)<n>Quantum optimization algorithms, hybrid or quantum-only, are currently general purpose, standalone solvers for ILP.<n>In this study we wrap any suitable quantum optimization algorithm into a quantum informed classical constraint generation framework.
  arXiv  Detail & Related papers  (2025-03-27T07:24:33Z)
• A quantum annealing approach to the minimum distance problem of quantum codes [0.0]
  We introduce an approach to compute the minimum distance of quantum stabilizer codes by reformulating the problem as a Quadratic Unconstrained Binary Optimization problem. We demonstrate practical viability of our method by comparing the performance of purely classical algorithms with the D-Wave Advantage 4.1 quantum annealer.
  arXiv  Detail & Related papers  (2024-04-26T21:29:42Z)
• A Universal Quantum Algorithm for Weighted Maximum Cut and Ising Problems [0.0]
  We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary problems. We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian. Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system.
  arXiv  Detail & Related papers  (2023-06-10T23:28:13Z)
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
  In this work, we integrate the potentials of quantum and classical techniques for optimization. We reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. We present numerous computational results from real quantum hardware.
  arXiv  Detail & Related papers  (2023-02-10T20:12:53Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Quantum Assisted Eigensolver [0.0]
  We propose a hybrid quantum-classical algorithm for approxing the ground state and ground state energy of a Hamiltonian. The output from the quantum part of the algorithm is utilized as input for the classical computer.
  arXiv  Detail & Related papers  (2020-09-23T08:33:18Z)

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.