[qmeso-seminar] семинар 8 апреля

[Mikhail A. Skvortsov]

                     СЕМИНАР СЕКТОРА КВАНТОВОЙ МЕЗОСКОПИКИ

                          пятница 8 апреля, 15:00, ИТФ


                                 K. S. Tikhonov

           What is the computational value of finite range tunneling?


Реферативный доклад по работе V. S. Denchev et al (Google Inc.), 
http://arxiv.org/abs/1512.02206

Quantum annealing (QA) has been proposed as a quantum enhanced optimization
heuristic exploiting tunneling. Here, we demonstrate how finite range tunneling
can provide considerable computational advantage. For a crafted problem designed
to have tall and narrow energy barriers separating local minima, the D-Wave 2X
quantum annealer achieves significant runtime advantages relative to Simulated
Annealing (SA). For instances with 945 variables, this results in a
time-to-99%-success-probability that is ∼108 times faster than SA running
on a single processor core. We also compared physical QA with Quantum Monte
Carlo (QMC), an algorithm that emulates quantum tunneling on classical
processors. We observe a substantial constant overhead against physical QA:
D-Wave 2X again runs up to ∼108 times faster than an optimized
implementation of QMC on a single core. We note that there exist heuristic
classical algorithms that can solve most instances of Chimera structured
problems in a timescale comparable to the D-Wave 2X. However, we believe that
such solvers will become ineffective for the next generation of annealers
currently being designed. To investigate whether finite range tunneling will
also confer an advantage for problems of practical interest, we conduct
numerical studies on binary optimization problems that cannot yet be represented
on quantum hardware. For random instances of the number partitioning problem, we
find numerically that QMC, as well as other algorithms designed to simulate QA,
scale better than SA. We discuss the implications of these findings for the
design of next generation quantum annealers.