量子コンピューティング：高速な量子MCMCアルゴリズムの実証

雑音が大きくて規模の小さい現在の量子コンピューターは、実用的には重要でない前もって準備された分布からのサンプリングにおいて古典的アルゴリズムに打ち勝つことが示されている。今回D Laydenたちは、古典的イジングモデルのボルツマン分布から効率的にサンプリングすることによってマルコフ連鎖モンテカルロ法（MCMC）を実行する、量子アルゴリズムを報告している。現在の量子プロセッサーでの実験によって、このアルゴリズムの、既存の古典的な代替アルゴリズムに対する三次から四次の多項式高速化が示唆された。MCMCが広く使われていることを考えると、今回の研究は、量子アルゴリズムが実用的なサンプリング問題で有利になる可能性を示唆している。

目次へ戻る