量子物理学：復号化量子干渉計測による最適化

最適化のために超多項式的な高速化を達成することは、長年にわたって量子アルゴリズムの中心的目標となってきた。今回我々は、量子フーリエ変換を用いて最適化問題を復号問題に還元する量子アルゴリズムである、復号化量子干渉計測（DQI：decoded quantum interferometry）を提示する。近似最適多項式が有限体上で適合する場合、DQIは既知の古典アルゴリズムを超える超多項式的な高速化を達成した。この高速化は、問題の代数構造が、効率良く解くことができる復号問題に反映されるために生じる。我々は次に、この手法が、代数構造を欠くが疎な節を持つ最適化問題の高速化を達成できるかどうか調べた。こうした問題は、強力な復号器が知られている、低密度パリティ検査符号の復号に還元される。これを検証するため、我々は、DQIがシミュレーテッドアニーリングなどの汎用的な古典ヒューリスティックよりも大幅に高速に近似最適解を見つける、max-XORSATのインスタンスを構築した。このインスタンスでは、目的に応じて最適化された古典ソルバーがDQIを凌駕し得るものの、今回の結果は、量子フーリエ変換と強力な復号プリミティブを組み合わせることで、困難な最適化問題の量子高速化に向けて新しく有望な道筋がもたらされることを立証している。

目次へ戻る