量子コンピューターってどんな計算機？
ゲート型と呼ばれる量子コンピューターを３行で表現してみましょう。
$ n $量子ビットの量子コンピューターは、
・$2^n$個の数を同時に表せるレジスタ（内部は、$|\alpha_n|^{2}+|\beta_n|^{2}=1$を満たす$ n $個の複素数組$\alpha_n,\beta_n$）をもち、
・そのレジスタに対して、$2n \times 2n $の複素係数のユニタリ行列の掛け算がある程度の回数だけ行えて、
・計算結果は実数値で得られ、しかも確率的にしか得られない。だから何度も試行しその確率も出力する。
という計算機です。
以上！っと。
小ネタ的にここで終わろうかなぁ、とも思ったのですが、各方面からツッコミが来そうですし、折角のアドベントカレンダーの記事ですから、以下で細かく解説してみたいと思います。
細かなところは気にされない方は、本記事の最後「量子コンピューターは本当に凄いのか」まで飛ばしてください。
なお、下図「量子コンピューターの概念図」1も、ついでに載せておきます。
【量子コンピューターの概念図】（勝手な解釈版）
扱う情報の最小単位「量子ビット」
「$|\alpha_n|^{2}+|\beta_n|^{2}=1$を満たす$ n $個の複素数組$\alpha_n,\beta_n$」
従来のコンピューター（「古典コンピューター」と呼びます）の情報の最小単位は 0 か 1 の二値（デジタル）を表す「ビット」です。これに対して、量子コンピューターの情報の最小単位「量子ビット」は、
$$ \{ \left( \begin{array}{c} \alpha \cr \beta \end{array} \right) \;\mid\;\alpha,\beta \in \mathbb{C},\,|\alpha|^2+|\beta|^2=1 \} \tag{1}$$ と、２つの複素数の組みの情報を持ちます。
一般的に、複素数$c \in \mathbb{C}$ を $ r e^{i\phi} (r,\theta \in \mathbb{R} )$ と表記できることを使うと、（$|e^{i\phi}|^2=1$の性質も使って）
$$ \rightarrow \{ \left( \begin{array}{c} r_{\alpha} e^{i\phi_{\alpha}} \cr r_{\beta} e^{i\phi_{\beta}} \end{array} \right) \;\mid\;r_{\alpha},r_{\beta},\phi_{\alpha},\phi_{\beta} \in \mathbb{R},\,|r_{\alpha}|^2+|r_{\beta}|^2=1 \} $$ $ |r_{\alpha}|^2+|r_{\beta}|^2=1 $ の条件から、$ r_{\alpha}=\cos{\theta/2},r_{\beta}=\sin{\theta/2}\,(0\le\theta\lt\pi) $と置き換えてよく、さらに、$ \phi_{\alpha}=\gamma, \phi_{\beta}=\gamma+\varphi $ としても一般性が失われないので、$$ \rightarrow \{ e^{i\gamma} \left( \begin{array}{c} \cos{\theta/2} \cr e^{i\varphi}\sin{\theta/2} \end{array} \right) \;\mid\;\theta,\varphi,\gamma \in \mathbb{R},\,0\le\theta\lt\pi,\,0\le\varphi,\gamma\lt2\pi \} \tag{2}$$ です。
ここでは、$ \gamma $ は任意にとれます。ただし、単一の１量子ビットの場合は、この $ \gamma $ を常に 0 にするように座標系を調整する（$ e^{-i\gamma}$を掛ける）という工夫ができます。そうすることで、１量子ビットの情報は、半径 1 の球面上の点の集合（「ブロッホ球」という）と等価な情報となります。
いま、古典コンピューターの 0 と 1 を量子ビットで考えてみます。
$$ \begin{align} \text{古典コンピューターの} 0 \text{は、量子コンピューターでは} \left( \begin{array}{c} 1 \cr 0 \end{array} \right) \text{です。} \left( \begin{array}{c} 0 \cr 0 \end{array} \right) \text{ではありません。} \\ \text{古典コンピューターの} 1 \text{は、量子コンピューターでは} \left( \begin{array}{c} 0 \cr 1 \end{array} \right) \text{です。} \left( \begin{array}{c} 1 \cr 1 \end{array} \right) \text{ではありません。} \end{align} $$
さて、ここで、ベクトルの簡略な表記を導入しておきます。この縦並びのベクトル表記は、紙面上書きづらく、読みづらいために、次のような記述（「ケット・ベクトル」という）で代用します。$$ \lvert 0 \rangle := \left( \begin{array}{c} 1 \cr 0 \end{array} \right) ,\quad \lvert 1 \rangle := \left( \begin{array}{c} 0 \cr 1 \end{array} \right) $$
こう書くと、古典ビットの 0 が量子ビットでは $ \lvert 0 \rangle$、古典ビットの 1 が量子ビットでは $ \lvert 1 \rangle $ と対応づけやすくなります。そしてこの表記により、式(1)は、$$ \{ \alpha \lvert 0 \rangle + \beta \lvert 1 \rangle \;\mid\;\alpha,\beta \in \mathbb{C},\,|\alpha|^2+|\beta|^2=1 \} \tag{3}$$ と書けます。多少、説明文の行が節約できそうです。
まとめると、$n$量子ビットがあるということは、この１量子ビットが $n$ 個あることを表します。つまり、$|\alpha_n|^{2}+|\beta_n|^{2}=1$という制約条件はありますが、その「制約条件を満たす$2n$個の複素数が、$n$量子ビットの情報」です。
ちなみに、$n$量子ビットの基底ケットベクトルでの表記は、$\lvert q_0 q_1 \cdots q_{n-1} \rangle \quad(q_0,q_1,\dots,q_{n-1}= 0\,or\,1)$ です#補足説明１。
「$2^n$個の数を同時に表せるレジスタ」
１量子ビットの値で次のような量子ビットがあるとします。 $$ \frac{1}{\sqrt{2}} \left( \begin{array}{c} 1 \cr 1 \end{array} \right) = \frac{1}{\sqrt{2}}\lvert 0 \rangle + \frac{1}{\sqrt{2}}\lvert 1 \rangle \tag{4}$$ これは、$ |\alpha|^2+|\beta|^2=1 $を満たす正しい量子ビットです。この量子ビットが示す情報はどのような意味があるのでしょうか。$\lvert0\rangle$（古典ビットの 0）でも、$\lvert1\rangle$（古典ビットの 1）でもなく、どちらともつかない中途半端な値のようです。いいかえると、$\lvert0\rangle$ でもあり、$\lvert1\rangle$ でもあるような値とも言えます。
この重ね合わせ状態を情報として保持できることが、量子ビットの特徴の１つです。
さて、この 0 と 1 を同時に表してる重ね合わせ状態を$\lvert0\rangle$から作るための演算を紹介します。アダマール（Hadamard）演算子$H^{(2)}$という操作が有名です。$$ \displaystyle H^{(2)} = \frac{1}{\sqrt{2}}\left( \begin{array}{c} 1 & 1 \cr 1 & -1 \end{array} \right) \tag{5}$$ これを使って、$$ H^{(2)}\lvert0\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle + \lvert1\rangle) $$と重ね合わせ状態を作れます。
１量子ビットについてみましたが、一般化すると、$n$量子ビットがあれば、次のような$2^n$個のすべての重ね合わせ状態をつくることができます。
$$ \displaystyle \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1} \lvert q_i \rangle = \frac{1}{\sqrt{2^n}} (\lvert0\rangle+\lvert1\rangle+ \dots +\lvert 2^n-1 \rangle ) \tag{6}$$
すなわち、「$n$量子ビットは、$2^n$個の数を同時に表せる」というのは、量子ビットのこの特性のことを意味しています。
量子ビットに対する演算「ユニタリ行列の掛け算」
「$2n \times 2n $の複素係数のユニタリ行列の掛け算」
$n$ 量子ビットの演算の全体は、$2n$ 次の特殊ユニタリ群 $SU(2n) := \{ g \in U(2n)\,\mid\, \det{g} = 1 \}$ となります。
例えば、１量子ビットの演算全体は、$SU(2)$ で、その表現（一般式）は
$$ U^{(2)} = \left( \begin{array}{c} \alpha & -\beta^{\dagger} \cr \beta & \alpha^{\dagger} \end{array} \right)\;\alpha,\beta \in \mathbb{C},\,|\alpha|^{2}+|\beta|^{2}=1 \tag{7}$$ です。
ここで、$2\times2$行列のパウリ（Pauli）演算子を定義します。
$$ \displaystyle \sigma_x = \left( \begin{array}{c} 0 & 1 \cr 1 & 0 \end{array} \right),
\quad \sigma_y = \left( \begin{array}{c} 0 & -i \cr i & 0 \end{array} \right),
\quad \sigma_z = \left( \begin{array}{c} 1 & 0 \cr 0 & -1 \end{array} \right) \tag{8} $$このパウリX演算子$(\sigma_x)$、パウリY演算子$(\sigma_y)$、パウリZ演算子$(\sigma_z)$を使って、$U^{(2)}$を表すと、$$ U^{(2)} = i\sigma_x x + i\sigma_y y + i\sigma_z z\quad x,y,z \in \mathbb{R}, |x|^{2}+|y|^{2}+|z|^{2}=1 \tag{9}$$とも表せます。
また、$n$ 量子ビットの演算を示す $SU(2n)$ は、$SU(2)$ の表現 $ U^{(2)} $ を使って、$$ \displaystyle \bigotimes_{i=0}^{n}U_i^{(2)},\quad \left( \begin{array}{c} U^{(2)} & O^{(2,2n-2)} \cr O^{(2n-2,2)} & U^{(2n-2)} \end{array} \right) \tag{10}$$ 等の形式の演算2です#補足説明２。
「ある程度の回数だけ」
理論的な量子コンピューターは、ユニタリ行列の演算をどれだけの回数でも操作できなければなりません。しかし、実際に物理現象を使って実現する量子コンピューターは、量子状態を保持しつづけながら計算を行わなければなりません。
量子的な物理現象を使うため、安定的に計算させるには、かなり高度な技術が要求されます。現実的にはこの計算時間には限りがあります。この量子状態を保持しつづけられる計算可能な時間を「コヒーレンス時間3」と呼びます。
つまり、ユニタリ行列の掛け算は、ある程度の回数だけしか行えません。
「測定」で計算結果を出す
「計算結果は実数値」と「その値をとる確率」を出力
量子コンピューターでは、情報が複素数で保持、計算されているため、それを直接的に得ることはできません。そこで、「測定」（あるいは「観測」という）でその値を実数値で取得します。内部的、論理的にはエルミート行列を掛ける計算操作として行います。
通常の量子計算は、ユニタリ行列の繰り返し操作で行いました。このユニタリ行列操作は、１量子ビットで考えるとブロッホ球面内の量子ビット情報を、同じブロッホ球面内に写す操作です。しかし、測定で用いるエルミート行列操作は、「射影」と呼ばれ、そうではありません。例えると、球面上の点をライトで照らして、その「影」を見るようなイメージです。
さて、測定は、どのようなエルミート行列を使うかによって種類があります。
最もオーソドックスな（IBM Qでも使われている）方法は、Z基底の射影です。射影演算子は、$$ \displaystyle P = \lvert0\rangle\langle0\rvert = \left( \begin{array}{c} 1 & 0 \cr 0 & 0 \end{array} \right),\quad Q = \lvert1\rangle\langle1\rvert = \left( \begin{array}{c} 0 & 0 \cr 0 & 1 \end{array} \right) \tag{11}$$ を使います。$ \lvert\psi_1\rangle=\lvert0\rangle $ と $\lvert\psi_2\rangle=\frac{1}{\sqrt{2}}(\lvert0\rangle+\lvert1\rangle) $ を、射影演算子 P で測定すると、$ \langle\psi_1\rvert P \lvert\psi_1\rangle = 1 $ と $ \lvert\psi_1\rangle $ は必ず $ \lvert0\rangle $ が得られ、一方、$ \lvert\psi_2\rangle $は、$ \langle\psi_2\rvert P \lvert\psi_2\rangle = \frac{1}{2} $ と確率$ 1/2 $で、$ \lvert0\rangle $ が得られます。ただし、この測定では、測定値として $ \lvert0\rangle $ が得られたときに、その元となった純粋な量子状態が、$ \lvert\psi_1\rangle=\lvert0\rangle $ だったのか、 $\lvert\psi_2\rangle=\frac{1}{\sqrt{2}}(\lvert0\rangle+\lvert1\rangle) $ だったのかはわかりません。
そこで、もう一つの測定方法「ＰＯＶＭ」（正値演算子測度）を紹介します。
詳しい数理は抜きにして、一例を挙げます。次のようなエルミート行列の組みで測定します。$$ \displaystyle E_1 = \left( \begin{array}{c} 0 & 0 \cr 0 & 1/2 \end{array} \right),\, E_2 = \left( \begin{array}{c} 1/2 & -1/2 \cr -1/2 & 1/2 \end{array} \right),\, E_3 = \left( \begin{array}{c} 1/2 & 1/2 \cr 1/2 & 0 \end{array} \right) \tag{12}$$補足説明３の計算のとおり、$E_1,E_2$で測定した結果は片方の、確率が$ 0 $となり、元の純粋状態の違いが測定によって確認できます。
「確率的にしか得られない」から「何度か試行する」
イメージしやすいようにZ基底の射影で考えます。
Z基底の射影を、１量子ビットの例でみると、量子ビットをブロッホ球のZ軸（$\lvert0\rangle$と$\lvert1\rangle$の軸）で影に写してみて、$\lvert0\rangle$寄りか、$\lvert1\rangle$寄りかを見ます。例え、値が$\lvert0\rangle$と得られたとしても、あくまで$\lvert0\rangle$寄りだったのだろうという意味でしかなく。たまたま、$\lvert0\rangle$が得られたということで、次に測定したときには、$\lvert1\rangle$になるかもしれません。
つまり、測定は、確率的にしか得られません。
そこで、この測定を何度か試みることにより、その値が出力される確率を計る必要があります。
勿論、問題設定とその計算が一意に解がある場合は、何度試みても同じ値になります。（かえって、量子的ゆらぎの影響で、答えが１つしかない計算でも、確率100%で測定できるかは、保証されないかもしれません。）
メモリは？外部記憶装置は？
量子状態のまま、状態を保持する方法は、理論的には提案されていますが、技術を模索している段階で、近々に実現するような状況ではありません。つまり、現状では、量子レジスタでの計算途中の結果は、外部には一時的に保持しておくことができません。そのため、量子レジスタ上の演算は、出力まで一気に作用させる必要があります。
量子コンピューターは本当に凄いのか
「量子コンピューターが凄い」と言われる大きな理由としては、$n$量子ビットの量子コンピューターは、$2^n$個の数を同時に表せる計算レジスタを備えているということです。いま、50量子ビット前後の量子コンピューターが、既存のコンピューターの性能を凌駕するとされています。このとき、$ n = 50 $ なので $ 2^{50} = 1.125899 \times 10^{15} $ までの値を同時にもてるということになります。これは、同じ数の計算レジスタを持っていることを意味します。$ 10^{15} $ 個となるとペタ（Peta）のオーダーです。古典コンピューターでは、この容量のメモリを搭載しただけでも凄そうですが、ここで比較しているのはCPUやGPUの中にあるレジスタです。そう考えると、一見、とても凄いです。
しかし、です。
この同時に数を扱えるという裏側には、「重ね合わせ状態」という複数の状態（数）が重なり合って同時に存在することが前提になります。$n$が大きくなればなるほど、物理的に重ね合わせ状態を安定的に維持するのは難しくなります。まず、重ね合わせられるかのハードルがあり、計算できる時間だけそれを維持し続けられるかに次のハードルがあります。さらには、安定させるためのエラー訂正のために、大多数の量子ビットをまとめて扱わなければならない4ため、有効に使える量子ビットは、$ 1/2^{k} $（k はその物理系の品質により調整）だけ減ってしまいます。
果たして、それだけの比較で凄いと言われてよいのでしょうか？
実は、全ての値を同時にもてることのメリットを生かした「量子アルゴリズム」の存在も、凄いと言われる要因です。因数分解が現実的な時間で解けるという「ショアのアルゴリズム」が示されています。それは、凄い！！
ただ、よく調べると、既知のアルゴリズムを利用しようとすると、２つの点で問題がみつかります。
１つは、単純に今、暗号などで使われている数字を量子ビットで表そうとすると、50量子ビット程度では、足らないということです。おそらく３桁以上で、量子ビット数が増えなければ有用ではありません。
そしてもう１つの問題は、アルゴリズムを「量子プログラム」にするための「量子コンパイラ」などのプログラミング環境が整っていないことです。本記事の冒頭の【量子コンピューターの概念図】で説明します。「量子プログラム」$ f(x) $ から「量子アセンブリ」であるユニタリ操作 $ U_{f(x)}^{(n)} $ に変換する仕組みが「量子コンパイラ」です。
このように、量子アルゴリズムがあっても、量子コンピューターを扱うための周辺環境が不足しています。
おそらく50量子ビット程度の量子コンピューターは、登場するでしょう。しかし、その量子ビットの範囲で有用な課題を見つける必要があります。これから先しばらくは、今までできなかった有用な問題の解法や、量子アルゴリズムの発見を目指しつつ、量子プログラミング環境の進化が盛んになることと思います。
補足説明１
例えば、３量子ビットでは、$$ \lvert 000 \rangle := \left( \begin{array}{c} 1 \cr 0 \cr 0 \cr 0 \cr 0 \cr 0 \cr 0 \cr 0\end{array} \right),
\quad \lvert 001 \rangle := \left( \begin{array}{c} 0 \cr 1 \cr 0 \cr 0 \cr 0 \cr 0 \cr 0 \cr 0\end{array} \right),
\quad \lvert 010 \rangle := \left( \begin{array}{c} 0 \cr 0 \cr 1 \cr 0 \cr 0 \cr 0 \cr 0 \cr 0\end{array} \right),
\quad \lvert 011 \rangle := \left( \begin{array}{c} 0 \cr 0 \cr 0 \cr 1 \cr 0 \cr 0 \cr 0 \cr 0\end{array} \right), \\
\lvert 100 \rangle := \left( \begin{array}{c} 0 \cr 0 \cr 0 \cr 0 \cr 1 \cr 0 \cr 0 \cr 0\end{array} \right),
\quad \lvert 101 \rangle := \left( \begin{array}{c} 0 \cr 0 \cr 0 \cr 0 \cr 0 \cr 1 \cr 0 \cr 0\end{array} \right),
\quad \lvert 110 \rangle := \left( \begin{array}{c} 0 \cr 0 \cr 0 \cr 0 \cr 0 \cr 0 \cr 1 \cr 0\end{array} \right),
\quad \lvert 111 \rangle := \left( \begin{array}{c} 0 \cr 0 \cr 0 \cr 0 \cr 0 \cr 0 \cr 0 \cr 1\end{array} \right).$$と、$ 8\,(=2^3) $個のベクトルが基底となり、$$
\alpha_0\lvert000\rangle+\alpha_1\lvert001\rangle+\alpha_2\lvert010\rangle+\alpha_3\lvert011\rangle+\alpha_4\lvert100\rangle+\alpha_5\lvert101\rangle+\alpha_6\lvert110\rangle+\alpha_7\lvert111\rangle = \left( \begin{array}{c}
\alpha_0 \cr \alpha_1 \cr
\alpha_2 \cr \alpha_3 \cr
\alpha_4 \cr \alpha_5 \cr
\alpha_6 \cr \alpha_7 \cr
\end{array} \right)$$ と表せます。
補足説明２
例えば、アダマール演算 $ H^{(4)} $ は、$ H^{(2)} \otimes H^{(2)} $ です。式(5)を使って、
$$ \displaystyle \begin{align} H^{(4)} = \frac{1}{\sqrt{2}}\left( \begin{array}{c} 1 \cdot H^{(2)} & 1 \cdot H^{(2)} \cr 1 \cdot H^{(2)} & -1 \cdot H^{(2)} \end{array} \right)
= \frac{1}{\sqrt{2}}\left( \begin{array}{cccc} 1 \cdot \frac{1}{\sqrt{2}}\left( \begin{array}{c} 1 & 1 \cr 1 & -1 \end{array} \right) & 1 \cdot \frac{1}{\sqrt{2}}\left( \begin{array}{c} 1 & 1 \cr 1 & -1 \end{array} \right) \cr 1 \cdot \frac{1}{\sqrt{2}}\left( \begin{array}{c} 1 & 1 \cr 1 & -1 \end{array} \right) & -1 \cdot \frac{1}{\sqrt{2}}\left( \begin{array}{c} 1 & 1 \cr 1 & -1 \end{array} \right) \end{array} \right) \\
= \frac{1}{2} \left( \begin{array}{c} 1&1&1&1 \cr 1&-1&1&-1 \cr 1&1&-1&-1 \cr 1&-1&-1&1 \end{array} \right) \end{align}$$ と表せます。
制御NOT演算 CNOT（$CX$）は、$$ \displaystyle CX = \left( \begin{array}{c} I^{(2)} & O^{(2)} \cr O^{(2)} & X \end{array} \right) = \left( \begin{array}{c} 1&0&0&0 \cr 0&1&0&0 \cr 0&0&0&1 \cr 0&0&1&0 \end{array} \right)$$ と表せます。
補足説明３
Z基底の射影で見た例、$ \lvert\psi_1\rangle=\lvert0\rangle $ と、 $\lvert\psi_2\rangle=\frac{1}{\sqrt{2}}(\lvert0\rangle+\lvert1\rangle) $ に作用してみましょう。
$ \lvert\psi_1\rangle=\lvert0\rangle $ の場合：$$ \begin{align*} \langle\psi_1\rvert E_1 \lvert\psi_1\rangle = \left( \begin{array}{cc} 1 & 0 \end{array} \right) \left( \begin{array}{c} 0 & 0 \cr 0 & 1/2 \end{array} \right) \left( \begin{array}{c} 1 \cr 0 \end{array} \right) = 0 \\
\langle\psi_1\rvert E_2 \lvert\psi_1\rangle = \left( \begin{array}{cc} 1 & 0 \end{array} \right) \left( \begin{array}{c} 1/2 & -1/2 \cr -1/2 & 1/2 \end{array} \right) \left( \begin{array}{c} 1 \cr 0 \end{array} \right) = 1/2 \\
\langle\psi_1\rvert E_3 \lvert\psi_1\rangle = \left( \begin{array}{cc} 1 & 0 \end{array} \right) \left( \begin{array}{c} 1/2 & 1/2 \cr 1/2 & 0 \end{array} \right) \left( \begin{array}{c} 1 \cr 0 \end{array} \right) = 1/2 \end{align*} $$
$\lvert\psi_2\rangle=\frac{1}{\sqrt{2}}(\lvert0\rangle+\lvert1\rangle) $ の場合：$$ \begin{align*} \langle\psi_2\rvert E_1 \lvert\psi_2\rangle = \frac{1}{2} \left( \begin{array}{cc} 1 & 1 \end{array} \right) \left( \begin{array}{c} 0 & 0 \cr 0 & 1/2 \end{array} \right) \left( \begin{array}{c} 1 \cr 1 \end{array} \right) = 1/4 \\
\langle\psi_2\rvert E_2 \lvert\psi_2\rangle = \frac{1}{2} \left( \begin{array}{cc} 1 & 1 \end{array} \right) \left( \begin{array}{c} 1/2 & -1/2 \cr -1/2 & 1/2 \end{array} \right) \left( \begin{array}{c} 1 \cr 1 \end{array} \right) = 0 \\
\langle\psi_2\rvert E_3 \lvert\psi_2\rangle = \frac{1}{2} \left( \begin{array}{cc} 1 & 1 \end{array} \right) \left( \begin{array}{c} 1/2 & 1/2 \cr 1/2 & 0 \end{array} \right) \left( \begin{array}{c} 1 \cr 1 \end{array} \right) = 3/4 \end{align*} $$ となり、確率 0 の結果が異なる演算となります。