講演会情報
- 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.