65. Graph cliques and quantum annealing
Invited abstract in session FB-4: Methods of optimization, stream contributed papers.
Friday, 10:15 - 11:45Room: C105
Authors (first author is the speaker)
| 1. | Mátyás Koniorczyk
|
| Department of Quantum Optics and Quantum Information, HUN-REN Wigner Research Centre for Physics | |
| 2. | Kristóf Váradi
|
| Department of Measurement and Information Systems, Budapest University of Technology and Economics | |
| 3. | Sandor Szabo
|
| Institute of Mathematics and Informatics, University of Pecs |
Abstract
We explore the usability of quantum annealers on graph clique problems of Erdős-Rényi graphs. These random graphs offer a way to generate well-parametrized sets of benchmark problems with known interesting structural properties. We calculate clique numbers using actual quantum hardware as well as with Cliquer for comparison; the latter is amongst the most efficient algorithms for the problem. We compare the timings and the quality of the solution, and analyze the effect of the quantum annealing parameters on the solution. We find that in certain cases the quantum hardware can be competitive.
Keywords
- Nature inspired methods and algorithms
- Complexity and efficiency of optimization algorithms
Status: accepted
Back to the list of papers