The pitfalls of planar spin-glass benchmarks: raising the bar for quantum annealers (again)

In an effort to overcome the limitations of random spin-glass benchmarks for quantum annealers, focus has shifted to carefully crafted gadget-based problems whose logical structure typically has a planar topology. Recent experiments on these gadget problems using a commercially available quantum ann...

Full description

Saved in:
Bibliographic Details
Published in:Quantum science and technology 2017-09, Vol.2 (3), p.38501
Main Authors: Mandrà, Salvatore, Katzgraber, Helmut G, Thomas, Creighton
Format: Article
Language:English
Subjects:
benchmarking
exact algorithms
P versus NP
quantum annealing
spin glasses
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c353t-194b4797a2b861c13a84ac3c366707338f97af5ea1a850eeb49e806a468f3ce43
cites cdi_FETCH-LOGICAL-c353t-194b4797a2b861c13a84ac3c366707338f97af5ea1a850eeb49e806a468f3ce43
container_end_page
container_issue 3
container_start_page 38501
container_title Quantum science and technology
container_volume 2
creator Mandrà, Salvatore
Katzgraber, Helmut G
Thomas, Creighton
description In an effort to overcome the limitations of random spin-glass benchmarks for quantum annealers, focus has shifted to carefully crafted gadget-based problems whose logical structure typically has a planar topology. Recent experiments on these gadget problems using a commercially available quantum annealer have demonstrated an impressive performance over a selection of commonly used classical optimisation heuristics. Here, we show that efficient classical optimisation techniques, such as minimum-weight-perfect matching, can solve these gadget problems exactly and in polynomial time. We present approaches on how to mitigate this shortcoming of commonly used benchmark problems based on planar logical topologies.
doi_str_mv 10.1088/2058-9565/aa7877
format article
fullrecord <record><control><sourceid>iop_cross</sourceid><recordid>TN_cdi_iop_journals_10_1088_2058_9565_aa7877</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>qstaa7877</sourcerecordid><originalsourceid>FETCH-LOGICAL-c353t-194b4797a2b861c13a84ac3c366707338f97af5ea1a850eeb49e806a468f3ce43</originalsourceid><addsrcrecordid>eNp9kL1PwzAQxS0EElXpzugJgUSoHSe2w4YqvqRKLGVisC7GTl1SJ7XTgf8eR0WIATHd6e69p6cfQueU3FAi5TwnpcyqkpdzACGFOEKTn9Pxr_0UzWLcEEJYTmlF-AS9rdYG926w0LYRdxb3LXgIOPbOZ00LMeLaeL3eQviItziAi843eEiuOslsF_BuD37YbzF4b6A1IeJLaMD5qzN0kmKjmX3PKXp9uF8tnrLly-Pz4m6ZaVayIaNVUReiEpDXklNNGcgCNNOMc0EEY9Kmny0NUJAlMaYuKiMJh4JLy7Qp2BSRQ64OXYzBWNUHlwp_KkrUyEeNANQIQB34JMv1weK6Xm26ffCp4H_yiz_kuzioXDFFWOpFVf9u2RfOAXM0</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>The pitfalls of planar spin-glass benchmarks: raising the bar for quantum annealers (again)</title><source>Institute of Physics:Jisc Collections:IOP Publishing Read and Publish 2024-2025 (Reading List)</source><creator>Mandrà, Salvatore ; Katzgraber, Helmut G ; Thomas, Creighton</creator><creatorcontrib>Mandrà, Salvatore ; Katzgraber, Helmut G ; Thomas, Creighton</creatorcontrib><description>In an effort to overcome the limitations of random spin-glass benchmarks for quantum annealers, focus has shifted to carefully crafted gadget-based problems whose logical structure typically has a planar topology. Recent experiments on these gadget problems using a commercially available quantum annealer have demonstrated an impressive performance over a selection of commonly used classical optimisation heuristics. Here, we show that efficient classical optimisation techniques, such as minimum-weight-perfect matching, can solve these gadget problems exactly and in polynomial time. We present approaches on how to mitigate this shortcoming of commonly used benchmark problems based on planar logical topologies.</description><identifier>ISSN: 2058-9565</identifier><identifier>EISSN: 2058-9565</identifier><identifier>DOI: 10.1088/2058-9565/aa7877</identifier><language>eng</language><publisher>IOP Publishing</publisher><subject>benchmarking ; exact algorithms ; P versus NP ; quantum annealing ; spin glasses</subject><ispartof>Quantum science and technology, 2017-09, Vol.2 (3), p.38501</ispartof><rights>2017 IOP Publishing Ltd</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c353t-194b4797a2b861c13a84ac3c366707338f97af5ea1a850eeb49e806a468f3ce43</citedby><cites>FETCH-LOGICAL-c353t-194b4797a2b861c13a84ac3c366707338f97af5ea1a850eeb49e806a468f3ce43</cites><orcidid>0000-0003-3341-9943 ; 0000-0002-3908-2694</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids></links><search><creatorcontrib>Mandrà, Salvatore</creatorcontrib><creatorcontrib>Katzgraber, Helmut G</creatorcontrib><creatorcontrib>Thomas, Creighton</creatorcontrib><title>The pitfalls of planar spin-glass benchmarks: raising the bar for quantum annealers (again)</title><title>Quantum science and technology</title><addtitle>QST</addtitle><addtitle>Quantum Sci. Technol</addtitle><description>In an effort to overcome the limitations of random spin-glass benchmarks for quantum annealers, focus has shifted to carefully crafted gadget-based problems whose logical structure typically has a planar topology. Recent experiments on these gadget problems using a commercially available quantum annealer have demonstrated an impressive performance over a selection of commonly used classical optimisation heuristics. Here, we show that efficient classical optimisation techniques, such as minimum-weight-perfect matching, can solve these gadget problems exactly and in polynomial time. We present approaches on how to mitigate this shortcoming of commonly used benchmark problems based on planar logical topologies.</description><subject>benchmarking</subject><subject>exact algorithms</subject><subject>P versus NP</subject><subject>quantum annealing</subject><subject>spin glasses</subject><issn>2058-9565</issn><issn>2058-9565</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2017</creationdate><recordtype>article</recordtype><recordid>eNp9kL1PwzAQxS0EElXpzugJgUSoHSe2w4YqvqRKLGVisC7GTl1SJ7XTgf8eR0WIATHd6e69p6cfQueU3FAi5TwnpcyqkpdzACGFOEKTn9Pxr_0UzWLcEEJYTmlF-AS9rdYG926w0LYRdxb3LXgIOPbOZ00LMeLaeL3eQviItziAi843eEiuOslsF_BuD37YbzF4b6A1IeJLaMD5qzN0kmKjmX3PKXp9uF8tnrLly-Pz4m6ZaVayIaNVUReiEpDXklNNGcgCNNOMc0EEY9Kmny0NUJAlMaYuKiMJh4JLy7Qp2BSRQ64OXYzBWNUHlwp_KkrUyEeNANQIQB34JMv1weK6Xm26ffCp4H_yiz_kuzioXDFFWOpFVf9u2RfOAXM0</recordid><startdate>20170901</startdate><enddate>20170901</enddate><creator>Mandrà, Salvatore</creator><creator>Katzgraber, Helmut G</creator><creator>Thomas, Creighton</creator><general>IOP Publishing</general><scope>AAYXX</scope><scope>CITATION</scope><orcidid>https://orcid.org/0000-0003-3341-9943</orcidid><orcidid>https://orcid.org/0000-0002-3908-2694</orcidid></search><sort><creationdate>20170901</creationdate><title>The pitfalls of planar spin-glass benchmarks: raising the bar for quantum annealers (again)</title><author>Mandrà, Salvatore ; Katzgraber, Helmut G ; Thomas, Creighton</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c353t-194b4797a2b861c13a84ac3c366707338f97af5ea1a850eeb49e806a468f3ce43</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2017</creationdate><topic>benchmarking</topic><topic>exact algorithms</topic><topic>P versus NP</topic><topic>quantum annealing</topic><topic>spin glasses</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Mandrà, Salvatore</creatorcontrib><creatorcontrib>Katzgraber, Helmut G</creatorcontrib><creatorcontrib>Thomas, Creighton</creatorcontrib><collection>CrossRef</collection><jtitle>Quantum science and technology</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Mandrà, Salvatore</au><au>Katzgraber, Helmut G</au><au>Thomas, Creighton</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>The pitfalls of planar spin-glass benchmarks: raising the bar for quantum annealers (again)</atitle><jtitle>Quantum science and technology</jtitle><stitle>QST</stitle><addtitle>Quantum Sci. Technol</addtitle><date>2017-09-01</date><risdate>2017</risdate><volume>2</volume><issue>3</issue><spage>38501</spage><pages>38501-</pages><issn>2058-9565</issn><eissn>2058-9565</eissn><abstract>In an effort to overcome the limitations of random spin-glass benchmarks for quantum annealers, focus has shifted to carefully crafted gadget-based problems whose logical structure typically has a planar topology. Recent experiments on these gadget problems using a commercially available quantum annealer have demonstrated an impressive performance over a selection of commonly used classical optimisation heuristics. Here, we show that efficient classical optimisation techniques, such as minimum-weight-perfect matching, can solve these gadget problems exactly and in polynomial time. We present approaches on how to mitigate this shortcoming of commonly used benchmark problems based on planar logical topologies.</abstract><pub>IOP Publishing</pub><doi>10.1088/2058-9565/aa7877</doi><tpages>6</tpages><orcidid>https://orcid.org/0000-0003-3341-9943</orcidid><orcidid>https://orcid.org/0000-0002-3908-2694</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 2058-9565
ispartof Quantum science and technology, 2017-09, Vol.2 (3), p.38501
issn 2058-9565
2058-9565
language eng
recordid cdi_iop_journals_10_1088_2058_9565_aa7877
source Institute of Physics:Jisc Collections:IOP Publishing Read and Publish 2024-2025 (Reading List)
subjects benchmarking
exact algorithms
P versus NP
quantum annealing
spin glasses
title The pitfalls of planar spin-glass benchmarks: raising the bar for quantum annealers (again)
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-03T09%3A33%3A47IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-iop_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=The%20pitfalls%20of%20planar%20spin-glass%20benchmarks:%20raising%20the%20bar%20for%20quantum%20annealers%20(again)&rft.jtitle=Quantum%20science%20and%20technology&rft.au=Mandr%C3%A0,%20Salvatore&rft.date=2017-09-01&rft.volume=2&rft.issue=3&rft.spage=38501&rft.pages=38501-&rft.issn=2058-9565&rft.eissn=2058-9565&rft_id=info:doi/10.1088/2058-9565/aa7877&rft_dat=%3Ciop_cross%3Eqstaa7877%3C/iop_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c353t-194b4797a2b861c13a84ac3c366707338f97af5ea1a850eeb49e806a468f3ce43%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true