Implementing Slack-Free Custom Penalty Function for QUBO on Gate-Based Quantum Computers

• URL: http://arxiv.org/abs/2504.12611v1
• Date: Thu, 17 Apr 2025 03:20:02 GMT
• Title: Implementing Slack-Free Custom Penalty Function for QUBO on Gate-Based Quantum Computers
• Authors: Xin Wei Lee, Hoong Chuin Lau,
• Abstract summary: Variational Quantum Algorithms (VQAs) typically require constrained problems to be reformulated as unconstrained ones using penalty methods.<n>A common approach introduces slack variables and quadratic penalties in the QUBO formulation to handle inequality constraints.<n>We explore a slack-free formulation that directly encodes inequality constraints using custom penalty functions.<n>These step-like penalties suppress infeasible solutions without introducing additional qubits or requiring finely tuned weights.
• Score: 4.266376725904727
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving NP-hard constrained combinatorial optimization problems using quantum algorithms remains a challenging yet promising avenue toward quantum advantage. Variational Quantum Algorithms (VQAs), such as the Variational Quantum Eigensolver (VQE), typically require constrained problems to be reformulated as unconstrained ones using penalty methods.A common approach introduces slack variables and quadratic penalties in the QUBO formulation to handle inequality constraints. However, this leads to increased qubit requirements and often distorts the optimization landscape, making it harder to find high-quality feasible solutions. To address these issues, we explore a slack-free formulation that directly encodes inequality constraints using custom penalty functions, specifically the exponential function and the Heaviside step function. These step-like penalties suppress infeasible solutions without introducing additional qubits or requiring finely tuned weights. Inspired by recent developments in quantum annealing and threshold-based constraint handling in gate-based algorithms, we implement and evaluate our approach on the Multiple Knapsack Problem (MKP). Experimental results show that the step-based formulation significantly improves feasibility and optimality rates compared to unbalanced penalization, while reducing overall qubit overhead.

Related papers

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex. Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs. We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• 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)
• Non-Variational Quantum Random Access Optimization with Alternating Operator Ansatz [3.5773675235837974]
  Quantum Random Access Optimization (QRAO) has been proposed to reduce the space requirements of quantum optimization. We show that instance-independent 'fixed' parameters achieve good performance, removing the need for variational parameter optimization. Our results pave the way for the practical execution of QRAO on early fault-tolerant quantum computers.
  arXiv  Detail & Related papers  (2025-02-06T18:25:31Z)
• Inequality constraints in variational quantum circuits with qudits [1.0923877073891446]
  Quantum optimization is emerging as a prominent candidate for exploiting the capabilities of near-term quantum devices. Here, we study an alternative direct implementation of inequality constraints within the QAOA algorithm, achieved using qudit-SUM gates. We find that the direct implementation of the inequality penalties vastly outperforms the slack variables method, especially when studying real-world inspired problems with many constraints.
  arXiv  Detail & Related papers  (2024-10-10T07:32:38Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Improving Performance in Combinatorial Optimization Problems with Inequality Constraints: An Evaluation of the Unbalanced Penalization Method on D-Wave Advantage [0.0]
  A new method known as unbalanced penalization has been presented to avoid using slack variables. This work tests the unbalanced penalization method using real quantum hardware on D-Wave Advantage for the traveling salesman problem (TSP) The results show that the unbalanced penalization method outperforms the solutions found using slack variables.
  arXiv  Detail & Related papers  (2023-05-30T05:40:50Z)
• 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)
• 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)
• 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)
• 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)

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.