A Rigorous Quantum Framework for Inequality-Constrained and Multi-Objective Binary Optimization

• URL: http://arxiv.org/abs/2510.13983v1
• Date: Wed, 15 Oct 2025 18:05:27 GMT
• Title: A Rigorous Quantum Framework for Inequality-Constrained and Multi-Objective Binary Optimization
• Authors: Sebastian Egginger, Kristina Kirova, Sonja Bruckner, Stefan Hillmich, Richard Kueng,
• Abstract summary: 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.
• Score: 0.4753535328327316
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Encoding combinatorial optimization problems into physically meaningful Hamiltonians with tractable energy landscapes forms the foundation of quantum optimization. Numerous works have studied such efficient encodings for the class of Quadratic Unconstrained Binary Optimization (QUBO) problems. However, many real-world tasks are constrained, and handling equality and, in particular, inequality constraints on quantum computers remains a major challenge. In this letter, we show that including inequality constraints is equivalent to solving a multi-objective optimization. This insight motivates the Multi-Objective Quantum Approximation (MOQA) framework, which approximates the maximum via smaller $p$-norms and comes with rigorous performance guarantees. MOQA operates directly at the Hamiltonian level and is compatible with, but not restricted to, ground-state solvers such as quantum adiabatic annealing, the Quantum Approximate Optimization Algorithm (QAOA), or imaginary-time evolution. Moreover, it is not limited to quadratic functions.

Related papers

• A Quantum Model for Constrained Markowitz Modern Portfolio Using Slack Variables to Process Mixed-Binary Optimization under QAOA [0.0]
  A quantum model for Markowitz portfolio optimization is presented.<n>The method maps each slack variable to a dedicated ancilla qubit, transforming the problem into a Quadratic Unconstrained Binary Optimization (QUBO) formulation.<n>A fundamental quantum limit on the simultaneous precision of portfolio risk and return is also posited.
  arXiv  Detail & Related papers  (2025-12-29T20:40:16Z)
• A Rigorous Quantum Framework for Inequality-Constrained and Multi-Objective Binary Optimization: Quadratic Cost Functions and Empirical Evaluations [0.4753535328327316]
  We provide novel, tractable mappings for the maxima of Quadratic Unconstrained Binary Optimization problems.<n>Our framework allows us to recast new types of classical binary optimization problems as ground state problems of a tractable Ising-type Hamiltonian.<n>This opens the possibility of new quantum- and quantum-inspired solutions to a variety of problems that frequently occur in practical applications.
  arXiv  Detail & Related papers  (2025-10-15T18:10:55Z)
• 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)
• QAMA: Scalable Quantum Annealing Multi-Head Attention Operator for Deep Learning [48.12231190677108]
  Quantum Annealing Multi-Head Attention (QAMA) is proposed, a novel drop-in operator that reformulates attention as an energy-based Hamiltonian optimization problem.<n>In this framework, token interactions are encoded into binary quadratic terms, and quantum annealing is employed to search for low-energy configurations.<n> Empirically, evaluation on both natural language and vision benchmarks shows that, across tasks, accuracy deviates by at most 2.7 points from standard multi-head attention.
  arXiv  Detail & Related papers  (2025-04-15T11:29:09Z)
• Distributed Variational Quantum Algorithm with Many-qubit for Optimization Challenges [0.25782420501870296]
  Existing quantum algorithms struggle with scalability and accuracy due to excessive reliance on entanglement.<n>We propose variational quantum optimization algorithm (VQOA), which leverages many-qubit (MQ) operations in an ansatz solely employing quantum superposition.<n>We also introduce distributed VQOA, which integrates high-performance computing with quantum computing to achieve superior performance across MQ systems and classical nodes.
  arXiv  Detail & Related papers  (2025-02-28T22:13:23Z)
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management [45.82374977939355]
  We introduce a new method for solving optimization problems with challenging constraints using variational quantum algorithms. We test our proposal on a real-world problem with great relevance in finance: the Cash Management problem. Our empirical results show a significant improvement in terms of the cost of the achieved solutions, but especially in the avoidance of local minima.
  arXiv  Detail & Related papers  (2023-02-08T17:09:20Z)
• Constrained Optimization via Quantum Zeno Dynamics [23.391640416533455]
  We introduce a technique that uses quantum Zeno dynamics to solve optimization problems with multiple arbitrary constraints, including inequalities. We show that the dynamics of quantum optimization can be efficiently restricted to the in-constraint subspace on a fault-tolerant quantum computer.
  arXiv  Detail & Related papers  (2022-09-29T18:00:40Z)
• 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)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers [3.04585143845864]
  We present a decomposition-based approach to extend the applicability of current approaches to "quadratic plus convex" mixed binary optimization problems. We show that the alternating direction method of multipliers (ADMM) can split the MBO into a binary unconstrained problem (that can be solved with quantum algorithms) The validity of the approach is then showcased by numerical results obtained on several optimization problems via simulations with VQE and QAOA on the quantum circuits implemented in Qiskit.
  arXiv  Detail & Related papers  (2020-01-07T14:43:13Z)

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.