量子アディアバティックアルゴリズムにおける最小励起ギャップのサイズ依存性

量子モンテカルロシミュレーションを用いて、正確なカバー問題の量子版における最小ギャップの典型的（中央値）値を調査し、従来よりもはるかに大きなサイズの量子アディアバティックアルゴリズムの複雑さを理解します。サイズN≦128の範囲では、古典的なデイビス・プトナムアルゴリズムが指数的な中央値の複雑さを示すのに対し、量子アディアバティックアルゴリズムは多項式の中央値の複雑さを示します。アルゴリズムのボトルネックは、ランダウ＝ゼナー型の孤立した回避交差点（最低エネルギー準位間の衝突のみ）です。