第三回、量子コンピュータ (II)


再び前口上

今回から量子コンピュータのメインパートに入ります。アップロードが大幅に遅れてしまいましたこと、誠に申し訳ありませんでした。

本題に入る前に、、、量子コンピュータについては、昔からいろいろと「そんなものできるわけない。たわけ!」といった意見もあります。しかし僕はまだまだわからないと思います。今使っているコンピュータの基礎となっている半導体技術は、50年ほど前の発見です。その当時、まさか現在のようにコンピュータが使われているなんて想像できたでしょうか。まったく同じ理由で、50年後に世界がどうなっているかは、想像することすらできないと思います。

私がこうして講義を書いているのは、皆さんに量子コンピュータの概念について深く理解してもらい、今後の技術の進展に関心をもってもらいたいからです。今後科学の進歩は、必ずしも人々の幸福にするものとはいかないかもしれません。例えば、研究を進めることで、人間の尊厳が傷つけられたり、地球環境を悪化させるようなことが今後あるかもしれません。しかし、単に現在の科学のあり方に問題があるからといって、単純に「科学不信」をとなえるのは間違っていると思います。今世紀に生じるだろうさまざまな問題に立ち向かうには、市民一人一人が、科学技術についての基礎的な知識を身に付けたうえで、問題解決にあたらなければいけないと思うのです。

前置きはこれぐらいにして、本題に入りましょう。

1ビット制御

まず、量子コンピュータも、今普及している(古典的な)コンピュータと似た組み立てをもっています。その最小単位はビットといって、「0」か「1」を記憶する場所と、それを操作する外部装置、という二つの道具立てでできています。イメージとしては、以下のような図を想像してもらいたいです。

上に並んでいるのがメモリで、下にヘッダと呼ばれるこのメモリ上にかかれた数字をうまく制御する装置があります。この図では脚が一本しかないですが、これは一つのビットにしか操作しませんよ、ということを表しています。このような道具立てを、もうすこし厳密に数学に載せたのがTuringという人でその人にあやかってTuring機械などと呼ばれます。(本当は下の機械にも記憶装置があるなど、細かい説明がいりますが、この講義ではそんなに関係ないので省略します。)これが、コンピュータのやっていることを、もっとも単純化したモデルになっています。

さてここまでは、量子コンピュータと古典コンピュータで大差がないように見えます。共にメモリをもち、メモリの内容を操作する機械があることは共通しているのです。では、何がちがうのか?

それは一個のビットに関する操作(制御)の方法で明らかになります。つまり以下の状況を考えます。

この絵でかいてあるメモリの状態は1です。これをかっこよく|1>と書くことにします。メモリが0の状態の時は|0>です。

古典コンピュータでは、状態は|0>と|1>の二つしかありません。しかし量子コンピュータのいいところは、「0と1の重ね合わせの状態」もつくれることです。これは古典コンピュータでは決して実現できないことです。

前回の復習もかねてこのことをおさらいしてみましょう。

量子力学の法則
1.重ね合わせ状態: |ψ>=x|0> + y|1>をつくることができる。(x,yは|x|2+|y|2=1を満たす複素数)
2.観測: この|ψ>の状態で、|0>あるいは|1>を観測する確率はそれぞれ|x|2,|y|2である。

これは量子力学の基本的な法則(一種の公理)です。これらの性質をもつビットを量子ビットと呼ぶことにします。重ね合わせ状態という新しい状態を作り、それを操作できることが量子ビットの新しいところで、古典ビットでは真似することができません。

次に肝心の量子ビットの操作を考えてみましょう。単一ビットに対する操作をUとし、量子ビットが|0>のときにこの操作Uを作用したときの結果をU|0>と書くことにします。例えば、|0>に操作Uを行った結果がa|0> + c|1>であるとき、

U |0> = a |0> + c |1>

と表現されます。同様にして、|1>に作用した結果は

U |1> = b|0> + d |1>

などとかけます。(ここでa,b,c,dは一般に複素数であることに注意してください。)実はこの二つの変換がわかっていれば、変換Uの特性が決まってしまいます。というのは、すでに知られている量子力学の法則として、重ね合わせの原理がなりたつからです。重ね合わせの原理というのは、作用Uを任意の状態の重ね合わせ状態 x |0> + y |1>に対して、操作Uを施した結果が、

U (x|0> + y|1>) = x U|0> + y U|1>

となることです。言葉でいえば、「|0>と|1>の重ね合わせ状態の操作は、各状態の操作の結果U|0>とU|1>の重ねあわせである」のです。これを操作Uの線形性といいます。これと、先ほどのU|0>とU|1>の結果を用いることで、

U (x|0> + y|1>) = x U|0> + y U|1> = x (a|0> + c|1>) + y (b|0> + d|1>)
= (ax + by)|0> + (cx + dy)|1>

を得ることになります。操作後の状態をx'|0> + y'|1>と書くことにすれば、

x' = ax + by
y' = cx + dy

となります。この形をみると、係数(x,y)から(x',y')への変換は一次変換になっていることがわかり、

という風に行列とベクトルで表すことができます。

さてここで、変換行列をUと置くことにしましょう。つまり

です。ここでUは、次の性質

|x|2 + |y|2 = 1 ならば |x'|2 + |y'|2 = 1

を満たしていなければいけないことに注意しましょう。(|x|2や|y|2が確率を表しているので、変換後も全確率が保存しなければいけない。)これを満たすようにa, b, c, dに対する条件式を求めてみましょう。x', y'に上の変換式を代入することによって、

1=|x'|2 + |y'|2 = (ax + by)(a*x* + b*y*) + (cx + dy)(c*x* + d*y*)
= (|a|2+|c|2) |x|2 + (a b* + c d*) x y* + (a* b + c* d) x* y + (|b|2+|d|2) |y|2

ここで、これが任意のx, yについて成り立つためには、

|a|2 + |c|2 = 1, .... (1)
|b|2 + |d|2 = 1, .... (2)
a b* + c d* = 0, .... (3)

が成り立てばよいことが解ります。(最後の式の複素共役をとれば、a* b + c* d=0もいえる。)これらの条件は、行列に書き直すときれいにまとまります。Uの複素転置行列を

と定義すると、(1)から(3)の式は、すべて

によってまとめられます。(任意課題:この行列の積を具体的に計算して、(1)から(3)が導け。)これより、UはUの逆行列であることがわかります。

このような性質をもつ行列をユニタリー行列といいます。またユニタリー行列による一次変換をユニタリー変換と呼びます。そもそもなぜこのような性質がでてきたかを振り返ると、「全確率が保存する」というのが利いているのです。確率が保存する変換は、自動的にユニタリー変換となります。

この性質のおかげで操作Uの逆操作が常に存在することに注意してください。操作Uの逆操作を表す行列U-1はUによって作ることができるのです。つまり量子ビットに対する操作は可逆操作(元に戻せる操作)なのです。

まとめてみましょう。

3.量子ビットに対する操作
量子状態 x|0> + y|1> に対する操作によって状態が x' |0> + y'|1> になったとき、この操作Uは行列によって、
と関係づけられる。ここでUはユニタリー行列である。

ここで強調しておきたいことは、ここで述べた量子ビットへの操作と、先ほど述べた量子ビットの観測とは決定的に違うことです。量子ビットの操作は可逆ですが、一方観測は量子ビットの状態を変えてしまい、もはやもとの重ね合わせ状態を知ることができません。(x|0> + y|1>の状態で観測すると、|0>または|1>であることを|x|2. |y|2の確率で観測しますが、得られた|0>もしくは|1>という結果からもとの重ね合わせ状態 x|0> + y|1>を復元することはできません。)以後操作観測は、明確に区別することにします。ヘッダによる操作と観測の図も、ちゃんと区別して書くことにしましょう。下の図で(a), (b)はそれぞれ操作と観測を表すこと事と約束します。

(補足)ここで観測することなく操作することなんて、できるのか?という素朴な疑問がわくと思いますが、それは実験的に可能です。例えば、量子ビットに光をあてるとか、電位を変化させる、などの操作を行うことができます。その間、量子ビットの状態を測定してしまうような要素はすべて排除するのです。

量子コンピュータ、というのは、この操作と観測をうまく組み合わせることで、早い計算を可能にしるのですが、しかしどのように操作と観測を組み合わせるか、というのは、決して自明な問題ではありません。重ね合わせ状態を利用できることが最大の利点ですが、どこかで観測もしなくてはいけない。しかし観測すると、重ね合わせ状態が破壊されてしまう、というジレンマを抱えているのです。よって、うまいこと、最後の観測でほしい結果が得られるように、途中の操作を工夫する必要があるのです。

さてこのような法則に従う量子ビットはどのようにつくればいいのでしょうか。ここでは詳細に触れる余裕はありませんが、一つの候補として、微小超伝導体を用いる方法があります。この方法をつかうと、操作も観測も原理的に可能です。この方法のいいところは、微細加工技術をつかって、複雑な回路を組むことが可能であること、超伝導なので量子力学的な重ね合わせ状態を保持しやすいこと、などです。現在のところ、背景のノイズを除去することがうまくできずにいて、この点にブレークスルーが期待されている状況です。(私の研究課題でもあります。)

2ビット制御

量子コンピュータがコンピュータとして働くためには、ここまで説明してきた1量子ビットの制御だけではなく、2量子ビットへの制御が必要になります。

まず古典コンピュータにおける、2ビット制御をみてみることにしましょう。代表的なものは、ANDとORです。これは二つの入力から一つの出力を出す演算です。

(AND制御)

入力1 入力2 出力
1 1 1
1 0 0
0 1 0
0 0 0

(OR制御)

入力1 入力2 出力
1 1 1
1 0 1
0 1 1
0 0 0

これらの古典的な制御は、可逆でないことに注意してください。つまり、一度演算をおこなって、出力を得てしまうと、その出力だけから、もとの入力の信号を特定することができなくなります。量子コンピュータでは、すべての演算は可逆でなければいけない、ので、そのままの形でこれらの演算を行うことはできません。もう少し違った形の演算を考える必要があるのです。

まず、2ビット状態の記述法を考えてみることにしましょう。古典コンピュータでは、2ビットを使うと

|0>|0>, |0>|1>, |1>|0>, |1>|1>

の4状態が可能です。ここで、|a>|b>とは、第一ビットがaで、かつ、第二ビットがbであるような状態を表します。量子コンピュータにおいては、これらの重ね合わせ状態も可能です。つまり、

x|0>|0> + y|0>|1> + z|1>|0> + w|1>|1>

のような状態も可能となります。ここでx,y,z,wは複素数です。このような状態にあるとき、この二つのビットを同時に観測したとすると、

|0>|0>という状態を確率|x|2で、
|0>|1>という状態を観測|y|2で、
|1>|0>という状態を確率|z|2で、
|1>|1>という状態を確率|w|2で観測する

ということが量子力学の法則の主張です。(実験すると確かにそうになります。)全確率が1となるはずなので、

|x|2 + |y|2 + |z|2 + |w|2 = 1

が要請されます。

これらの2ビット状態は、それぞれのビットの重ね合わせ状態の拡張になっていなければいけません。まずは簡単な状況から考えましょう。第一ビットが a|0> + b|1> の重ね合わせ状態にあり、第二ビットは|0>の状態にあったとしましょう。このような状態を形式的に

(a|0> + b|1>) |0>

と書くことにします。しかし、これらは先ほど書いたような形式で書き直すと

a|0>|0> + b |1>|0>

となることがわかります。これは意味からいっても成り立ちますよね。第二ビットを観測すると100パーセント|0>を観測するので重ね合わせ状態に関係しないのです。つまり第一ビットが|0>と|1>の重ね合わせ状態であることが反映して、2ビット全体も|0>|0>と|1>|0>の重ね合わせ状態になるのです。この二つの式を見比べると、あたかも分配法則が成り立っているように見えます。これはうまい表記法なのです。

同様のことは、第2ビットでも同様になりたちます。

次に第一ビットがa|0> + b|1>にあり、かつ、第二ビットが c|0> + d|1>である状態を考えましょう。このときは、2ビットの量子状態は、

(a|0> + b|1>)(c|0> + d|1>)
= ac |0>|0> + ad|0>|1> + bc|1>|0> + bd |1>|1>

となります。(あたかも分配法則がなりたっているように計算する。)

ここで脱線して問題。一般にx |0>|0> + y |0>|1> + z |1>|0> + w |1>|1>という状態を与えたとき、それを(a|0> + b|1>)(c|0> + d|1>)のようにそれぞれ独立な重ね合わせ状態に書けるでしょうか?(ヒント:x=w=0という特殊な場合を考えてみてください。このような状態をエントアング状態(絡み合い状態)といいます。)

次に進みましょう。このような2ビット状態のうち、一方のビットに対して1ビット演算をすることを考えます。このとき、2種類の1ビット演算が可能です。つまり、第一ビットに対する1ビット演算U(1)と第二ビットに対する1ビット演算U(2)です。ここでは、第一ビットに対する演算だけを考えてみましょう。(上図参照)第一ビットに対して演算が、

U(1) |0> = a |0> + c|1>
U(1) |1> = b |0> + d |1>

で与えられたとします。ここで、|0>|1>は第一ビットの状態であることに注意してください。この演算によって、例えば|0>|0>という状態を操作したとしましょう。すると、U(1)が第一ビットにだけ作用することに注意して、

U(1)|0>|0>
= (a|0> + c|1>) |0>
= a|0>|0> + c|1>|0>

となります。このように、2ビット状態は、おのおのの1ビット演算によって操作することができます。

しかし、始めにも述べたように、1ビット演算だけではコンピュータの機能を持たせることができません。よって2ビット演算を考える必要があります。2ビット演算というのは、二つのビットの状態に応じた操作で、イメージで言うと、下図のようなものです。

原理的には、いろいろな2ビット制御が考えられるのですが、すべてのビット制御を考える必要はありません。古典コンピュータでは、AND演算とOR演算が基本的となっていたのですが、同様にして量子コンピュータでは、次に述べるような制御NOT(Controlled-NOT)が基本的な2ビット制御となります。制御NOT演算UCNとは、

UCN |0> |0> = |0> |0>
UCN |0> |1> = |0> |1>
UCN |1> |0> = |1> |1>
UCN |1> |1> = |1> |0>

という演算です。この操作の様子を、以下のように書きます。(左に操作前の状態を書き、左から順に操作をおこなっている様子をあらわしています。後で複数の操作を行うときも、左から順番に操作を書きます。)

実験的には、二つのビットの間をうまく物理的に結合させることで、制御NOTを実現できます。赤いところだけ変わることに注意してください。制御NOTとは、「もし第一ビットが0ならば第二ビットはそのままにし、もし第一ビットが1ならば第二ビットを変える」という演算です。このとき、第一ビットを制御ビット、第二ビットを標的ビットと呼びます。この操作は、量子力学的な操作なので、重ね合わせ状態x|0>|0> + y|0>|1> + z|1>|0> + w|1>|1>にも適用できて、操作後には、

UCN ( x|0>|0> + y|0>|1> + z|1>|0> + w|1>|1> )
= x UCN |0>|0> + y UCN|0>|1> + zUCN||1>|0> + wUCN||1>|1>
= x |0>|0> + y|0>|1> + z|1>|1> + w|1>|0>

が得られます。重ね合わせ状態が保持されることに注意してください。

実は、2ビット演算である制御NOTと、任意の1ビット制御だけから、量子コンピュータを作ることができます。これだけの簡単な操作も、組みあわせの妙によって、強力な計算が可能になるのです。

ただ、次回の講義でお話する「シューアの定理」を証明するのに、いちいち1ビット制御と制御NOTに戻るのはしんどいので、1ビット制御と制御NOTからつくられる「制御-U」と「制御-制御-U」というものを導入しましょう。

制御-U(Controlled-U)とは次のような演算です。

UCN |0> |0> = |0> |0>
UCN |0> |1> = |0> |1>
UCN |1> |0> = |1> (U(2) 1>)
UCN |1> |1> = |1> (U(2) 0>)

第一ビット(制御ビット)が1のときのみ、第二ビットに対する一ビット演算U(2)を作用させるという演算です。もしも一ビット演算U(2)=Xを次のようにとれば、制御NOTと同じになります。

U(2) |0> = X|0> = |1>
U(2) |1> = X|1> = |0>

つまり、制御-Uというのは、制御NOTの自然な拡張であるといえます。制御NOTと一ビット制御からこの演算は下図のように表します。

この演算を、制御NOTと一ビットの演算から構成することを考えましょう。それには第二ビットへのU(2)与えたときに、

CBA=E
CXBXA=U(2)

となる第二ビットへの3個の1ビット演算A, B, Cを見つければいいこととがわかります。ここで積CBAとは、「まずAを作用させ、次にB、最後にCを作用させる操作」を表します。これは一次変換の時にもでてきますよね。積の順番(CBA)と実際の操作の順番(ABC)がひっくりかえっていることに注意。またXは先ほど出てきた制御NOTのときのU(2)であり、Eは何もしない1ビット演算(E|0>=|0>, E|1>=|1>)です。(ここででてくる演算A, B, C, Xはすべて一ビット演算であることに注意。これらは2x2行列でかける。)図で書くと、3回の一ビット演算と2回の制御NOTの組み合わせで表せます。(下図)

このように一ビット演算A,B,Cが見つけられるかどうかは、当たり前ではありませんが、2x2のユニタリー行列(SU(2)といいます)の理論から、CBA=E, CXBXA=U(2)をみたすA,B,Cが存在することを証明することができます。(やや進んだ課題:U(2)を与えたときに、A, B, Cの行列が必ず見つかることを示せ。オイラー角をいうものを導入して示す。)ここではその証明は述べません。うまく制御NOTと一ビット制御を組み合わせて制御-Uがつくれるのだ、くらいに思っておいてください。

次に2ビット制御からははずれてしまいますが、制御-制御-U(Controlled-Controlled-U)を紹介しましょう。これは、次のような3ビット演算です。

UCCN |0>|0>|0> = |0>|0>|0>
UCCN |0>|0>|1> = |0>|0>|1>
UCCN |0>|1>|0> = |0>|1>|0>
UCCN |0>|1>|1> = |0>|1>|1>
UCCN |1>|0>|0> = |1>|0>|0>
UCCN |1>|0>|1> = |1>|0>|1>
UCCN |1>|1>|0> = |1>|1>U(3) |0>
UCCN |1>|1>|1> = |1>|1>U(3) |1>

この場合は、第一ビットと第二ビットが制御ビットで、第三ビットが標的ビットです。「第一ビットと第二ビットがともに1であるときに限って、第三ビットに一ビット操作U(3)を行う」という演算です。下図に書くと、

です。これも使えると大変便利です。これは、以下のように制御-Uの組み合わせによって実現されます。(任意課題:実際に以下の回路において制御-制御-Uが実現されていることを示せ。ただしV2=Uとなるようにとる。)

以上で量子ビットへの基本操作の解説は終わりですが、最後にこれらの演算(一ビット演算+制御NOT、およびその組み合わせから得られる制御-Uと制御-制御-U)をつかって、古典コンピュータにおけるANDやOR演算ができることを示しましょう。もちろん、まったく同じようにつくってしまうと不可逆な操作になるので、補助ビットをおいてあげます。

(任意課題:4通りの入力をしらみつぶしに調べ、以上の回路がAND・OR演算を行うことを確かめよ。)このことから、量子ビットへの演算をもちいて、古典コンピュータと同様の演算を行うことができることがわかります。

量子アルゴリズムとその設計概念

量子コンピュータの特徴は、量子ビットの重ね合わせ状態の利用にあります。よって、量子コンピュータにおける効率のよい計算アルゴリズムは、必ず次のような過程をたどります。

(1)重ね合わせ状態の準備
(2)重ね合わせ状態を保持したままでの量子ビット操作
(3)観測

今回の講義では、(1)についてだけ考えてみましょう。(2)以降については、次回の「ショーアの定理」の証明を通して、具体的に触れる予定です。

もっとも簡単な重ね合わせ状態とは、「量子ビットのとりうるすべての状態が等しく重ね合わされた状態」です。例えば、1ビットの状態については、

であり、2ビット状態については、

です。(すべての係数を2乗して足すと1になることに注意。)3ビット状態では、

となります。このような状態はどのようにしてつくったらいいでしょうか?

ここでは3ビット状態に対する説明だけをすることにしましょう。(一般のnビット状態についても、同様です。)まず、始めに|0>|0>|0>という状態を用意します。ここに各ビットに一ビット演算、U(1), U(2), U(3)をそれぞれ書けます。U(a)は第aビットに対する一ビット制御です。この一ビット演算U(a)は各ビットについて、

U(a) |0> = (|0> + |1>)/√2

という演算を行うとしましょう。(|1>に対する結果は何でもいい。)この1ビット演算をたて続けにおこないます。

U(3) U(2) U(1) |0> |0> |0>
= U(3) U(2) ((|0> + |1>)/√2) |0> |0>
= U(3) ((|0> + |1>)/√2) ((|0> + |1>)/√2) |0>
= ((|0> + |1>)/√2) ((|0> + |1>)/√2) ((|0> + |1>)/√2)
= (|0>|0>|0> + |0>|0>|1> + |0>|1>|0> + |0>|1>|1> + |1>|0>|0> + |1>|0>|1> + |1>|1>|0> + |1>|1>|1>)/(√2)3

そうすると、望んでいた「とりうるすべての状態が等しく重ねあわされた量子状態」が、ちゃんと実現されることがわかります。4ビット以上も同様です。一般にnビット状態の重ね合わせの準備に、n回の1ビット演算しかいらないことに注意してください。この状態の準備は効率的に行うことができます。

ここで表記法について述べておきましょう。2ビット状態については、それぞれの2ビット状態をそれぞれ

|0>|0> = |0)
|0>|1> = |1)
|1>|0> = |2)
|1>|1> = |3)

とおくことにします。これは、|x>|y>の状態に対して、二進数xyを十進数aで書き直して|a)と書いたものです。言い換えると、2ビットの状態をはじめから番号付けして、a番目の状態を|a)と書いています。こうすると等しく重ねあわされた状態というのは、

と略記できます。同様に3ビット状態を、

|0>|0>|0> = |0)
|0>|0>|1> = |1)
|0>|1>|0> = |2)
|0>|1>|1> = |3)
|1>|0>|0> = |4)
|1>|0>|1> = |5)
|1>|1>|0> = |6)
|1>|1>|1> = |7)

とかくことにすれば、2ビットと同様にして、3ビットで等しく重ね合わされた状態というのは、

となります。

このようなに、「等しく重ねあわされた状態」というのは、分かりやすいやり方でつくることができました。ところが、これではせっかくの重ね合わせ状態も、それほど役にたたないことがすぐにわかります。非常に大雑把にいってしまうと、「あらゆる数aの重ねあわせをつくって、一種の並列計算をやっても、どうせ最後に観測をしてしまう。そうすると、確率的に|a1>を得たり|a2>を得たりなので、結局はじめからa1, a2, ,,,をしらみつぶしに計算していくのと変わらない」ということです。(前回の講義でも述べましたよね。)

ではどうするか。改良は二段階に分けられます。

まず第一段階として、|a)の前の係数をいじります。つまり、

という状態を作ることにするのです。ここでf(a)は複素数で、|f(a)|=1を満たすようにとっておきます。(こうすれば、全確率が1となることが自動的に保証されます。任意課題:それを示せ。)|f(a)|=1を満たす関数f(a)はたくさんありますが、もっとも役に立つには、次のような形です。

ここでexp(x) = exは指数関数です。「おおお、ついに訳のわからないものがでてきた」と引いてしまうかもしれませんが、なんとかついてきてください。まずiというのは、虚数です。今考えているのは、「虚数に関する指数関数」なのです。これをどのように定義するか、というのは、簡単に説明するのは難しいですが、大雑把にいうと、実数に対する指数法則の諸性質をたもったまま、虚数の指数関数を定義します。そしてその値は、「オイラーの公式」とよばれる美しい公式によって計算されます。このあたりは、他の教科書を参照してください。(当座はオイラーの公式を、指数関数の定義と思ってもらっても構いません。)

ここで角度θはラジアンで計ることにしています。この公式にしたがって、3ビット状態に対してf(a)の値を計算してみましょう。

f(0) = cos 0 + i sin 0
f(1) = cos (π/4) + i sin (π/4)
f(2) = cos (π/2) + i sin (π/2)
f(3) = cos (3π/4) + i sin (3π/4)
f(4) = cos (π) + i sin (π)
f(5) = cos (5π/4) + i sin (5π/4)
f(6) = cos (3π/2) + i sin (3π/2)
f(7) = cos (7π/4) + i sin (7π/4)

です。式ではイメージが浮かばないでしょうが、これを図にしてみると状況がもっとよくわかります。複素数z=x + iyを2次元平面内の点(x,y)として点を書いてあげます。すると、これら8個の複素数が、半径1の円の上にあり(|f(a)|=1)、さらに中心角がπ/8(=45度)づつ異なっていることがみてとれます。

ということで、先ほどの状態

とは、イメージで言ったら、

(1/√2)3( →|0) + / |1) + ↑|2) + \ |3) + ← |4) + / |5) + ↓|6) + \ |7) )

です。(斜め矢印が入力できないのは、ご愛嬌ということで。)

このような状態をつくりだす操作を、量子フーリエ変換(の特殊な場合)と呼びます。量子フーリエ変換は、量子アルゴリズムの中でも、非常に大切な手法となっています。

次の問題は、どのやってこの量子状態をつくるか、です。これは、先ほどの「等しい重みを持つ状態」を作っておき、さらに補助ビット|0>を用意します。

次に下の図のような操作を連続して行います。|a)の各ビットを制御ビットとし、一方補助ビットを標的ビットとして、制御-Uを次々に作用させていきます。

このとき補助ビットに対する一ビット演算U(m)を次のように定義しておきます。

この演算は|0>の前の係数を変えるだけなので、始め補助ビットを|0>としておけば、永遠に補助ビットは|0>です。

回路図にかかれた制御-Uの繰り返しをまとめて操作Wとしましょう。操作Wから、求める状態がでてくることを式でもみることができます。例えば、|5) = |1>|0>|1>という状態に、図に書かれた一連の操作をしてみることを考えましょう。このとき、

のようになります。一般の|a)|0>に対してもW|a)|0>を計算ができます。よってこの操作Wを先ほどの、「等しい重みによって重ね合わせた状態」の作用することによって、

とできます。(この操作Wに必要な基本操作の回数は、せいぜいビット数に比例することがわかりますから、これらの操作は効率的に行うことができます。)

しかしながらまだこれでは不十分です。この状態においても、観測を行うと|0)から|7)まで等確率で観測されることに代わりがないからです。

そこで改良の第二段として、重ね合わせ状態をつくっているビット群|a)のほかに、補助ビット群|c)を用意します。この補助ビット群のビット数は|a)の方のビット数とそろえておきます。つまり、3ビットの場合には、|a), |c)ともに|0>|0>|0>から|1>|1>|1>までの8とおりの状態を表します。さて、ここで得たいのは、

という状態です。ここでf(a,c)はaとcで決まる係数ですが、ここをうまく工夫して、aとcのある種の絡まった状態を作るのがポイントです。このf(a,c)を

ととるのがうまいです。これが一般の量子フーリエ変換です。シューアの定理では、中心的な役割を果たします。

イメージがわかないでしょうから、このたくさんの状態の重ね合わせの中から|c)が|0)の部分を見てみましょう。比例係数(1/2)3をのぞくと、

|0) |0) + |1) |0) + |2) |0) + |3) |0) + |4) |0) + |5) |0) + |6) |0) + |7) |0)

となっています。これは単なる等しい重みで重ね合わせているだけですね。ところが、|c)が|1)のときは、次のようになっています。

exp(0) |0) |1) + exp(iπ/4) |1) |1) + exp(i2π/4) |2) |1) + exp(i3π/4) |3) |1)
exp(i4π/4) |4) |1) + exp(i5π/4) |5) |1) + exp(i6π/4) |6) |1) + exp(i7π/4) |7) |1)

= {cos(0) + i sin(0) } |0) |1)
+ {cos(π/4) + i sin(π/4) } |1) |1)
+ {cos(π/2) + i sin(π/2) } |2) |1)
+ {cos(3π/4) + i sin(3π/4) } |3) |1)
+ {cos(π) + i sin(π) } |4) |1)
+ {cos(5π/4) + i sin(5π/4) } |5) |1)
+ {cos(3π/2) + i sin(3π/2) } |6) |1)
+ {cos(7π/4) + i sin(7π/4) } |7) |1)

これはどこかでみましたよね、、。各係数は、平面上で表すとπ/4づつ、つまり45度ずつ変化するような、複素数の係数がまえにかかっているのです。同じように|c)を|2)とすることで、

{cos(0) + i sin(0) } |0) |2)
+ {cos(π/2) + i sin(π/2) } |1) |2)
+ {cos(π) + i sin(π) } |2) |2)
+ {cos(3π/2) + i sin(3π/2) } |3) |2)
+ {cos(2π) + i sin(2π) } |4) |2)
+ {cos(5π/2) + i sin(5π/2) } |5) |2)
+ {cos(3π) + i sin(3π) } |6) |2)
+ {cos(7π/2) + i sin(7π/2) } |7) |2)

と変わります。今度はπ/2づつ、つまり90度ずつかわっていることに注意してください。cとは、aが1だけ変化したときの回転角の大きさをしていしているのです。

このように絡み合った量子フーリエ変換は、下の図のように制御-制御-Uの組み合わせでかけます。ここでU(m)は既にでてきたような、一ビットに対する制御です。(任意課題:以下がたしかに量子フーリエ変換になっていることを示せ。)

この基本操作の回数が、ビット数の高々2乗に比例することに注意してください。量子フーリエ変換は効率的にできるのです。

ここで紹介したテクニックを用いて、因数分解のアルゴリズムがつくられます。それは、次回の講義で紹介することにいたします。

まとめ

今回の講義では、量子ビットの演算について詳しく述べてきました。まとめると

(1)量子コンピュータの操作は「状態の準備」+「量子状態の操作」+「観測」の手順でおこなう。ここで、量子ビットへの操作観測は、まったく異なることに注意する必要がある。
(2)任意の量子ビット操作は「制御NOT」と「任意の一ビット演算」の組み合わせで行うことができる。
(3)シューアの定理の証明には、状態の準備として量子フーリエ変換をつかう必要がある。

となります。本当に長い講義でしたが、(実際に物理系でどのように実験するかは別にして)一つ一つの事柄には、深遠なことはありません。じっくり考えてみてください。なお今回の講義では、「量子コンピュータの基礎」、細谷暁夫著、サイエンス社を大変参考にさせてもらいました。本講義をここまでまとめられたのは、ひとえにこの本の存在によってである、といっても過言ではありません。この場を借りて感謝したいと思います。また詳しいことがらを勉強したい人は、まずこの本を手にとってみられることを、強くお勧めいたします。