Towards Robust Benchmarking of Quantum Optimization Algorithms
- URL: http://arxiv.org/abs/2405.07624v1
- Date: Mon, 13 May 2024 10:35:23 GMT
- Title: Towards Robust Benchmarking of Quantum Optimization Algorithms
- Authors: David Bucher, Nico Kraus, Jonas Blenninger, Michael Lachner, Jonas Stein, Claudia Linnhoff-Popien,
- Abstract summary: A key problem in existing benchmarking frameworks is the lack of equal effort in optimizing for the best quantum and, respectively, classical approaches.
This paper presents a comprehensive set of guidelines comprising universal steps towards fair benchmarks.
- Score: 3.9456729020535013
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Benchmarking the performance of quantum optimization algorithms is crucial for identifying utility for industry-relevant use cases. Benchmarking processes vary between optimization applications and depend on user-specified goals. The heuristic nature of quantum algorithms poses challenges, especially when comparing to classical counterparts. A key problem in existing benchmarking frameworks is the lack of equal effort in optimizing for the best quantum and, respectively, classical approaches. This paper presents a comprehensive set of guidelines comprising universal steps towards fair benchmarks. We discuss (1) application-specific algorithm choice, ensuring every solver is provided with the most fitting mathematical formulation of a problem; (2) the selection of benchmark data, including hard instances and real-world samples; (3) the choice of a suitable holistic figure of merit, like time-to-solution or solution quality within time constraints; and (4) equitable hyperparameter training to eliminate bias towards a particular method. The proposed guidelines are tested across three benchmarking scenarios, utilizing the Max-Cut (MC) and Travelling Salesperson Problem (TSP). The benchmarks employ classical mathematical algorithms, such as Branch-and-Cut (BNC) solvers, classical heuristics, Quantum Annealing (QA), and the Quantum Approximate Optimization Algorithm (QAOA).
Related papers
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
gradient-based algorithms are widely used in bilevel optimization.
We introduce a without-replacement sampling based algorithm which achieves a faster convergence rate.
We validate our algorithms over both synthetic and real-world applications.
arXiv Detail & Related papers (2024-11-07T17:05:31Z) - Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
This study systematically benchmarks several non-fault-tolerant quantum computing algorithms across four distinct optimization problems.
Our benchmark includes noisy intermediate-scale quantum (NISQ) algorithms, such as the variational quantum eigensolver.
Our findings reveal that no single non-FTQC algorithm performs optimally across all problem types, underscoring the need for tailored algorithmic strategies.
arXiv Detail & Related papers (2024-10-30T08:41:29Z) - Randomized Benchmarking of Local Zeroth-Order Optimizers for Variational
Quantum Systems [65.268245109828]
We compare the performance of classicals across a series of partially-randomized tasks.
We focus on local zeroth-orders due to their generally favorable performance and query-efficiency on quantum systems.
arXiv Detail & Related papers (2023-10-14T02:13:26Z) - 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) - Exploring the Algorithm-Dependent Generalization of AUPRC Optimization
with List Stability [107.65337427333064]
optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning.
In this work, we present the first trial in the single-dependent generalization of AUPRC optimization.
Experiments on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
arXiv Detail & Related papers (2022-09-27T09:06:37Z) - Iteration Complexity of Variational Quantum Algorithms [5.203200173190989]
We argue that noise makes evaluations of the objective function via quantum circuits biased.
We derive the missing guarantees and find that the rate of convergence is unaffected.
arXiv Detail & Related papers (2022-09-21T19:18:41Z) - 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) - Stochastic optimization algorithms for quantum applications [0.0]
We review the use of first-order, second-order, and quantum natural gradient optimization methods, and propose new algorithms defined in the field of complex numbers.
The performance of all methods is evaluated by means of their application to variational quantum eigensolver, quantum control of quantum states, and quantum state estimation.
arXiv Detail & Related papers (2022-03-11T16:17:05Z) - Stochastic batch size for adaptive regularization in deep network
optimization [63.68104397173262]
We propose a first-order optimization algorithm incorporating adaptive regularization applicable to machine learning problems in deep learning framework.
We empirically demonstrate the effectiveness of our algorithm using an image classification task based on conventional network models applied to commonly used benchmark datasets.
arXiv Detail & Related papers (2020-04-14T07:54:53Z) - 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.