量子コンピュータの計算量(応用函数解析の研究)

量子コンピュ

–

タの計算量

名古屋大学 小澤正直

(Masanao Ozawa)*

名古屋大学 西村治道

(Harumichi

Nishimura)\dagger

アブストラクト 量子計算の研究は, 1980 年頃, Feynmanによって, 量子力学系を古典力学的計算機で模倣すること の計算量的複雑性から, 量子力学の原理を利用した, より効率の高い計算の可能性が示唆されたことから 始まった. 1980年代後半に Deutsch は量子 Turing機械と量子回路の 2 種類の計算モデルを定式化し, 現在, 量子アルゴリズムは, これら2種類のモデルを通して表現される. 本論文では, 量子Turing 機械 と量子回路の厳密な数学的定式化を与え, 量子回路族に対する–様性の概念を導入することで, この 2 種 類の計算モデルの計算能力が多項式計算量の観点から同等であることを示す.

1.

はじめに

Turing

機械を始めとする従来の計算モデルは古典力学に基づいたものである.

ところが計算素子のミク ロ化をどんどん押し進めていけば, 電子や原子などの微視的物理系の量子力学的振舞いの影響が現れてく る.

Feynman

[101

は古典力学的計算機を用いて量子力学的現象を模倣すると非常に多くの計算時間が必要

となることを指摘し, 量子力学的原理に基づく計算機は古典力学的計算機よりも効率的に計算が行なえる のではないかという示唆を与えた.

この量子計算機のモデルとして

Deustch

は

Turing

型 (量子

Turing

機械)

[6]

と回路型 (量子回路)

[7]

の計算モデルを考案した. それは次の量子力学的原理を満たすものであった:

(1)

その時間発展はユニタリ 作用素によって特徴付けられる.

(2)

計算機内では1度に複数の計算 (量子並列計算) が実行され得る.

(3)

測定によって得られる結果は複数の計算結果のうち

1

つだけであり

,

どの計算結果を観測するかは各計算結 果の量子振幅によって特徴付けられる. この

Deustch

の考案したモデルにもとづき, 量子計算機の計算効 率に関して, 幾つかの成果が得られた

[1,3,4,8,11,17].

とりわけ, 量子計算機の利用によって高確率で効率 的に整数の因数分解問題及び離散対数問題が解けるという

Shor

$[15,16]$ の結果は大きな影響を与えた. こ れらの問題を効率的に解くことのできる古典的計算機上のアルゴリズムはまだ発見されていないし, また, 従来の計算量の観点からは存在しないであろうといういうのが, 大方の見方であった. また, こうした計算 量的困難が公開鍵暗号の理論の基になっている点からも, このことは非常に意義のあるものであった. これ により量子計算機は–躍脚光を浴びることになり, その実現へ向けて多くの研究がなされることとなった. 量子

Turing

機械と量子回路は二つの基本モデルであるが, 量子計算の研究において異なった役割を担っ ている. 量子

Turing

機械は量子計算の能力を研究するうえでの純数学的モデルとしての側面が強く

,

–方, 量子回路はその実現へ向けて研究されている物理的モデルとしての側面が強い. そのため, 2つのモデル の計算能力の関係を調べることは重要な問題である. 本論文では数学的に厳密な方法により, 量子

Turing

機械と量子回路の計算能力の関係を研究する. とりわけ, 従来, あいまいな取り扱いがされてきた, 量子

Turing

機械の停止問題と量子回路族の–様性の概念に関する厳密な定式化を与え, 量子

Turing

機械と– 様量子回路族の計算能力の同等性を証明することを目的とする. 1 情報文化学部大学院人間情報学研究科 \dagger大学院人間情報学研究科

2.

古典

Turing

機械 古典

Turing

機械 1

(CTM)

は両側無限のテープとそのテープ上の記号を読み書きする決定性かつ離散時 間の力学系である. その状況

(configuration)

は機械の内部状況 $q$

,

テープ上の記号列 $T$

,

そしてテープ上 のヘッドの位置 $x$ によって決定される. 任意の整数$n$ に対して, テープ上の位置 $n$ にあるマス目の記号は $T(n)$ によって表される. $C$ _が

CTM

_{の状況を表すとき}

,

_状況$C$ の内部状況

,

_{テープ記号列}

,

_{ヘッドの位置} はそれぞれ $q_{C}$

,

$\tau_{c}$

,

_{$x_{C}$} によって表すものとする テープ記号列の変化を述べるため $T_{C}^{\tau}$ は位置 _{$x_{C}$} にお ける記号を\tau に置き換えることで $\tau_{c}$ から得られるテープ記号列を表すものとする.

CTM

の時間発展は

遷移関数$\delta(p, \sigma)=(q, \tau, d)$ によって決定され

,

これは内部状況が$p$

,

ヘッドが指しているマス目の記号が $\sigma$

のとき, ヘッドがそのマス目を $\tau$ に書き換え

,

内部状況は $q$ に変わり

,

そしてヘッドが方向 $d$ に移動する

,

という1ステップの状況の変化を表す. 但し

,

$d\in\{0, \pm 1\}$ _で

$d=1(-1)$

_は右 (左) 方向に1 マスの移動, $d=0$ はヘッドが移動しないことを表す. これにより $\delta(qc, T_{C}(xc))=(q, \tau, d)$ なら状況$C=(q_{C}, Tc, xc)$ は状況 $(q, T_{C}^{\tau}, x_{C}+d)$ へ変化する. 以下で

CTM

の形式的な定義を与えることにする. 本論文において, 任意の整数 $n,$

$m(n<m)$

に対して $[n, m]_{\mathrm{Z}}$ は$\{n, n+1, \ldots, m-1, m\}$ を表すものとする. 内部状況集合とは, $q0$ と $q_{f}$ という特別な元を含 む有限集合で$q0$ は初期内部状況,$q_{j}$ は終了内部状況を表す. 記号集合は

,

空白を表す $B$ という特別な元を

含む有限集合である. ある記号集合 $\Sigma$ に対するテープ記号列 $T$ _とは, 有限個の $i\in \mathrm{Z}$ を除いて $T(i)=B$

なる $\mathrm{Z}$

から $\Sigma$ への関数である. 特に

$T(i)=\sigma_{i}(i\in[0, k-1]_{\mathrm{Z}})$

,

$B$

(otherwise)

のとき, テープ記号列$T$ _と長さ $k$ _の \Sigma -列 ($\Sigma\backslash \{B\}$ の有限列) $\sigma_{0}\cdots\sigma_{k-1}$ は 1 対 1 に対応するので, しば

しば$T\sim x$ _と書いて$T$ _を長さ $k$ のテープ記号列という. $\Sigma$ からのテープ記号列の集合を $\Sigma\#$ と表すこと

にする.

Turing

フレームとは, 内部状況集合$Q$ と記号集合 $\Sigma$ の組 _{$(Q, \Sigma)$} のことを指す ある

Turing

フ

レーム $(Q, \Sigma)$ の状況空間とは

,

$C(Q)\Sigma)=Q\cross\Sigma\#\mathrm{x}\mathrm{Z}$ _{のことであり,} その元 $C=$

(

_$qc$

,

Th

_$xc$

)

を $(Q, \Sigma)$

の状況という. この状況は,

機械の内部状況が忙で,

テープ記号列$\tau_{c}$ がテープ上に書かれていて

,

ヘッド

の位置が $x_{C}$ であることを表す. $(Q, \Sigma)$ の任意の状況 $C=(qc, Tc, xc)$ に対して$T_{C}^{\tau}$ は次の関係によって

定義されるテープ記号列である.

$T_{C}^{\tau}(n)=T_{C}(n)(n\neq x_{C})$

,

$\tau(n=x_{C})$

$(Q, \Sigma)$ に対する遷移関数とは$Q\cross\Sigma$ から $Q\cross\Sigma\cross[-1,1]_{\mathrm{Z}}$ への関数である 古典

Turing

機械は

Turing

フレーム $(Q, \Sigma)$ と $(Q, \Sigma)$ に対する遷移関数$\delta$ からなる3つ馬

M.

$=(Q, \Sigma, \delta)$ である.

$M=(Q, \Sigma, \delta)$ を

CTM

とする. $Q$ の元は $M$ _{の内部状況, 集合} $\Sigma$ は $M$ のアルファベット, 関数 $\delta$ は

$M$ _{の遷移関数, そして} $(Q, \Sigma)$ の状況は $M$ _{の状況と呼ばれる}. $M$ _{の初期状況とは$q_{C}=q0,$ $x_{C}=0$ なる}

状況$C$ _{のことを指す}. 任意のテープ記号列 $T$ _{に対して, 入力テープ記号列} $T_{in}$ を持つ $M$ の計算とは, 次

の条件を満たす状況の (有限, または無限の) 列 $\{C(n)|n\in I\})I=\{0,1, \ldots, N\}$ または $I=\{0,1, \ldots\}$

のことである.

(1)

$C(\mathrm{O})$

は乃 (o)

$=T_{in}$ なる初期状況である.

(2)

$C(n+1)$ は $C(n)$ と $\delta$ から次のように決定される:

$\delta qc(n)$

,

$T_{C(n)}(x_{C(n)}))=(q)\tau,$$d)$ _のとき $C(n+1)=(q, T_{C(n)}^{\tau}, x_{C(n)}+d)$

.

特に \Sigma -列 $x$ に対して $T_{in}$ $\sim x$ のとき, 入力 $x$ を持つ $M$ の計算という. 計算$\{C(n)|n\in I\}$ は $q_{C(n)}=q_{f}$

なるある $n$ が存在して $T_{C(m)}=T_{out},$ $m= \min\{n\in I|q_{C(n)}=q_{f}\}$ のとき, 出カテープ記号列 $T_{out}$ で停

1_{これは通常計算量の分野では,決定性Turing機械と呼ばれるものである. この論文では古典と量子の対応を与えるためこのよ}

止するという. やはり特に $T_{out}\sim y$ _のとき, $M$ _{は \Sigma -}列 $y$ を出力するという. $m$ を入カテープ記号列 $T_{in}$ に対する $M$ _{の計算時間という}. _任意の $n\in \mathrm{N}$ _{に対し, 長さ $n$ の入力を持つ $M$} の計算時間が高々$t(n)$ で あるとき

,

$M$ _を $t(n)$ 時間限定

CTM

といい, 関数 $t$

が多項式のとき,

多項式時間限定

CTM

という.

CTM

$M$ _{のアルファベットが} $\Sigma_{1}\cross\cdots\cross\Sigma_{k}$

と書けるとき,

_{$M$ を} $k$ _トラック

CTM

_と呼ぶ. これは 物理的には$M$ _{のテープが} $k$

個のトラックに分割されていることを意味する.

このとき $\Sigma_{i}$ によって表さ れるトラックを第 $i$ トラックという.

形式的には,

第 $i$ トラックは $T(j)=(Tr_{1}(j), \ldots, Tr_{k}(j))$ となる ような関数 $Tr_{i}$ によって表される. _これは第 $i$ トラック記号列と呼ぶことにする

.

$T=(Tr_{1}, \ldots, Tr_{k})$ とも書くことにする. $x$ を長さ $n$ の \Sigma 1-列 とする. 第 1 トラックに入力 _{$x$ を持つ $M$}

の計算とは,

入力 $(x, B^{n}, \ldots, B^{n})$ を持つ $M$ _{の計算のことである.}

_{同様にして,}

_{第訃ラックに入力} $x$ を持つ $M$

の計算,

$M$ は前 $i$ トラックに $x$ を出力するといった概念が定義できる

.

$x_{1},$_$\ldots,$$x_{j}$ をそれぞれ長さが

n

以下の

\Sigma -列 とし, $x_{1}B^{n_{1}},$ $\ldots,$$x_{j}B^{n_{\mathrm{j}}}$ をそれぞれ, それらのあとに空白記号列が続く長さが $n$ の $\Sigma$-列とする. このと き, $T\sim(x_{1}B^{n_{1}}, \ldots, x_{j}B^{n_{\mathrm{j}}}, B^{n}, \ldots, B^{n})$ を $T\sim(x_{1)}\ldots, x_{j})$ _{と略すことにする}.

3.

量子

Turing

機械 量子

Turing

機械

(QTM)

は

CTM

の量子化である. その状態は

,

計算基底と呼ばれる

CTM

の状況の集

合と 1 対 1 対応を持つ完備直交系によって張られる

Hilbert

空間内のベクトルによって表現される.

つま り計算基底は

CTM

の任意の状況$C$ _{に対して,} $|C\rangle$ $=|qc$

,

$\tau_{c}$

,

$xc$

)

によって表現される.

QTM

の時間発展 は,

1

_{ステップ後の状況の遷移の振幅を与える量子遷移関数によって決定されるユニタリ作用素}

$U$ _によっ

て述べられる.

_{量子遷移関数とは,}

複素関数 $\delta(p)\sigma,$_$q,$$\tau,$$d)=c$ のことで, 古典的遷移 $\delta(p, \sigma)=(q)\tau,$ $d)$ _が

振幅 $c$ で生じることを表す. これにより時間発展作用素 $U$ _は,

$U|qc,$$Tc,$

$x_{C} \rangle=\sum_{q,\tau,d}\delta(qc, T_{C}(x_{C}),$$q,$$\tau,$$d)|q,$$T_{C}^{\tau},$$xc+d)$

によって決定される.

QTM

の形式的な定義は次のようになる.

$(Q, \Sigma)$ _を

Turing

_{フレームとする}. $(Q, \Sigma)$ の状態空間とは

,

_状況空間 $C(Q, \Sigma)$ _{によって生成される}

Hilbert

空間 $\mathcal{H}(Q, \Sigma)$ である. $C(Q)\Sigma)$ _と1_対1_{対応を持つ基底$\{|q_{C}, T_{C}, x_{C}\rangle|(q_{C}, T_{C}, x_{C})\in C(Q, \Sigma)\}$}

は $\mathcal{H}(Q, \Sigma)$ の計算基底と呼ばれる. それゆえ空間 $\mathcal{H}(Q, \Sigma)$ は _{$\sum_{C\in C(Q,\Sigma)}|f(C)|^{2}<\infty$ であるような} $C(Q, \Sigma)$ 上の複素関数の空間によって表現される

; この表現において,

_{全ての $f,$}

$g\in \mathcal{H}(Q, \Sigma)$ に対し, 内

積は $(f|g)= \sum_{C\in C(Q,\Sigma)}f(C)^{*}g(C)$

_{によって定義され,}

_{その計算基底状態} $|qc,$$Tc,$$xc\rangle$ は _{$\delta_{C}(C’)=1$}

if

$C’=C,$ $\delta_{C}(C’)=0$

otherwise, となるような関数

\mbox{\boldmath $\delta$}c

_{と同–視される.} $(Q, \Sigma)$ に対する $C$ _{値遷移関数と}

は, $Q\cross\Sigma\cross Q\cross\Sigma\cross[-1,1]_{\mathrm{Z}}$ から複素数体 $\mathrm{C}$ への関数である.

プレ量子

Turing

機械 (プレ QTM) は,

Turing

フレーム $(Q, \Sigma)$ _と $(Q, \Sigma)$ に対する $\mathrm{C}$

値遷移関数からなる

3

つ組$M=(Q, \Sigma, \delta)$ _{として定義され}

る.

$M=(Q, \Sigma, \delta)$ _{をあるプレ}

QTM

_とする. $Q$ の元は $M$ _{の内部状況}

,

_集合 $\Sigma$ は $M$

のアルファベット, 関

数$\delta$ は _$M$

の量子遷移関数

,

$(Q, \Sigma)$ の状況は $M$ _の状況

,

_そして冗

(Q,

$\Sigma$

)

の元は _$M$

の状態と呼ばれる. $M$

の時間発展作用素とは,

$M_{\delta}= \sum_{q\in Q,\tau\in\Sigma,d\in[-1,1]_{\mathrm{Z}},C\in C(Q,\Sigma)}\delta(q_{C}, T_{C}(x_{C}),$

$q)\tau,$$d)|q,$$T_{C}^{\tau},$$x_{C}+d\rangle\langle qc,$$T_{C)}x_{C}|$

によって定義される $\mathcal{H}(Q, \Sigma)$ 上の作用素 $M_{\delta}$ である. 以下では記号

$\sum_{q,\tau,d}$ にょって $q$ は $Q$ 上, $\tau$ は $\Sigma$

上, そして $d$ _は $[$

-1,

$1]_{\mathrm{Z}}$ 上を変化するものとする.

プレ

QTM

_{はその時間発展作用素がユニタリであるとき,}

量子

Turing

機械

(QTM)

と呼ばれる. プレ

QTM

が

QTM

_{であるための,}

_{その量子遷移関数がみたすべき必要十分条件は,}

_{以下の定理に述べられるよ}

定理3.1 プレ量子

Turing

機械が量子

_{Turing 機械であるための必要十分条件は以下の条件が成り立つ}

ことである.

(a)

任意の $(p. ’\sigma)\in Q\cross\Sigma$ に対して

$\sum_{q,\tau,d}|\delta(p, \sigma, q, \tau, d)|^{2}=1$

(b)

任意の異なる $(p, \sigma),$$(p’, \sigma’)\in Q\cross\Sigma$ _に対して

$\sum_{q,\tau,d}\delta(p)\sigma,$$q,$

$\tau,$$d)\delta(p’, \sigma’, q, \tau, d)^{*}=0$

(c)

任意の $(p, \sigma, \tau),$ $(p’, \sigma’, \tau’)\in Q\cross\Sigma^{2}$ _に対して

$\sum_{q}\delta(p, \sigma, q, \tau, -1.)\delta(p’, \sigma’, q, \tau’, 1)^{*}=0$

(d)

任意の $(p, \sigma, \tau),$ $(p’, \sigma’, \tau’)\in Q\cross\Sigma^{2}$ _に対して

$\sum_{q,d=0,1}\delta(p, \sigma, q, \tau, d)\delta(p’, \sigma’, q, \tau’)d-1)^{*}=0$

4.

停止型量子

Turing

機械と定終型量子

Turing.

機械

QTM

$M$

_{のテープ記号列の個数は可算なので,}

_それらは $\{T_{1}, T_{2}, \ldots\}$ と番号付されているものとする.

$\mathcal{I}(Q, \Sigma)$ 及び$\mathrm{O}(Q, \Sigma)$ を各々, 基底 $\{|q_{0)}T_{i}, 0\rangle\}$ 及び$\{|q_{f}, T_{i}, 0\rangle\}$ によって張られる$\mathcal{H}(Q, \Sigma)$ の部分空間と

する. $\mathcal{I}(Q, \Sigma)$ 及び_{$O(Q, \Sigma)$} の元は各々初期状態

, 終了状態といい,

$\mathcal{I}(Q, \Sigma)$ に属する計算基底状態は初期

状況, $O(Q, \Sigma)$ _{に属する計算基底状態は終了状況という}. _{任意の初期状態}$\psi$ に対して, $M$ の状態の無限列

,

$\psi,$$M_{\delta}\psi,$$M_{\delta}^{2}\psi,$

$\ldots$

を $M$ _{の初期状態}

Cb

_{に対する時間発展という ユニタリ作用素} $M_{\delta}$ は量子

Turing

機械の計算ステップと

呼ばれる–定時間 $\tau$ の時間発展を表わす. このとき $M$ の状態 $M_{\delta}^{t}\psi$ を入力状態 $\psi$ に対する $t$ ステップ後

の $M$ _{の状態という.}

我々は

QTM

の停止及び計算時間について考える. $[6, 12]$ において

QTM

は次のようなスキームによっ

て測定結果を得るものと定義されている. このスキームは, 停止スキームと呼ばれる.

(I)

物理量 $\hat{n}_{0}=|q_{j}\rangle\langle$$q_{f}|\otimes I\otimes I$ は, 停止フラグと呼ばれ

,

各ステップ後に測定される.

(II)

一度,

QTM

の内部状況が $q_{j}$ になれば

, QTM

はその後, 内部状況とテープ記号列を書き換えること

はしない. すなわち,

QTM

$M=(Q, \Sigma, \delta)$ _の場合

,

_{量子遷移関数} $\delta$ が次の条件をみたす: 任意の $T\in\Sigma\#$

に対し, $M_{\delta}|q_{j},$$T,$ $x \rangle=\sum_{d}\alpha_{d}|q_{f},$$T,$$x+d)$

(4.1)

となる.

(III)

$\hat{n}_{0}$ の測定結果が

1

となったとき

,

その

QTM のテープ記号列が測定され,

その測定結果がその計算 の出力テープ記号列と定義される. 量子

Turing

機械を初期状態に準備した後, 以上のスキームに従って出力テープの記号列を得るまでの 過程を計算と呼び, $\hat{n}_{0}$ の測定結果が 1 となるまでのステップ数をその計算の計算時間という. 停止スキームにおける条件

(4.1)

は全ての数学的に定義された QTM がみたすわけではない. そこで条 件

(4.1)

をみたす

QTM

を停止型量子

Turing

機械

(HQTM)

という. 停止スキームをみたさない

QTM

は

停止フラグの測定によって

–

般にその計算を乱すことになるが

,

停止型量子

Turing

機械に対しては, 任

意の計算ステップの後に停止フラグを測定しても, 計算結果の確率分布が変化しないことが

[12]

で証明さ

れている.

次に

QTM の計算量理論を展開するとき便利な QTM

を述べることにする. $P$ _を $\hat{n}_{0}$ の固有値1に対応

する射影作用素

,

$S$ _{をヘッドの位置} $x\in \mathrm{Z}$ を表す物理量$\hat{x}$ の固有値 $0$ に対応する射影作用素 _{$I\otimes I\otimes|0\rangle$}$\langle 0|$

とする. 任意の初期状況 $|C$

)

_{に対して, 次の条件をみたすような}$t$ が存在するとき

, QTM

_{$M=(Q, \Sigma, \delta)$}

を定四型であるという: 全ての $s<t$ に対して,

$||PM_{\delta}^{s}|C\rangle||^{2}=0,$ $\mathrm{B}^{\mathrm{a}}\supset||SPM_{\delta}^{t}|C\rangle||^{2}=1$

.

このときこのような $t$ に対して有限列 $|C\rangle$

,

$M_{\delta}|C$

),

$\ldots$

,

$M_{\delta}^{t}|C\rangle$ を初期状況 $|C\rangle$ に対する定終型

QTM

$M$

の計算

,

$t$ をその計算時間という. また $|C\rangle$ $=|q_{0},$$T_{in},$ $0$

),

$T_{in}\sim x$ のときは各々入力 $x$ に対する $M$ の計

算及びその計算時間という. $\{x_{i}\}$ を長さの等しい任意の $\Sigma$-列の集合とし, $\phi$ を

$\phi=\sum_{i}\alpha_{i}|q_{0},$$T_{i},$

$0\rangle$ $(T_{i}\sim x_{i})$

をみたす初期状態とする. すべての入力 $x_{i}$ に対してその計算時間が$t$ のとき, 有限列 $\phi,$$M_{\delta}\phi,$ $\ldots,$ $M_{\delta}^{t}\phi$ を入力状態 $\phi$ に対する $M$ の計算といい, $t$ をその計算時間, $M_{\delta}^{t}\phi$ をその出力状態という. 任意の $n$ に対 し, 長さ $n$ の任意の入力に対する $M$ の計算時間が高々 $f(n)$ のとき $M$ は $f(n)$ 時間限定定終型

QTM

と いい, $f$ が多項式のとき, 多項式時間限定定零下

QTM

という. テープ記号列を表す物理量 $\hat{T}$ は, $\hat{T}=\sum_{j=1}^{\infty}\lambda_{j}I\otimes|T_{j}\rangle\langle T_{j}|\otimes I$

と表現される. 但し, $\{\lambda_{1)}\lambda_{2}, \ldots\}$ は $\{T_{1}, T_{2}, \ldots\}$ と多項式時間計算可能関数により1対1に対応する正数

の可算集合である. $Q_{j}$ を物理量

$\hat{T}$

の固有値 $\lambda_{j}$ に対応する射影作用素 $I\otimes|T_{j}$

)

$\langle$$T_{j}|\otimes I$ とする. $t$ を入力

$x$ に対する $M$ の計算時間とするとき

$||Q_{j}M_{\delta}^{t}|q_{0},$ $T_{in},$$0\rangle||^{2}=p$

,

$T_{in}\sim x$

のとき, $M$ _は確率$P$

でテープ記号列勾を出力するといい,

$T_{j}\sim y$ のときは, 確率$P$ で \Sigma -列$y$ を出力する

という. 注意. トラックの概念は古典同様の方法で

QTM

にも定義できる. また $k$ _トラック

QTM

$M=(Q,$$\Sigma_{1}\cross$ $\Sigma’,$$\delta)(\Sigma’=\Sigma_{2}\cross\cdots\cross\Sigma_{k})$ の停止スキームは条件

(4.1)

が以下の条件

(4.2)

に代わることを除いて同様に 定義される: $M_{\delta}|q_{j},$$T,$ $x)= \sum_{\tau\in\Sigma’,d}\alpha_{\tau,d}|q_{f},$ $T^{(Tr_{1}(x),\tau)},$$x+d\rangle$

(4.2)

一般に, 定終型

QTM

$M$ _は

HQTM の条件をみたしていないが,

_{その計算時間が}$t$ のとき, $t$ ステップ後 の $M$ _{の状態に対して,} $M$ _{のテープ記号列に対応する物理量が測定されたときの確率分布に対応づけ可能} な確率分布を $t$ ステップ以降, 常に得ることのできる多トラック

HQTM

_$M’$ が存在することは確認でき る. さらに

HQTM

の与えられたステップ後における出力の確率分布を任意の精度で効率的に模倣するよ うな定終型

QTM

が存在することも示すことができる

[13].

よってあるアルゴリズムを実行する

HQTM

が作りたいとき

,

我々は定終型

QTM

を作れば十分野ある.

QTM

$M=(Q, \Sigma, \delta)$ の量子遷移関数が任意の$\sigma\in\Sigma \text{に対して}\delta(q_{f}, \sigma, q_{0)}\sigma, 1)=1$ となるとき, $M$ を標

準型という. 特に定終型かつ標準型

QTM

は第

6

章の補題により

, QTM

の計算の–部として使用できる

のでアルゴリズムを作るには有用である. 以後, 定終型かつ標準型

QTM

を

SNQTM (stationary,

normal

5.

可逆性

Turing

機械と二方向量子

Turing

機械

QTM

の時間発展作用素はユニタリなので

QTM

は可逆性を有している. その–方で

CTM

は–般には

非可逆であるが

,

Bennett [2]

は任意の

CTM

が可逆性を持った

CTM

によって効率的に模倣できることを

示した. そのような

_CTM

は, 可逆性

Turing

機械

(RTM)

と呼ばれている 我々は

RTM

$M=(Q, \Sigma, \delta)$

を任意の状況$C$ _{に対して,} $\delta$

(

$q_{C’},$$T_{C’}$

(xc–d))

$=(qc, T_{C}(xc-d),$$d)$ _{となるような状況} $C’$ _と方向 $d$ の組

が丁度1組存在するような

CTM

である, と定義することができる 後に,

Deuscth [6]

は

RTM

の時間発

展作用素の計算基底に関する行列表現が,

成分として $0$ と1

しか持たない直交行列であることから,

_次の

意味で

RTM

が

QTM

_{の–種であることを述べた:.}

_RTM

$M=(Q, \Sigma, \delta)$ _と

QTM

$M’=(Q, \Sigma, \delta’)$ _は任

意の $(p, \sigma, q, \tau, d)\in Q\cross\Sigma\cross Q\cross\Sigma\cross[-1,1]_{\mathrm{Z}}$ に対して $\delta’(p, \sigma, q, \tau, d)=1$ _のとき, _{そしてそのときのみ} $\delta(p, \sigma)=(q, \tau, d)$

,

という対応のもとで同–視できる. 以後

,

$M’$ _のような

QTM

_も

RTM

_{ということにす}

る.

Bennett

の証明で用いられた

RTM

は多テープ$\mathrm{T}_{\mathrm{J}}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{g}$ 機械であったが

, [4]

では 1 テープ二方向

RTM

によって模倣できることが示された. 但し

,

二方向(古典または量子)

Turing

機械とは

,

head

の動きを表 す $d$ _を $\pm 1$ に制限した

Turing

機械のことである 以下では,

RTM

に関しては二方向

RTM

_{のみを考える} ことにする. また定終型かつ標準型

RTM

を

SNRTM

と略す. 定理 5.1 (同時化定理)

[4]

$f$

:

$\Sigma^{*}arrow\Sigma^{*}$ が多項式時間限定

CTM によって計算可能な関数で,

_入力 $x$ に対して $|f(x)|$ が $|x|$

のみに依るならば,

$x$ に対して $(x, f(x))$ を出力する二方向定終型かつ標準型

RTM

が存在して

,

その計算時間は $|x|$ の多項式時間である. さらに $f$ が全単射で $f^{-1}$ が多項式時間限定

CTM

によって計算可能な関数とすると $x$ に対して $f(x)$ を出力する二方向焼残型かつ標準型

RTM

が存在して, その計算時間は $|x|$ の多項式時間である. これまで

Turing-型の量子コンピュータのモデルとしては [3], [6]

などで, 二方向

QTM

が使用されてき た. その理由は, プレ

QTM

が

QTM

になるための条件の扱いやすさにある. 具体的には, 二方向プレ量子

Turing

機械$M=(Q, \Sigma, \delta)$_が二方向

QTM

_{となるための必要十分条件は}

,

_定理31_の条件

(a),(b),(c)

_が成り

立つだけでよくなる

[3].

さらに $\delta$ が次の条件をみたす二方向

QTM

は,条件

(c)

が自然と成立しているもの

であり, –方向

QTM

と呼ばれる

[3]:

任意の$q\in Q$ 及び任意の $(p)\sigma,$$\tau,$$d),$ $(p’, \sigma’, \tau’, d’)\in Q\cross\Sigma^{2}\cross\{-1,1\}$

に対し, $\delta(p, \sigma, q, \tau, d)$ 及び $\delta(p’, \sigma’, q, \tau’, d’)$ がともに $0$ でないなら $d=d’$. –方向

QTM

のヘッドは, 新

しい内部状況 $q$ によって決定される方向 $d$ に移動するので

,

その時間発展は $(p, \sigma)$ 列 $(q, \tau)$ 行の成分が

$\delta(p, \sigma, q, \tau, d)$ となるような, 有限次元ユニタリ行列 $L_{\delta}$ によって表現できる. 実は

,

任意の

QTM

は–方向

QTM

によって模倣できる

[4].

補題 52(完成補題) $Q\cross\Sigma\cross Q\cross\Sigma\cross\{-1,1\}$ 内の部分集合上で

,

_定理31_の条件

(a),(b),(c)

_を

満たす関数 $\delta’$ に対して, $\delta’$ の定義域では $\delta’$ と同じ値を取る量子遷移関数 $\delta$ を持つような二方向

QTM

$M=(Q, \Sigma, \delta)$ が存在する. この補題は二方向

QTM

のもう 1 つの利点である. これにより, 我々はある二方向

QTM

に実行させた いアルゴリズムを容易に構築することができる. なぜならアルゴリズムの中で使用される全ての内部状況 と記号の組に対して

,

定理31の条件

(a),(b),(c)

を満たす部分関数を定義すれば十分前からである.

6.

QTM

のプログラムのための補題 この章では

,

8章の定理を証明するために必要な

[4]

の補題を記す. これらの証明は

[4]

を参照されたい.

任意の

QTM

$M=(Q, \Sigma, \delta)$ _{と任意のアルファベット}$\Sigma’$

が与えられたとき, 次の 2 トラック

QTM

$M(\Sigma’)=(Q, \Sigma\cross\Sigma’, \delta’)$ は, ( $M$ _{へのアルファベット} $\Sigma’$ を持つ) トラックの付加により構成されたとい

う: 任意の $(p, (\sigma, \sigma’), q, (\tau, \tau’))d)\in(Q\cross(\Sigma\cross\Sigma’))^{2}\cross[-1,1]_{\mathrm{Z}}$ に対して

また $k$ トラック

QTM

$M=(Q, \Sigma_{1}\cross\cdots\cross\Sigma_{k}, \delta)$ と置換 $\pi$

:

$[1, k]_{\mathrm{Z}}arrow[1,$$k|\mathrm{z}$

が与えられたとき,

次の $k$

トラック

QTM

$M’=(Q, \Sigma_{\pi(1)}\cross\cdot, . \mathrm{x}\Sigma_{\pi(k)}, \delta’)$は ($M$ に対する) トラックの置換$\pi$ によって構成され

たという: 任意の $(p, (\sigma_{1}, \ldots, \sigma_{k}), q, (\tau_{1}, \ldots, \tau_{k}), d)\in(Q\cross(\Sigma_{\pi(1)}\cross\cdots\cross\Sigma_{\pi(k)}))^{2}\cross[-1,1]_{\mathrm{Z}}$ _{に対して,}

$\delta’(p, (\sigma_{1}, \ldots, \sigma_{k}), q, (\tau_{1}, \ldots, \tau_{k}), d)\cdot=\delta(p, (\sigma_{\pi(1)}, \ldots, \sigma_{\pi(k)}), q, (\tau_{\pi(1)}, \ldots, \tau_{\pi(k)}), d)$

.

多トラック

QTM

において,

あるトラックであるアルゴリズムを実行したいときは,

そのアルゴリズムを 実行する

QTM

を構成してから

,

トラックの付加及び置換を用いればよい.

_{8 章の定理の証明では,}

トラッ

クの付加及び置換を頻繁に利用しているので,

その使用を一っ一つ断わることはしないものとする. 次に

QTM

のアルゴリズム設計に必要な補題を与えておく. 補題6.1 (接続補題) $M_{1},$$M_{2}$ が同じアルファベットを持ち

,

$M_{1}$ が

SNQTM

なら $M_{1}$ の行う計算の 実行後

,

$M_{2}$ の計算を実行する

QTM

M

が存在する _{このような} $M$ _を$M_{1}$ と $M_{2}$ を接続して構成された

QTM

という. 注意. 各ステップ後のヘッドの位置が入力の長さにのみ依存する (古典または量子)

_Turing

機械を忘 却$-(\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{o}\mathrm{u}\mathrm{s})$

Turing

機械という 一般にたとえ _{$M_{2}$} が定終型でも _$M$ が定終型であるとは限らない. $M$

が定終型であるには

,

次の条件を満たせば十分である: $M_{1}$ の終了状態が $\sum_{i:\alpha}:\neq 0\alpha_{i}|q_{j},$$T_{i)}0\rangle$ ならば

,

全

ての $i$ に対して長さの等しい

$x_{i}$ が存在して$T_{i}\sim x_{i}$ であり, $M_{2}$ が定終型忘却

QTM

である. この条件を

接続条件という. 補題6.2 (分岐補題) $M_{1},$$M_{2}$ が同じアルファベットを持つ

SNQTM

なら次のような

SNQTM

$M$ _が存 在する “第 2 トラックが空白なら, $M$ _は第1 _{トラックで}$M_{1}$

の計算を実行し,

マス目 $0$ に 1 を持つなら $M_{2}$ の計算を実行する. いずれも第2 トラックは書き換えない)’. $M$ _{の計算時間は実行される}

QTM

_{$M_{i}(i=1$}

or

2)

の計算時間より4ステップ余分にかかる. 補題6.3 (ループ補題) 次のような

SNRTM

$M$ _と定数 $c$ が存在する. “正整数$k$ _{の 2 進表示を入力と} したとき $M$ _は$O(k\log^{c}k)$

_{時間で終了状況に入り,}

_{そのテープ記号列は初期状況のものと同じである. さ} らに $M$ _{はある特定の内部状況}$q^{*}$ にマス目 $0$ でちょうど $k$ 回入る”. 注意. この $q^{*}$ に

SNQTM

$M’$ を“挿入” する, すなわち, _$M$ の内部状況が $q^{*}$ になるごとに $M’$ の計算 を実行することにより, $M’$ _{によって行われる計算を} $k$ 回実行する

SNQTM

_{が構成できることになる.} $M$ _と $M’$ _は

SNQTM

_{であり, また同じアルファベットを持つものとする そのとき} $M’$ _が $M$ _を逆行す るとは, $M$ _{の初期内部状況と} $M’$ _{の最終内部状況}

,

$M’$ _{の初期内部状況と} $M$ _{の最終内部状況を同}–_視する ことで次のことが成り立つことをいう: もし $|C$

)

と $|\phi\rangle$ がそれぞれ $M$ の初期状況と終了状態なら $M’$ の 初期状態 $|\phi\rangle$ に対する終了状態は _$|C$

)

である. 補題6.4 (逆行補題) $M=(Q, \Sigma, \delta)$ _が–_方向

SNQTM

(二方向標準型 RTM) _なら, $M$ _{の計算を逆} 行する–方向

SNQTM

(二方向標準型 RTM) $M’$ _{が存在して}

,

$M$ _{の計算時間を}$t$ ステップとすると $M’$ の計算時間は$2:t+2$ ステップである.

7.

量子回路 以下

,

我々$\iota’\mathrm{h}\{0,1\}$ の元をビット

,

_{$\{0,1\}^{m}$ の元を長さ} $m$ のビット列と呼ぶことにする. また長さ $m$ の

ビット列 $x=x_{1}\cdots x_{m}$ に対して, $x_{i}$ を $x$ の第 $i$ ビットという. _$m$ 入力 _$n$ 出力の古典ゲート $G$ _とは, _長さ

$m$ のビット列に長さ $n$ のビット列を対応させる関数である. $G(x_{1}\cdots x_{m})=y_{1}\cdots y_{n}$ _のとき, $y_{1}\cdots y_{n}$ を

入力 $x_{1}\cdots x_{m}$ に対する $G$ の出力という. $G$ が全単射のとき $G$ は可逆性ゲートという. $G$ の入力の長さ

が $n$ のとき, $G$ を $n$ ビット可逆性ゲートと呼ぶ. 例えば入力 _$xy$ に対して $x(x\oplus y)$ _{を出力する古典ゲート}

$M_{2}(N)$ は 2 ビット可逆性ゲートであり

,

制御否定ゲートと呼ばれる. 第 1 ビットは制御ビット

,

第 2 ビッ

図1: 制御否定ゲート $M_{2}(N)$

次に量子ゲートの定義を与える. そのため,

まず可算無限個の

2

状態系の集まりを考える

.

この集合に属

する各々の2状態系をワイヤと呼ぶ_{. 各ワイヤには}

,

指標$i=1,2,$$\ldots$ が与えられており, この指標をビッ

ト番号と呼ぶ. 形式的には, 指標$j$ をもつワイヤは

,

ビットに

–

対一対応を与える正規直交系

$\{|0\rangle_{j)}|1\rangle_{j}\}$

を基底とする

Hilbert

空間 $\mathcal{H}_{j}\cong \mathrm{C}^{2}$ で記述される.

Hilbert

空間

$\mathcal{H}_{j}$

の物理量 n^j

$=|1\rangle_{j}\langle 1|_{j}$ を第 $j$ ビッ

ト物理量と呼ぶ. $\Lambda=$

{

$j_{1},$

$\ldots$

,

in}

$(j_{1}<\cdots<j_{n})$ を大きさ $n$ の指標の集合とする. 指標 $j\in\Lambda$ をもつ $n$

個のワイヤの合成語は,

Hilbert

空間$\mathcal{H}_{\Lambda}=\otimes_{j\in\Lambda}\mathcal{H}_{j}$ で記述される

Hilbert

空間 $\mathcal{H}_{\Lambda}$ において, 長さ _$n$

のビット列の集合 $\{0,1\}^{n}$ _に–_{対一対応を与える正規直交基底}

$\{|x_{1})_{j_{1}}\cdots|x_{n}\rangle_{j_{n}}|x_{1}\cdots x_{n}\in\{0,1\}^{n}\}$

を

A

上の計算基底という. 以後, $|x_{1}\cdots x_{n}$

)

$=|x_{1}\rangle_{j_{1}}\cdots|x_{n}\rangle_{j_{n}}$ と略記する. このとき

$1\otimes\cdots 1\otimes\hat{n}_{j_{k}}\otimes 1\cdots\otimes 1|x_{1}\cdots x_{k}\cdots x_{n}\rangle=x_{k}|x_{1}\cdots x_{k}\cdots x_{n})$

となる. $\mathcal{H}_{\Lambda}$ の単位ベクトルは長さ _$n$ の状態と呼ばれる. 以下では, 指標の集合 $\{1, \ldots, n\}$ _を $\Lambda^{(n)}$ と表すことにする. $n$ ビット量子ゲートとは, $n$個のワイヤが 相互作用していて, 入力状態から出力状態への状態変化がそれら $n$個のワイヤの合成系の時間発展により 得られるものである. 形式的には, ワイヤの指標の集合

A

に対して,

Hilbert

空間$\mathcal{H}_{\Lambda}$ 上のユニタリ作用素 をAl子ゲートと定義する. 特に $\Lambda^{(n)}$ .

-量子ゲートは,

$n$ ビット量子ゲートと呼ばれる. A-量子ゲートの計 算基底に関する行列を $\mathrm{S}$-行列という. A-量子ゲート _$G$

に対して, $\mathcal{H}_{\Lambda}$ の単位ベクトル $\psi,$$\phi$ が $G\psi=\emptyset$ と

いう関係をみたすとき, $\phi$ を入力状態 $\psi$ に対する $G$ の出力状態という. 特に, 入力状態が $\psi=|x_{1}\cdots x_{n}\rangle$

のとき, ビット列 $x_{1}\cdots x_{n}$ を $G$ の入力と呼ぶ.

$n$ ビット可逆性ゲートは $\mathrm{S}$-行列が, 各行各列に 1 つだけ 1 をもち, 他は $0$ であるような $2^{n}\cross 2^{n}$ 直交行

列であるユニタリ作用素とみなせるので, $n$ ビット量子ゲートの–種である. 以下では, このような S-行

列を持つ量子ゲートをも可逆性ゲートと呼ぶことにする.

$\Lambda^{(n)}$

上の置換を $P$ _{とする. このとき長さ} $n$ の状態 $|x_{1}\cdots x_{n}\rangle$ を $|x_{P(1)}\cdots x_{P(n)}\rangle$ に変換する $\mathcal{H}_{\Lambda^{(n)}}$ 上

の作用素 $V_{P}$ を $\Lambda^{(n)}$

上の置換作用素という. また $m\leq n$ _のとき, $\Lambda^{(m)}$-量子ゲー $\vdash G$ _に対して, $\Lambda^{(n)}- \text{量}$

子ゲート $G\otimes I_{\Lambda(n)\backslash \Lambda^{(\varpi)}}2$を $G$ _の ($n$ ビットへの) $\text{拡大といって}\tilde{G}$ と表す. このとき $n$ ビット量子ゲート

$G$ が量子ゲートの集合$\mathcal{G}$

によって分解可能であるとは

,

ni $(\leq n)$ ビット量子ゲート $G_{i}\in \mathcal{G}(i=1, \ldots, k)$

及び$\Lambda^{(n)}$

上の置換作用素 $V_{P}$

,

$(i=1, \ldots, k)$ が存在して,

$G=U_{1}\cdots U_{m}^{\backslash }$

,

$(U_{i}=V_{P}\dagger.\tilde{G}_{i}V_{P}\dot{.})$

と書けることを指し

,

このとき量子ゲート $G$ _は$\mathcal{G}$ に属する

$m$ 個の量子ゲートに分解可能であるという. こ

のような $m$ の最小数を $G$ _の $\mathcal{G}$ に対するサイズという. また $||G-U_{1}\cdots U_{m}||\leq\epsilon$ と書けるとき $G$ は $\mathcal{G}$

によって精度\epsilon 以内で分解可能であるという.

任意の量子ゲートを任意の精度で分解可能であるような量子ゲートの集合を万能集合,

その元を基本ゲー

トという. $R_{1,\theta},$$R_{2,\theta},$$R_{3,\theta}$ をその S-行列が

$R_{1,\theta}=$

,

$R_{2,\theta}=$

,

$R_{3,\theta}=$

となるような1 ビット量子ゲートであるとする. このとき無限集合

$\mathcal{G}_{u}=\{R_{1,\theta}, R_{2,\theta}, R_{3,\theta}, M_{2}(N)|\theta\in[0,2\pi]\}$

によって, 任意の量子ゲートが分解可能であることが

[1]

において示されている.

定理71任意の $n$ ビット量子ゲート $G$ _は, 高々$O(n^{3}2^{2n})$ _{個の仇内の量子ケ}

–

_{トによって分解可能で}

ある.

よって無限集合$\mathcal{G}_{u}$ は万能集合である. 以下では, $\mathcal{G}_{u}$ に対するサイズを特に

u-

サイズという.

次に我々は有限の万能集合を考える. そのためにまず “効率的に計算可能な数’) の概念を与える. 実数 $x$

が多項式時間計算可能であるとは,

任意の $n\in \mathrm{N}$ に対して $|\phi(1^{n})-x|\leq 2^{-n}$ かつ $\phi(1^{n})\in\{m/2^{n} ; m\in \mathrm{Z}\}$

なる多項式時間限定

CTM

$T$ によって計算可能な関数 $\phi$ が存在することを意味する. 多項式時間計算可能

な実数の集合を $P\mathrm{R}$ と表す. また財部及び警部が多項式時間計算可能な複素数を多項式時間計算可能な複

素数といってその集合を $P\mathrm{C}$ と表す.

以下, 本論文では$\mathcal{R}=2\pi\sum_{i=1}^{\infty}2^{-2^{i}}$ _{と表すことにする. このとき次}

の補題が成り立つ.

補題7.2

[4]

実数\theta \in $[0,2\pi],$ $\epsilon>0$ に対して_{$|kR-\theta|$}

(mod

$2\pi$

)

$\leq\epsilon$ となる最小の非負整数 $k\leq O(1/\epsilon^{2})$

が存在する.

また入力として

\theta ,

$\epsilon\in P\mathrm{R}$ を与えたとき

3

上のような $k$ を出力する入力の長さの多項式時間

限定

CTM

が存在する.

補題 7.2 より $\mathcal{G}_{\mathcal{R}}=\{R_{1,\mathcal{R}}, R_{2,\mathcal{R}}, R_{3,\mathcal{R}}, M_{2}(N)|\mathcal{R}=2\pi\sum_{i=1}^{\infty}2^{-2^{i}}\}$ とすると $\mathcal{G}_{u}$ の 1 ビット量子ゲート

はGえの1 ビット量子ゲートによって任意の精度で分解可能なので有限集合

G えは万能集合である.

以下, $\mathcal{G}_{\mathcal{R}}$ に対するサイズのことを単にサイズということにする. 任意の古典ゲートは論理積

,

論理和, そして否定の合成によって得られるので, 古典の場合これらのゲー トをもとに古典回路が考えられている. 形式的には, 古典回路は非循環有向グラフとして定義され, その各 頂点が古典ゲート

,

側辺が古典ゲートを接続するワイヤに対応する

[14].

方, $n$ ビット量子回路とは

,

複数の量子ゲートが各々 $n$ 個のワイヤのうち,決められた幾つかのワイヤに つながれている様を表すものである. 形式的には次のように定義される. $\mathcal{G}$ を量子ゲートの集合とする. $\mathcal{G}$ を 基底とする $n$ ビット量子回路

If

とは, 次の条件を満たす2つ組 $(G_{i}, P_{i})$ の有限列 $(G_{1}, P_{1}),$ $\ldots,$$(G_{m}, P_{m})$ である.

(1)

$G_{i}$ は $\mathcal{G}$ に属する ni $(\leq n)$ ビット量子ゲートである.

(2)

$P_{i}$ は$\Lambda^{(n)}$

上の置換作用素である.

このとき $G_{i}$ の $j$ 番ピンには, ビット番号$P_{i}\mathrm{O}$

)

のワイヤが接続されているという. また $I\dot{\iota}’$ は _{$G_{1},$}

$\ldots,$$G_{m}$

の連結によって構成されているという. $m$ を $I\mathrm{t}’$ の $\mathcal{G}$ に対するサイズという. 特に蜘に対するサイズの

ことを $\mathrm{u}$

-

サイズ

,

$\mathcal{G}n$ に対するサイズを単にサイズということにする. ユニタリ作用素 $U_{1}\cdots U_{m},$ $(U_{i}=$ $V_{P}^{\uparrow}.\tilde{G}_{i}V_{P}.\cdot,$

$G_{i}\in \mathcal{G})$ を$I\zeta$で定まる _$n$ ビット量子ゲートといって

,

以下これを記号_{$G_{K}$} で表すことにする. 定義 より $G_{K}$ の$\mathcal{G}$ に対するサイズは

If

の$\mathcal{G}$ に対するサイズ以下である. また$I\acute{\mathrm{e}}_{1}=(G_{1}^{(1)}, P_{1}^{(1)}))\ldots,$ $(G_{m}^{(1)}, P_{m}^{(1)})$

及び $I\mathrm{t}_{2}’=(G_{1}^{(2)}, P_{1}^{(2)}),$ $\ldots,$ $(G_{l}^{(2)}, P_{l}^{(2)})$ _を $\mathcal{G}$ を基底とする _$n$ ビット量子回路とするとき, $I\mathrm{f}_{1}+I\dot{\iota}_{2}’=$ $(G_{1}^{(1)}, P_{1}^{(1)}),$ $\ldots,$ $(G_{\mathfrak{m}}^{(1)}, P_{m}^{(1)}),$ $(G_{1}^{(2)}, P_{1}^{(2)}),$ $\ldots,$ $(G_{l}^{(2)}, P_{l}^{(2)})$ _は $I\zeta_{1}$ と $I\mathrm{f}_{2}$ の連結によって構成された量子回 路といい, $nI\mathrm{f}_{1}=\underline{I\mathrm{t}_{1}’+\cdots+I\{^{r_{1}}}$は $n$ 個の $I\iota_{1}^{\nearrow}$ の連結によって構成された量子回路という. 次に, $k$ 入力 _{$m$ 出力の量子回路の物理的定義を与える}. $k$ 入力 _$m$ 出力の $n$ ビット量子回路とは

,

量子 ゲートの集合を基底とする $n$ ビット量子回路 (で定まる $n$ ビット量子ゲート) に長さ $k$ のビット列及び 長さ $n-k$ の–定のビット列を入力して, このゲートによるユニタリ変換を受けた後, ある決められた $m$ 個のワイヤのビット物理量を測定して, 長さ $m$ のビット列を出力として得るもののことである. 3 入力として多項式時間計算可能な実数 $\theta$ を与えるということは, $\theta$ の有理数による近似値を計算する CTM $T_{\theta}$ のコードと必要 な精度\epsilon 0 の組を与えることを意味する.

形式的には, $k$ _{入力 $m$ 出力の $n$ ビット量子回路}$\mathrm{K}$

とは, 次の条件をみたす 4 つ組 $(K, \Lambda_{1}, \Lambda_{2}, S)$ であ

る.

(1) If

は$n$ ビット量子回路である.

(2)

$\Lambda_{1}$

,

A2は $\Lambda^{(n)}$ の部分集合で _{$|\Lambda_{1}|=k,$ $|\Lambda_{2}|=m$}

である.

(3)

$S$ _は$\Lambda^{(n)}\backslash \Lambda_{1}$

を添字集合とするビットの族である. つまり, $S=\{b_{j}| j\in\Lambda^{(n)}\backslash \Lambda_{1}\}(b_{j}\in\{0,1\})$

.

$\mathrm{K}=$

(

_$IC,$$\Lambda_{1}$

, A2,

$S$

)

を $k$ 入力 _$m$ 出力の $n$ ビット量子回路とし, $\Lambda_{1}=\{j_{1)}\ldots, j_{k}\},$ $\Lambda_{2}=\{i_{1}, \ldots, i_{m}\}$

とする. $k$ _{ビット列 $x_{1}\cdots x_{k}$ に対して},

$u_{j_{1}}=x_{1},$$\ldots,$$u_{j_{k}}=x_{k}$, かつ$j\in\Lambda^{(n)}\backslash \Lambda_{1}$ に対して, $u_{j}=b_{j}\in S$

となるように, $n$ ビット列 $u_{1}\cdots u_{n}$ を定める. 入力 $u_{1}\cdots u_{n}$ に対する $G_{K}$ の出力状態を $\phi$ とし, 状態$\phi$ で

ビット物理量 $\hat{n}_{i_{1}},$$\ldots,\hat{n}_{i_{m}}$ を同時測定して, 測定値 $\dot{y}_{1)}\ldots$

,

_{$y_{m}$} が得られるとき, ビット列

$y_{1}\cdots.y_{m}$ は入力 $x_{1}\cdots x_{k}$ に対する $\mathrm{K}$ の出力であるという. 入力が

$x$ であ$\text{るという条件のもとで}$

,

出力として _{$y=y_{1}\cdots y_{m}$}

を得る確率 $\rho^{K}(y|x)$ _{は量子力学の統計公式から次のように書ける}.

$\rho^{K}(y|x)=\langle u_{1}\cdots u_{n}|c_{K}\dagger_{E_{i_{1}}(y_{1})\cdot\cdot E_{i_{m}}(y_{m})G_{K}},|u_{1}\cdot$ ,$.u_{n}\rangle$

但し

,

$E_{i_{\mathrm{p}}}(y_{p})$ は $\hat{n}_{i}$

,

の固有値

$y_{\mathrm{p}}$ に対応する射影作用素である.

$\mathrm{K}$ は各入力 _{$x=x_{i_{1}}\cdots x_{i_{k}}\in\{0,1\}^{k}$} を

$\{0,1\}^{m}$ 上の確率分布 $\rho^{K}(x)$ に対応させていると考えられる. このとき $\rho^{K}(x)$ を $\mathrm{K}$ によって定まる旧こ

対する分布という. 以後, 特に混同しないときは$\mathrm{K}$ と

If

を同–視して扱う.

関数 $e$

:

$\Sigmaarrow\{0,1\}^{l_{0}}(l_{0}=\lceil\log|\Sigma|\rceil)$ を単射

,

$d:\{0,1\}^{l_{0}}arrow\Sigma$ を $d\cdot e=\mathrm{i}\mathrm{d}|_{\Sigma\backslash \{B\}}$ かっ $d(x)=B(x\not\in$ $\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(e))$ をみたす関数とする また \Sigma -列 $x=x_{1},$

.

_{$.x_{k}$} 及びビット列 $z=z_{1}\cdots z_{k}(z_{i}\in\{0,1\}^{l_{0}})$ に対し

て$e_{k}(x_{1}\cdots x_{k})=e(x_{1})\cdots e(x_{k})$

,

$d_{k}(z_{1}\cdots z_{k})=d(z_{1})\cdots d(z_{k})$ とする. このとき ($kl_{0}$ 入力 $(t+l+\sim 1)l_{0}$

出力) 量子回路 $K$ _が

QTM

$M=(Q, \Sigma, \delta)$ を (符号化関数 $e$

,

復号化関数 $d$ のもと) 精度 $\epsilon$ で $rightarrow$

, t)-

模倣

する($\epsilon=0$ _の場合, _{単に $(k,$$t)-$}模倣するという) _とは, _長さ $k$ の任意の \Sigma -列 $x$ に対し, $M$ に $x$ を入力し

て$t$ ステップ後にテープのマス目 $-t$ からマス目$t= \max(t, k)\sim$ を測定したときの測定値の確率分布と

If

に

$e_{k}(x)$ を入力したときの出力を $z$ としたときの $d_{t+\overline{t}+1}(z)$ の確率分布の

TVD

4が $\epsilon$ 以内となる

,

すなわち

$\sum_{y\in\Sigma 2+\overline{\mathrm{c}}+1}|\rho_{t}^{M}(y|x)-\tilde{\rho}^{K}(y|x)|\leq\epsilon$

をみたすような $kl_{0}$ 入力 $(t+t+\sim 1)l_{0}$ 出力の量子回路$I\acute{\iota}$ が存在することである. 但し

,

$\overline{\rho}^{K}(y|x)$ $=$

$\sum_{z_{-*}\cdots z_{f}\in d_{\mathrm{t}+\overline{|}+1}^{-1}(y)}\rho^{K}(z_{-t}\cdots z_{t^{\sim}}|e_{k}(x))$

$\rho_{t}^{M}(y|x)$ _$=$ $\langle q_{0},$$T_{in},$$0|M_{\delta}^{t\uparrow}E_{-t}(y_{-t})\cdots E_{\overline{t}}(y_{\overline{t}})M_{\text{\’{o}}}^{t}.|q_{0},$$T_{in},$$0\rangle$

,

$(T_{in}\sim x)$

である. 但し, マス目 $i$ の記号を表す物理量の $y_{i}\in\Sigma\backslash B$ に対応する固有値を $\lambda_{i}$ とすれば

,

$E_{i}(y_{i})$ は\mbox{\boldmath$\lambda$}i に

対応する射影作用素である.

Yao

は

[17]

で任意の

QTM

$M$

,

_入力 $x$

,

そして時間$t$ に対して,_$M$ を_{$(|x|, t)$}-模倣する量子回路$K$

(

$M$

, 国,

$t$

)

が存在して

,

その “サイズ’) (“サイズ” は

Deustch

ゲート

[7]

の個数である) は高々 $t$ の多項式以下であ ることを示した. 我々はこの

Yao

の証明で使われた量子回路を少し変形することで多フ—-7

QTM

にも定 理が成立するようにしておく. また後でこの証明を利用するために “サイズ)’ として u-サイズを用いるこ とにする.

定理7.3 $M=(Q, \Sigma, \delta)$ をある

QTM,

$t>k$ とすると

,

$M$ _を $(k,t)$-模倣するような $\mathrm{u}$-サイズ $O(t^{2})$ の

量子回路が存在する.

証明 $l=O(2+\lceil\log(|Q|+1)\rceil+\lceil\log|\Sigma|\rceil)$ _とする

QTM

$M$ _{を $(k,t)- \text{模倣するような量子}$路} $I\zeta_{Q}$ で

定まる量子ゲート $G_{Kg}$ は $(2t+4)l$本のワイヤが接続されている. そのワイヤは $l$ 個ごとに分けて考える

4 同じ定義域上の分布 $D,$ $\mathcal{D}’$ の全変動距離(TVD)

とは, $\sum_{1\in I}.|D-D’|$ のことである TVD と Euclid 距離の関係として,

ことにする. ビット番号$jl+1,$$\ldots,$$jl+l(0\leq j\leq 2t)$ のワイヤは $M$ のマス目

$j-t$

を表現していて

,

こ

のワイヤの集合を $IC_{\mathcal{G}}$ のマス目 $j-t$ と呼ぶことにする. $K_{\mathcal{G}}$ のマス目 $i(-t\leq i\leq t)$ の状態は計算基底

$\{|q_{i}a_{i}s_{i}b_{i}\rangle\}$

,

$q_{i}a_{i}s_{i}b_{i}\in\{0,1\}^{1}$

によって張られる

Hilbert

空間内の単位ベクトルによって表現される ( $b_{i}$ は

–

定のビット列であり

,

以

下では省略する)

.

$q_{i}$ は $M$ のヘッドがマス目 $i$ tこあるときは $M$ の内部状況

,

マス目 $i$ にないときは

$\emptyset=0^{\lceil\log(|Q|+1)\rceil}$ _{を表す $\lceil\log(|Q|+1)\rceil$}

ビット列, $a_{i}l\mathrm{h}M$ _のマス目 $i$ の記号を表す $\mathrm{p}\mathrm{o}\mathrm{g}|\Sigma|\rceil$ ビット列, そ

して$s_{i}$ は$M$ のヘッドがマス目 $i$ にあるとき 1 または 2, ないときは $0$ を表す 2 ビット列である. ビット 番号 $(2t+1)l+1,$$\ldots,$$(2t+4)l$ の$3l$ 本のワイヤは$M$

の量子遷移関数に対応する操作を行うため使用して,

ビット番号が小さい順$|^{arrow}.l$ 個つつのワイヤの集合をマス目 _{$L,$ $N,$ $R$} または, マス目

$2t+2,2t+3,2t+4$

と呼ぶことにする. 次に $K_{\mathcal{G}}$ を構成する量子ゲート $G_{1},$ $G_{2},$ $G_{3}$ を与えることにする. 以下において _$p,$$q,$ $\ldots$ は $Q$ の元, $\sigma,$$\tau,$$\ldots$ は

$\Sigma$ の元を表すものとする.

$G_{1}$ は次の条件をみたす$4l$ _{ビット可逆性ゲートである}:

$G_{1}|p\sigma 1;\emptyset B\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O}\rangle=|\emptyset B2;\emptyset B\mathrm{O};p\sigma 1;\emptyset B\mathrm{O}\rangle$

,

$G_{1}|\emptyset B0;\emptyset B\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O}\rangle=|\emptyset B0;\emptyset B\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O}\rangle$

.

$G_{2}$ は次の条件

(A)

をみたす $3l$ _{ビット量子ゲートである}

:(A)

$|w_{p,\sigma}\rangle$ $=$ $|\emptyset B0;p\sigma 1;\emptyset B0\rangle$

,

$|v_{p,\sigma}\rangle$ $=$

$\sum_{q,\tau}\delta(p, \sigma, q, \tau, -1)|qB2;\emptyset\tau 0;\emptyset B0)+\sum_{q,\tau}\delta(p, \sigma, q, \tau, 0)|\emptyset B0;q\tau 2;\emptyset B0)$

$+ \sum_{q,\tau}\delta(p, \sigma, q, \tau, 1)|\emptyset B0;\emptyset B0;q\tau 2)$

とするとき $G_{2}|w_{p,\sigma}\rangle$ $=|v_{p,\sigma}\rangle$

.

最後に $G_{3}$ は次の条件をみたす $6l$ ビット可逆性ゲートである:

$(a)G_{3}|\emptyset\sigma_{1}0;\emptyset B2;\emptyset\sigma_{2}0;qB2;\emptyset\tau 0;\emptyset B\mathrm{O}\rangle=|q\sigma_{1}1;\emptyset\tau 0;\emptyset\sigma_{2}0;\emptyset B\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O}\rangle$

$(b)G_{3}|\emptyset\sigma_{1}0;\emptyset B2;\emptyset\sigma_{2}0;\emptyset B\mathrm{O};q\tau 2;\emptyset B\mathrm{O}\rangle=|\emptyset\sigma_{1}0;q\tau 1;\emptyset\sigma_{2}0;\emptyset B\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O}\rangle$

$(c)G_{3}|\emptyset\sigma_{1}0;\emptyset B2;\emptyset\sigma_{2}0,$ $\emptyset B\mathrm{O};\emptyset\tau 0;qB2\rangle=|\emptyset\sigma_{1}0;\emptyset\tau 0\cdot,$$q\sigma_{2}1;\emptyset B\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O}\rangle$

$(d)G_{3}|\phi\rangle=|\phi\rangle$

但し, $|\phi$

)

は次の 9 種類の計算基底状態からなる任意の状態を表す.

(1)

$|\emptyset\sigma_{1}0;\emptyset\sigma_{2}0;\emptyset B2;qB2;\emptyset\tau 0;\emptyset B\mathrm{O}\rangle$

,

(2)

$|\emptyset\sigma_{1}0;\emptyset\sigma_{2}0;\emptyset B2;\emptyset B\mathrm{O};q\tau 2;\emptyset B\mathrm{O})$

(3)

$|\emptyset\sigma_{1}0;\emptyset\sigma_{2}0;\emptyset B2;\emptyset B\mathrm{O};\emptyset\tau 0;qB2\rangle$

,

(4)

$|\emptyset\sigma_{1}0;\emptyset\sigma_{2}0;\emptyset\sigma_{3}0;qB2;\emptyset\tau 0;\emptyset B\mathrm{O})$

(5)

$|\emptyset\sigma_{1}0;\emptyset\sigma_{2}0,$$\emptyset\sigma_{3}0;\emptyset B\mathrm{O};q\tau 2;\emptyset B\mathrm{O}\rangle$

,

(6)

$|\emptyset\sigma_{1}0;\emptyset\sigma_{2}0;\emptyset\sigma_{3}0;\emptyset B\mathrm{O};\emptyset\tau 0;qB2\rangle$

(7)

$|q\tau 1;\emptyset\sigma_{1}0;\emptyset\sigma_{2}0;\emptyset B\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O}\rangle$

,

(8)

$|\emptyset\sigma_{1}0;q\tau 1;\emptyset\sigma_{2}0;\emptyset B\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O})$

(9)

$|\emptyset\sigma_{1}0;\emptyset\sigma_{2}0;\emptyset\sigma_{3}0;\emptyset B0;\emptyset B0;\emptyset B0)$

今

,

$K_{\mathcal{G}}$ を$\mathcal{G}=\{G_{1}, G_{2}, G_{3}\}$ を基底として, 以下のように構成される量子回路とする. 以下で, $ml$ _ビット

量子ゲート $G(m=1,2, \ldots, 2t+4)$がマス目$i_{1},$

$\ldots,$$i_{m}(i_{1}<\cdots<i_{m})$ に接続されるとは

,

$G$ の $(j-1)l+k$

番ピン$(j=1, \ldots, m, k=1, \ldots, l)$がビット番号$(i_{j}+t)l+k$ のワイヤに接続されることを表す: $2t+1$ {固

の $G_{1}$ を順に接続する. このとき $j$ 番目 $(1 \leq j\leq 2t+1)$_の $G_{1}$ はマス目

$j-t-1,$

$L,$$N,$$R$ _{に接続する. こ} の $2t+1$ 個の $G_{1}$ から構成される $(2t+4)l$ ビット量子回路を $I\mathrm{f}_{1}$ と呼ぶ. 次に $G_{2}$ をマス目 $L,$$N,$$R$ _に接 続する. この $G_{2}$ から構成される $(2t+4)l$ ビット量子回路を $I\zeta_{2}$ と呼ぶ. 最後に $2t-1$ 個の $G_{3}$ を順に接 続する. このとき $j$ 番目 $(1 \leq j\leq 2t-1)$ _の $G_{3}$ はマス目

$j-t-1,$

$j-t,$

$j-t+1,$

$L,$$N,$$R$ _{に接続する}. _こ の $2t-1$ 個の $G_{3}$ から構成される $(2\mathrm{t}+4)l$ ビット量子回路を $K_{3}$ と呼ぶ. そして$K_{\mathcal{G}}=t(K_{1}+K_{2}+\mathrm{A}_{3}^{\nearrow})$ とする. $IC_{1}+I\iota_{2}^{\nearrow}+IC_{3}$ は図

2

に表されるような量子回路であり

,

これが$M$ の1 _{ステップに対応する操作} を実行することは $G_{1)}G_{2},$$G_{3}$ の定義から確認することができる.

$2$

:

$\mathcal{G}$ を示収と9\copyright

厘才凹始 $\Lambda_{1}+\Lambda_{2}+\mathrm{A}_{3}$

実際

,

$t’$ _{ステップ後$(0\leq t’<t)$ における $M$の状態が}$|p,$$T,$$i$

)

_{$;T(i)=\sigma$}

のとき,$t’+1$個目の$K_{1}+K_{2}+K_{3}$

の入力状態は

,

計算基底状態

$|\emptyset T(-t)0;\cdots$

;

$\emptyset T(i-1)0;pT(i)\mathrm{r};\emptyset T(i+1)0;\cdots$

;

$\emptyset T(t)\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O}\rangle$

であり, $G_{1}$ の定義からこの計算基底状態が $G_{K_{1}}$ によって

$|\emptyset T(-t)0;\cdots$

;

$\emptyset T(i-1)0;\emptyset B2;\emptyset T(i+1)0$

;

. .

.

;

$\emptyset T(t)\mathrm{O};\emptyset B\mathrm{O};pT(i)1;\emptyset B\mathrm{O})$

に決定的に変換される. $G_{2}$ の定義からこの状態は $G_{K_{2}}$ によって,

$|\emptyset T(-t)0;\cdots$

;

$\emptyset T(i-1)0;\emptyset B2;\emptyset T(i+1)0;\cdots$

;

$\emptyset T(t)0\rangle\otimes|v_{p,\sigma}\rangle$

に変換される. つまり $I1’2$ _はマス目 $L,$ $N,$ $R$ _上で $M$ _の“_振幅 $\delta(p, \sigma, q, \tau, d)$ でヘッドが指すマス目の記

号 $\sigma$ を\tau に書換え

,

内部状況を _$P$ から $q$ にして, ヘッドを $d$ 方向に移動する” に対応する操作を実行する ことになる. 最後に $G_{3}$ の定義から $G_{K_{2}}$ 通過後の状態は $G_{K_{3}}$ によって,

$\sum_{q,\tau}\delta(p, \sigma, q, \tau, -1)|\emptyset T(-t)0;\cdots$

;

$qT(i-1)1;\emptyset\tau 0;\emptyset T(i+1)0;\cdots$

;

$\emptyset T(t)\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O}\rangle$

$+ \sum_{q,\tau}\delta(p, \sigma, q, \tau, \mathrm{O})|\emptyset T(-t)0;\cdots$

;

$\emptyset T(i-1)0;q\tau 1;\emptyset T(i+1)0;\cdots$

;

$\emptyset T(t)\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O})$

$+ \sum_{q,\tau}\delta(p, \sigma, q, \tau, 1)|\emptyset T(-t)0;\cdots$

;

$\emptyset T(i-1)0,$$\emptyset\tau 0;qT(i+1)1;\cdots$

;

$\emptyset T(t)\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O};\emptyset B\mathrm{O}\rangle$

に変換される. 以上により $I\zeta_{1}+K_{2}+\mathrm{A}_{3}’$ によって, ($‘ t’$ ステップ後にマス目 $i$

にヘッドを持ち

,

マス目 $i$

の記号 $\sigma$

,

内部状況_$P$ の $M$ の状況は振幅 $\delta(p, \sigma, q, \tau, d)$ でマス目 $i+$旧こヘッドを持ち, マス目 $i$ の記号 $\tau$

,

内部状況 $q$ の状況に変換される” という操作に対応する変換が$K_{\mathcal{G}}$ のマス目 $i,$ $i+d$ 上でなされたこと

になる.

$G_{1},$ $G_{2},$ $G_{3}$ はいずれも定理71 より $\mathcal{G}_{u}$ に属する ($t$ に依存しない) 定数個の量子ゲートに分解可能 なので $\mathrm{u}$

-

サイズが定数で

,

定まる量子ゲートが各々 $G_{1},$ $G_{2},$ $G_{3}$ である $\mathcal{G}_{u}$ を基底とする $4l$ ビット量子回

路 $I5\mathrm{i}_{u,1},3l$ ビット量子回路 $I\iota_{u,2}^{\nearrow}$

,

そして $6l$ ビット量子回路 $I1_{u,3}’$ が存在する. さらに各々 u-サイズが

$O(2t+1))O(1),$ $O(2t-1)$ で, 定まる量子ゲートが $G_{K_{1}},$ $G_{K_{2}},$ $G_{K_{3}}$ であるような

(2t+4)

」ビット量子回

路 $I\mathrm{f}_{a},$$I\backslash _{b)}^{\nearrow}$K。が存在する. $K=t$

(

$K$

。$+\mathrm{A}_{b}^{r}+K_{c}$

)

とすると,

$I\dot{\iota}’$ は $M$ を $(k, t)$-模倣する $\mathrm{u}$-サイズ $O(t^{2})$

8.

一様量子回路族と

QTM

の計算量に関する同等性

量子回路に対する–様性の概念は

Shor

[16],

Ekert

と

Jozsa [9] などによって触れられてはいるが,

基本

ゲートなど–様性の厳密な数学的定義を与えるのに必要な概念が述べられていない.

そこで我々は万能集

合として $\mathcal{G}n$ 及び仇 を考え, それらをもとに–様性の概念を導入する.

量子ゲートの有限集合が$\mathcal{G}=\{G_{1}, \ldots, G_{l}\}$ ($G_{i}$ は $n_{i}$ ビット量子ゲート) と番号付が行われているもの

と仮定する. このとき $\mathcal{G}$ を基底とする量子回路 $I\acute{\mathrm{t}}$

のコードは量子回路の定義から自然に定義できて

,

$I\mathrm{l}’=$

$(G_{i}, , P_{1}),$

$\ldots,$$(G_{i_{m}}, P_{m})$ のとき, その標準コード $c(I\mathrm{f})$ と$l\mathrm{h}\backslash$

’ 自然数の有限列

$\langle(i_{1}, P_{1}(1), \ldots, P_{1}(n_{i_{1}})\rangle,$ $\ldots$

,

$(i_{m}, P_{m}(1),$_$\ldots,$$P_{m}(n_{i_{m}})\rangle)$ であると定義する. $\mathcal{G}_{\mathcal{R}}$ の場合 _{$R_{1,R},$}$R_{2,\mathcal{R}},$$R_{3,\mathcal{R}},$$M_{2}(N)$ の順に 1,

2, 3,

4 と番

号付することで

G

えを基底とする量子回路 $I\mathrm{t}’$ に対する標準コード $c(I\acute{\mathrm{t}})$ が定義できる. 方

,

任意の量子回路

Il’

で定まる量子ゲート $G_{K}$ は, 定理71より $\mathcal{G}_{u}$ によって分解可能なので

,

以下 では$\mathcal{G}_{u}$(またはその有限部分集合) を基底とする量子回路のみを考えることにする. $\mathcal{G}_{u}$ を基底とするサイ ズ$s$ の $n$ ビット量子回路$K=(G_{1}, P_{1}),$ $\ldots,$$(G_{s}, P_{s})$ の $\epsilon$-近似とは, $IC$ を構成する各1 ビット量子ゲート

$R_{j,\theta}(j=1,2,3)$ _{に対して,} $||R_{j,\theta}-R_{j,\mathcal{R}}^{m}||\leq\epsilon/s$ となるような最小の$m=m_{j,\theta}$ を取り, $R_{j,\theta}$ を _$m$ 個の 1

ビット量子ゲート $R_{j,\mathcal{R}}$ の積によって置き換えることで得られる, $\mathcal{G}_{\mathcal{R}}$

を基底とする量子回路のことであり,

以下これを $I1_{\epsilon}’$ と表すことにする. 但し, 量子回路 $K=(G_{1}, P_{1}),$

$\ldots,$$(G_{i}, P_{i}),$$\ldots,$$(G_{l)}P_{l})$ 内の1 ビット

量子ゲート $G_{i}$ を _$m$ 個の 1 ビット量子ゲート $G_{i}’$ の積によって置き換えることで得られる量子回路とは,

$(G_{1}, P_{1}),$

$\ldots,$$\underline{(G_{i}’,P_{i}),\ldots,(G_{i)}’P_{i})},$$\ldots,$$(G_{l}, P_{l})$ のことである. このとき $K$ の精度

$\epsilon$ での標準コードを$I\dot{\iota}_{\epsilon}’$

$m$

の標準コード $c(I\acute{\mathrm{t}}_{\epsilon})$ であると定義する. そしてこれを $I\acute{\mathrm{t}}_{\epsilon}-$ と表すことにする.

$\mathcal{G}=\{G_{1}, \ldots, G_{l}\}$ を基底とする $k$ 入力 _$m$ 出力の $n$ ビット量子回路$\mathrm{K}=$

(

$I\zeta,$$\Lambda_{1}$,

A2,

$S$

)

の標準コード

$c(\mathrm{K})\text{は}\Lambda^{(n)}\backslash \Lambda_{1}=\{i_{1}, \ldots, i_{n-k}\}$

,

A2

$=\{j_{1}, \ldots, j_{m}\},$ $S=\{b_{j}|j\in\Lambda^{(n)}\backslash \Lambda_{1}\}$ とすると次のような有限

列で定義される.

$c(\mathrm{K})=\langle(i_{1}, b_{i_{1}}\rangle,$

$\ldots,$$\langle i_{n-k}, b_{i_{\mathfrak{n}-k}}\rangle,$$c(K),j_{1},$$\ldots,j_{m}\rangle$

量子回路族とは, $n$ 入力 ($f(n)$ 出力の $g(n)$ ビット) 量子回路 $\mathrm{K}_{n}$ からなる無限列 $\mathcal{K}=\{\mathrm{K}_{n}\}_{n\geq}\iota$ であ

り, 全ての $\mathrm{K}_{n}\text{が}.\mathcal{G}$ を基底としているとき, $\mathcal{K}$ は$\mathcal{G}$.を基底とする量子回路族という. さらに $\mathrm{K}_{n}$ の$\mathcal{G}$ に対

するサイズが関数 $s$ によって$s(n)$ で押さえられるとき, $\mathcal{K}$ を $\mathcal{G}$ を基底とするサイズ関数

$s$ の量子回路族

といい, 特に $s$ が多項式のとき $\mathcal{G}$ を基底とする多項式サイズ量子回路族という. また $\mathcal{G}=\mathcal{G}_{u}$ のとき $\mathcal{K}$ を

u-

多項式サイズ量子回路族, $\mathcal{G}=\mathcal{G}n$ のときは単に多項式サイズ量子回路族という. $\mathcal{K}=\{\mathrm{K}_{n}\}_{n\geq 1}$ を $\mathcal{G}_{u}$

を基底とするサイズ関数 $s$ の量子回路族とする. このとき $\mathrm{K}_{n}=$

(

$\mathrm{A}_{n}’,$$\Lambda_{1}$

, A2,

$S$

)

の精度 $\epsilon$ での標準コード

は $n$ 入力量子回路$\mathrm{K}_{n,\epsilon}=$

(

$(IC_{n})_{\epsilon},$$\Lambda_{1}$

, A2,

$S$

)

の標準コード $c(\mathrm{K}_{n,\epsilon})$ と定義して

,

これを $\overline{\mathrm{K}}_{n,\epsilon}$ と表すこと

にする. $\mathrm{K}_{n,\epsilon}$ は$\mathrm{K}$ の $\epsilon$-近似と呼ぶ. 以下では $(K_{n})_{\epsilon}$ を $I1_{n,\epsilon}’$ と書くことにする. 関数 $c:(1^{n}, \epsilon)arrow\overline{\mathrm{K}}_{n,\epsilon}$ を

Poly

$(s(n)\log 1/\epsilon)$ 時間で計算可能な

CTM

が存在するとき$\mathcal{K}$ は–様であるという.

次に $\mathcal{G}_{u}$ の有限部分集合を基底とする量子回路に対する–様性の概念を与えることにする. 有限集合 $B\subseteq \mathcal{G}_{u}$ は $\{R_{1}, \cdots, R_{k}, R_{k+1}\},$ $(R_{k+1}=M_{2}(N))$ と番号付がされているものとする. $B$ _{を基底とするサ}

イズ関数 $s$ の量子回路族 $\mathcal{K}=\{\mathrm{K}_{n}\}_{n\geq 1}$ に対して, 関数 $c$

:

$1\mathrm{n}arrow c(\mathrm{K}_{n})$ を

Poly

$(s(n))$ 時間で計算可能な

CTM

が存在するとき$\mathcal{K}$ は入力長一様量子回路族という.

定義からサイズ関数 $s$ の–様量子回路族$\mathcal{K}$ とは,任意の精度\epsilon 及び$\mathrm{K}_{n}\in \mathcal{K}$ に対して $||G_{K_{n}}-G_{K_{\mathfrak{n},\epsilon}}||\leq\epsilon$

となり, $K_{n}$ の精度$\epsilon$ での標準コードを

Poly

$(s(n)\log 1/\epsilon)$時間で計算できることを意味している. このとき さらに $\{\mathrm{K}_{n,\epsilon}\}_{n\geq 1}$ が入力長–様量子回路族となることがわかる. $\{\mathrm{K}_{n,\epsilon}\}_{n\geq 1}$ は $\mathcal{K}$ の \epsilon -近似であるといっ て, $\mathcal{K}_{\epsilon}$ と表すことにする. 以後, 特に混同しない限り $R_{n}’$ と $\mathrm{K}_{n}$ は同–視して扱うことにする.

離散フ一リエ変換を行う $\mathrm{u}$-多項式サイズ量子回路族$\mathcal{K}=\{I\acute{\mathrm{t}}_{n}\}_{n\geq 1}$ は図3及び図4のように構成される

(図3は$I\zeta_{4}$ を表している)

.

但し_{$A=R_{\pi/4}$} であり, $B_{k}$ は$\mathcal{G}_{u}$ を基底とする, 図 4 のような量子回路$I\acute{\mathrm{t}}_{B}$ で