PowerPoint プレゼンテーション

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ゲート数最小回路(1)

ゲート数最小回路
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ゲート数最小回路(2)

C-NOTゲート数と量子回路計算量の関係について,
以下の結果を示した.




最小の量子回路と,C-NOTゲート数最小回路は,
回路サイズのオーダーが同じ.
C-NOT ゲートのみの回路のサイズは On2  .
2

.
O
n
C-NOTゲートとNOTゲートのみの回路のサイズも
出力可能なパターン数は,C-NOTゲートのみの場合の
高々 2 n 倍.
量子回路計算量の評価においては,C-NOTゲート数が
本質的であるが,一方,C-NOTゲートやNOTゲートのみ
では,単純な回路しか構成できない.
因数分解回路の設計(1)


因数分解のための効率的な古典アルゴリズム
は知られていないが,Shor は効率的な量子
アルゴリズムを提案した
Shor のアルゴリズムのための効率的な量子
回路は,量子計算機上でこのアルゴリズムを
実行するために有用である
Shor のアルゴリズムのための効率的な
量子回路の構成は極めて重要
因数分解回路の設計(2)

2n+2 個の量子ビットを使い,因数分解ア
ルゴリズムのための量子回路を構成した


[量子ビット数について効率的]
提案回路で使われる量子ビットは,従来回路
で使われる量子ビットと比較して,最も少ない
[サイズについて効率的]
提案回路のサイズは,2n+3 個の量子ビットを
使う Beauregard の回路の半分である
因数分解回路の設計(3)

提案回路は 2n+2 個の量子ビットを使う



QFT のために 1量子ビット
剰余乗算の中で, b , z , x を表現するため
に2n+1 個の量子ビット
提案回路のサイズは,Beauregard の回
路の約半分

QFT に基づく加算回路の数が,提案回路では,
Beauregard の回路の約半分
量子回路サイズの下界(1)


幾何学的手法を用いて,量子論理回路のサイズ
の下界に関する研究を進める.
参考文献
M.A. Nielsen,
“A geometric approach to quantum circuit
lower bounds”
(quant-ph/0502070, Feb. 2005)
量子回路サイズの下界(2)

定理(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 を基
底とする量子回路の最小サイズとする.
量子回路サイズの下界(3)

定理
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 の積項数とする.
量子回路サイズの下界(4)
1. 特定のブール関数に対応する U について,
d F I ,U  の強い下界を求めること.
1. 補助量子ビットが,回路計算量に及ぼす影
響を明らかにすること.
これまでの研究成果
論文
21
国際会議
31
口頭発表
132
量子コンピュータの実現研究
 様々な物理的実現に関する研究が行われている.
 2007年2月
カナダのD-Waveが
量子計算機の実用
化モデルを公開.
 16量子ビットを
備えていると主張
 2008年には1024量子
ビットを作る!?
© D-Wave
ご静聴、有難うございました。