第 14 回量子コンピュータ

本日の内容

14-1. 量子コンピュータ

14-1. 量子コンピュータ

qubit とテンソル積

量子コンピュータでは、1bitの情報、つまり、0または1のどちらかを保持する情報の単位をqubitと呼ぶ。具体的には0 を表す現象と 1 を表す現象のどちらかを観測できるような物理現象で情報を保持する。そのため、qubit は以下のように表される (この 0と1は情報の表現であって、数学の0とは異なることに注意)。

|ψ⟩ = a |0⟩ + b |1⟩

{|a|}^{2} + {|b|}^{2} = 1

状態 0 を $|0⟩ = (\begin{matrix} 1 \\ 0 \end{matrix})$ とし、 $|1⟩ = (\begin{matrix} 0 \\ 1 \end{matrix})$ とし、これをパウリの σ_zで観測すると、 0 を観測する確率が ${|a|}^{2}$ , 1 を観測する確率が ${|b|}^{2}$ となる。

複数の状態 $ψ$ , $φ$ に対して、テンソル積 $|ψ⟩ \otimes |φ⟩$ を考える。これは、内積空間 V, W に対して、それぞれの正規直交基底が $\{|ξ_{1}⟩ ... |ξ_{n}⟩\}$ , $\{|η_{1}⟩ ... |η_{m}⟩\}$ である時、 $|ψ⟩ = \sum_{i = 1}^{n} a_{i} |ξ_{i}⟩$ , $|φ⟩ = \sum_{j = 1}^{m} b_{j} |η_{j}⟩$ の時、 $|ψ⟩ \otimes |φ⟩ = \sum_{i = 1}^{n} \sum_{j = 1}^{m} a_{i} b_{j} |ξ_{i}⟩ \otimes |η_{j}⟩$ なお、この場合、基底どうしのテンソル積は単なる直積として考える。また、テンソル積を $|ψ⟩ |φ⟩$ や、 $|ψ, φ⟩$ や、 $|ψ φ⟩$ とも表す。

さらに、 $|ψ^{'} φ^{'}⟩ = \sum_{i = 1}^{n} \sum_{j = 1}^{m} a_{i}^{'} b_{j}^{'} |ξ_{i} η_{j}⟩$ と $|ψ φ⟩$ の内積を考える。 $⟨ξ_{i} η_{j}| ξ_{k} η_{l}⟩ = ⟨ξ_{i}| ξ_{k}⟩ ⟨η_{j}| η_{l}⟩$ と定義することにより、 $⟨ψ φ| ψ^{'} φ^{'}⟩ = \sum_{i, j, k, l} a_{i}^{*} b_{j}^{*} a_{k}^{'} b_{l}^{'} ⟨ξ_{i}| ξ_{k}⟩ ⟨η_{j}| η_{l}⟩ = \sum_{i, j} a_{i}^{*} b_{j}^{*} a_{i}^{'} b_{j}^{'} = (\sum_{i} a_{i}^{*} a_{i}^{'}) (\sum_{j} b_{j}^{*} b_{j}^{'}) = ⟨ψ| ψ^{'}⟩ ⟨φ| φ^{'}⟩$ また、 $(\hat{A} \otimes \hat{B}) (|ψ⟩ \otimes |φ⟩) = (\hat{A} |ψ⟩) \otimes (\hat{B} |φ⟩)$

状態が複素ヒルベルト空間の元であれば、テンソル積で得られた複合状態は次元が違うが複素ヒルベルト空間の元なので、量子力学の公理を満たすことができる。

非クローン化定理

観測されていない任意の量子状態をコピーすることはできないことを示します。これを示すには仮に二つの量子状態に対してコピーができたとき、必ず満たすべき状態が導かれるため、任意の状態のコピーにならないことを示します。まず、状態 ψ と φ のコピーができるとします。これは初期の任意状態 s があるユニタリ行列 U によって、 ψ や φ に遷移できることを意味します。

U |ψ s⟩ = |ψ ψ⟩

U |φ s⟩ = |φ φ⟩

この二つの内積を取ります。

⟨U ψ s| U φ s⟩ = ⟨ψ ψ| φ φ⟩

⟨ψ s| U^{†} U| φ s⟩ = ⟨ψ ψ| φ φ⟩

⟨ψ| φ⟩ ⟨s| s⟩ = ⟨ψ| φ⟩ ⟨ψ| φ⟩

⟨ψ| φ⟩ = {⟨ψ| φ⟩}^{2}

⟨ψ| φ⟩ = 0, 1

つまり、どのようなユニタリ行列でもコピーができる状態は平行か直交かしかなく、任意の状態のコピーはできないということです。

量子コンピュータの基本構成

量子コンピュータの実現性を示すためには、基本的には論理回路の構成と同様にします。論理回路の構成を示すには、基本ゲートを定め、入力長を固定します。そして、任意の入力長に対して、基本ゲートのみで回路の構成の仕方のアルゴリズムを与えます。（なお、回路の非存在を示すような場合、入力長毎のアルゴリズムを与えられないような回路列も想定できるため、 uniformity, non-uniformity という区分を考えることがあります）。通常の論理回路では、任意の2入力論理ゲートや、多入力 and, or, nand 回路などを想定します。

しかし量子コンピュータでは、and, or, nand ゲートなど、入力数と出力数が異なったり、逆演算ができないようなゲートは実現できません。そこで、入出力ゲート数が同じで、可逆計算可能で、あらゆる計算を実現できる Toffoli Gate をユニタリ行列で実現できることを示します。

Toffoli Gate は controlled-Controlled-not (CCNOT)とも呼ばれ、次の論理式で与えられます

CCNOT(x,y,z)=(x,y,(x,y)+z)

量子コンピュータは入力に対して、入力に対応した qubit を作り、さらにその入力の長さに対応したユニタリ行列を構成し、qubit にユニタリ行列を適用し、最終的に特定の qubit の観測を出力とします。ユニタリ行列の積はユニタリ行列なので、原理的には一つのユニタリ行列で最終状態にすることはできます。しかし、そのユニタリ行列の複雑度を考える上で、ユニタリ行列を基本的な操作の組み合わせに分解することを考えます。

さらに、基本的な操作の組み合わせで計算を定義する事自体が、量子計算のプログラミングとなります。以下は量子コンピュータの構成の流れになります：

qubit を2つの角度で表す Bloch球表現
qubit への任意のユニタリ行列演算が、3つの基本ユニタリ行列の積で表せる
制御NOT
Tofforiゲートのユニタリ行列による構成

2状態系のBloch 球表示

観測すると2つの状態のうちの一つが観測される状態 ψ は、2つの正規直交基底 $|0⟩$ と $|1⟩$ により、次で表される。

|ψ⟩ = a |0⟩ + b |1⟩

{|a|}^{2} + {|b|}^{2} = 1

a を(広く使われている表記に合わせて) $a = e^{ⅈ α} cos \frac{θ}{2}$ と置き、同じく bも $b = e^{ⅈ β} sin \frac{θ}{2}$ と置く。すると、状態の表記を次のように表示できる。

|ψ⟩ = e^{ⅈ α} cos \frac{θ}{2} |0⟩ + e^{ⅈ β} sin \frac{θ}{2} |1⟩ = e^{ⅈ α} (cos \frac{θ}{2} |0⟩ + e^{ⅈ (β - α)} sin \frac{θ}{2} |1⟩)

ここで、全体の係数 $e^{ⅈ α}$ は、観測の確率と関係なく、また、 $φ = β - α$ と置くことで、2状態系の状態を二つの角度を表す実数 $(θ, φ)$ で表すことができる。これは、半径1の三次元球の表面の極座標になるので、この2状態系を2実数の極座標で表すことを Bloch 球表現と呼ぶ。

単一qubitに対するZ-Y変換(定理4.1)

パウリ行列について次の関数を定義する

R_{x} (θ) = e^{- ⅈ θ σ_{x} / 2}

単一qubitに対するユニタリ行列 U に対して、次の実数の α, β, γ, δ が存在する。

U = e^{ⅈ α} R_{z} (β) R_{y} (γ) R_{z} (δ)

補題

以下のユニタリ行列もパウリ行列の積で表せる

Hadamard: $H = \frac{1}{\sqrt{2}} (\begin{matrix} 1 & 1 \\ 1 & -1 \end{matrix})$
π/8 ゲート: $T = (\begin{matrix} 1 & 0 \\ 0 & e^{ⅈ π / 4} \end{matrix})$
位相ゲート: $S = (\begin{matrix} 1 & 0 \\ 0 & ⅈ \end{matrix})$

制御Not

$CNOT = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix})$

Toffoli Gate の構成

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 14 回 量子コンピュータ