Divide-And-Conquer Hybrid Methods for Smaller Quantum Computers

          @misc{ scivideos_15615,
            doi = {},
            url = {https://simons.berkeley.edu/talks/divide-and-conquer-hybrid-methods-smaller-quantum-computers},
            author = {},
            keywords = {},
            language = {en},
            title = {Divide-And-Conquer Hybrid Methods for Smaller Quantum Computers},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {may},
            note = {15615 see, \url{https://scivideos.org/index.php/Simons-Institute/15615}}
          }
          

Abstract

Theory shows that arbitrary-sized quantum computers may offer computational advantages for many problems. However, quantum computers on a reasonable horizon will be restricted in many ways, including size. Motivated by this, we investigate how a smaller quantum computer can genuinely speed up interesting algorithms, even when the problem size is much larger than the computer itself. To do so, we study hybrid classical-quantum divide-and-conquer strategies, and prove that if certain conditions on the structure and complexities of the underlying classical and quantum algorithms are met, then genuine speed-ups can be obtained. We will demonstrate how these conditions are met for a few exact constraint satisfaction algorithms (for SAT and Hamilton cycles). In closing we will discuss some of the more recent ideas showing how the hybrid methods can be expanded to the heuristic domain, and (hopefully) achieve practically relevant speed-ups in optimization with near-term devices. This talk will be based on the following papers: -VD, Y. Ge, J. I. Cirac, Computational speedups using small quantum devices, Phys. Rev. Lett. 121, 250501 (2018); -Y. Ge, VD, A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles, J. Math. Phys. 61, 012201 (2020); -C. Moussa, H. Calandra, VD, To quantum or not to quantum: towards algorithm selection in near-term quantum optimization, arXiv:2001.08271 (2020);