量子情報処理の壁と その乗り越え方 －最近の量子情報処理の発展と共に－

Presentation on theme: "量子情報処理の壁と その乗り越え方 －最近の量子情報処理の発展と共に－"— Presentation transcript:

1 量子情報処理の壁と その乗り越え方 －最近の量子情報処理の発展と共に－
村尾美緒 東京大学大学院理学系研究科物理学専攻 東京大学ナノ量子情報エレクトロニクス研究機構

2 人工量子系と量子情報処理 人工量子系 自然量子系 個々の量子を情報処理に用いてみよう！
通常の物理学（物性物理）： 自然を記述するハミルトニアンが与えられた場合の系の状態を調べる テクノロジーの進化によって、集合アンサンブルではなくて、量子ひとつずつを人工的に制御・測定することができるようになった。ハミルトニアンを人工的に操作できる！ 人工量子系 自然量子系 １量子状態制御 相互作用制御 １量子測定 個々の量子を情報処理に用いてみよう！

3 量子情報を使えば何でも解けるのか？ 量子情報処理の壁とその乗り越え方
残念ながら、量子情報処理をすれば、いつでも通常の古典情報処理より必ずしも良くなるわけではない。 量子情報処理には、苦労するだけの価値があるのか？ 量子情報処理の壁とその乗り越え方

4 outline 量子情報処理についてのoverview 秘匿量子計算（時間があれば） 量子情報における量子力学
量子ビットとHolevo boundの壁 エンタングルメントと光速の壁 エンタングルメントとGottesman-Knillの壁 測定ベース量子計算 量子計算量とQMAの壁 秘匿量子計算（時間があれば） 目的 方法 証明のアウトライン

5 量子情報処理とは… 量子力学の基盤的な理解とその情報処理への応用
量子情報（量子ビット）を用いることで従来の古典情報（古典ビット）を用いたものでは不可能であったり難しかったりする情報処理を行なうことを目指す。 量子計算：より高速な計算 量子通信：より効率的・高付加価値な通信 量子暗号：より安全性の高い通信 研究の舞台 ハードウェア：ナノテクノロジー、エレクトロニクス、量子光学、原子分子… ソフトウェア：アルゴリズム、暗号・通信プロトコル、誤り訂正… 注意：量子効果自体は通常の古典情報処理でも使われている。 量子力学の基盤的な理解とその情報処理への応用

6 量子情報を理解するための量子力学(1) 1. 量子ビット＝spin ½系 （2次元ヒルベルト空間）
2. 測定過程：期待値やオブザーバブルではなく、測定演算子による状態変化や確率分布を扱う。測定は、系の情報と取り出すだけではなく、系の情報をとりださない情報処理に使うこともある。 |0> |1>

7 量子情報を理解するための量子力学(2) 3. 密度行列：失われた情報を取り扱うために、密度行列による定式化を使う。状態の記述は、我々が系について何を知っているかに依存する。 4. エンタングルメント：多量子ビットの系では、テンソル積空間を考えるため、エンタングルメントが生じる。 A B A B

8 量子ビットの個数が増えると自由度が激しく増大。
古典ビットと量子ビット 古典状態は実数で表される ビット　“0” or “1” 量子状態は複素ベクトルで表される 量子ビット　|0>,|1> 　　　　と重ね合わせも可能 C Q Quantum > 1 Qubit z y x Classical or “ ” Bit | とりうる状態 とりうる状態 上向きか下向きの組み合わせのみ 量子ビットの個数が増えると自由度が激しく増大。 測定結果 測定結果 ０と１の２つの値のみ。 ０と１の２つの値のみ。 Holevo boundの壁 量子ビットに情報をたくさんつめこんでも、適当な測定ではうまくとりだせない! ソフトウェア的研究の重要性

9 Holevo boundの壁 量子情報処理で、何ができるのか？ 量子情報処理を優位にする本質は、何か？
たとえば、量子計算は超並列計算とも言われるが、最終的には、量子状態の測定に関する不確定性のために、並列計算したすべての結果をそれぞれ独立に取り出せるわけではない。量子アルゴリズムには工夫が必要。 量子情報処理で、何ができるのか？ 量子情報処理を優位にする本質は、何か？ 量子情報処理ならではのソフトウェア（量子プロトコル・量子アルゴリズム）を探求する必要。 「Holevo boundの壁」：1量子ビットから1古典ビット分しか読み出すことができない。

10 U 量子計算(1) Shorの因数分解アルゴリズム、Groverの探索アルゴリズムが古典より優位な量子アルゴリズムとして知られている。
Q 量子計算(1) Shorの因数分解アルゴリズム、Groverの探索アルゴリズムが古典より優位な量子アルゴリズムとして知られている。 量子計算の手順 １．量子系を初期化する。 ２．量子系にユニタリ変換をする。 ３．量子系を測定する。 量子回路(quantum circuit) U 1 2 3

11 量子計算(２) 基本量子ゲートの組み合わせによって、どんな大きなハミルトニアンも人工的に作ることができ、任意のユニタリ変換を操作できる。また、一つ一つの量子ビットに対して測定を行うことができる。 干渉効果をうまく使うことによって、Holevoの壁を回避して重ね合わせ状態における並列計算のパワーを使う。 Shorの因数分解アルゴリズム：量子状態の重ね合わせを用いて因数分解アルゴリズムで必要となる「周期発見(period finding)」のプロセスを多項式時間で実行。 Groverの検索アルゴリズム Ｕ Ｖ Ｗ 基本ゲートの例：１量子ビットユニタリ＋CNOT演算 でも、古典計算機より早くなる本質はよくわかっていない。

12 エンタングルメント (ノイズのない系) エンタングルメントの定義： 複数の部分系を持つ結合量子系を考える。
結合系の状態が分離不可能な状態にあるとき、エンタングルメントがあるという。 たとえばBell状態： エンタングルしている状態では、片方の系を測定すると、それに応じて他方の系の状態がどこにあろうとも瞬時に変化する。(非局所的量子相関） Ａ Ｂ Spooky action at a distance! © The Nobel Foundation

13 エンタングルメント(ノイズのある場合) 以下のように書くことのできない状態（分離不可能な状態）
定義: By R.F.Werner: Phys. Rev. A 40, 4277 (1989) 以下のように書くことのできない状態（分離不可能な状態） ノイズのある量子状態の場合、密度行列を見て状態がエンタングルしているかどうかを判断するのは計算量的(NP-Hard)に難しい問題。 単純な量子系の場合には、Peres-Horodecki criterionという方法がある　 エンタングルメント量の測度には色々なものがあり、多体エンタングルメントなど一般の場合には、目的に応じて使い分ける必要がある。 例：多体エンタングルメントとLOCC状態識別：M. Hayashi, D. Markham, M. Murao, M. Owari and S. Virmani, 　Phys. Rev. Lett. (2006). 「エンタングルメント理論」はまだ発展途中である。

14 さまざまな少数量子ビットエンタングル状態
Telecloning状態 Cluster状態 Bell状態 GHZ状態 W状態 一般的には これらの状態は、既に実験的に作成可能。

15 エンタングルメントと量子通信・量子暗号 光速の壁とHolevoの壁は存在するが・・・・ エンタングルメントは非局所的量子相関 できること
エンタングルしている片方の系を操作することで、全体の系の状態を変えることができる。 しかし、もちろん、光速を超えた情報通信はできない。 できること エンタングルメントを利用して、１量子ビットを送ることで2ビット（古典）情報を送ることができる。（Superdence coding）　 盗聴なしで乱数の共有ができる。(QKD:　量子鍵分配) 量子情報を送ることができる。（量子テレポーテーション） エンタングルメントを利用した量子度量衡学（リソグラフィー他） 光速の壁とHolevoの壁は存在するが・・・・

16 量子通信 量子鍵配布(QKD)プロトコル：非直交の量子状態を用いることで、２者間での乱数の共有が可能となる。盗聴者は乱数を盗めない。
認証が成立していれば、絶対安全性が保障されている。 既に市販品あり　(一説によると500万円程度？）。 今年の10月のスイス国会選挙において、通信につかわれた。 スイス　 米MagiQ Technologies

17 エンタングルメントと量子計算 Gottesmann-Knill 定理の壁 エンタングルメントがあれば量子計算がいつも速くなる？
必ずしも、そうでないことが証明されている。 量子計算：１量子ビットのユニタリ変換とＣＮＯＴ演算ができれば、どのようなユニタリ変換も実現できる。 CNOT演算はエンタングルメントを作りだすことができるが、CNOT演算とパウリ・H・S ゲートのみからなる演算（クリッフォード演算）は古典計算機でシミュレート可能である。 エンタングルメントを使って量子計算ができるか？ クラスター状態を用いた測定ベース量子計算 Ｕ Ｖ Ｗ パウリゲート：x,y,z軸に関する180度回転 H/Sゲート：ｙ/z軸に関する90度回転 Gottesmann-Knill　定理の壁 > 1 z y x |

18 測定ベースの量子計算（測定を情報処理に使う）
エンタングルメント資源と1量子ビットのユニタリ変換および測定のみを用いて、ゲート演算をせずに普遍的な量子計算を行なうことができる。 Cluster状態 量子計算の行い方 個々の量子ビットに対してz軸まわりの任意の回転、Hadamardゲート、z軸への射影測定を行い、測定結果に応じた補正を繰り返すことによって行なう。 R. Raussendorf and H. J. Briegel, Phys. Rev. Lett. 86, 5188 (2001). 作り方 量子ビットを格子点上に置いて|0>状態におく。（x方向を向いた状態） 最近接の量子ビット間に制御sz演算を行なう。 > 1 z y x | Optical Lattice系で実現されている ここで普遍性をかせいでいる!

19 ＱＭＡの壁 量子計算機は何ができるのか？ 量子計算機があれば、 量子系の計算やシミュレーションが 効率よくできるかもしれない
Feynman, 1982 現段階での理解： 量子多体系の動力学のシミュレーションには向いているようだ。 ハミルトニアンの基底状態のエネルギーを求めるような問題には、向いていなさそうだ。 ＱＭＡの壁

20 Quantum Merlin-Arthur (QMA)
J. Watrous, 2000 NP問題の量子計算機版と言われている問題。 “Yes” の答えが１メッセージ量子対話型証明で検証可能であるような判定問題のクラス。次の要請がある。 もし答えが“Yes”なら、量子計算機を用いて多項式時間で検証者(verifier)が少なくとも2/3の確率でacceptするような量子状態が存在する。 もし答えが“No”なら、検証者(verifier)は少なくとも2/3の確率ですべての量子状態に対してrejectをする。 証拠 Marlin Arthur 検証者 証拠となる量子状態がない場合には、量子計算機を使っても多項式時間で “Yes” か“No”かを見つけることができない。

21 対話型証明 証明者は、秘密のパスワードによって、自分が権限を持つ者であることを検証者に示したい。
L. Babai (1985); 量子版：J. Watrous (1999) 証明者は、秘密のパスワードによって、自分が権限を持つ者であることを検証者に示したい。 パスワードを直接打ち込むのは危険。検証者は証明者に質問してその答えを計算して吟味することで、証明者が本当にパスワードを持っているかどうかを知ることができる。 Arthur Question Q A: witness 証明者 検証者

22 QMA完全であることが知られている問題 2-local hamiltonian問題
J. Kempe, A. Kitaev, and O. Regev, SIAM Journal of Computing 35 (5: , 2006 R. Oliveira and B. M. Terhal, quant-ph/ 5-local Hamiltonian, A. Kitaev, A. Shen, and M. N. Vyalyi. (2002)

23 第一部のまとめ 量子情報分野のキーワード・overview 量子情報処理の最近の発展 以上に加えて実験的な発展を付け加えると…
Gottesman-Knillの壁 測定ベース量子計算 量子計算量：ＱＭＡクラスの問題 以上に加えて実験的な発展を付け加えると… QKDはもはやfuture technologyではない。 量子計算機は最大でO(10)程度。 超伝導を使った光子検出器・超伝導cavityなど発展 量子情報メモリーが未だ実現されていない！

24 秘匿量子計算

25 古典暗号vs量子計算vs量子暗号 古典暗号 量子計算（Shorの因数分解アルゴリズム） 量子暗号（ＱＫＤ）
現在広く用いられている公開鍵暗号(RSA暗号）は、大きな数の因数分解にかかる時間が指数関数的となる点を利用する。 量子計算（Shorの因数分解アルゴリズム） 量子状態の重ね合わせを用いて因数分解アルゴリズムで必要となる「周期発見(period finding)」のプロセスを多項式時間で実行。 量子暗号（ＱＫＤ） 量子状態を用いることで、２者間での乱数の共有が可能となる。盗聴者は乱数を盗めない。認証が成立していれば、絶対安全性が保障されている。 非対称鍵暗号 Q Attack! Eve Bob Alice Eve

26 量子計算機にできることと、できないことをうまく組み合わせた計算量的量子認証プロトコルはできないか？
Q 研究の動機　1 量子計算機が存在している世の中を考える。 RSA暗号などの公開鍵暗号は安全ではない。 QKD（量子鍵分配）は安全であるが、Aliceが話している相手Bobが「なりすまし」をしているEveではないことの認証が必要。しかし、現在の認証には公開鍵暗号が使われている。（河内らの量子公開鍵暗号は認証にはつかえない） しかし、量子計算機も万能ではない。2次元のLocal Hamiltonian問題などのハミルトニアンの基底状態のエネルギーは、量子計算機を用いても効率よく見積もることができないことが知られている。(ただし答え合わせは可能) 量子計算機は暗号系にとってやはり脅威となりうる QMA（Quantum Merlin-Arthur)問題：NP問題の量子計算機版 量子計算機にできることと、できないことをうまく組み合わせた計算量的量子認証プロトコルはできないか？

27 量子認証プロトコルを目指して、新しいタイプの計算量に基づく秘匿量子計算を提案した。
研究の動機　２ “QuantumSoft” 量子計算機が存在している世の中を考える。 量子ソフトウェア会社の立場から 量子プログラム（量子ゲート列）は知的財産であり、勝手にコピーされては困る。コピー不可・正規ユーザのみ実行できるようにしたい。 末端ユーザーの立場から プログラムの中身を知る必要なく、実行できればよい。ただし、怪しいプログラムを実行したくないので、認証されたソフトウェア会社によるプログラムであることを確認したい。 Qwindows Q 二者間で非対称なプロトコル 量子認証プロトコルを目指して、新しいタイプの計算量に基づく秘匿量子計算を提案した。

28 我々の提案する秘匿量子計算 正規ユーザのみがプログラムを実行できる。 ユーザはプログラムの中身を読むことができない。
プログラムは認証局を通じて公開されている。 プログラマ：　量子計算のユニタリ変換を決定し、正規ユーザ用の量子鍵(quantum key)を生成 ユーザー：任意の入力を選んで、認証されたプログラムを実行できる。 既に提案されているクライアント・サーバタイプの秘匿量子計算(blind quantum computation)とは異なることに注意。 Qwindows Q 量子の不確定性 Q P. Arrighi and L. Salvail, Int. J. of Quantum Information 4, 883 (2006).

29 （量子）計算量的秘匿量子計算 認証されて公開された量子プログラムは、実行可能であるが読み出し不可能であるように暗号化されていないといけない。
この量子プログラムの解読には、量子計算機を使っても指数時間かかるならば、量子計算機があっても安全。 正規ユーザのための量子鍵は量子力学の不確定性によってコピー不可能 入力量子ビット数はn>>1 Qwindows 古典情報 |f> 認証局 Q 暗号化された量子プログラム U 入力 Q 量子情報 U|f> 正規ユーザーのための量子鍵 出力 ソフトウェア会社（プログラマ） ユーザ

30 基本原理 プログラム可能な量子プロセッサ* を利用して量子鍵|i>に応じてユニタリ変換 Ui を演算するような、より広いヒルベルト空間にかかる演算子Gを導入。 ランダム行列LとRを用いて量子鍵の暗号化を行う。　 G’のゲート列を難読化する。難読化とは、G’のゲート列の分解　　　　　　　　　　　 　　が簡単に見つからないようにG’のゲート列を表すことである。 　　難読化されたゲート列は、認証局を通じて公開される。 *M. A. Nielsen and I. L. Chuang, Phys. Rev. Lett. 79, 321 (1997). 量子情報 Q 量子鍵は未知状態となる 古典情報 Qwindows この過程に計算量的な難しさを押し込めている。

31 g(U): ユニタリ演算Uを表すゲート列全体の集合
ゲート構成の例 難読化 Shuffling algorithm ・・・ ・・・ ・・・ ・・・ ・・・ ・・・ S ・・・ ・・・ ・・・ ・・・ ・・・ ・・・ ・・・ は、ランダムユニタリ演算 g(U): ユニタリ演算Uを表すゲート列全体の集合 nが大きいとき, Uの行列表現を求めることは計算量的に困難となる.

32 安全性 秘匿量子演算の安全性は、難読化されたゲート列g(G’)からユニタリ変換Ui を抽出することの計算量的な難しさによる。
正規ユーザ用の量子鍵の情報　　　　と、認証局を通じて公開されたゲート列情報　x’g(G’) からUi を引き出すことが、量子計算機をもってしても多項式時間ではできない、ということを、量子証拠なしには多項式時間で解けないQMA完全問題であるnon-identity check 問題に還元して証明する。 秘匿量子計算でゲート列抽出ができるようなアルゴリズムがあるならば、 non-identity check 問題が多項式時間で解けてしまうことを示す。その対偶をとれば、安全性が証明できる。

33 2. 認証局が量子プログラムのゲート列情報 x’を公開
プロトコル 定義 : x’g(G’) はランダム難読化を行ったあとのゲート表現. Qwindows 3.　量子鍵の請求. 0. Ui からゲート列x’ を生成 Authenticator 1. x’を認証局に持って行く 公共通信路 2. 認証局が量子プログラムのゲート列情報 x’を公開 x’ 認証されていない 量子通信路 ユーザ プログラマ 5. プログラム実行. Q 4. 正規ユーザのための量子鍵を送信. ユーザーはR とLを知らないので、 x’ からUi を読み出すことはできないがUiを実行できる。 x’g(G’)を作成したプログラマのみが正規ユーザのための量子鍵を発行できる。

34 証明した定理 シャッフリングによって難読化したゲート列x’g(G’)に対して、
もし、x’ からR を抽出する多項式時間の量子アルゴリズム Aが存在するならば、 変形modified non-identity問題が量子証拠状態なしに多項式時間で解けてしまう。 →　対偶により、A はQMA困難である。 もし、x’ と量子鍵　　　　から量子鍵を消費することなくUi を実行する別のユニタリ変換Vi を抽出する多項式時間の量子アルゴリズムA1 が存在するならば、変形modified non-identity問題が量子証拠状態なしに多項式時間で解けてしまう。 →　対偶により、A はQMA困難である。

35 第二部のまとめ 新しいタイプの秘匿量子計算を提案.
この秘匿量子計算の安全性は、量子鍵の情報と難読化されたゲート列の情報から暗号化された量子計算を解読する量子計算量的な難しさ(QMA困難）によっている。 この秘匿量子計算は非対称プロトコルであり、量子認証プロトコルへと発展する可能性がある。 今回の証明は存在証明であり、実際に難読化を行うためのアルゴリズムはまだ知られていない。量子暗号として成立させるには、アルゴリズムの解析が必須である。

36 付録

37 エンタングルメントと 量子プロトコル

38 情報だけをどうやって送るか？ 状態を測定して、測定した情報（ビット）を送る。 古典的な状況 ゾウを送る必要はない！
そちらのゾウの色はピンクですか、黄色ですか？ パリのゾウの色と同じ色のコインを作りたい。 ピンクです! ゾウを送る必要はない！

39 量子情報をどうやって送るか？ f f 量子状態は、観測すると状態が変化する。未治量子状 態を観測によって知ることはできない。
古典の場合のような方法が使えない。 そこでエンタングルメントを用いてテレポーテーションする。 Alice Bob エンタングルメント 本体は送らずに、量子ゾウ の量子情報だけを通信 f f 量子コイン 量子ゾウ

40 エンタングルメントを用いた量子プロトコル
量子テレポーテーション 量子情報通信のもっとも基本的なプロトコル エンタングルメントと測定過程をうまく用いることで、物理的な 粒子（光や原子）を送らずに、量子情報のみを伝達する。 Y i,j テレポーテーション： エンタングルメントを通じて量子情報を送信 f ? f i,j Bob Alice   エンタングルメントなしでは、量子情報を高い精度でテレポーテーションによって送ることができないことが証明されている。 Theory: C.H. Bennett et al, Phys. Rev. Lett. 70, 1895 (1993) Experiment: Zeilinger and de Martini groups (1997), Kimble’s group (1998), Wineland and Blatt groups (2004)

41 数式からみたテレポーテーション 0. 初期状態: Bell測定による量子情報の入力 (測定後の状態は Fiのいずれか)
Alice Bob 0. 初期状態: Bell測定による量子情報の入力　　(測定後の状態は Fiのいずれか) 2. 　iの値を古典的通信路で送信 3. 　パウリ演算si を作用させて補正する。 4. 最終状態: 初期状態 ? 3 1 ? Bell Measurement   2 最終状態 ? 量子情報がAからBに「移った」と考えることができる。

42 テレクローニング テレポーテーションは量子情報をそのまま伝える。量子 情報をプロセスしつつその結果を送ることができるか？
エンタングルメント（テレクローンニング状態）を資源とし て用いて、量子最適クローニング演算とその結果の送信 を同時に行なうことができる。（遠隔情報処理） テレクローニング状態 Ａ Ｂ Ｃ Theory: M. Murao et al, Phys. Rev. A 59, (1999) Experiment: Furusawa’s group, Phys. Rev. Lett (2006)

43 量子最適クローニング これはユニタリ演算なので、量子コンピューターを用いれば、この量子情報処理を行なうことができる。 未知量子状態
クローン禁止原理 完全クローン 未知状態の量子ビットから完全なクローンを作ることはできないが、もとの状態に近い最適クローンを作ることはできる。 最適クローン １つのオリジナルから2つの最適クローンを作る場合には オリジナルと複製の量子ビットのほかに補助量子ビットが１つ必要 これはユニタリ演算なので、量子コンピューターを用いれば、この量子情報処理を行なうことができる。

44 テレクローニング 遠隔最適量子クローン演算 量子演算のユニタリー変換を多粒子エンタングルメントに「保存」することが可能となった最初の提案
最適クローニングのゲート演算 自体はクリッフォード演算ではない。補助入力ビットの部分の演算をうまくエンタングルメントに組み込むことによって遠隔量子演算が可能となった。

45 数式でみるテレクローニング 1→２テレクローニング状態 テレクローニングの際の状態変化 X・B・C それぞれの量子ビットに注目すると
テレクローン状態は量子コンピューターを使わずに生成することが可能。 1→２テレクローニング状態 テレクローニングの際の状態変化 ただし、最適クローン基底： X・B・C それぞれの量子ビットに注目すると 最適量子クローン状態 量子コンピューターなしに量子計算と同等のことができる！ Fidelity:　正しいコピーに対する忠実度

46 M. Murao et al, Phys. Rev. Lett. (2001)
　　 逆テレクローニング M. Murao et al, Phys. Rev. Lett. (2001) テレクローニングとは逆のプロセ ス（遠隔量子情報集約）を束縛さ れたエンタングル状態を用いて 実行する提案。 送信者達が協力した時のみ量 子情報が集約される。 ABCで共有する 最適クローン状態 Dでのオリジナル （集約された）状態 量子暗号鍵の安全な分配手段として使える可能性

47 数式でみる逆テレクローニング ロック可能な束縛エンタングル状態を資源として用いる。 where
束縛エンタングル状態のみでは量子情報を送ることができないが、送信者が協力して「出所が同じ状態」を送信することによって、「自由」なエンタングル状態が生じ、遠隔地に量子情報を集約することが可能となる。 このような状態を作ることができれば、量子コンピューターなしに逆クローニングが可能。

48 遠隔量子情報スイッチプロトコル 非対称なエンタングルメント用いることによって、量子情 報の条件付通信を行なう Charlie Bob
Alice 状況: アリスが許可を与えるならば、チャーリーからボブに量子情報を古典限界を超えて送ることができる. チャーリーはアリスに量子情報そのものを渡したくない。 アリスはボブに許可を与えたかどうかを、チャーリーに知られたくない。 アリスとボブとチャーリーの間で不公平に共有されたエンタングルメントを用いた量子プロトコル。

49 3者間の非対称なエンタングルメント共有 GHZ状態やW状態は対称 なエンタングル状態 次のような非対称なエンタ ングル状態を考える。
補助量子ビットとの間の 非対称エンタングルメント抽出 ancilla 何もしない C LOCC A B Ｃ C C A B A B Ａ Ｂ LOCC によるエンタングルメント抽出

50 非対称なエンタングルメント共有の条件 必要十分条件: Aが行う測定は、 BはAの測定結果に応じた1量子ビットユニタリ変換を行う ただし

51 混合状態の遠隔量子情報スイッチプロトコル
４量子ビットCluster状態のうち一つの量子ビットをなくし てしまった状態も、不公平エンタングルメントを持つ状態 Charlie Alice Bob Q 許可 測定 + 測定結果の通信 テレポーテーション 第一段階 第二段階 BC間のエンタングルメント確立

52 遠隔量子情報スイッチプロトコル 続き BC間のエンタングルメント破壊 テレポーテーション 測定 + 測定結果の通信
遠隔量子情報スイッチプロトコル　続き BC間のエンタングルメント破壊 テレポーテーション 第一段階 測定 + 測定結果の通信 第二段階 Charlie Alice Charlie 不許可 Q Bob Bob Aliceの許可無しには、CharlieとBobはエンタングルできない。 無理にCharlieとBobとでテレポーテーションを行った場合、Bobの受け取る状態の 信頼度は 2/3以下となり、古典限界を超えることができない。

53 Eveの関与を防ぐために 量子鍵プロトコルでは、量子鍵を持つAliceのみが許可の決定を 行うことができる必要がある。
EveがAliceの量子鍵にエンタングルすることで、EveがAliceより 先に許可/拒否の決定をしてしまう可能性がある。 Charlie, Alice, Bobが共有している状態が本当にrであるかを チェックする必要がある。 rをN個用意する。 ランダムにN-1個を選び　　　　　　で測定し、残った一つは許可/ 拒否に応じた測定を行う。 測定結果と、選んだ量子ビットをアナウンス CharlieとBobが　　　　　で測定し、Aliceの結果との整合性チェッ クをする。 整合性が確かめられたら、Charlieはテレポーテーションを行う。

54 秘匿量子計算の証明

55 Non-identity check 与えられたゲート列が恒等演算にほぼ近いか、そうではないかを判断する判定問題(Non-identity check)は、QMA完全の問題である。 D. Janzing, P. Wocjan, and T. Beth, Int. J. Quantum Inf. 3, 463 (2005), quant-ph/ ＝ ？

56 シャッフリングによる難読化 シャッフリングの定義 S:
多項式ステップによる の写像 ランダムシャッフリング: log[p(n)]個の固定したゲート数のゲート列表現の中でランダムにとってくる。 このi を多項式回ランダムに選ぶことにより, (p(n)-log[p(n)]+1)! タイプの組み合わせが得られる. g(G’) の集合からバラバラなゲート列をとってくることができる。∵) |g(G’)|<2Cp(n)< (p(n)-log[p(n)]+1)!

57 変形non-identity check問題
U をControlled-U （CUと書く）で置き換える。この置き換えは多項式時間で実行可能。 R L U … U … U … … … … これは量子計算機を用いても多項式時間ではできないはず. この二つを見分ける！

58 Proof for the algorithm A
Consider that the algorithm Apply A to a random shuffled gate sequence For U ≠ I, the algorithm A returns where i=0,1. We can check the matrix representation of Therefore, the statement is true: For U = I, note that where LR=L’R’ . By the random shuffling, we cannot extract R. Therefore, the statement is false. By comparing the actions of A on U, we can perform the non-identity check in polynomial time. Permutation of basis

59 Proof for the algorithm A1
This allows performing the unitary operation without consuming the authorization quantum key. Consider that the algorithm A1 The action of A1 is simulated by a unitary operation: Applying A1 to the following two cases: For U = I, For U ≠ I, the following actions of A1 are required: However since orthonotmal ancilla Distinguishable!