量子アルゴリズムを用いた多項式GCDの計算その2

摘要

1　 はじめにGroverの量子探索アルゴリズム[2]は、オラクルf(x):{0,1}~n→{0，1}が与えられたときに、f(x）＝1をみたす解?を0（伸）回のJの評価で探し出すアルゴリズムである。これを古典的に解くには、O((2~n)~(1/2))回のJの評価が必要である。著者らは、Groverのアルゴリズムを、発見的な多項式GCDアルゴリズムであるGCDHEUアルゴリズム［1］へ応用することを考察した［4］。 GroveTのアルゴリズムは、解の存在率が低い場合に有効であるが、解の存在率が高いときには成功確率が下がってしまう欠点がある。 したがって、GCDHEUアルゴリズムで扱うような解の存在率が高い問題に対しては、Groverのアルゴリズムをそのままの形で応用することは得策でないといえる。