Evidence that PUBO outperforms QUBO when solving continuous optimization
problems with the QAOA
- URL: http://arxiv.org/abs/2305.03390v1
- Date: Fri, 5 May 2023 09:37:48 GMT
- Title: Evidence that PUBO outperforms QUBO when solving continuous optimization
problems with the QAOA
- Authors: Jonas Stein, Farbod Chamanian, Maximilian Zorn, Jonas N\"u{\ss}lein,
Sebastian Zielinski, Michael K\"olle and Claudia Linnhoff-Popien
- Abstract summary: A core step in solving optimization problems with quantum algorithms is the problem formulation.
Recent studies show that many problems can be solved more efficiently in their native Polynomial Unconstrained Optimization forms.
Our evaluation on suitable benchmark functions, shows that PUBO formulations generally yield better results, while requiring less qubits.
- Score: 4.670374869377859
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum computing provides powerful algorithmic tools that have been shown to
outperform established classical solvers in specific optimization tasks. A core
step in solving optimization problems with known quantum algorithms such as the
Quantum Approximate Optimization Algorithm (QAOA) is the problem formulation.
While quantum optimization has historically centered around Quadratic
Unconstrained Optimization (QUBO) problems, recent studies show, that many
combinatorial problems such as the TSP can be solved more efficiently in their
native Polynomial Unconstrained Optimization (PUBO) forms. As many optimization
problems in practice also contain continuous variables, our contribution
investigates the performance of the QAOA in solving continuous optimization
problems when using PUBO and QUBO formulations. Our extensive evaluation on
suitable benchmark functions, shows that PUBO formulations generally yield
better results, while requiring less qubits. As the multi-qubit interactions
needed for the PUBO variant have to be decomposed using the hardware gates
available, i.e., currently single- and two-qubit gates, the circuit depth of
the PUBO approach outscales its QUBO alternative roughly linearly in the order
of the objective function. However, incorporating the planned addition of
native multi-qubit gates such as the global Molmer-Sorenson gate, our
experiments indicate that PUBO outperforms QUBO for higher order continuous
optimization problems in general.
Related papers
- Tensor Network Based HOBO Solver [0.0]
The proposed solver is a promising tool with significant potential for future extensions in terms of formulation.
This solver holds promising potential for a wide range of applications in quantum computing.
arXiv Detail & Related papers (2024-07-23T00:33:34Z) - Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems.
In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems.
We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
arXiv Detail & Related papers (2024-04-17T11:00:12Z) - 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) - Quantum approximate optimization via learning-based adaptive
optimization [5.399532145408153]
Quantum approximate optimization algorithm (QAOA) is designed to solve objective optimization problems.
Our results demonstrate that the algorithm greatly outperforms conventional approximations in terms of speed, accuracy, efficiency and stability.
This work helps to unlock the full power of QAOA and paves the way toward achieving quantum advantage in practical classical tasks.
arXiv Detail & Related papers (2023-03-27T02:14:56Z) - A Study of Scalarisation Techniques for Multi-Objective QUBO Solving [0.0]
Quantum and quantum-inspired optimisation algorithms have shown promising performance when applied to academic benchmarks as well as real-world problems.
However, QUBO solvers are single objective solvers. To make them more efficient at solving problems with multiple objectives, a decision on how to convert such multi-objective problems to single-objective problems need to be made.
arXiv Detail & Related papers (2022-10-20T14:54:37Z) - Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs [0.0]
Current quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent Ising model suitable for the quantum device.
We propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits.
This results in a new variant of the Quantum Approximate Optimization Algorithm (QAOA), which we name the Prog-QAOA.
arXiv Detail & Related papers (2022-09-07T18:01:01Z) - 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) - Polynomial unconstrained binary optimisation inspired by optical
simulation [52.11703556419582]
We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization.
We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance.
The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
arXiv Detail & Related papers (2021-06-24T16:39:31Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices.
We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT)
Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
arXiv Detail & Related papers (2020-10-01T18:14:11Z) - 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) - Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical
and Quantum Computers [3.04585143845864]
We present a decomposition-based approach to extend the applicability of current approaches to "quadratic plus convex" mixed binary optimization problems.
We show that the alternating direction method of multipliers (ADMM) can split the MBO into a binary unconstrained problem (that can be solved with quantum algorithms)
The validity of the approach is then showcased by numerical results obtained on several optimization problems via simulations with VQE and QAOA on the quantum circuits implemented in Qiskit.
arXiv Detail & Related papers (2020-01-07T14:43:13Z)
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.