量子力学100周年研究会：量子基礎・量子情報のこれまでとこれから

量子コンピュータ上で指数関数的に小さい空間を用いて大規模な古典系をシミュレートする研究が注目を集めている。先行研究では、長距離相互作用を持つ古典系のシミュレーションにおいて、指数関数的な量子加速が示された。しかし、多くの現実世界の古典系、例えば偏微分方程式に由来する系などは、局所的な相互作用しか持たない。このような条件下でも量子アルゴリズムが指数関数的な優位性を持てるのかという疑問が残る。本研究では、この問題に答えるため、以下3つの主要な結果を示す。第一に、このような古典系の短時間（多項式時間）発展を効率的にシミュレートする脱量子化アルゴリズムを与える。これは、短時間発展では指数関数的な量子優位性が得られないことを意味する。第二に、短時間発展をシミュレートする量子アルゴリズムの計算複雑性が、多項式時間の確率的古典計算と同等であることを示す。第三に、長時間（指数時間）のダイナミクスにおいては、その計算複雑性が指数時間かつ多項式空間の量子計算と等価であることを示す。この結果は、長時間発展において空間計算量の観点から指数関数的な優位性があることを保証する。