Q-CHOP: Quantum constrained Hamiltonian optimization
- URL: http://arxiv.org/abs/2403.05653v1
- Date: Fri, 8 Mar 2024 20:03:59 GMT
- Title: Q-CHOP: Quantum constrained Hamiltonian optimization
- Authors: Michael A. Perlin, Ruslan Shaydulin, Benjamin P. Hall, Pierre Minssen,
Changhao Li, Kabir Dubey, Rich Rines, Eric R. Anschuetz, Marco Pistoia,
Pranav Gokhale
- Abstract summary: We propose a new quantum algorithm for constrained optimization, which we call quantum constrained Hamiltonian optimization (Q-CHOP)
The basic idea is to enforce a Hamiltonian constraint at all times, thereby restricting evolution to the subspace of feasible states.
We benchmark Q-CHOP against the commonly-used adiabatic algorithm with constraints enforced using a penalty term.
- Score: 2.7022651232296946
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Combinatorial optimization problems that arise in science and industry
typically have constraints. Yet the presence of constraints makes them
challenging to tackle using both classical and quantum optimization algorithms.
We propose a new quantum algorithm for constrained optimization, which we call
quantum constrained Hamiltonian optimization (Q-CHOP). Our algorithm leverages
the observation that for many problems, while the best solution is difficult to
find, the worst feasible (constraint-satisfying) solution is known. The basic
idea is to to enforce a Hamiltonian constraint at all times, thereby
restricting evolution to the subspace of feasible states, and slowly "rotate"
an objective Hamiltonian to trace an adiabatic path from the worst feasible
state to the best feasible state. We additionally propose a version of Q-CHOP
that can start in any feasible state. Finally, we benchmark Q-CHOP against the
commonly-used adiabatic algorithm with constraints enforced using a penalty
term and find that Q-CHOP performs consistently better on a wide range of
problems, including textbook problems on graphs, knapsack, combinatorial
auction, as well as a real-world financial use case, namely bond
exchange-traded fund basket optimization.
Related papers
- Quantum Relaxation for Solving Multiple Knapsack Problems [7.003282322403712]
Combinatorial problems are a common challenge in business, requiring finding optimal solutions under specified constraints.
In this study, we investigate a hybrid quantum-classical method for constrained optimization problems.
Our proposed method relies on relaxations to local quantum Hamiltonians, defined through commutative maps.
arXiv Detail & Related papers (2024-04-30T11:40:07Z) - 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) - 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) - Classically-Boosted Quantum Optimization Algorithm [0.0]
We explore a natural approach to leveraging existing classical techniques to enhance quantum optimization.
Specifically, we run a classical algorithm to find an approximate solution and then use a quantum circuit to search its "neighborhood" for higher-quality solutions.
We demonstrate the applications of CBQOA to Max 3SAT and Max Bisection, and provide empirical evidence that it outperforms previous approaches on these problems.
arXiv Detail & Related papers (2022-03-25T23:36:14Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time.
As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware.
We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
arXiv Detail & Related papers (2022-02-17T18:59:20Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation.
We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
arXiv Detail & Related papers (2021-08-18T09:26:17Z) - 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) - 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) - Training variational quantum algorithms is NP-hard [0.7614628596146599]
We show that the corresponding classical optimization problems are NP-hard.
Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard.
arXiv Detail & Related papers (2021-01-18T19:00:01Z) - 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) - An adaptive quantum approximate optimization algorithm for solving
combinatorial problems on a quantum computer [0.0]
The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves optimization problems.
We develop an iterative version of QAOA that is problem-tailored, and which can also be adapted to specific hardware constraints.
We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA.
arXiv Detail & Related papers (2020-05-20T18:00:01Z)
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.