量子コンピューターについて

現在、一般的に流通しているコンピューターを古典コンピューター、開発中の量子ビット等の技術を活用したものを量子コンピューターと定義します。
以下、私の認識になります。
5^2通りのビットが必要な計算をする場合です。
※OS等で必要となる領域は含みません。


古典コンピューターで必要となるCPUやメモリ
5^2×2(0と1の表現が必要なため)=64ビット(各ビットが単一の値しか示せないという前提)
量子コンピューターで必要となるCPUやメモリ
5^2(量子ビットが重ねあわせ状態での表現が可能なため)=32ビット

このように2種のコンピューターで必要となるスペックを数式で表すと
古典コンピューター:2×必要となる計算のビット数
量子コンピューター:必要となる計算のビット数

ということでしょうか?
上記の認識が違うということであればご指摘願います。
さらに他に量子コンピューターで使われる(根本的な定理等ではなく)数式が有るのであればご教示願います。

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2014/01/14 13:11:19
  • 終了:2014/01/19 08:46:35

ベストアンサー

id:language_and_engineering No.2

lang_and_engine回答回数170ベストアンサー獲得回数632014/01/17 09:45:51

上の方が回答して下さったとおりですが,簡単にまとめます。

質問文には,前提として間違っている部分があります。

古典コンピュータと量子コンピュータの違いは
「(ある作業のために)必要なスペック」
ではなく
「(ある作業のために)必要な時間」
です。

時間は計算時間です。
プログラミングの用語でいえばステップ数,
計算機科学の用語でいえば計算量のオーダーです。

つまり,
古典と量子で,同じスペックで同じ問題を解かせた時に,
量子のほうが圧倒的に時間が少なくて済む場合がある。
という結論になります。
必要なスペックがどう異なるのか,という観点ではないです。

id:practicalscheme

おお、わかりやすい! まとめありがとうございます。

2014/01/17 16:45:50
id:keijun5145

なるほど…
スペック=周波数のように考えていたのがそもそも違っていたのですね。
アルゴリズムというか量子の特性が時間に影響しているかということを問題にしないといけなかったのですね。
完全に量子コンピューターで計算を行うと古典コンピューターのクロック数が向上するようなイメージを持ってしまっていました。

わかりやすい解説と訂正ありがとうございます。

2014/01/19 08:45:29

その他の回答(1件)

id:practicalscheme No.1

practicalscheme回答回数157ベストアンサー獲得回数422014/01/16 05:37:04

スペックが何ビットになるか、というふうにひとくちには言えません。

まず、量子コンピュータは量子力学的効果を計算過程に使うというだけで、入力や確定した計算結果を格納しておくメモリなどは古典コンピュータと変わりません。演算器や中間結果を保持しておくレジスタ部分が異なるだけです。

また、量子コンピュータの利点を活かせるアルゴリズムを使わないと速くならないので、そのアルゴリズムが使えない問題でわざわざ量子コンピュータを使う意味はありません。

なので、量子コンピュータが実用化されるとしても、古典コンピュータを置き換えるのではなく、古典コンピュータに追加して使う、コプロセッサとかアクセラレータのようなものになるのではないかと思います。

ところで上で「速くなる」と書きましたが、これはCPUのクロックが4倍になるとか、バス幅が32ビットから64ビットになるとか、そういったスペック上の変化とはちょっと意味が違います。

古典コンピュータが苦手とする問題は、入力の大きさNに対して計算時間が2^N (2のN乗) で増えてゆくような問題です。Nが大きくなるにつれ計算時間がどんどん急激に大きくなるので、古典コンピュータでどんなにハードをがんばって速くしても、ちょっと大きなNを持ってくればまたすぐに膨大な時間がかかってしまいます。

このような問題の中に、量子アルゴリズムを使うと「Nの何乗」の計算時間で計算できるものがあります。たとえそれが N^100 (Nの100乗) だったとしても、Nが十分に大きければ 2^N (2のN乗) よりずっと小さくなるので、そういった問題に対して量子コンピュータの期待が高まっています。

有名なのは素因数分解で、古典アルゴリズムで知られている最速のものでも、入力の大きさNに対して 2^{定数×(((log N) (log log N)^2) ^ (1/3))} の計算時間が必要です。これが、量子コンピュータでは (log N)^3 で計算できることが知られています。

id:language_and_engineering No.2

lang_and_engine回答回数170ベストアンサー獲得回数632014/01/17 09:45:51ここでベストアンサー

上の方が回答して下さったとおりですが,簡単にまとめます。

質問文には,前提として間違っている部分があります。

古典コンピュータと量子コンピュータの違いは
「(ある作業のために)必要なスペック」
ではなく
「(ある作業のために)必要な時間」
です。

時間は計算時間です。
プログラミングの用語でいえばステップ数,
計算機科学の用語でいえば計算量のオーダーです。

つまり,
古典と量子で,同じスペックで同じ問題を解かせた時に,
量子のほうが圧倒的に時間が少なくて済む場合がある。
という結論になります。
必要なスペックがどう異なるのか,という観点ではないです。

id:practicalscheme

おお、わかりやすい! まとめありがとうございます。

2014/01/17 16:45:50
id:keijun5145

なるほど…
スペック=周波数のように考えていたのがそもそも違っていたのですね。
アルゴリズムというか量子の特性が時間に影響しているかということを問題にしないといけなかったのですね。
完全に量子コンピューターで計算を行うと古典コンピューターのクロック数が向上するようなイメージを持ってしまっていました。

わかりやすい解説と訂正ありがとうございます。

2014/01/19 08:45:29

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません