量子コンピューターという、チューリングマシンとは異なる新しい発想に基づ
くコンピューターが生まれてきている。量子コンピューターでは、$2$値論理
を基礎とするディジタルコンピューターとは異なり、演算は情報を担う量子状
態へのユニタリー変換として構成される。現在の一連の研究は、素因数分解が
量子コンピューター上では多項式時間で実行可能であるというSchorが1994年
に発表した結果により一気に火がついた感がある。実装面では小さな数の因数
分解が現在の限界ではあるが、将来の進展に期待して量子コンピューターの適
用価値のある問題を発掘する努力もなされている。Schackは、カオス系の典型
例としてよく知られているbaker's mapの量子化として得られるユニタリー変
換が量子コンピューター上で高速計算できることを見出した。baker's mapの
量子化自体は量子カオスの研究につながるものとして興味深い話題だが、それ
に量子コンピューターが深く関わっているところが面白いところである。本報
告書では、Schackの論文に基づいてbaker's mapの量子化を行い、得られたユ
ニタリー変換が量子コンピューター上でどのように計算されるかを議論する。
量子化baker's map(QBM)は、離散フーリエ変換(DFT)によって記述できること
がわかる。QBMの作用するヒルベルト空間の次元が$2^L$に等しいときには、
DFTに基づくQBMの計算量は$O(2^{2L})$となるが、高速フーリエ変換アルゴリ
ズムを利用するとさらに$O(2^LL)$に改善できる。量子コンピューターを利用
すると、高速フーリエ変換の計算量は、したがって量子化baker's mapの計算
量も$O(L^2)$にまで減らせることがわかる。