はじめに
Qiitaアドベントカレンダーの時期なので,
勉強中の量子コンピュータについて数日にわたりまとめる.
一日目は量子コンピュータについての導入ということで,基本的な単語をまとめる.
量子ゲート等には次回以降の記事で触れていきたい.
量子コンピュータとは？
量子コンピュータは,従来のコンピュータとは異なる原理で計算を行う
次世代のコンピュータである.
量子コンピュータは,量子力学の法則を利用して計算を行い,従来のコンピュータでは解くことが難しい問題を高速に解決することができるとされている.
次世代のコンピュータである量子コンピュータの研究や開発は活発に取り組まれており,
その実現が期待されている.
古典コンピュータと量子コンピュータ
古典コンピュータと量子コンピュータの最も異なる点は、情報の表し方である.
それぞれの情報の表し方は以下のようになる.
古典コンピュータ:情報は0か1のどちらか(古典ビット)
量子コンピュータ:情報は0と1の両方の状態を同時にとれる(量子ビット)
1量子ビット
量子ビットは0と1の両方の状態を同時に保持できる.(重ね合わせの状態)
量子ビットは複素数を用いて,2次元の列ベクトルで表す.
複素数α,βを用いて1量子ビットは以下のように表現できる.
\left(
\begin{matrix}
α \\
β
\end{matrix}
\right)
\quad または \quad
α\left(
\begin{matrix}
1 \\
0
\end{matrix}
\right)
+
β\left(
\begin{matrix}
0 \\
1
\end{matrix}
\right)
\quad
(ただし,|α|^2 + |β|^2 = 1)
ベクトルによる表現の代わりに, $|0\rangle$, $|1\rangle$というブラケット記法を用いることもある.
すると、上のベクトルは以下のように表現できる.
α|0\rangle + β|1\rangle
これらは$|α|^2$の確率で0が観測され、$|β|^2$の確率で1が観測されることを意味する.
2量子ビット
複数量子ビット状態は1量子ビット状態のテンソル積で表現される.
2量子ビットの場合は$|0\rangle ⊗ |0\rangle$,省略形で$|0\rangle|0\rangle$ や$|00\rangle$で表記する.
以下はテンソル積の計算例である.
x ⊗ y =
\left(
\begin{matrix}
a \\
b
\end{matrix}
\right)
⊗
\left(
\begin{matrix}
c \\
d
\end{matrix}
\right)
=
\left(
\begin{matrix}
ay \\
by
\end{matrix}
\right)
=
\left(
\begin{matrix}
ac \\
ad \\
bc \\
bd
\end{matrix}
\right)
2量子ビットをブラケット記法を用いて表すと以下のようになる.
α|00\rangle + β|01\rangle + γ|10\rangle + δ|11\rangle
これは
00が測定される確率が$|α|^2$, 01が測定される確率が$|β|^2$
10が測定される確率が$|γ|^2$, 11が測定される確率が$|δ|^2$
であることを表している.
$|00\rangle, |01\rangle$などの演算結果の覚え方としては0と1の並び方に注目すればよい.
|00\rangle
=
\left(
\begin{matrix}
1 \\
0 \\
0 \\
0
\end{matrix}
\right)
,
|01\rangle
=
\left(
\begin{matrix}
0 \\
1 \\
0 \\
0
\end{matrix}
\right)
,
|10\rangle
=
\left(
\begin{matrix}
0 \\
0 \\
1 \\
0
\end{matrix}
\right)
,
|11\rangle
=
\left(
\begin{matrix}
0 \\
0 \\
0 \\
1
\end{matrix}
\right)
論理回路と同じように00が1番目,01が2番目,10が3番目,11が4番目の数字の並び方だと捉え,
n番目の数は上からn番目の位置が1になると覚えればよい.
このように考えると,
$|001\rangle$は2番目に現れる数字の並びであるので上から2番目の位置が1となり,
$|110\rangle$は6番目に現れる数字の並びであるので上から6番目の位置が1となる.
また,n量子ビットであれば$2^n$通りの状態の重ね合わせを表現することができる.
測定
古典ビットにおいては,0を読み取ると0になり,1を読みだすと1になる.(当たり前だが)
しかし,量子コンピュータの世界では,当たり前ではない.(量子ビットの定義からわかる通り)
$\frac{1}{\sqrt{2}} |0\rangle + \frac{1}{\sqrt{2}} |1\rangle$のように,$|0\rangle$でも$|1\rangle$でもない状態を表すことができる.
量子コンピュータでは,その測定値は確率的に変化する.
量子ゲート
古典コンピュータでは,ビット演算を行うゲート(AND, OR, XORなど)を使い,
ビットの状態を変化させることで計算を行う.
量子コンピュータにおいて,古典コンピュータのゲートに相当するものが,量子ゲートとなる.
量子ゲートは量子ビットを操作する役割を持つが,
量子ゲートの操作は主に行列で行う.
量子ゲートの操作は可逆的な操作である必要がある.
変化した状態に対して元に戻す変化が可能であることを可逆という.
要するに,量子ゲートの操作をする際には,出力から入力を導き出せなければならない.
代表的な量子ゲートは,H, X, Y, Z, CNOT, Toffoliゲートなどがある.
ほかにもさまざまなゲートが多数存在する.
代表的な量子ゲートは次回の記事で扱う.
量子アルゴリズム
量子ビットは重ね合わせによって多数の状態を同時に表現できる.
n個の量子ビットがあれば$2^n$個の状態を表現でき、量子ゲートでそれらの状態を
同時に操作することが可能である.
だからと言って古典コンピュータと比べて並列な分,高速に計算ができている訳ではない.
(勘違いされがちだが)
量子コンピュータでの計算の結果は,観測によってどれか一つしか得られない.
したがって,ほしい状態が1つの場合,それを得られる確率は$1/2^n$で,
工夫しなければ古典コンピュータと同じだけの回数計算を繰り返す必要がある.
ほしい状態を高確率で得られるように量子計算を設計したアルゴリズムを量子アルゴリズムと呼ぶ.
代表的な量子アルゴリズムとして,
アダマールテスト,Shorのアルゴリズムなどがある.
(おまけ)ブラケット記法
$|φ\rangle$をケットベクトルと呼ぶ.(ケットベクトル=列ベクトル)
ケットベクトル$|φ\rangle$, $|ψ\rangle$の内積をブラケットと呼び,以下のように表す
\langle φ |ψ\rangle
参考にしたサイト