数理解析研究所講究録980 巻 1997 年 66-75

呈66

磁電子
$\mathrm{Q}n$a$\overline{\ulcorner-\Leftrightarrow\neg}$$\mathrm{D}\mathrm{e}\mathrm{p}$a

矢口$\mathrm{E}\mathrm{l}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{r}\mathrm{o}\mathrm{m}$$\mathrm{n}\mathrm{t}\iota\iota \mathrm{m}$$\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{P}^{\mathrm{u}}\mathrm{t}$a$\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{x}\frac{\backslash }{rightarrow}\neq\ovalbox{\tt\small REJECT}\frac{\backslash }{rightarrow}$$\mathrm{r}\mathrm{t}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}$$\mathrm{o}\mathrm{f}$$\mathrm{H}\mathrm{i}\mathrm{d}\mathrm{e}$Ia$\mathrm{k}\mathrm{i}$a1a—-r5’ 清幸匿$\ovalbox{\tt\small REJECT}$$\mathrm{M}$

算

a

素子

$\mathrm{g}\mathrm{n}\mathrm{e}\mathrm{t}\mathrm{i}\mathrm{c}$$\mathrm{D}\mathrm{e}\vee \mathrm{i}\mathrm{c}\mathrm{e}\mathrm{s}$$\mathrm{n}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}$$T\Xi$$T_{\triangle}^{J^{-}\vee}$計a$T_{--}^{\backslash }\backslash$ト—\mp ‘-\tau 斗$\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{S}\mathrm{c}\mathrm{i}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{e}$$\mathrm{B}\mathrm{H}$$\mathrm{t}\mathrm{s}\mathrm{u}\mathrm{e}\mathrm{d}$a量子計算機は、 その原理の実証結果の報告、 及び、 アルゴリズムの数学的な証
明が、 近年、 見られるようになってきた。

そのうち特に、 計算を実行する素子につき、 その歴史的経過、 主要な考察と提案、 理論、 最近の研究結果等を論考する。

1. 緒

言

量子論を掘り下げて行くと、 情報理論と密接に関連する領域に行き当たる。
観測の問題等がそれである。 他方、 情報理論においても、 信号の量子化や、 情報伝達の確率等、 量子力学に相通ずる要素を有している。 さらに、 計算速度の限界や計算に伴うエネルギー消費の極限を追究するとき、 量子論の利用可能性に期待が寄せられる。

現行のコンピュータの限界、 中でも計算速度に関する限界を超越するために、量子力学の導入が考えられた。 その中には、 計算を物理的な量子現象によって行67う構想と、 計算過程の記述への量子力学の数学的な援用との、 両面が含まれる。
前論文 1) に述べた R. P. Feynman

E. Goto による提案と実証 3)による提案 2) およびは前者に属し、 P. Benioff の理論 4) や D. Deutch の提案

5)は現在までのところ後者の範疇に入ると考えられる。 いずれも、 量子コンピュータとして研究されてきた 6)

ところが、 最近の一、 二年間に、 状態の重ね合わせ、 波動関数の空間的な並列性、 エンタングルメント (Entanglement) 現象等、 量子力学に特有の性質を、 実際の演算に利用するためのアルゴリズム 7)$\text{、}$及び、 それに関する計算量論的な考察が相次いで発表された 8) 。その結果、 特に、 先に述べた D. Deutch の提案がしばしば取り上げられ、 かつ、 さらにその発展形態が考察されるようになってきている。

整数の素因数分解を、 その整数の対数の多項式$(\sim\{\log \mathrm{N}\}^{3} )$で表される時間以内に計算することができる、 量子計算のアルゴリズムが示された 7) 。このことは、 これを実行する量子計算機が実現すれば、 暗号や情報セキュリティ一の分野には画期的、 かつ、 衝撃的な結果を生ずる可能性を孕んでいる。

本稿においては、 最近頻繁に議論される量子計算機の理論的な基礎を、 簡潔に述べる。

2. 量子計算機の歴史的な背景
量子計算機の研究は、 昨年来、 活発化の兆を見せている。 その背景となる過去の代表的な研究を、 原理に基づいて分類すると、 表 1 のようになる。 ただし、 近年この分野の研究発表は激増しているので、 この表にすべての研究を尽くすことは困難である。 読者各位に、 情報の追加を期待する次第である。

$\circ$68
1$\ovalbox{\tt\small REJECT}$$\neq=_{-}-|\supset$$\overline{\cong}-rightarrow \mathrm{D}-\overline{=}+^{\wedge}\ovalbox{\tt\small REJECT} \mathrm{j}\mathrm{f}*_{A}x\Leftrightarrow\ovalbox{\tt\small REJECT} 7^{-}\mathrm{n}^{**}\mathrm{r}\mathrm{E}\mathrm{i}$$\vee^{\sim}$p“+幾と$\neq_{\mathrm{e}}-\Sigma \mathrm{g}_{>B\mathrm{H}\tau}-=\subset_{A}P$

テープヘッド素子 (内部状態)$:\mathfrak{k}\Phi$A. M. Turing, Proc. Lomdon Mathematical Soc. Ser. 2, 42 (1936) 230.
$\overline{\square \lrcorner}\supset \mathrm{E}\backslash \neq=_{-}-$

リン$p^{\sim}\mathrm{j}\mathrm{F}\sim \mathrm{g}_{\lrcorner \mathrm{i}}z\mathrm{t}j\dagger \mathrm{B}$

可逆論理素子機械化学酵素

C. H. Bennett, IBM J. Res. Develop Nov

Int. J. Theor$=\Rightarrow\approx^{\xi}\mathrm{P}^{\backslash }\neq\sim\#_{\overline{\mathrm{D}}\mathrm{R}}^{-}\sqrt-arrow$+幾 tafPhys(1973) 525,21 (1982) 905.

双安定単安定素子

J. von Neumann, US Patent no. 2815488, Dec. 3, 1957.

E. Goto, IRE Trans. Electronic Computers, EC-9 (1960) 25.
R. W. Keyes, R. Landauer, IBM J. Res. Develop. March (1970) 152.
内合 5\breve$\backslash \backslash \backslash$冫肖$\ovalbox{\tt\small REJECT}_{-}$

口」$\ovalbox{\tt\small REJECT}\sim\backslash$

言十$\ovalbox{\tt\small REJECT}\sim$+幾

フレドキン. ゲート (弾性散乱、 光、 等)

E. Fredkin and T. Toffoli, Int. J. Theor. Phys. 21 (1982) 219.
T. Toffoli, Math Systems Theory 14 (1981) 13.
$\overline{\Leftrightarrow}-\neq$

口」$\ovalbox{\tt\small REJECT}\backslash \backslash$

言十 ^--+幾

ハミルトニアン素子

P. Benioff, J. Statistical Phys$\overline{\Leftrightarrow}-\neq\overline{\mathrm{D}\rfloor}\grave{\mathrm{J}}\grave{\Xi}\Xi$

弓単$\grave{\mathrm{x}}\underline{\Xi}$

言十$\ovalbox{\tt\small REJECT}^{\wedge}$+幾22 (1980) 563.

量子可逆弾道素子 (スピン、 双極子、 等)

R. P. Feynman, Optics News, 11 (1985) 11.
$\sqrt zz_{\backslash }\Leftrightarrow_{\overline{\Leftrightarrow}}\approx-\neq$

言十$\ovalbox{\tt\small REJECT}\sim$+幾磁束量子パラメトロン (本論文の補遺参照)

E. Goto, Proc. 3rd Int. Symp. Foundations of Quantum Mech. Tokyo (1989) 412.
有旨\Leftrightarrow ---- \neq 言十\tilde+幾連続位相状態素子 (分極方位、 偏光、 等)

D. Deutsch, Proc . R. Soc
糸屯 \acute J’’1」\Leftrightarrow ----\neq ] 大\check --R--\sim \geqq ‘言十$\neq\backslash$London A 400 (1985) 97.

エンタングル状態、 並列性$\ovalbox{\tt\small REJECT}_{\mathrm{j}}^{\sim}\mathrm{F}\mathrm{g}X^{\angle}\mathrm{i}$P. Shor, Proc. 35th Ann. Symp. Found. Computer Sci. , IEEE (1994) 124.
D. P.

$\mathrm{D}\mathrm{i}\mathrm{V}\mathrm{i}\mathrm{n}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{z}\mathrm{o}$, Phys

Rev A51 (1995) 1015.

C. H. Bennett, Phys Today, Oct
S. Lloyd, SciAmerican, Oct

I. L. Chuang &Y. Yamamoto, Phys

(1995)

24.

(1995) 44.

Rev A52 (1995) 3489.

69
3. 連続位相状態$3\cross 3$

ビット量子演算素子

先ず D. Deutch の提案による$5$)$\backslash$

万能量子演算素子につき、 その要点を述べる。

基準状態の重ね合わせによって新しくできる、 量子力学的な純粋状態を取り入れるために、 次のような$=$$\mathrm{S}\mathrm{N}\alpha$$\mathrm{S}$

行列を持ったゲート{$\mathrm{N}^{O}$\dag erを導入する。

$\frac{1}{2}$

但し、 二進法に対応した 1 ビットの情報を、 状態ベクトル (10) とよって表現し、 このベクトルに式 (1)パラメータ$\alpha$(1)$\exp(\mathrm{i}\pi\alpha)$の$\mathrm{S}$(01) に行列を作用させるものとする。 位相は無理数まで含む実数であり、 連続的な変化が可能である。

$\alpha$が整数の場合には、 偶数なら式 (1) は単純接続素子 (単位行列) を表し、 奇数ならNOT ゲート (否定論理素子) を表すことは、 式より明白である。 式 $(’1)$ によって表現される素子を、 NOT の$\alpha$式 (1) の素子を利用し、 2$\mathrm{S}\mathrm{Q}22^{-}-$乗または$\cross 2$$\alpha$根と呼ぶ場合がある。

量子ゲート$\mathrm{S}$Q22 を次式によって定義する。

$1|\mathrm{e}-\mathrm{i}\pi\alpha/2\mathrm{S}\mathrm{N}\alpha$(2)—これを、 次式 (4) のように $8\cross 8$ 行列に拡張すれば、 下図に示すような 3 端子入力. 3 端子出力の量子論理ゲートを表現できる。

$\in \mathrm{L}$a’’$\mathrm{b}$$\mathrm{b}$$\subset$$\mathrm{O}$701$\mathrm{S}\mathrm{Q}=$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

1

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

1

$0$

$0$

$0$

$0$

$0$

$0$

屋

$0$

$0$

1

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

1

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

1

$0$

$0$

$00$

$00$

$00$

$00$

$00$

(4)

$00\llcorner|\overline{\underline{\mathrm{s}}}^{--}\ulcorner\neg|--\lrcorner \mathrm{Q}22$

但し、 3 入力端子 a,8$\cross 8$$\mathrm{b}$,$\mathrm{c}$の状態ベクトルは、 次のように簡略化して表現し、行列に対応させる。

(000)$=|0\rangle$,$(001)=|1\rangle$,$(010)=|2\rangle$,$(011)=|3\rangle$(100)$=|4\rangle$,(101) $=|5\rangle$ ,$(110)=|6\rangle$,$(111)=|7\rangle$と出力状態との間の真理値表は次のように表すこと

即ち、 入力状態$|$$\mathrm{i}\rangle$$|0\rangle$,(5)ができる。

$\rangle$$\rangle$

ここで、ic は $\mathrm{i}\cos(\pi\alpha/2)$ ,$\mathrm{s}$は$\sin$($\pi\alpha/2$!

をそれぞれ表す。

更に、 この量子ゲートは、 次式によっても表現される。

$\mathrm{s}_{\mathrm{o}_{\mathrm{a}8}^{\mathrm{a}\mathrm{b}\mathrm{c}}},\mathrm{c}’=\delta_{\mathrm{a}}^{\mathrm{a}},\delta^{\mathrm{b}}\mathrm{b}’[(1-\mathrm{a}\mathfrak{b})\delta_{\mathrm{c}}^{\mathrm{C}},$

1’ a$+$$\mathfrak{b}\mathrm{e}-\mathrm{i}\pi\alpha/2\mathrm{S}_{\mathrm{I}\mathrm{c}}^{\alpha_{\mathrm{T}/}}\searrow)\mathrm{C}$

(6)

71

量子ゲート

$\mathrm{S}_{\mathrm{Q}}$を組み合わせることによって、 通例の計算に必要な演算すべてを実行することができる。 即ち、 量子ゲート$\mathrm{S}\mathrm{Q}$は万能ゲートである。 なお、 この

9)量子ゲートは、 古典的な Toffoli ゲートを量子化したゲートである

パラメータ$\alpha$を通して、 異なる基準状態$|6\rangle$と$|7\rangle$

即ち、$\circ$との、 任意の割合の重ね合わせを表現することができる。 量子光学および磁気共鳴等の実験における、
スや $\pi/2$ パルスに対応した演算が、 このパラメータ量子ゲート$\mathrm{S}_{\mathrm{Q}}$の 4n 乗$\mathrm{s}_{\mathrm{Q}}^{4\mathrm{n}}$や、 4$\mathrm{n}+1$乗$\alpha$パルによって可能になる。

$\mathrm{s}_{\mathrm{Q}}^{4\mathrm{n}1}\star$等も容易に求めることができる。 類似の方法により、 次の論理ゲートが組み立てられる$\mathrm{U}\lambda$$\pi$5)$\circ$——$[$—ここで、 要素

$1|2\lambda/\pi\alpha \mathrm{S}\mathrm{Q}-2\lambda/\pi\alpha$$|\mathrm{m}\rangle$と$|\mathrm{n}\rangle$$\mathrm{P}\ulcorner \mathrm{a}6(\mathrm{U}\lambda \mathrm{P}57)‘\angle)$との入替えを、$\mathrm{p}_{\mathrm{m}\mathrm{n}}$(7)によって表現すれば、$(\mathrm{U}-\lambda \mathrm{P}57)2$$\mathrm{P}56$

—-

$0$
$0$
$0$

I

$+$

$00$

$+$

$00$

$0(\uparrow_{\vee}.3)$$(’8)$$\lambda^{2}$$-\lambda^{2}0$となるので、$\mathrm{V}\lambda$——$=1\mathrm{i}\mathrm{m}$$\mathrm{n}arrow\infty$$\{\mathrm{P}_{56}(\mathrm{U}\lambda\ulcorner/\mathrm{n}\mathrm{P}57)2 (\mathrm{U}-\sqrt{\gamma_{/\mathrm{n}}}\mathrm{P}57)2\mathrm{P}_{56}\}^{7}\iota$

(9)

72
および、

1

1

1$\mathrm{W}\lambda\overline{=}$1

11$\mathrm{e}^{-\mathrm{i}1}$$\dot{\mathrm{e}}^{\lambda}$$=1\mathrm{i}\mathrm{m}$$\{\mathrm{U}_{\sqrt{\wedge/2\mathrm{n}}}\mathrm{V}_{\sqrt{7\backslash _{f2\mathrm{n}}}}\mathrm{U}-\sqrt{2\Pi}^{\mathrm{I}_{\mathit{1}}^{\gamma}}-\sqrt{\lambda_{/2\Pi}}\}\mathrm{n}$(10)$\mathrm{n}arrow\infty$が得られる。 また、 特定の要素だけを. 倍する素子は下記のようになる。

$\dot{\mathrm{e}}^{\lambda}$

$- 1$

1

1$\mathrm{X}\lambda---$111(1 1)

1$\dot{\mathit{4}}^{\lambda}$

これらの素子を組み合わせ、 回路ないしはネットワークを組み立てることにより、 万能量子計算機を作ることができる $10$ )に定義した状態$(110)=|6\rangle$と。

$(111)=|7\rangle$

量子計算においては、 式 (5)等の、 重ね合わせ状態を利用する。 量子力学的な純粋状態のまま、 重ね合わせを構成する多数の状態に対して、同時かつ並列的に演算を実行する。 これにより、 従来の逐次処理式の計算機では、計算量論の観点から、 実行不可能と見傲されていた計算が、 可能になると期待されている。

なお、 計算の初期状態を準備する場合等には、 人為的に量子状態の設定を行うことが必要である。 そのためには、 異なる粒子の間等に、 量子力学的な相関ないしはエンタングルメントを生じさせることが、 有効であろうと考えられている。

734. 量子演算素子の単純化および実現方法
前説に述べた 3$\cross 3$ビットの量子演算素子の考察を基礎として、 より単純な万能演算素子が考案され、 最近の数年間に、 2$\cross 2$ビット素子を中心とする量子演算回路ないしは量子演算ネットワークが発表されるようになってきた$11$ )$\circ$

いずれにしても、 状態の重ね合わせに基礎をおき、 並列処理を特徴とする量子演算には、 コヒーレントな状態が十分な時間継続することが必要である。 即ち、所期の計算を完了するまでの所要時間より、 コヒーレントな状態の寿命のほうが長いことが要求される。 前者は、 演算機能の単位となるスイッチング時間に比例して短くなると考えられる。 このような観点から、 次のような物理現象が、 量子演算素子の実現にとって有効な原理として研究されている

11)$\circ$(1) イオントラップ(2) 固体内、 双極子 $-$ 双極子相互作用$8$$1213$ )(3) 光学的な微小共振器 (Cavity Quantum Electro-Dynamics)(4) メスバウワー効果(5) 核スピン$(\mathrm{N}\mathrm{M}\mathrm{R})$(6) メソスコピック構造量子構造等における電子(7) 電子スピン$(\mathrm{E}\mathrm{S}\mathrm{R})$(8) 半導体における電子

これらの研究は、 現在まさに、 日進月歩の勢いで遂行されている。

当該論文の著者も、 上記 (’ 2) の方法を中心とする研究成果の–部を、 すでに発表した

5. 結$8$$1213$ )$\circ$言

量子計算機は、 その原理の実証結果の報告、 及び、 アルゴリズムの数学的な証明が、 近年、 見られるようになってきた。

そのうち特に、 計算を実行する素子につき、 その歴史的経過、 主要な考察と提案、 理論、 最近の研究結果等を論考した。

74
現在、 特に欧米の研究者の間で考えられている量子計算機は、 多数の基準状態の重ね合わせ状態、 および、 エンタングルメント状態を利用することによって、巨大な量の同種類の計算を、 同時かつ並列的に実行させる装置である。 そこには、どの様な構造と形態の量子計算機を実現させるかという工学的な問題は言うに及ばす、 純粋状態、 観測の問題、$\mathrm{E}\mathrm{P}\mathrm{R}$パラドックス等、 量子力学の本質に関する、興味深い基本的な問題が残されている。

6. 参考文献(1) 松枝秀明「量子光計算処理」京都大学数理解析研究所講究録(量子情報理論とその応用、 Sep. 2-4,

885 号

1992 )pp. 29-45 (1994).

(2) R. P. Feynman, \dagger ’Quantum Mechanical Computers\dagger \daggerOptics News 11,

pp. 11-20 (1985).
(3) 松枝秀明、 後藤英–、 K. F. Loe 「エントロピ–生成・移送と情報の消去.

損失」 (「量子電磁計算素子」 補遺) 本講究録
(4) P. Benioff, \dagger \dagger The Computer as a Physical System: A MicroscopicQuantum Mechanical Hamiltonian Modelby Turing Machines ,$\uparrow’$of Computers as Represented

J. Statistical Phys. 22, pp. 563-591 (1980).

(5) D. Deutch, \dagger ’Ouantum computational”$\mathrm{n}\mathrm{e}\mathrm{t}\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{k}_{\mathrm{S}}$Proc R. Soc. Lond.

A425, pp. 73-90 C1989).
(6) 松枝秀明、 井桁和浩、 須鎗弘樹「量子コンピュータにおける可逆と非可逆」

数理科学

361, pp. 17-23, July (1993).

(7) P. W. Shor, ”Algorithms for Quantum Computation: Discrete Logarithms

and Factoring”, Proc. 35th Ann. Symp. Found. Computer Sci. , ed.
S. Goldwasser, IEEE Computer Soc. Press, Los Alamitos,, pp. 124$\mathrm{C}\mathrm{A}$

134 (1994).
(8) H. Matsueda,”$\mathrm{Q}\mathrm{u}\mathrm{a}\mathrm{n}\mathrm{t}\mathrm{u}\mathrm{m}$Implementations\dagger f

Computer in Theory and Optoelectronic

Proc. 1st Int. Workshop on Quantum MechanicalComputer (QMC’95), Osaka, Dec. 19-20 (1995), Abstract p.

$\mathrm{L}14$.

75(9) T. Toffoli, \dagger ’Bicontinuous Extensions of Invertible Combinatorial

Math. Systems Theory 14, pp. 13-23 (1981).

Functions\dagger f(10) D. Deutch, \dagger ’Quantum theory, the Church-Turing principle and theuniversal quantum computer\dagger t

Proc R. Soc. Lond. A 400, pp. 97-117(1985).
(1 1) D. P.

”Two-bit gates are universal for quantum, Phys. Rev. A51, pp. 1015-1022 (1995).

$\mathrm{D}\mathrm{i}\mathrm{V}\mathrm{i}\mathrm{n}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{z}\mathrm{o}$,$\mathrm{C}0\mathrm{m}\mathrm{P}^{\mathrm{u}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{i}_{0}\mathrm{n}^{\mathrm{f}}}’$(12) H. Matsueda and S. Takeno, ”Spectral Entrainment due to Second

Harmonic Collective Polarizations in Solids\dagger ’, and$,,\mathrm{S}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{l}$Entrainment in Second Harmonic Coherent Light Generatedby Semiconductor Laser$\mathrm{D}\mathrm{i}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{S}’|$

Proc. 7th Rochester Conf. on

Coherence and Quantum Optics (CQ07) , Rochester, June 7-10 (1995)
paper.
$\mathrm{I}\mathrm{Y}4\mathrm{B}-67,69$(13) H. Matsueda and S. Takeno, \dagger ’Spectral Features due to Dipole-Dipole

Interactions in Harmonic Generations”

Proc. Int. Symp. on

Nonlinear Theory and its Applications (NOLTA’paper 3.
Dec 10-14 1995) Session$\langle$(14)$95_{\mathit{1}}^{\backslash }$, Las Vegas,$7\mathrm{E}$$\mathrm{L}^{\backslash },\int_{-}\llcorner \mathit{0})i7\uparrow l_{\check{}}\text{、}\pm_{\mathfrak{o},<\overline{\mathfrak{o}}}^{\text{、}\prime}\equiv_{J}-r=B\text{文}\Re \mathit{0})\underline{\text{表_{}1}}\iota_{\vec{}}\not\in)\prime \text{考}/\approx \text{文}\vee\ovalbox{\tt\small REJECT}_{i}\mathfrak{y}\grave{\grave{1}}\mathrm{g}\ovalbox{\tt\small REJECT}\dagger\dot{\text{て}}\backslash x\mathrm{z}_{)}\circ$