量子計算デバイスの最近の急速な実験的進歩によって動機付けられて、量子計算の優位性を示すために様々なモデルが研究されている。商業的には、量子アニーリングマシンは横磁場量子イジングモデルを実現し、組合せ最適化問題をヒューリステックに解く方法として利用されはじめている。この計算機の計算能力は、疑似古典確率的ハミルトニアンと呼ばれるハミルトニアンに限定した場合の断熱量子計算（AQC）と密接に関連しており、万能量子計算に比べて計算能力は低いと考えられてきた。しかし、疑似古典確率的ハミルトニアンを用いたAQC（以降stoqAQC と呼ぶ）における計算量的な意味での量子加速に関する知見はほとんど得られていない。
　本研究では、stoqAQCの計算能力を特徴づけを行い、その計算量的な量子加速の強い証左について報告する。具体的には、stoqAQCの終状態に対して非標準基底の適応単一量子ビット測定可能な場合は、万能量子計算同等の計算能力を持つことが明らかになった。また、AQCのロバスト性を考慮し、測定を非適応的なものに限定した場合でも、計算幾何学的な予想に基づいて古典計算に対する優位性を示すことができる。さらに、ショアのアルゴリズムをstoqAQCに埋め込み、因数分解問題を多項式時間で解くことができることも分かった。読みだしのエラーのための量子誤り訂正の埋め込みや、stoqAQCの計算結果の検証のための方法も提案する。

連絡教員　物理学系　西森　秀稔（内線2488）