1．は　じ　め　に

　量子論というのは原子や光といったミクロな世界の振舞いを説明する物理理論であり，量子的重ね合わせや量子もつれ，不確定性原理やNo-cloningといった普段の生活では目にしないような不思議な現象にあふれている．この不思議な現象をうまく使うことによりこれまでにないような高性能な情報処理技術を実現するのが量子情報である．特に，高速な計算が可能である量子計算や，古典では実現できないような様々な機能を持った暗号を実現する量子暗号が最も中心的な応用であり，約50年間にわたって世界中で活発に理論的・実験的研究がなされてきている^(注1)．

　本稿のテーマは量子計算である．前半の内容は量子計算量理論についてであり，量子計算ができることとできないこと（できないと思われていること）を明らかにする．後半では，量子計算ができることの例として，量子アルゴリズムについて説明する．特に，近年盛んに研究されている量子特異値変換について詳しく解説する．

2．計算量理論基礎：P，BPP，BQP，PSPACE

　計算量理論というのは大雑把に言うと，ある問題を解くのにどのくらいのリソース（時間，メモリ）を必要とするかを定量的に分析する学問であり，理論計算機科学の中心的な分野の一つである．（標準的な教科書としては，例えばAroraとBarakの文献(１)．）量子計算の研究でまず気になるのが量子計算と古典計算の違いである．古典計算機を用いて決定的アルゴリズム（つまり乱数を使わない）で（問題サイズの）多項式時間で解ける問題の集合はPと呼ばれる．また，古典計算機を用いて確率的アルゴリズムで多項式時間で解ける問題の集合はBPPと呼ばれる．（確率的アルゴリズムの場合は，確率的にしか正解を出さないが，ある程度の成功確率で正しい解を出せるのであれば，アルゴリズムを多項式回繰り返して多数決を取ることにより，間違える確率を指数的に小さくすることが可能である．）量子計算も確率的な計算であるので，自然な比較対象はBPPである．BPPの定義において，確率的アルゴリズムを量子アルゴリズムに置き換えたものはBQPと呼ばれる．