B03 量子論理回路の 最適化に関する研究 西野哲朗，垂井淳，太田和夫，國廣昇 電気通信大学　情報通信工学科.

Presentation on theme: "B03 量子論理回路の 最適化に関する研究 西野哲朗，垂井淳，太田和夫，國廣昇 電気通信大学　情報通信工学科."— Presentation transcript:

1 B03 量子論理回路の 最適化に関する研究 西野哲朗，垂井淳，太田和夫，國廣昇 電気通信大学　情報通信工学科

2 量子計算(1) 量子コンピュータのシステムの状態は、 次元複素ベクトル空間のベクトルで表される。
量子コンピュータのシステムの状態は、　　次元複素ベクトル空間のベクトルで表される。 システムの状態は、あるユニタリ変換 　　によって推移する。 (　　　　　　　　　　) 複合的な量子システムの状態空間は、その空間のテンソル積ベクトル空間で与えられる。

3 量子計算(2) 状態 と の線形結合もまた、その空間の状態である。 この重ねあわせ状態を観測すると、 が成り立つ。
状態　　　と　　 の線形結合もまた、その空間の状態である。 この重ねあわせ状態を観測すると、 が成り立つ。 観測を行うと重ねあわせ状態は失われる。(波束の収縮)

4 基本的な量子ゲート NOTゲート N C-NOTゲート (Controlled-Not ゲート)

5 C-NOTゲート数最小回路（１） ゲート数最小回路 C-NOTゲート数最小回路 定理 の証明 の証明 したがって， が成り立つ
基本ゲート数の総数 基本ゲートの総数 C-NOTゲートの個数 C-NOTゲートの個数 1qubitゲートの個数 1qubitゲートの個数 定理 の証明 の証明 河内さんに言われた条件を書くこと 高々n個 1つのC-NOTゲートにつき 高々2つの1量子ビットゲート と したがって， が成り立つ より

6 C-NOTゲート数最小回路（２） C-NOTゲート数と量子回路計算量の関係について， 以下の結果を示した．
C-NOTゲートとNOTゲートのみの回路のサイズも　　　　　． 出力可能なパターン数は，C-NOTゲートのみの場合の 高々　　倍． 量子回路計算量の評価においては，C-NOTゲート数が本質的であるが，一方，C-NOTゲートやNOTゲートのみでは，単純な回路しか構成できない．

7 因数分解回路の設計（１） 因数分解のための効率的な古典アルゴリズムは知られていないが，Shor は効率的な量子アルゴリズムを提案した
量子回路の構成は極めて重要

8 因数分解回路の設計（２） 2n+2 個の量子ビットを使い，因数分解アルゴリズムのための量子回路を構成した
[量子ビット数について効率的] 　　　　　　　　　提案回路で使われる量子ビットは，従来回路で使われる量子ビットと比較して，最も少ない [サイズについて効率的] 　　　　　　　　　　　　提案回路のサイズは，2n+3 個の量子ビットを使う Beauregard の回路の半分である

9 因数分解回路の設計（３） 提案回路は 2n+2 個の量子ビットを使う 提案回路のサイズは，Beauregard の回路の約半分
QFT のために 1量子ビット 剰余乗算の中で， 　　　　　　　を表現するために2n+1 個の量子ビット 提案回路のサイズは，Beauregard の回路の約半分 QFT に基づく加算回路の数が，提案回路では，Beauregard の回路の約半分

10 量子回路サイズの下界（１） 幾何学的手法を用いて，量子論理回路のサイズの下界に関する研究を進める．
参考文献 M.A. Nielsen, “A geometric approach to quantum circuit lower bounds” (quant-ph/ , Feb. 2005)

11 量子回路サイズの下界（２） 定理（Nielsen, 2005） 　　を　　　　 上の万能量子基底とし，　を　　　 上のある条件を満たす計量とするとき，　　　　 に属する任意の　　に対して，以下が成り立つ． ただし，　　　　　は，　　を計量とする可微分多様体上における　 量子ビット恒等変換　　と　　の距離，　　　　は，ユニタリ変換　　を実現する　　を基底とする量子回路の最小サイズとする．

12 　 量子回路サイズの下界（３） 定理 　　 を　　　　　上の万能量子基底とし，　　を　　　　　上のある条件を満たす計量とするとき，任意の　　　 変数ブール関数に対応するユニタリ変換　　 に対して，以下が成り立つ． ただし，　　　 は，ユニタリ変換　　 を実現する　　を基底とする量子回路で，前述の条件を満たすものの最小の深さとし，　　　　　　　は，　　に対応する　　　　変数ブール関数の最小 ESOP の積項数とする．

13 量子回路サイズの下界（４） 特定のブール関数に対応する について， の強い下界を求めること．
特定のブール関数に対応する　　について，　　　　　　　 　　　　　　　　の強い下界を求めること． 補助量子ビットが，回路計算量に及ぼす影響を明らかにすること．

14 これまでの研究成果 論文 国際会議 口頭発表 ２１ ３１ １３２

15 量子コンピュータの実現研究 様々な物理的実現に関する研究が行われている．
2007年2月 カナダのD-Waveが量子計算機の実用化モデルを公開． 16量子ビットを 備えていると主張 2008年には1024量子 ビットを作る!? © D-Wave

16 ご静聴、有難うございました。