（元になる回路）

西野研究室 http://www.tnlab.ice.uec.ac.jp

情 報 通 信 工 学 科情報メディア工学講座電気通信大学

研究テーマ紹介研究テーマ紹介

量子回路

西野研究室　量子計算グループ西野研究室　量子計算グループ

量子

セルオートマトン

並列

シミュレーション

現在のコンピュータは基本的に論理回路で構成されています。

量子コンピュータにおいても回路を考えることができ、 それを量子回路と呼びます。

量子コンピュータの状態は量子力学的に非常にデリケートなので、

計算時間と使用する領域 （現在のコンピュータのメモリに相当） は

なるべく小さくする必要があります。

では、 より多くの領域を使用して計算することで、 計算時間を短くすることができるのでしょうか？

現在のコンピュータにおいては、 計算時間の短縮のためにそのような方法がよく用いられます。

量子コンピュータにおいてもその手法は有効なのでしょうか？

西野研究室では、 領域の使い方をいくつかに分類し、

どのタイプの使い方で計算時間の短縮効果が得られるかを調べています。

もし、 どの使い方にも計算時間短縮に効果が無いということが判れば、

量子回路を設計する人は補助領域のことを何も考えずに回路を設計できるようになります。

セルオートマトンは、 格子状に並んだ無数の “セル （小部屋の意）” が、

ある規則に従ってそれぞれの状態を時々刻々と変化させることで計算を行う、

離散的計算モデル （コンピュータのモデル） です。

このセルオートマトンを量子コンピュータのモデルとして拡張したものを、

量子セルオートマトンと言います。

西野研究室では、

量子セルオートマトンを実用的なアプリケーションに用いる研究を行っています。

そのひとつとして、 2007 年度、 量子セルオートマトンのシミュレーションを応用した、

古典コンピュータ上の暗号化システムを提案しました。

現在、 安全性の検証など更なる研究を進めています。

また、 西野研究室では、 量子セルオートマトン研究を円滑に進めるための

シミュレータ開発も行っています。

量子コンピュータの研究において実験結果を評価するために、 計算の実行過程を

既存の計算機でシミュレーションすることが必要です。

しかし量子コンピュータのシミュレーションは、 現在のコンピュータを使用すると

非常に時間がかかってしまいます。

そこで西野研究室では、

複数の CPU を搭載したコンピュータを使用する方法や

最近その計算能力が注目されている GPU （Graphics Processing Unit） を

使用する方法の研究に取り組んでいます。

現在は、 量子コンピュータの代表的なアルゴリズムである

Grover のアルゴリズムのシミュレーションを行っています。

その際、 量子コンピュータを実現するにあたって考慮する必要があると考えられる、

ノイズの影響についても研究しています。

量子コンピュータでは一度にセルが様々な状態に遷移する

補助量子ビット（補助領域）の様々な使い方。補助量子ビットをうまく使えば計算時間が短縮できる？

CPU

CPU×3

GPU

並列にシミュレーションを行えば早く計算できることがある

西野研究室 http://www.tnlab.ice.uec.ac.jp

情 報 通 信 工 学 科情報メディア工学講座電気通信大学

量子コンピュータ

とは

原理

威力

問題点

原子などのミクロな粒子は波のように振舞うことがあります。

そのような波は、 水面にたつ波のようにいくつも重ね合わせることが出来ます。

波が重なり合ったとき、 その粒子の位置は不確定になります。

このような粒子の状態を重ね合わせの状態といいます。

量子コンピュータは、 この重ね合わせ状態を利用して、 量子ビット (qubit) を

実現します。 古典的な原理で動作する現在のコンピュータのメモリは 1 ビット

と呼ばれる一区画に 「0」 か 「1」 のどちらかの値しか保持できません。

それに対して、 量子コンピュータのメモリの一区画は 1 量子ビットと呼ばれ、

　　　　先に述べた量子力学的な性質を用いて、通常の 「0」、「1」 に変わって、

様々な 「0 と 1 の重ね合わせ状態」 をとることができます単純に 1 量子ビットで 「0」 と 「1」 の両方の値を保持できると考えれば、

たとえば 2 量子ビットの場合、 メモリ全体で 「00」 「01」 「10」 「11」 の

4 つの値に関する計算を同時に実行できます。

もし、 もっと量子ビットの数が大きな量子コンピュータどうでしょうか。

たとえば 15 量子ビットの量子コンピュータが実現できたなら、

この量子コンピュータはメモリ全体で 215 （約 32,000） 通りの値

それぞれについての計算を同時に行うことが出来ます。

16 量子ビットなら、 さらにその 2 倍です。

量子コンピュータは古典的なコンピュータの限界である粒子の量子的

特性を逆手に取ることで、 一度に計算できる計算回数を爆発的に

増やすことが出来ます。

しかし、 量子コンピュータは単純な並列計算機ではありません。

実際には様々な量子力学的制約が課せられます。

そのため、 どのような計算法 ( アルゴリズム ) が量子コンピュータ上で威力を

発揮するのか、 量子コンピュータはどのような可能性を持っているのか、

などを研究する必要があります。

0 0 0 0 0 0 11 1 1 1 1

西野研究室

量子計算グループ

Groverのアルゴリズム整列されていないデータベースの中から、 所望のデータを高い確率で高速に探し出します。１００万個のデータからほしいデータを探す場合、 現在のコンピュータで動く既存のアルゴリズムでは平均５０万回調べなければ探し当てられませんが、 このアルゴリズムを量子コンピュータ上で動かせば、 １０００回調べればほしいデータを発見することができます。

整数の因数分解を小さな誤り確率で高速に行うアルゴリズムです。 一般に大きな整数の因数分解は現在のコンピュータでは非常に時間がかかります。５００桁ほどの整数の因数分解は１０００万年程度かかります。

この因数分解の困難さによって RSA 公開鍵暗号など主要な暗号の安全性が保証されています。

つまり、 もしこのアルゴリズムを実行できる量子コンピュータが実現されたら、インターネット上での情報のやり取りの安全性が失われてしまいます。

Shor のアルゴリズム

電子的なコンピュータが発明されて以来、

一つのプロセッサが計算できる回数は年々向上してきました。

これは回路の集積度が技術の進歩により上がってきた為です。

しかし、 ひとつひとつの部品を細かくするのにも限界があります。 なぜなら、 部品が原

子数百個分、 数十個分の大きさに小さくなっていけば不思議な性質 -- 量子的な特性

が現れてくるからです。 これでは既存のコンピュータが使えなくなってしまう可能性があ

ります。 しかしこの性質を利用して、 現在のコンピュータとは全く違う構造の

コンピュータを作ることができないかという研究が行われています。

それが量子コンピュータです。

B.C. そろばんの発明

A.D.17C Pascal が歯車を用いた機械式計算機を発明

1936 Church によって「計算」とは何か？が明らかに

1937 Turing がチューリングマシンを考案

1944 リレースイッチを使用した電子計算機 Mark- Ⅰ

1946 真空管を使用した電子計算機 ENIAC

1985 Deutsch が量子チューリングマシンを考案

1989 Deutsch が量子回路を定式化

1993 Bernstein と Vazirani が効率的な万能量子チューリングマシンを構成

1994 Shor のアルゴリズムが考案された

1995 Watrous が量子セルオートマトンを提案

1996 Grover のアルゴリズムが考案された

歴史

量子的特性は私たちの目には見えない不可思議な状態をとる

主要なアルゴリズム

量子コンピュータ量子コンピュータ