B03 量子論理回路の最適化に関する研究西野哲朗，垂井淳，太田和夫，國廣昇電気通信大学情報通信工学科量子計算(1)    量子コンピュータのシステムの状態は、 2 n 次元複素ベクトル空間のベクトルで表される。 1 0  0  , 1   0  1 システムの状態は、あるユニタリ変換 U によって推移する。 ) UU( *  U *U  I U x  y 複合的な量子システムの状態空間は、その空間のテンソル積ベクトル空間で与えられる。量子計算(2)  状態 x と y の線形結合もまた、その空間の状態である。   x  y     1 2 この重ねあわせ状態を観測すると、 Pr x  2   2 , Pr y   2 が成り立つ。観測を行うと重ねあわせ状態は失われる。(波束の収縮) 基本的な量子ゲート  NOTゲート x {0,1} x  N N x  x x C-NOTゲート (Controlled-Not ゲート) x , y {0,1} x y C yx x , y  x , x  y x xy C-NOTゲート数最小回路（１）  ゲート数最小回路 mG U  : 基本ゲートの総数 c : C-NOTゲートの個数 s : 1qubitゲートの個数定理  C-NOTゲート数最小回路 g : 基本ゲート数の総数 mG U   mC U  mG U    OmC U  の証明 g  3mC U   n mc Uと  c  mG U 高々n個 mG U   したがって， g より   mC U  が成り立つ mG U mG U   OmC U    mC U  : C-NOTゲートの個数 s : 1qubitゲートの個数   1つのC-NOTゲートにつき高々2つの1量子ビットゲート C-NOTゲート数最小回路（２）  C-NOTゲート数と量子回路計算量の関係について，以下の結果を示した．     最小の量子回路と，C-NOTゲート数最小回路は，回路サイズのオーダーが同じ． C-NOT ゲートのみの回路のサイズは On2  ． 2  ． O n C-NOTゲートとNOTゲートのみの回路のサイズも出力可能なパターン数は，C-NOTゲートのみの場合の高々 2 n 倍．量子回路計算量の評価においては，C-NOTゲート数が本質的であるが，一方，C-NOTゲートやNOTゲートのみでは，単純な回路しか構成できない．因数分解回路の設計（１）   因数分解のための効率的な古典アルゴリズムは知られていないが，Shor は効率的な量子アルゴリズムを提案した Shor のアルゴリズムのための効率的な量子回路は，量子計算機上でこのアルゴリズムを実行するために有用である Shor のアルゴリズムのための効率的な量子回路の構成は極めて重要因数分解回路の設計（２）  2n+2 個の量子ビットを使い，因数分解アルゴリズムのための量子回路を構成した   [量子ビット数について効率的] 提案回路で使われる量子ビットは，従来回路で使われる量子ビットと比較して，最も少ない [サイズについて効率的] 提案回路のサイズは，2n+3 個の量子ビットを使う Beauregard の回路の半分である因数分解回路の設計（３）  提案回路は 2n+2 個の量子ビットを使う    QFT のために 1量子ビット剰余乗算の中で， b , z , x を表現するために2n+1 個の量子ビット提案回路のサイズは，Beauregard の回路の約半分  QFT に基づく加算回路の数が，提案回路では， Beauregard の回路の約半分量子回路サイズの下界（１）   幾何学的手法を用いて，量子論理回路のサイズの下界に関する研究を進める．参考文献 M.A. Nielsen, “A geometric approach to quantum circuit lower bounds” (quant-ph/0502070, Feb. 2005) 量子回路サイズの下界（２）  定理（Nielsen, 2005） n n を上の万能量子基底とし，を G SU 2  F SU 2  上のある条件を満たす計量とするとき， SU 2n  に属する任意の U に対して，以下が成り立つ． d F I ,U   mG U  ただし，d F I ,U  は， F を計量とする可微分多様体上における n 量子ビット恒等変換 I と U の距離， mG U  は，ユニタリ変換 U を実現する G を基底とする量子回路の最小サイズとする．量子回路サイズの下界（３）  定理 n n SU 2 SU 2 を上の万能量子基底とし，を上の F G ある条件を満たす計量とするとき，任意の n  1 変数ブール関数に対応するユニタリ変換 U に対して，以下が成り立つ．     d F I ,U   mG U   n  lG U   n  ESOPU  ただし，lG U  は，ユニタリ変換 U を実現する G を基底とする量子回路で，前述の条件を満たすものの最小の深さとし， ESOPU  は， U に対応する n  1 変数ブール関数の最小 ESOP の積項数とする．量子回路サイズの下界（４） 1. 特定のブール関数に対応する U について， d F I ,U  の強い下界を求めること． 1. 補助量子ビットが，回路計算量に及ぼす影響を明らかにすること．これまでの研究成果論文２１国際会議３１口頭発表１３２量子コンピュータの実現研究  様々な物理的実現に関する研究が行われている．  2007年2月カナダのD-Waveが量子計算機の実用化モデルを公開．  16量子ビットを備えていると主張  2008年には1024量子ビットを作る!? © D-Wave ご静聴、有難うございました。