A07:現実的な状況での量子計算の能力に関する研究
奈良先端科学技術大学院大学
山下 茂
国立大学法人
情報科学研究科
中西正樹
奈良先端科学技術大学院大学
A07:現実的な状況での量子計算の能力に関する研究
背景
次世代の計算機 – 量子計算機 –
実際に量子計算(通信)使う状況を考えると…
古典計算機とは異なる量子計算機特有の問題が生じる
エラーの問題,古典計算機との役割分担,現実的な計算モデ
ル...
いろいろな状況を想定して、研究を行なってきた。
1
http://www.naist.jp/
A07:現実的な状況での量子計算の能力に関する研究
具体的には…
•量子計算におけるエラーをどうする?
① エラーのある量子サブルーチンの利用法
② Dephasing Errorの対処方法
•古典のリソースと量子のリソースがある状況をどうする?
③ 古典計算機と量子計算機を協調して利用する枠組み
④ 一部が古典のメモリの場合のオートマトンの能力
•古典ではできないことを量子を使うとできるか?
• 古典のランダムネスを使う場合の量子通信量
• 古典情報を安全に送信
• 文字列の封印
•その他,量子計算モデル,量子回路合成,...
2
http://www.naist.jp/
量子計算機を使う上で...
• 量子計算のエラーをどうする?
• 量子リソースと古典リソースが混在する
状況をどうする?
3
http://www.naist.jp/
①エラーのある量子サブルーチンの利用法
• 量子アルゴリズム ⇒ 基本的に確率アルゴリズム
– サブルーチンとして使う場合には,成功確率の増幅が必要!
• エラーが生じるサブルーチン:biased-oracle
– Oracle 呼び出し時にエラーが生じる.
– 確率1/2+εで正解を返すオラクル.
• 古典計算の場合:
– オラクルを複数回呼び出して多数決を取ると
perfect oracleでOT  時間→biased-oracleで OT logT  2  時間
• 量子計算の場合は?
– 多数決をひと工夫できないか!?
4
http://www.naist.jp/
①エラーのある量子サブルーチンの利用法
結果
正答率 1 2   以上の quantum biased oracle を O1   回用いて
正答率 2 3 以上の qunautm biased oracle をシミュレートできる
※古典では、O1  2 
探索問題に適用 (f(x)=1となるxは? f: oracle)


• O N  の量子探索アルゴリズム
• これは下限  N  と一致


• 古典計算では N  2 
 
perfect oracleの場合⇒量子: N
古典:
5
http://www.naist.jp/
② Dephasing Errorの対処方法
• 古典計算の場合、
アルゴリズム的なエラー=デバイスの物理エラー
(0と1の反転)
• 量子の場合は?明らかに異なる。
• 物理的なエラーとしてDephasing Errorが重要
(1  p )b 
a b 
 a
   '  

  
d 
c d 
 (1  p)c
( p  1 / 2とする )
二量子状態を比較する手法を誤り訂正(多数決)に応用
物理学の研究者との融合領域研究
6
http://www.naist.jp/
② Dephasing Errorの対処方法
結果
2つの量子状態をC-SWAPテストし、0を観測したときに
第2ビットを出力すれば、誤りをいくらか回復できる.
*1を観測すると失敗
*改善率はもとの状態に依存するので明示的には示せない
量子状態は観測すると壊れる(変化する)
→ 観測することで元の状態に戻るように仕向ける
C-SWAPテスト
|0
|φ
|ψ
H
H
|0?
S
W
A
P
7
http://www.naist.jp/
量子計算機を使う上で...
• 量子計算のエラーをどうする?
• 量子リソースと古典リソースが混在する
状況をどうする?
8
http://www.naist.jp/
③古典計算機と量子計算機を協調して利用する枠組み
• 世の中のアプリケーション:
• 現実的には殆どの部分は古典計算機の方が速い.
• 量子ー古典協調計算が重要!
• 古典アルゴリズムを主体に量子探索をサブ
ルーチン呼び出し
• 現実的な量子計算機の使い方の一つ
9
http://www.naist.jp/
③古典計算機と量子計算機を協調して利用する枠組み
開発した量子アルゴリズム設計環境
• C++で記述したプログラムから、グロバーサーチ(G. S.)に
より高速化できる部分を切り出す(ディレクティブ)
• 実際に量子回路設計を行い量子的に加速可能かを見積もる
• G.S.の実行エラーが起こった場合のリトライを行なう制御
も自動付加
• 量子回路設計方法としては、実用的な大きさの回路でも扱
える(おそらく)初めての手法
• 今後、具体的なプログラムでG. S.が実際に役立つのかを検
証するのに利用する予定
10
http://www.naist.jp/
④ 一部が古典のメモリの場合のオートマトンの能力
• 各種オートマトンでの量子計算の能力は?
– プッシュダウンオートマトンを対象
– スタックが古典デバイス
– 有限状態制御部が量子デバイス
– 「古典だけ」,「量子だけ」よりも「古典+量子」が
有効
11
http://www.naist.jp/
④ 一部が古典のメモリの場合のオートマトンの能力
• 片側誤りモデルの場合
– 量子+古典モデルが古典モデルより真に能力が
高くなる.
One-sided error
QCPDA’s
One-sided error
probabilistic PDA’s
Non-deterministic
PDA’s
L1
12
http://www.naist.jp/
その他,量子計算に関する研究
•古典ではできないことを量子を使うとできるか?
• 古典のランダムネスを使う場合の量子通信量
• 古典情報を安全に送信
• 文字列の封印
•その他,量子計算モデル,量子回路合成,...
13
http://www.naist.jp/
古典のランダムネスを使う場合の量子通信量
結果
量子でも古典のpublic coinをO(log n)ビットの通信でprivate
coinに変更可
その利用により、全域関数で量子と古典の通信量の分離
Q2 (LNE(m, k ))  O( m log m  log k )
 R2 (LNE(m, k ))  (m  log k )
EQk
m
 EQk ( x , y )   EQk ( x , y
(1)
(1)
EQ (x
k
LNE (m, k )  EQ k
m
( m)
(i )
( m)
, y )  true iff x  y
(i )
(i )
)
(i )

: list non - equality function
14
http://www.naist.jp/
その他,量子計算に関する研究
• 量子秘匿通信
– 量子暗号: 安全な鍵配布プロトコルをさすことが
多い.
– 量子直接秘匿通信: 秘密を直接相手に送る.
– 量子状態を送信できる.
– 光子数分割攻撃に強い.
15
http://www.naist.jp/
その他,量子計算に関する研究
• 量子封印
– メッセージを「封印」するプロトコル.
– 誰かがメッセージを読んだかどうかを確認できる.
• 誰でもメッセージを読める.
• メッセージを読むと痕跡が残る.
– 古典通信プロトコルでは実現不可能
– 提案手法は流出する情報量が自明な下界に一致
→最適な量子封印プロトコル
16
http://www.naist.jp/
今後の研究方針
実際に(将来の)量子計算を使いこなすには….
物理的なエラーをアルゴリズムのテクニックで
克服できるか?
物理的なエラーを計算モデルに取り入れることを考
える
→新しい量子計算の計算モデル
17
http://www.naist.jp/
END
18
http://www.naist.jp/
ダウンロード

A07