量子コンピュータ#

読み: りょうしこんぴゅーた
英名:
別名: 量子計算機

量子コンピュータとは量子現象を計算機械の動作原理として採用してつくるコンピュータのことをいう．量子計算機ともいう．一方で古典物理学の範疇で動作原理が記述できるコンピュータのことを古典計算機といい，これは従来のコンピュータのことを意味し，しばしば量子計算機と対比される形で持ち出される．

量子コンピュータは可逆計算機の具体的な模型例として古くから研究されている．観測を伴わない量子現象の時間発展はユニタリー性を持つため，原理的に可逆になっている．可逆計算は熱の発生とも密接に関係しており，エネルギー消費の少ない計算機開発という点でも，量子コンピュータは重要な模型例となっている．

通常の論理演算は非可逆になっており，したがって可逆計算では万能性が自明ではない．例えば AND 演算は FALSE の演算結果に対して (FALSE, FALSE), (TRUE, FALSE), (FALSE, TRUE) という三通りの入力が対応して，元の入力を一意にたどることができず可逆になっていない．しかしながら可逆な論理演算は例えば制御 NOT ゲートや Toffoli ゲート，Fredkin ゲートなどによって構成することができ，可逆計算でも計算万能性があることが保証されている．

量子計算で扱われる多くのアルゴリズムは可逆なアルゴリズムであり，それらは万能性が保証された可逆論理演算子の合成になっている．以上の話題を扱っていた 1980 年代前半では，量子コンピュータが従来のコンピュータよりも高速かどうかはまだ理論的にも確固としたものがなかった．この後，まもなくして Deutsch が量子コンピュータを Turing 機械として定式化しアルゴリズム定量化の基礎を与え， 1990 年代には Shor アルゴリズムへと繋がっていくことになる．

Shor アルゴリズムは素因数分解を多項式時間で解くことができ，現時点 (2020/4/27) で見つかっている古典計算の最速アルゴリズムよりも理論上高速である．この事実は当時，大変な発見であったが，あくまでも理論的なもので，量子コンピュータの実機の作成は絶望的だった．

しかし 21 世紀に入ると超電導分野でブレイクスルーがあり，いくつかの量子コンピュータの実機が作成されることになった．まだごくごく小規模な計算しかできないが，着実に性能改善の努力がなされている．