複数固有値に対する推定
上記の記事で解説した位相推定の量子回路(下図)では、状態 はユニタリ演算子
の特定の固有値に属する固有状態でした。
それでは、複数の固有値に対する固有状態の重ね合わせの場合、どうなるでしょうか?
結論から言うと、最後の逆フーリエ変換の出力は、それぞれの固有値に対応する状態の重ね合わせになります。
たとえば、 と
の固有状態
、
の重ね合わせ
に対しては、最後の出力は、
となります。従って、これを観測すると等確率で もしくは
という結果が得られます。
これは次の簡単な計算で確認できます。たとえば、先の量子回路の一番下の量子ビット(および Second register)の変化は次になります。
(
演算)
(Controlled-
演算)
他の量子ビットについても同様で、全体として、2種類の計算を個別に行って、結果を重ね合わせたものと同じになります。(量子回路演算の線形性を考えると、実は当たり前なのですが。。。。)
これから位相情報を取り出す逆フーリエ変換もまた、線形変換なので、結果は、個別に計算したものの重ね合わせと同じにものになります。
Cirq による実験例はこちらにあります。
Order finding
「 を適当な自然数として、
となる最小の自然数
を発見する」という問題を考えます。
これは、「 で
倍する」というユニタリ演算
に対する固有値から解くことができます。
を自然数
の各桁を量子ビットで表現した状態として、
は次で定義されます。
これは、 として、次の
個の固有状態を持ちます。
直接計算から分かるように、固有値は です。
そして、これらの固有状態をすべて重ね合わせると、ちょうど になります。これも直接計算でわかります。
したがって、冒頭の量子回路で、Second registor を に初期化して、演算子
に対する位相推定を行うと、
(
)のいずれか1つが得られます。得られた値に対して、「互いに素な値による既約分数として表す」ための既知のアルゴリズム(Continued fractions)を適用すると、
と
が個別に決定されます。これで、先ほどの問題の解
が得られます。(運悪く
が観測された場合は、測定をやり直します。)