大会名称 |
---|
2020年 情報科学技術フォーラム(FIT) |
大会コ-ド |
F |
開催年 |
2020 |
発行日 |
2020-08-18 |
セッション番号 |
126 |
セッション名 |
アルゴリズムとソフトウェア工学 |
講演日 |
2020/09/02 |
講演場所(会議室等) |
第4イベント会場 |
講演番号 |
TCS-5-3 |
タイトル |
浅層量子回路による平均量子優位性 |
著者名 |
Le Gall Francois, |
キーワード |
抄録 |
Recently Bravyi, Gosset and König (Science 2018) proved an unconditional separation between the computational powers of small-depth quantum and classical circuits for a relation. In this paper we show a similar separation in the average-case setting that gives stronger evidence of the superiority of small-depth quantum computation: we construct a computational task that can be solved on all inputs by a quantum circuit of constant depth with bounded-fanin gates (a "shallow" quantum circuit) and show that any classical circuit with bounded-fanin gates solving this problem on a non-negligible fraction of the inputs must have logarithmic depth. Our results are obtained by introducing a technique to create quantum states exhibiting global quantum correlations from any graph, via a construction that we call the extended graph. |