動かして学ぶ量子コンピュータプログラミング ―シミュレータとサンプルコードで理解する基本アルゴリズム

242

12

章 ショアの素因数分解アルゴリズム

作業レジスタ

図12-8 

a

x



N



ステップ

3

：条件付きの

2

の乗算

精度レジスタ内の入力の重ね合わせに対して関数

a

x

mod(N)

を実行し、作業レジスタを使用してそ

の結果を保存することを考えます。ここで問題となるのはキュビットレジスタで

a

x

mod(N)

をどのよう

に実行するかということです。

以前に述べたように

a

＝

2

を選択し、その結果、関数の

a

x

部分が

2

x

になることを思い出してください。

つまり、関数のこの部分を実現するには、作業レジスタに

2

を乗ずる必要があります。この乗算を実行

する必要がある回数は

x

に等しくなります。ここで、

x

は精度レジスタにある

2

進法で表される値です。

2

（または実際に

2

の任意の累乗）の乗算は、単純なビットシフトによって任意のバイナリレジスタ上

で実行できます。この場合、

QCEngine

の

rollLeft()

メソッドを使って、各キュビットを次に大きな

重みを持つ位置と交換します。計

x

回の

2

の乗算を行うために、精度レジスタに含まれるキュビットの

値に応じた乗算を行います。

x

の値を表すために、精度レジスタ中で最も重みが小さい

2

つのキュビッ

ト の み を 使 用 す る こ と に 注 意 し て く だ さ い（ つ ま り 、

x

は値

0

、

1

、

2

、

3

をとることができる）。したがって、

12.3

 

整数

15

の素因数分解を

1

ステップずつ行う

243

この

2

つのキュビットのみに ...