Effective Embedding of Integer Linear Inequalities for Variational Quantum Algorithms

• URL: http://arxiv.org/abs/2403.18395v2
• Date: Mon, 29 Apr 2024 15:14:19 GMT
• Title: Effective Embedding of Integer Linear Inequalities for Variational Quantum Algorithms
• Authors: Maximilian Hess, Lilly Palackal, Abhishek Awasthi, Karen Wintersperger,
• Abstract summary: In variational quantum algorithms, constraints are usually added to the problem objective via penalty terms. In this work, we explore approaches to model linear inequalities for quantum algorithms without these drawbacks. Our main suggestion is to omit the slack qubits completely and evaluate the inequality classically during parameter tuning.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In variational quantum algorithms, constraints are usually added to the problem objective via penalty terms. For linear inequality constraints, this procedure requires additional slack qubits. Those extra qubits tend to blow up the search space and complicate the parameter landscapes to be navigated by the classical optimizers. In this work, we explore approaches to model linear inequalities for quantum algorithms without these drawbacks. More concretely, our main suggestion is to omit the slack qubits completely and evaluate the inequality classically during parameter tuning. We test our methods on QAOA as well as on Trotterized adiabatic evolution, and present empirical results. As a benchmark problem, we consider different instances of the multi-knapsack problem. Our results show that removing the slack bits from the circuit Hamiltonian and considering them only for the expectation value yields better solution quality than the standard approach. The tests have been carried out using problem sizes up to 26 qubits. Our methods can in principle be applied to any problem with linear inequality constraints, and are suitable for variational as well as digitized versions of adiabatic quantum computing.

Related papers

• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems. We show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts on various tasks.
  arXiv  Detail & Related papers  (2024-10-22T10:19:27Z)
• 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)
• Hybrid classical-quantum branch-and-bound algorithm for solving integer linear problems [0.0]
  Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation. The solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large. We propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits.
  arXiv  Detail & Related papers  (2023-11-16T09:19:01Z)
• 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)
• 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)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Efficient Classical Computation of Quantum Mean Values for Shallow QAOA Circuits [15.279642278652654]
  We present a novel graph decomposition based classical algorithm that scales linearly with the number of qubits for the shallow QAOA circuits. Our results are not only important for the exploration of quantum advantages with QAOA, but also useful for the benchmarking of NISQ processors.
  arXiv  Detail & Related papers  (2021-12-21T12:41:31Z)
• 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)
• Solving Inequality-Constrained Binary Optimization Problems on Quantum Annealer [0.966840768820136]
  We propose a new method for solving binary optimization problems under inequality constraints using a quantum annealer. In this study, we employ the alternating direction method of multipliers. We found that the computational time of our method is faster than that of the exact solver when we tackle various QKPs defined on dense graphs.
  arXiv  Detail & Related papers  (2020-12-11T04:30:16Z)

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.