Skip to main content

Research Repository

Advanced Search

Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms

Mirkarimi, Puya; Callison, Adam; Light, Lewis; Chancellor, Nicholas; Kendon, Viv

Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms Thumbnail


Authors

Profile Image

Puya Mirkarimi puya.mirkarimi@durham.ac.uk
PGR Student Doctor of Philosophy

Adam Callison

Lewis Light



Abstract

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 analyze 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).

Journal Article Type Article
Acceptance Date Apr 17, 2023
Online Publication Date Jun 5, 2023
Publication Date 2023
Deposit Date Jun 14, 2023
Publicly Available Date Jun 14, 2023
Journal Physical Review Research
Electronic ISSN 2643-1564
Publisher American Physical Society
Peer Reviewed Peer Reviewed
Volume 5
Issue 2
DOI https://doi.org/10.1103/physrevresearch.5.023151
Public URL https://durham-repository.worktribe.com/output/1172543

Files

Published Journal Article (896 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.






You might also like



Downloadable Citations