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
- 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) - First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
We present a unified approach for the theoretical analysis of first-order variation methods.
Our approach covers both non-linear gradient and strongly Monte Carlo problems.
We provide bounds that match the oracle strongly in the case of convex method optimization problems.
arXiv Detail & Related papers (2023-05-25T11:11:31Z) - 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) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - 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.