Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems

被引:40
作者
Willsch, Dennis [1 ]
Willsch, Madita [1 ,2 ]
Gonzalez Calaza, Carlos D. [1 ]
Jin, Fengping [1 ]
De Raedt, Hans [1 ,3 ]
Svensson, Marika [4 ,5 ]
Michielsen, Kristel [1 ,2 ,6 ]
机构
[1] Forschungszentrum Julich, Inst Adv Simulat, Julich Supercomp Ctr, D-52425 Julich, Germany
[2] AIDAS, D-52425 Julich, Germany
[3] Univ Groningen, Zernike Inst Adv Mat, Nijenborgh 4, NL-9747 AG Groningen, Netherlands
[4] Jeppesen, S-41103 Gothenburg, Sweden
[5] Chalmers Univ Technol, Dept Comp Sci & Engn, SE-41296 Gothenburg, Sweden
[6] Rhein Westfal TH Aachen, D-52056 Aachen, Germany
关键词
Quantum computing; Quantum annealing; Optimization problems; Benchmarking;
D O I
10.1007/s11128-022-03476-y
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
We benchmark the quantum processing units of the largest quantum annealers to date, the 5000+ qubit quantum annealer Advantage and its 2000+ qubit predecessor D-Wave 2000Q, using tail assignment and exact cover problems from aircraft scheduling scenarios. The benchmark set contains small, intermediate, and large problems with both sparsely connected and almost fully connected instances. We find that Advantage outperforms D-Wave 2000Q for almost all problems, with a notable increase in success rate and problem size. In particular, Advantage is also able to solve the largest problems with 120 logical qubits that D-Wave 2000Q cannot solve anymore. Furthermore, problems that can still be solved by D-Wave 2000Q are solved faster by Advantage. We find, however, that D-Wave 2000Q can achieve better success rates for sparsely connected problems that do not require the many new couplers present on Advantage, so improving the connectivity of a quantum annealer does not per se improve its performance.
引用
收藏
页数:22
相关论文
共 71 条
  • [31] QUANTUM ANNEALING - A NEW METHOD FOR MINIMIZING MULTIDIMENSIONAL FUNCTIONS
    FINNILA, AB
    GOMEZ, MA
    SEBENIK, C
    STENSON, C
    DOLL, JD
    [J]. CHEMICAL PHYSICS LETTERS, 1994, 219 (5-6) : 343 - 348
  • [32] Fox D.M., 2021, MRNA CODON OPTIMIZAT, DOI DOI 10.1101/2021.02.19.431999
  • [33] Grozea C., ARXIV210907212CSAI
  • [34] A Study of Spanning Trees on a D-Wave Quantum Computer
    Hall, J. S.
    Novotny, M. A.
    Neuhaus, T.
    Michielsen, Kristel
    [J]. PROCEEDINGS OF THE 28TH WORKSHOP ON COMPUTER SIMULATION STUDIES IN CONDENSED MATTER PHYSICS (CSP2015), 2015, 68 : 56 - 60
  • [35] Experimental investigation of an eight-qubit unit cell in a superconducting optimization processor
    Harris, R.
    Johnson, M. W.
    Lanting, T.
    Berkley, A. J.
    Johansson, J.
    Bunyk, P.
    Tolkacheva, E.
    Ladizinsky, E.
    Ladizinsky, N.
    Oh, T.
    Cioata, F.
    Perminov, I.
    Spear, P.
    Enderud, C.
    Rich, C.
    Uchaikin, S.
    Thom, M. C.
    Chapple, E. M.
    Wang, J.
    Wilson, B.
    Amin, M. H. S.
    Dickson, N.
    Karimi, K.
    Macready, B.
    Truncik, C. J. S.
    Rose, G.
    [J]. PHYSICAL REVIEW B, 2010, 82 (02)
  • [36] Perspectives of quantum annealing: methods and implementations
    Hauke, Philipp
    Katzgraber, Helmut G.
    Lechner, Wolfgang
    Nishimori, Hidetoshi
    Oliver, William D.
    [J]. REPORTS ON PROGRESS IN PHYSICS, 2020, 83 (05)
  • [37] Probing for quantum speedup in spin-glass problems with planted solutions
    Hen, Itay
    Job, Joshua
    Albash, Tameem
    Ronnow, Troels F.
    Troyer, Matthias
    Lidar, Daniel A.
    [J]. PHYSICAL REVIEW A, 2015, 92 (04):
  • [38] Test-driving 1000 qubits
    Job, Joshua
    Lidar, Daniel
    [J]. QUANTUM SCIENCE AND TECHNOLOGY, 2018, 3 (03):
  • [39] Quantum annealing with manufactured spins
    Johnson, M. W.
    Amin, M. H. S.
    Gildert, S.
    Lanting, T.
    Hamze, F.
    Dickson, N.
    Harris, R.
    Berkley, A. J.
    Johansson, J.
    Bunyk, P.
    Chapple, E. M.
    Enderud, C.
    Hilton, J. P.
    Karimi, K.
    Ladizinsky, E.
    Ladizinsky, N.
    Oh, T.
    Perminov, I.
    Rich, C.
    Thom, M. C.
    Tolkacheva, E.
    Truncik, C. J. S.
    Uchaikin, S.
    Wang, J.
    Wilson, B.
    Rose, G.
    [J]. NATURE, 2011, 473 (7346) : 194 - 198
  • [40] Quantum annealing in the transverse Ising model
    Kadowaki, T
    Nishimori, H
    [J]. PHYSICAL REVIEW E, 1998, 58 (05): : 5355 - 5363