最大列ユークリッドノルムへの依存が最適なスパースハミルトニアンシミュレーション

本論文は、dスパースなエルミートハミルトニアンのシミュレーションにおいて、最大列ユークリッドノルムの上界Λに依存するクエリ複雑性O(tΛ√d+√d log(2/ε))の量子アルゴリズムを提案した。Lowのアルゴリズムの劣多項式オーバーヘッドを、加法的な対数精度項に置き換えた。d>1かつtΛ≥log(2/ε)の範囲では最悪ケースの下界と一致する。応用としてスパース量子線形システムソルバーとブラックボックスユニタリ実装を示し、誤差一定のもとで任意のN×Nユニタリに対してΘ(√N)クエリとなり最適である。