機械では解けないとされる問題がある。
問題が明確に定義できないもの。計算量の多すぎるもの。（俗にNP問題と言われるもの）
- 巡回セールスマン
- 囲碁
- 因数分解
- 組み合わせ全般
仕組みの概要
量子の双対性
主な内容は当ブログの別記事参照。
ここでは光子を例に取る。
偏光ビームスプリッタに45度偏光の光子を入れると、半分の確率でどちらかに出てくるが、どちらに出てくるかは測定してみないとわからない。
確率波
偏光ビームスプリッタを2つ用意して位相をずらすと、波が増幅しあうときには現れる確率が増え、打ち消しあうときには現れる確率が減る。こういった事象を確率波と呼んでいて、これを利用する。
測定した瞬間に確率が崩れる。
基本となるゲート
従来の機器の基本ゲートがNANDゲートであるように、
量子ゲートには二種類ある
-
スピン（アダマール変換）を行うゲート
-
制御q-bitの値に応じて反転を行うゲート
結果を取り出したら結果は一意に収束する
重ね合わせを用いることで、複数の入力パターンを一度に試すことはできる。 しかし「観測したらその瞬間に確率は壊れる」といったとおり、結果を取り出したら一つに収束してしまう
それでは使い物にならないと思うかもしれないが、確率波を操作することで特定の条件の確率だけを高めることが出来る。
以下に具体的なアルゴリズムを載せる。
ドイチュ-ジョサのブラックボックス
ゴール
あるビット列が入っており、そのビット列と入力のxorをとったものを出力する回路をブラックボックスとおく。 このとき、この「あるビット列」の０と１の個数が等しいか、全て０か１であるかを判別したい。
従来のアルゴリズム
一つ一つ順番に試す。最大でn/2+1まで試せばわかる。
量子コンピュータのアルゴリズム
１の状態を持つ量子ビットにアダマール変換をかけて50%の重ねあわせの状態にしてブラックボックスにかける。 あるビット数の量子を入力して、ブラックボックスにかけて変換したのちに制御ビットを反転する。 すると解があるもののみ位相がずれる。 それを再度ブラックボックスにかけてからアダマール変換をかける。
すると、均一の場合はアダマール変換をかけると全て0に収束するのだが、等分の場合は部分的に位相が反転しているためそうならない。
グローバーのアルゴリズム
ゴール
ある値を入れた時のみ１（あるいは入力を反転したもの）を出力する回路をブラックボックスとおく。 このとき、「ある値」を調べたい
従来のアルゴリズム
一つ一つ順番に試す。最大でnまで試せばわかる。
量子コンピュータのアルゴリズム
１の状態を持つ量子ビットにアダマール変換をかけて50%の重ねあわせの状態にしてブラックボックスにかける。 すると特定のビット列の場合のみ反転するので、その結果に「折り返し量子回路」をかける。（この処理は複雑だが、一つだけずれているビット列があるとそれの比率を上げてくれる。） その操作を何度か繰り返すことで、特定のビット列の発生する確率がドンドン高くなるので、適度なタイミングで測定する。 高い確率で求めたいビット列になっているので、試しにそのビット列を入力してみて正しく反転するか確認する。 もし違っていたら同じ操作を繰り返す。
ショアのアルゴリズム。
ゴール
因数分解を高速に行う。
ユークリッドの互除法を使って最大公約数を求める方法は見つかっている。
ある数nに対して互いに素な数xを用意し、x^r/nの余りが1を満たす自然数rを探す。
それが偶数であれば、(x^r)/2-1と(x^r)/2+1はnと１以外の約数を持つ。
これでｎが因数分解できる。あとはこの繰り返し。
このうち、rを効率よく探す方法がなかった。
従来のアルゴリズム
一つ一つ順番に試す。
量子コンピュータのアルゴリズム
（※理解不足）
実現に向けて
用いる量子として光子が検討に上がっている。 すでに一粒単位で取り出す方法や検出する方法が確率されている。
また、アダマールゲートは半透鏡か偏光で、量子位相ゲートは鏡の中にセシウム原子を置くことで解決しようという試みがある。
量子暗号
暗号は中間車に盗聴されてしまう危険を常に孕んでいる。
ところが量子暗号を使うと、盗聴者が覗き見た時点で答えが変わることを利用する。
これが普及すれば、インターネットにおける認証局が不要になる
送信側は45度偏光させたものかそのままかの光子を送る。 受けては偏光して受け取るかそのまま受け取るかをランダムに選び受診する。 このとき、もちろん意図しない伝え方でつ変わることがありうる。
盗聴者がいた場合、送信受診の偏光具合が合っていても誤った情報が送られることが25%ありえる。
それを定期的に検出することで、その暗号が他者に傍受されていないか調べることができる。