Skip to Content
No preview available

Actions

Download Analytics Citations

Export to: EndNote  |  Zotero  |  Mendeley

Collections

This file is not currently in any collections.

Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms [dataset] Open Access

An algorithm for a particular problem may find some instances of the problem easier and others harder to solve, even for a fixed input size. We numerically analyse the relative hardness of MAX 2-SAT problem instances for various continuous-time quantum algorithms and a comparable classical algorithm. This has two motivations: to investigate whether small-sized problem instances, which are commonly used in numerical simulations of quantum algorithms for benchmarking purposes, are a good representation of larger instances in terms of their hardness to solve, and to determine the applicability of continuous-time quantum algorithms in a portfolio approach, where we take advantage of the variation in the hardness of instances between different algorithms by running them in parallel. We find that, while there are correlations in instance hardness between all of the algorithms considered, they appear weak enough that a portfolio approach would likely be desirable in practice. Our results also show a widening range of hardness of randomly generated instances as the problem size is increased, which demonstrates both the difference in the distribution of hardness at small sizes and the value of a portfolio approach that can reduce the number of extremely hard instances. We identify specific weaknesses of these quantum algorithms that can be overcome with a portfolio approach, such their inability to efficiently solve satisfiable instances (which is easy classically).

Descriptions

Resource type
Dataset
Contributors
Contact person: Kendon, Viv 1
Data curator: Kendon, Viv 1
Creator: Callison, Adam 2
Contact person: Callison, Adam 2
Data collector: Callison, Adam 2
Data curator: Callison, Adam 2
Creator: Mirkarimi, Puya 3
Contact person: Mirkarimi, Puya 3
Data curator: Mirkarimi, Puya 3
Contact person: Chancellor, Nicholas 3
Data curator: Chancellor, Nicholas 3
Contact person: Light, Lewis 3
Creator: Crosson, Elizabeth 4
Contact person: Crosson, Elizabeth 4
Data collector: Crosson, Elizabeth 4
Data curator: Crosson, Elizabeth 4
1 University of Strathclyde, United Kingdom
2 University College London, United Kingdom
3 Durham University, United Kingdom
4 University of New Mexico, United States
Funder
Engineering and Physical Sciences Research Council
dunnhumby
US Army Research Laboratory
National Science Foundation
Natural Sciences and Engineering Research Council of Canada
Research methods
Computer assisted numerical calculations
Other description
This archive contains two datasets. The first dataset was produced by the authors of  https://arxiv.org/abs/2206.06876
. The abstract here is the abstract of that paper. The second dataset was produced by the authors of  https://arxiv.org/abs/1401.7320
 and is being shared with their permission.
Keyword
Quantum computing
Quantum walk
Adiabatic quantum computing
Quantum annealing
Subject
Quantum computing
Algorithms
Location
Language
English
Cited in
arxiv:2206.06876
Identifier
ark:/32150/r2x346d419f
doi:10.15128/r2x346d419f
Rights
Creative Commons Attribution 4.0 International (CC BY)

Publisher
Durham University
Date Created
2023-05-26

File Details

Depositor
P. Mirkarimi
Date Uploaded
Date Modified
26 May 2023, 14:05:49
Audit Status
Audits have not yet been run on this file.
Characterization
File format: zip (ZIP Format)
Mime type: application/zip
File size: 45339383
Last modified: 2023:05:26 12:42:27+01:00
Filename: MAX2SATQuantumData.zip
Original checksum: 693ebad5c4cfe9776d76c1abb1289224
Activity of users you follow
User Activity Date
User P. Mirkarimi has updated Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms [dataset] 11 months ago