§E15.17量子計算モデル

最終更新

量子回路では、計算途中の状態を複素ベクトルで表し、ゲートをノルムを保つ線形変換として作用させる。出力は状態ベクトルそのものではなく、測定によって得られる古典ビット列である。従って、状態の規格化、ユニタリ変換、および測定確率を同じ内積の規約の下で記述する必要がある。本記事では有限次元の純粋状態と回路末尾の計算基底測定に限定し、BQP の計算モデルを定義する。

1 量子ビットと多量子ビット状態

§E3.32 定義 1.1の規約に従い、複素座標空間Cd\mathbb C^dの内積を

⟨v,w⟩=∑j=1dvjwj‾\langle v,w\rangle=\sum_{j=1}^d v_j\overline{w_j}

とする。この内積は第1変数について線形である。ノルムは§E3.32 定義 1.2により∥v∥=⟨v,v⟩\|v\|=\sqrt{\langle v,v\rangle}である。

定義 1.1. 一量子ビットの状態空間をH1=C2\mathcal H_1=\mathbb C^2とし、その標準正規直交基底を

∣0⟩=(10),∣1⟩=(01)|0\rangle= \begin{pmatrix}1\\0\end{pmatrix}, \qquad |1\rangle= \begin{pmatrix}0\\1\end{pmatrix}

と書く。量子ビット (qubit) の純粋状態は、ノルム11のベクトル

∣ψ⟩=α∣0⟩+β∣1⟩,α,β∈C,∣α∣2+∣β∣2=1|\psi\rangle=\alpha|0\rangle+\beta|1\rangle, \qquad \alpha,\beta\in\mathbb C,\qquad |\alpha|^2+|\beta|^2=1

である。

量子状態に現れる係数α,β\alpha,\betaは確率ではなく複素確率振幅である。確率は測定時に係数の絶対値の二乗から得る。

定義 1.2.00量子ビットの状態空間をH0=C\mathcal H_0=\mathbb Cとする。空テンソル積はスカラー11であり、{0,1}0={ε}\{0,1\}^0=\{\varepsilon\}の唯一の空語に対応する計算基底ベクトルを

∣ε⟩=1∈H0|\varepsilon\rangle=1\in\mathcal H_0

と定める。n≥1n\ge1に対し、nn量子ビットの状態空間 (multiqubit state space) を

Hn=(C2)⊗n≅C2n\mathcal H_n=(\mathbb C^2)^{\otimes n}\cong\mathbb C^{2^n}

と書く。本記事では、この空間を

{∣x⟩:x∈{0,1}n}\{|x\rangle:x\in\{0,1\}^n\}

を正規直交基底とする2n2^n次元複素内積空間として具体的に定める。ここでx=x1⋯xnx=x_1\cdots x_nに対し

∣x⟩=∣x1⟩⊗⋯⊗∣xn⟩|x\rangle=|x_1\rangle\otimes\cdots\otimes|x_n\rangle

である。純粋状態は

∣ψ⟩=∑x∈{0,1}nαx∣x⟩,∑x∣αx∣2=1|\psi\rangle=\sum_{x\in\{0,1\}^n}\alpha_x|x\rangle, \qquad \sum_x|\alpha_x|^2=1

と表される。

m,n≥0m,n\ge0とし、∣ψ⟩=∑xαx∣x⟩∈Hm|\psi\rangle=\sum_x\alpha_x|x\rangle\in\mathcal H_mと∣ϕ⟩=∑yβy∣y⟩∈Hn|\phi\rangle=\sum_y\beta_y|y\rangle\in\mathcal H_nのテンソル積 (tensor product) を

∣ψ⟩⊗∣ϕ⟩=∑x,yαxβy∣xy⟩∈Hm+n|\psi\rangle\otimes|\phi\rangle =\sum_{x,y}\alpha_x\beta_y|xy\rangle \in\mathcal H_{m+n}

と定める。

この定義では、抽象的なテンソル積の追加の性質を仮定せず、計算基底に関する座標によって本記事で必要な積を定めている。文字列の連結順序が量子ビットの順序も固定する。

命題 1.3. 任意のm,n≥0m,n\ge0、∣ψ⟩∈Hm|\psi\rangle\in\mathcal H_m、および∣ϕ⟩∈Hn|\phi\rangle\in\mathcal H_nについて

∥∣ψ⟩⊗∣ϕ⟩∥=∥∣ψ⟩∥ ∥∣ϕ⟩∥\||\psi\rangle\otimes|\phi\rangle\| =\||\psi\rangle\|\,\||\phi\rangle\|

が成り立つ。従って、二つの状態ベクトルのテンソル積も状態ベクトルである。

証明.∣ψ⟩=∑xαx∣x⟩|\psi\rangle=\sum_x\alpha_x|x\rangle、∣ϕ⟩=∑yβy∣y⟩|\phi\rangle=\sum_y\beta_y|y\rangleとする。計算基底は正規直交基底なので、

∥∣ψ⟩⊗∣ϕ⟩∥2=∑x,y∣αxβy∣2=(∑x∣αx∣2)(∑y∣βy∣2)=∥∣ψ⟩∥2 ∥∣ϕ⟩∥2.\begin{aligned} \||\psi\rangle\otimes|\phi\rangle\|^2 &=\sum_{x,y}|\alpha_x\beta_y|^2\\ &=\left(\sum_x|\alpha_x|^2\right) \left(\sum_y|\beta_y|^2\right)\\ &=\||\psi\rangle\|^2\,\||\phi\rangle\|^2. \end{aligned}

両辺は非負であるため平方根を取れば最初の等式を得る。二つのベクトルのノルムがともに11なら、テンソル積のノルムも11である。▨

全ての多量子ビット状態が一量子ビット状態のテンソル積に分解されるわけではない。そのような分解をもたない状態をエンタングルした状態という。後で計算する Bell 状態がその例である。

2 ユニタリゲートと量子回路

複素行列UUの共役転置をU∗U^*と書く。

定義 2.1.dd次複素正方行列UUが ユニタリ (unitary) であるとは

U∗U=UU∗=IdU^*U=UU^*=I_d

を満たすことをいう。Hk\mathcal H_k上のユニタリ変換を kk量子ビットゲート (k-qubit gate) という。

nn量子ビットのうち指定したkk本へUUを作用させるとき、残りの量子ビットには恒等変換を作用させる。連続した量子ビットに対しては、この変換を

I⊗U⊗II\otimes U\otimes I

と書く。指定した量子ビットが連続していない場合には、計算基底の順序を置換して同じ変換を定める。

命題 2.2. ユニタリ行列UUと任意のベクトルv,wv,wについて

⟨Uv,Uw⟩=⟨v,w⟩,∥Uv∥=∥v∥\langle Uv,Uw\rangle=\langle v,w\rangle, \qquad \|Uv\|=\|v\|

が成り立つ。

証明. 本記事の内積規約では⟨v,w⟩=w∗v\langle v,w\rangle=w^*vである。従って、

⟨Uv,Uw⟩=(Uw)∗(Uv)=w∗U∗Uv=w∗v=⟨v,w⟩\langle Uv,Uw\rangle =(Uw)^*(Uv) =w^*U^*Uv =w^*v =\langle v,w\rangle

である。w=vw=vと置けば

∥Uv∥2=⟨Uv,Uv⟩=⟨v,v⟩=∥v∥2\|Uv\|^2=\langle Uv,Uv\rangle =\langle v,v\rangle=\|v\|^2

を得る。両辺は非負なので∥Uv∥=∥v∥\|Uv\|=\|v\|である。▨

定義 2.3.nn量子ビット上の 量子回路 (quantum circuit) は、有限個の1量子ビットゲートと2量子ビットゲートを、作用させる量子ビットの番号とともに順に並べたものである。回路

Q=UsUs−1⋯U1Q=U_sU_{s-1}\cdots U_1

は、初期状態∣ψ0⟩|\psi_0\rangleを

∣ψs⟩=UsUs−1⋯U1∣ψ0⟩|\psi_s\rangle=U_sU_{s-1}\cdots U_1|\psi_0\rangle

へ移す。ゲート数ssを回路のサイズという。

各UjU_jは全状態空間上では、指定した1本または2本へ作用するゲートと、残りの量子ビット上の恒等変換のテンソル積である。この拡張は計算基底の各ブロックで同じユニタリ行列を作用させるため、内積を保存する。非連続な量子ビットへ作用させる際に用いる計算基底の置換も、内積を保存する置換行列である。また、ユニタリ行列U,VU,Vについて(UV)∗(UV)=V∗U∗UV=I(UV)^*(UV)=V^*U^*UV=Iかつ(UV)(UV)∗=UVV∗U∗=I(UV)(UV)^*=UVV^*U^*=Iなので、その積もユニタリである。従って、命題 2.2により全ての中間状態のノルムは11に保たれる。

本記事で用いる基本ゲートは

H=12(111−1),T=(100eiπ/4)H=\frac1{\sqrt2} \begin{pmatrix} 1&1\\ 1&-1 \end{pmatrix}, \qquad T= \begin{pmatrix} 1&0\\ 0&e^{i\pi/4} \end{pmatrix}

と、計算基底上で

CNOT⁡∣a,b⟩=∣a,a⊕b⟩(a,b∈{0,1})\operatorname{CNOT}|a,b\rangle=|a,a\mathbin{\oplus}b\rangle \qquad(a,b\in\{0,1\})

と定まる CNOT である。直接計算によりH∗H=T∗T=I2H^*H=T^*T=I_2であり、CNOT は計算基底を置換する行列なのでユニタリである。実際、

H∗H=12(111−1)(111−1)=I2,T∗T=(100e−iπ/4eiπ/4)=I2.H^*H=\frac12 \begin{pmatrix}1&1\\1&-1\end{pmatrix} \begin{pmatrix}1&1\\1&-1\end{pmatrix}=I_2, \qquad T^*T= \begin{pmatrix}1&0\\0&e^{-i\pi/4}e^{i\pi/4}\end{pmatrix}=I_2.

CNOT は∣00⟩,∣01⟩,∣10⟩,∣11⟩|00\rangle,|01\rangle,|10\rangle,|11\rangleをそれぞれ∣00⟩,∣01⟩,∣11⟩,∣10⟩|00\rangle,|01\rangle,|11\rangle,|10\rangleへ写すため、その列は計算基底の置換であり、共役転置が逆行列になる。

3 Born 規則と測定

定義 3.1. 規格化された状態

∣ψ⟩=∑x∈{0,1}nαx∣x⟩|\psi\rangle=\sum_{x\in\{0,1\}^n}\alpha_x|x\rangle

を 計算基底で測定する (computational-basis measurement) と、古典ビット列xxを確率

Pr⁡[x]=∣αx∣2\Pr[x]=|\alpha_x|^2

で得る。この規則を Born 規則 (Born rule) という。

n≥1n\ge1のとき、最初の量子ビットだけを測定してb∈{0,1}b\in\{0,1\}を得る確率は

Pr⁡[b]=∑y∈{0,1}n−1∣αby∣2\Pr[b]=\sum_{y\in\{0,1\}^{n-1}}|\alpha_{by}|^2

である。

命題 3.2. 計算基底測定における各Pr⁡[x]\Pr[x]は非負であり、

∑x∈{0,1}nPr⁡[x]=1\sum_{x\in\{0,1\}^n}\Pr[x]=1

である。従って、Born 規則は有限標本空間{0,1}n\{0,1\}^n上の確率分布を定める。また、n≥1n\ge1ならば、最初の量子ビットに関する二つの確率も非負であり、その和は11である。

証明. 複素数の絶対値の二乗は非負なのでPr⁡[x]=∣αx∣2≥0\Pr[x]=|\alpha_x|^2\ge0である。計算基底は正規直交基底であり、∣ψ⟩|\psi\rangleのノルムは11なので、

∑xPr⁡[x]=∑x∣αx∣2=∥∣ψ⟩∥2=1.\sum_x\Pr[x] =\sum_x|\alpha_x|^2 =\||\psi\rangle\|^2 =1.

従って、Ω={0,1}n\Omega=\{0,1\}^n、F=2Ω\mathcal F=2^\Omegaと置き、各A∈FA\in\mathcal FにP(A)=∑x∈A∣αx∣2P(A)=\sum_{x\in A}|\alpha_x|^2を対応させると、有限和の加法性とP(Ω)=1P(\Omega)=1から§E11.1 定義 1.1の確率空間を得る。実際、有限集合Ω\Omegaの互いに素な部分集合列は、空集合を除けば有限個の項しかもたないため、有限加法性から可算加法性が従う。

n≥1n\ge1とする。最初の量子ビットの値がbbである事象は、互いに素な結果{by:y∈{0,1}n−1}\{by:y\in\{0,1\}^{n-1}\}の集合である。従って、その確率は各結果の確率の和であり、二つのbbに対する和は全てのx∈{0,1}nx\in\{0,1\}^nに対する和11である。▨

状態ベクトルに絶対値11の複素数eiθe^{i\theta}を掛けても、各測定確率は∣eiθαx∣2=∣αx∣2|e^{i\theta}\alpha_x|^2=|\alpha_x|^2のままである。この全体に共通する係数を大域位相という。

4 一量子ビット回路と二量子ビット回路

例 4.1 (Hadamard ゲートと干渉). 初期状態∣0⟩|0\rangleにHHを一回作用させると

H∣0⟩=∣0⟩+∣1⟩2H|0\rangle =\frac{|0\rangle+|1\rangle}{\sqrt2}

となる。従って、直後に計算基底で測定すれば、00と11をそれぞれ確率1/21/2で得る。

測定せずにHHをもう一回作用させると

H2∣0⟩=H∣0⟩+∣1⟩2=12((∣0⟩+∣1⟩)+(∣0⟩−∣1⟩))=∣0⟩.\begin{aligned} H^2|0\rangle &=H\frac{|0\rangle+|1\rangle}{\sqrt2}\\ &=\frac12\bigl((|0\rangle+|1\rangle)+(|0\rangle-|1\rangle)\bigr)\\ &=|0\rangle. \end{aligned}

従って、二つ目のHHの後の測定結果は確率11で00である。二つの経路に由来する∣1⟩|1\rangleの振幅は加算時に打ち消し合う。

例 4.2 (Bell 状態). 初期状態∣00⟩|00\rangleの第1量子ビットへHHを作用させると、

(H⊗I)∣00⟩=∣00⟩+∣10⟩2(H\otimes I)|00\rangle =\frac{|00\rangle+|10\rangle}{\sqrt2}

となる。続いて第1量子ビットを制御、第2量子ビットを標的とする CNOT を作用させると、

CNOT⁡(H⊗I)∣00⟩=∣00⟩+∣11⟩2\operatorname{CNOT}(H\otimes I)|00\rangle =\frac{|00\rangle+|11\rangle}{\sqrt2}

を得る。従って、二量子ビットを測定すると0000と1111をそれぞれ確率1/21/2で得て、0101と1010を得る確率は00である。各量子ビットを単独で見た0,10,1の確率はともに1/21/2であるが、二つの結果は常に一致する。

この状態が(α∣0⟩+β∣1⟩)⊗(γ∣0⟩+δ∣1⟩)(\alpha|0\rangle+\beta|1\rangle)\otimes (\gamma|0\rangle+\delta|1\rangle)と分解されると仮定すると、01,1001,10の係数からαδ=βγ=0\alpha\delta=\beta\gamma=0、00,1100,11の非零係数からαγ≠0\alpha\gamma\ne0かつβδ≠0\beta\delta\ne0を得る。後二式は四つの係数が全て非零であることを意味し、前二式と矛盾する。従って、この Bell 状態は一量子ビット状態のテンソル積には分解されない。

5 一様な量子回路族と BQP

ゲート集合

G={H,T,CNOT⁡}\mathcal G=\{H,T,\operatorname{CNOT}\}

を固定する。回路記述にはゲートの種類と作用する量子ビット番号だけを書けばよく、行列要素を入力長ごとに近似して記述する必要はない。本記事では、この固定ゲート集合を用いる回路モデルによって BQP を定義する。異なる普遍ゲート集合が同じ有界誤りクラスを与えることの証明は扱わない。

定義 5.1. 言語L⊆{0,1}∗L\subseteq\{0,1\}^*が BQP (BQP) に属するとは、多項式ppと、次の条件を満たす量子回路族(Qn)n≥0(Q_n)_{n\ge0}が存在することをいう。

  1. max⁡{1,n}≤m(n)\max\{1,n\}\le m(n)であり、QnQ_nの量子ビット数m(n)m(n)とサイズはともにp(n+1)p(n+1)以下である。また、全てのゲートはG\mathcal Gに属する。

  2. §E15.16 定義 2.2と同じ意味で、ある決定性多項式時間生成器が入力1n1^nからQnQ_nの完全な記述を出力する。

  3. 入力x∈{0,1}nx\in\{0,1\}^nに対する初期状態を∣x⟩∣0m(n)−n⟩|x\rangle|0^{m(n)-n}\rangleとし、QnQ_nの作用後に第1量子ビットを計算基底で測定して、結果11を受理とする。この受理確率をPQn(x)P_{Q_n}(x)と書くと、全てのxxについて

    {x∈L⟹PQn(x)≥23,x∉L⟹PQn(x)≤13\begin{cases} x\in L &\Longrightarrow P_{Q_n}(x)\ge\dfrac23,\\[2mm] x\notin L &\Longrightarrow P_{Q_n}(x)\le\dfrac13 \end{cases}

    が成り立つ。

    n=0n=0の場合にはx=εx=\varepsilonかつ∣x⟩=∣ε⟩=1|x\rangle=|\varepsilon\rangle=1であるため、初期状態は∣ε⟩⊗∣0m(0)⟩=∣0m(0)⟩|\varepsilon\rangle\otimes|0^{m(0)}\rangle=|0^{m(0)}\rangleとして定まる。

一様性は、入力長ごとに量子回路へ計算不能な情報を埋め込むことを防ぐ。多項式サイズだけでなく量子ビット数にも多項式上界を要求するため、初期状態に用意する補助量子ビットの総数も計算資源に含まれる。2/32/3と1/31/3は一つの入力について観測した頻度ではなく、全ての入力に対して回路族が満たすべき確率条件である。

6 決定性計算・確率的計算との比較

決定性 Boolean 回路では、入力を固定すると各線の値と出力ビットが一意に定まる。確率的計算では、乱数列を固定すると一つの古典的な計算経路が定まり、受理確率は古典的な経路の確率の和である。これに対して量子回路では、測定前に複素振幅を線形に加え、その後で絶対値を二乗して確率を得る。例 4.1 (Hadamard ゲートと干渉)で二回目のHHが結果11の振幅を消したことは、この順序の違いを具体的に示している。

三つのモデルを比較するときには、確率が現れるという共通点だけで確率的計算と量子計算を同一視してはならない。また、本記事の定義だけから BQP と古典的な主要計算量クラスの包含または分離を結論してはならない。

注意 6.1 (本記事の境界). 本記事は状態、ゲート、測定、および BQP の量化を定義する。量子 Fourier 変換、探索、素因数分解などの量子アルゴリズム、雑音に対する量子誤り訂正、混合状態と一般の測定、および計算量クラス間の深い包含関係は扱わない。これらの主張には、本記事で定義したモデルに加えて、それぞれ独立した構成と証明が必要である。

7 演習

問題 7.1.

  1. ∣ψ⟩=(∣00⟩+i∣11⟩)/2|\psi\rangle=(|00\rangle+i|11\rangle)/\sqrt2を計算基底で測定したとき、各ビット列を得る確率を求めよ。
  2. ユニタリゲートを何個合成しても状態のノルムが11に保たれる理由を説明せよ。
  3. 例 4.2 (Bell 状態)の Bell 状態について、第1量子ビットだけを測定したときの確率を求めよ。
  4. BQP の定義に回路族の P 一様性が必要である理由と、入力xxではなく1∣x∣1^{|x|}を生成器へ与える理由を説明せよ。
解答 (演習の要点).
  1. 0000と1111の確率はそれぞれ1/21/2であり、0101と1010の確率は00である。
  2. 各ゲートはユニタリであり、その積もユニタリである。命題 2.2により、ユニタリ変換はノルムを保存する。
  3. 00と11の確率はそれぞれ1/21/2である。第2量子ビットとの相関は、この周辺確率だけからは判定することができない。
  4. 一様性は入力長ごとの回路へ計算不能な情報を埋め込むことを防ぐ。生成器が入力値xxを受け取ると、xxに対する答えを生成時に計算して回路へ埋め込む余地が生じるため、入力長だけを与える。

▨

参考文献

  1. Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary ed., Cambridge University Press, 2010.量子状態、ユニタリ回路、計算基底測定、および Bell 状態の標準的な定式化を参考にした。
  2. John Watrous, The Theory of Quantum Information, Cambridge University Press, 2018.有限次元複素内積空間上の量子状態と測定の線形代数的な定式化を参考にした。
  3. Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, Cambridge, 2009.一様な量子回路族と有界誤り計算量クラス BQP の定義を参考にした。

前提記事