A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear
Programs
- URL: http://arxiv.org/abs/2103.15433v2
- Date: Mon, 12 Jul 2021 06:11:59 GMT
- Title: A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear
Programs
- Authors: Marika Svensson, Martin Andersson, Mattias Gr\"onkvist, Pontus
Vikst{\aa}l, Devdatt Dubhashi, Giulia Ferrini, and G\"oran Johansson
- Abstract summary: We present a method that integrates any quantum algorithm capable of finding solutions to integer linear programs into the Branch-and-Price algorithm.
The role of the quantum algorithm is to find integer solutions to subproblems appearing in Branch-and-Price.
- Score: 0.4925222726301578
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a method that integrates any quantum algorithm capable of finding
solutions to integer linear programs into the Branch-and-Price algorithm, which
is regularly used to solve large-scale integer linear programs with a specific
structure. The role of the quantum algorithm is to find integer solutions to
subproblems appearing in Branch-and-Price. Obtaining optimal or near-optimal
integer solutions to these subproblems can increase the quality of solutions
and reduce the depth and branching factor of the Branch-and-Price algorithm and
hence reduce the overall running time. We investigate the viability of the
approach by considering the Tail Assignment problem and the Quantum Approximate
Optimization Algorithm (QAOA). Here, the master problem is the optimization
problem Set Partitioning or its decision version Exact Cover and can be
expressed as finding the ground state of an Ising spin glass Hamiltonian. For
Exact Cover, our numerical results indicate that the required algorithm depth
decreases with the number of feasible solutions for a given success probability
of finding a feasible solution. For Set Partitioning, on the other hand, we
find that for a given success probability of finding the optimal solution, the
required algorithm depth can increase with the number of feasible solutions if
the Hamiltonian is balanced poorly, which in the worst case is exponential in
the problem size. We therefore address the importance of properly balancing the
objective and constraint parts of the Hamiltonian. We empirically find that the
approach is viable with QAOA if polynomial algorithm depth can be realized on
quantum devices.
Related papers
- The Differentiable Feasibility Pump [49.55771920271201]
This paper shows that the traditional feasibility pump and many of its follow-ups can be seen as gradient-descent algorithms with specific parameters.
A central aspect of this reinterpretation is observing that the traditional algorithm differentiates the solution of the linear relaxation with respect to its cost.
arXiv Detail & Related papers (2024-11-05T22:26:51Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem.
We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
arXiv Detail & Related papers (2024-06-11T04:40:05Z) - A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems.
This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios.
We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
arXiv Detail & Related papers (2023-06-15T15:28:12Z) - Ising formulation of integer optimization problems for utilizing quantum
annealing in iterative improvement strategy [1.14219428942199]
We propose an Ising formulation of integer optimization problems to utilize quantum annealing in the iterative improvement strategy.
We analytically show that a first-order phase transition is successfully avoided for a fully connected ferro Potts model if the overlap between a ground state and a candidate solution exceeds a threshold.
arXiv Detail & Related papers (2022-11-08T02:12:49Z) - Problem-Size Independent Angles for a Grover-Driven Quantum Approximate
Optimization Algorithm [0.0]
We show that the calculation of the expectation of a problem Hamiltonian under a Grover-driven, QAOA-prepared state can be performed independently of system size.
Such calculations can help deliver insights into the performance of and predictability of angles in QAOA in the limit of large problem sizes.
arXiv Detail & Related papers (2022-08-22T17:18: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) - A quantum-inspired tensor network method for constrained combinatorial
optimization problems [5.904219009974901]
We propose a quantum-inspired tensor-network-based algorithm for general locally constrained optimization problems.
Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem.
Our results show the effectiveness of this construction and potential applications.
arXiv Detail & Related papers (2022-03-29T05:44:07Z) - Quantum constraint learning for quantum approximate optimization
algorithm [0.0]
This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace.
One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz.
We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints.
arXiv Detail & Related papers (2021-05-14T11:31:14Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00: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) - Lower Bounds on Circuit Depth of the Quantum Approximate Optimization
Algorithm [0.3058685580689604]
We show how the structure of problem instances can be used to identify lower bounds for circuit depth.
We argue that MaxCut, MaxIndSet, and some instances of Vertex Covering and Boolean satisifiability problems are suitable for QAOA approaches.
arXiv Detail & Related papers (2020-08-04T20:52:34Z)
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.