Combinatorial optimization with quantum imaginary time evolution
- URL: http://arxiv.org/abs/2312.16664v1
- Date: Wed, 27 Dec 2023 18:18:12 GMT
- Title: Combinatorial optimization with quantum imaginary time evolution
- Authors: Nora M. Bauer, Rizwanul Alam, James Ostrowski, George Siopsis
- Abstract summary: We show that a linear Ansatz yields good results for a wide range of PUBO problems.
We obtain numerical results for the Low Autocorrelation Binary Sequences (LABS) and weighted MaxCut optimization problems.
- Score: 2.048226951354646
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We use Quantum Imaginary Time Evolution (QITE) to solve polynomial
unconstrained binary optimization (PUBO) problems. We show that a linear Ansatz
yields good results for a wide range of PUBO problems, often outperforming
standard classical methods, such as the Goemans-Williamson (GW) algorithm. We
obtain numerical results for the Low Autocorrelation Binary Sequences (LABS)
and weighted MaxCut combinatorial optimization problems, thus extending an
earlier demonstration of successful application of QITE on MaxCut for
unweighted graphs. We find the performance of QITE on the LABS problem with a
separable Ansatz comparable with p=10 QAOA, and do not see a significant
advantage with an entangling Ansatz. On weighted MaxCut, QITE with a separable
Ansatz often outperforms the GW algorithm on graphs up to 150 vertices.
Related papers
- 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) - NISQ-compatible approximate quantum algorithm for unconstrained and
constrained discrete optimization [0.0]
We present an approximate gradient-based quantum algorithm for hardware-efficient circuits with amplitude encoding.
We show how simple linear constraints can be directly incorporated into the circuit without additional modification of the objective function with penalty terms.
arXiv Detail & Related papers (2023-05-23T16:17:57Z) - 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) - 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) - Predicting parameters for the Quantum Approximate Optimization Algorithm
for MAX-CUT from the infinite-size limit [0.05076419064097732]
We present an explicit algorithm to evaluate the performance of QAOA on MAX-CUT applied to random Erdos-Renyi graphs of expected degree $d$.
This analysis yields an explicit mapping between QAOA parameters for MAX-CUT on Erdos-Renyi graphs, and the Sherrington-Kirkpatrick model.
arXiv Detail & Related papers (2021-10-20T17:58:53Z) - Combinatorial Optimization with Physics-Inspired Graph Neural Networks [0.0]
We show how graph neural networks can be used to solve optimization problems.
We find that the neural network performs on par or outperforms existing solvers.
arXiv Detail & Related papers (2021-07-02T16:54:35Z) - Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
The predict+optimize problem combines machine learning ofproblem coefficients with a optimization prob-lem that uses the predicted coefficients.
We show how to directlyexpress the loss of the optimization problem in terms of thepredicted coefficients as a piece-wise linear function.
We propose a novel divide and algorithm to tackle optimization problems without this restriction and predict itscoefficients using the optimization loss.
arXiv Detail & Related papers (2020-12-04T00:26:56Z) - Improving the Quantum Approximate Optimization Algorithm with
postselection [0.0]
Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers.
We consider a well-studied quantum algorithm for optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs.
We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable.
arXiv Detail & Related papers (2020-11-10T22:17:50Z) - Warm-starting quantum optimization [6.832341432995627]
We discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of an optimization problem.
This allows the quantum algorithm to inherit the performance guarantees of the classical algorithm.
It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.
arXiv Detail & Related papers (2020-09-21T18:00:09Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope.
Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
arXiv Detail & Related papers (2020-06-11T17:43:19Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications.
Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem.
In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
arXiv Detail & Related papers (2020-03-11T13:52:41Z)
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.