量子コンピューティング：量子増強マルコフ連鎖モンテカルロ法
Nature 619, 7969 doi: 10.1038/s41586-023-06095-4
量子コンピューターは、ある種の計算問題を古典的なコンピューターよりもはるかに高速に解くと期待されている。しかし、現在の量子プロセッサーは、その小さなサイズや大きな誤り率によって制限されている。従って、量子高速化を実証する最近の取り組みでは、複雑だが明示的に有用ではない確率分布からのサンプリングなどの、古典的な難問であるとともに、現在の量子ハードウエアに本来適した問題に重点が置かれている。今回我々は、同様に現在のハードウエアに適しているが、いくつかの用途で生じる複雑な分布からサンプリングする量子アルゴリズムを導入し、これを実験的に実証した。このアルゴリズムは、よく知られた反復手法であるマルコフ連鎖モンテカルロ（MCMC）を実行して、古典的イジングモデルのボルツマン分布からサンプリングする。近い将来の量子アルゴリズムの大半とは異なり、我々のアルゴリズムは、古典的にシミュレートするのは困難だが、立証可能な方法で正しい分布に収束する。しかし、MCMCアルゴリズムの大半と同様に、その収束速度を理論的に定めるのは難しいため、我々はその代わりに、実験とシミュレーションの両方を通してこれを分析した。実験では、今回の量子アルゴリズムは、一般的な古典的MCMCアルゴリズムよりも少ない反復回数で収束したことから、雑音に対して非常にロバストであることが示唆される。シミュレーションでは、代替アルゴリズムを上回る三次と四次の間の多項式高速化が観測された。この経験的な高速化は、より大きなスケールでも維持されるのとすれば、機械学習、統計物理学、最適化において、このサンプリング問題によって課される計算のボトルネックを緩和できる。従って、このアルゴリズムは、単に難しいだけでなく有用なサンプリング問題を解く量子コンピューターへの新たな道を開く。
