Solving Combinatorial Optimization Problems with a Block Encoding Quantum Optimizer
- URL: http://arxiv.org/abs/2404.14054v2
- Date: Mon, 29 Apr 2024 08:41:05 GMT
- Title: Solving Combinatorial Optimization Problems with a Block Encoding Quantum Optimizer
- Authors: Adelina Bärligea, Benedikt Poggel, Jeanette Miriam Lorenz,
- Abstract summary: Block ENcoding Quantum (BEQO) is a hybrid quantum solver that uses block encoding to represent the cost function.
Our findings confirm that BENQO performs significantly better than QAOA and competes with VQE across a variety of performance metrics.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the pursuit of achieving near-term quantum advantage for combinatorial optimization problems, the Quantum Approximate Optimization Algorithm (QAOA) and the Variational Quantum Eigensolver (VQE) are the primary methods of interest, but their practical effectiveness remains uncertain. Therefore, there is a persistent need to develop and evaluate alternative variational quantum algorithms. This study presents an investigation of the Block ENcoding Quantum Optimizer (BENQO), a hybrid quantum solver that uses block encoding to represent the cost function. BENQO is designed to be universally applicable across discrete optimization problems. Beyond Maximum Cut, we evaluate BENQO's performance in the context of the Traveling Salesperson Problem, which is of greater practical relevance. Our findings confirm that BENQO performs significantly better than QAOA and competes with VQE across a variety of performance metrics. We conclude that BENQO is a promising novel hybrid quantum-classical algorithm that should be further investigated and optimized to realize its full potential.
Related papers
- Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
Variational Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems.
This paper explores the current state and recent developments of VQAs, emphasizing their applicability to Approximate optimization.
We implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes.
arXiv Detail & Related papers (2024-07-08T22:02:39Z) - 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) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms.
New challenges arise concerning which field quantum speedup can be achieved.
Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z) - Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
We apply variational quantum algorithm QAOA to a variant of satisfiability problem (SAT): Not-All-Equal SAT.
We show that while the runtime of both solvers scales exponentially with the problem size, the scaling for QAOA is smaller for large enough circuit depths.
arXiv Detail & Related papers (2024-01-05T15:11:24Z) - 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) - 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) - 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) - Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
We propose a resource and runtime efficient scheme termed quantum architecture search (QAS)
QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates.
We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
arXiv Detail & Related papers (2020-10-20T12:06:27Z) - 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) - 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.