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

12.4

 注意事項

253

y -= N;

if (y < 0) {

y += N;

}

値

y

から

N

を減算し、符号を判定して、値をそのまま返すか、元の値に戻すかを決定します。従来

のコンピュータでは、この方法は適切ではないかもしれません。しかし、

QPU

では正しい答えが得ら

れます。このとき、デクリメント、インクリメント、そして比較の演算を用います。私たちの知ってい

るすべての論理演算が、

5

章の議論にあった

QPU

演算で実行されることになります。

（ある値

val

に関する）このメソッドによって剰余演算を実行するための回路を図 12-19 に示していま

す。

N

による剰余

図 12-19

この例では、単純な計算を実行するために複雑な演算を多数使用していますが、重ね合わせで剰余

の計算をすることができます。

図

12-19

の剰余演算の実装では、作業レジスタの符号ビットを隠すためにスクラッチキュ

ビットが

1

つ追加され、利用されます。これは条件付き加算で用いられます。

12.4.2

 時間対空間

前節で説明した剰余演算では、一般的な素因数分解の計算速度がかなり低下します。これは、主に

2

を乗ずる演算が

1

回に一度だけ実行されるからです。必要な操作数（したがって、全体的な演算時間）