本文へジャンプ

  • HOME
  • 講演会情報

講演会情報

Quantum Supremacy with Shallow Circuits
講演者:Francois Le Gall(Nagoya University)
2021年1月8日(金)13時30分〜15時00分 Zoom
Recent works have shown that even weak models of quantum computation, which often are almost implementable with current technology, can outperform classical computers. For instance, in 2017 a major breakthrough by Bravyi, Gosset and König showed a separation between the computational powers of small-depth quantum and classical circuits. In this talk I will present similar separations that give even stronger evidence of the superiority of quantum computation. The first part of the talk will explain the average-case separation from ArXiv:1810.12792, which constructs a computational task that can be solved on all inputs by a quantum circuit of constant depth (a "shallow" quantum circuit) and shows that any classical circuit solving this problem on a non-negligible fraction of the inputs must have logarithmic depth. The second part of the talk will discuss further recent developments and open problems.