詳細解説レポート

Factoring with \(n+2\) clean qubits and \(n-1\) dirty qubits

Craig Gidney, Google, 2018年1月版。Shor の factoring に必要な clean qubit 数を、dirty ancilla を使って \(1.5n+O(1)\) から \(n+2\) へ下げる回路構成の詳細。

\(n+2\)

clean qubits

\(n-1\)

dirty qubits

\(2n+1\)

total qubits

\(O(n^3\lg n)\)

gates; depth \(O(n^3)\)

0. 結論: この論文が実現したこと

この論文の主張は明確である。\(n\)-bit の整数 \(R\) を Shor のアルゴリズムで因数分解する周期発見回路について、必要な clean qubit を \(n+2\) 本まで下げられる。ただし、そのために \(n-1\) 本の dirty qubit を借りる。総 qubit 数は \(2n+1\) であり、これは clean qubit 数の改善であって、総 qubit 数だけを見ると Zalka の \(1.5n+O(1)\) より多い。

最終構成の内訳: phase-estimation qubit 1本、work register \(n\) 本、modular multiplication 用の補助 register \(n\) 本である。補助 register の MSB 1本だけを clean \(|0\rangle\) にし、残り \(n-1\) 本を dirty とする。よって clean は \(1+n+1=n+2\)、dirty は \(n-1\)、total は \(2n+1\)。

計算量は先行する Toffoli-based な \(2n+2\) qubit 構成と同じ漸近次数で、gates は \(O(n^3\lg n)\)、depth は \(O(n^3)\)。この維持が重要で、dirty ancilla を使ったからといって漸近的な時間・サイズを悪化させない。

中心的なアイデアは次の3つである。

pivot-flip によって modular addition / offset を dirty ancilla だけで構成する。
dirty bimultiplication によって、補助 register が clean でなくても modular multiplication を実現する。
1 dirty ancilla の \(O(n)\) incrementer によって、offset や larger-target addition の下位構成を線形サイズに保つ。

実用上の注意: 著者は、この構成が T gate 数やアーキテクチャ制約の観点で最適化されていないと明言している。all-to-all connectivity を仮定し、定数因子はかなり悪い。例として controlled 32-qubit multiplication はおよそ 130 万 Toffoli gates とされ、先行研究より一桁以上重い。

1. 記号・前提・回路図の読み方

記号	意味	注意
\(R\)	因数分解対象であり、modular arithmetic の modulus。	本文では \(R\) を奇数と仮定する。偶数因子 2 は古典的に除去できる。
\(n\)	\(R\) を格納するのに必要な bit 数。\(n=\lceil \lg R\rceil\)。	最小サイズ register を使う。
\(B\)	Shor の base。ランダムに選ぶ。	\(\gcd(B,R)=1\) が必要。そうでなければ gcd が因子を与える。
\(K\)	compile-time constant。multiplier や offset。	modular multiplication では \(K^{-1}\bmod R\) が必要。
\(c\)	control qubit 数。	bundle control は bundle 内の全 wire が on の場合に条件成立。
\(p\)	phase estimation precision。	\(p\in\Theta(n)\)。半古典的 QFT により物理 qubit は1本へ削減。
\(m=n+e\)	target register が input より大きい場合の target size。	pivot-flip with enregistered pivot などで使う。
clean ancilla	既知の computational basis state、典型的には \(\|0\rangle\)、で渡される補助 qubit。	回路の作りやすさ・コンパクトさのために価値が高い。
dirty ancilla	未知で、場合によっては外部と entangled している補助 qubit。	使い終わるまでに厳密に元の状態へ戻す必要がある。

算術表現

全構成は two's-complement 表現を使う。register size を超える非 modular 算術は wrap し、実際には \(2^n\) を法として動作する。したがって ordinary addition は

\[ |x\rangle|y\rangle \longmapsto |x\rangle|y+x \pmod {2^n}\rangle. \]

一方、modular arithmetic は \(R\) を法とする。ただし論文は 範囲外入力に対する動作を定義しない。例えば modular addition \(x += y \pmod R\) に \(y\ge R\) を入れた場合、\(y\bmod R\) が足されるとは保証しない。最適化により動作が変わっても構わないという扱いで、C 言語の undefined behavior に近い。

図の規約

wire は LSB が上、MSB が下。
三角形の注記は必要な clean / dirty ancilla 数を表す。緑は図中の未使用 wire で要求が満たされることを示す。
灰色の “Input A” は、その operation 開始時点の input register 値を指す。別々の operation の “A” は同じ値とは限らない。
“+K” は compile-time constant を足す offset、 “+A” は register の値を足す enregistered addition。
単一 qubit gate が wire bundle に描かれると、bundle 内の各 wire へ個別に作用する。

2. Shor の周期発見と、この論文での置換

2.1 まず base を選ぶ

古典的にランダムな \(B\) を選ぶ。もし \(\gcd(B,R)\ne 1\) なら、それ自体が非自明因子を与えるため、量子回路を走らせる必要がない。\(\gcd(B,R)=1\) の場合にだけ、\(x\mapsto Bx\bmod R\) の周期を量子的に推定する。

2.2 period finding の量子部分

概念的には phase register に一様重ね合わせを作り、work register に modular exponentiation をかける。

\[ |a\rangle|1\rangle \longmapsto |a\rangle|B^a \bmod R\rangle. \]

周期を \(\ell\) とすると、modular exponentiation 後の phase register は周期 \(\ell\) の同値類に分かれる。QFT をかけると、スペクトルは概ね

\[ N\cdot 0/\ell, N\cdot 1/\ell, N\cdot 2/\ell, \ldots \]

付近にピークを持つ。測定値 \(s_i\) から、分母が \(

2.3 phase register を1 qubit にする

通常の QFT の直後に全 qubit を測るなら、各 qubit はもっと早く測定できる。測定結果に応じて後続の rotation を古典制御する半古典的 QFT を使うと、phase-estimation register 全体は1本の qubit を繰り返し reset して使えばよい。図3の X-axis control は Hadamard で挟んだ control と同値で、通常の \(|1\rangle\) ではなく \((|0\rangle-|1\rangle)/\sqrt2\) へ条件付ける。

2.4 なぜ bimultiplication が必要か

通常の modular multiplication は、補助 register を clean にしやすい。しかし本論文では補助 register の大部分を dirty にしたい。そこで、単に work を \(K\) 倍するのではなく、もう一方の register に逆倍率をかける bimultiplication を使う。

\[ (x,y) \longmapsto (xK,\; yK^{-1}) \pmod R. \]

これにより dirty register は途中で変化するが、work register は \(|1\rangle\) から始まり、最後に測定される。測定された work の値から dirty register に蓄積された逆倍率を古典的に知り、cleanup multiplication をかけて dirty register を元に戻す。

3. qubit 会計: どこに何本使うか

役割	本数	clean / dirty	説明
phase-estimation qubit	1	clean	半古典的 QFT により1本を reset して再利用。
work register	\(n\)	clean	\(\|0\rangle^{\otimes n}\) から \(+1\) して \(\|1\rangle\) にする。最終的に測定され、dirty cleanup factor を与える。
multiplication auxiliary register の MSB	1	clean	補助 register の値を確実に \(
multiplication auxiliary register の残り	\(n-1\)	dirty	未知状態で借りるが、bimultiplication と cleanup により最後に復元する。

\[ Q_{\mathrm{clean}} = 1+n+1 = n+2,\qquad Q_{\mathrm{dirty}} = n-1,\qquad Q_{\mathrm{total}} = 2n+1. \]

Interactive: n-bit modulus の qubit 数

\(n\)

概念図の \(p\)

\(p\) は図2の概念的な phase register 幅。最終構成では phase qubit は1本にリサイクルされる。

4. 計算量の合成: なぜ \(O(n^3\lg n)\) gates / \(O(n^3)\) depth か

この論文のコストは bottom-up に見ると分かりやすい。

constant offset は \(O(n\lg n)\) gates、\(O(n)\) depth、1 dirty。
pivot-flip は comparison と bi-flip を使い、constant pivot では \(O(c+n\lg n)\) gates、\(O(c+n)\) depth、2 dirty。
modular addition / offset は3つの pivot-flip で構成され、同じく \(O(c+n\lg n)\) gates、\(O(c+n)\) depth。
modular doubling は offset と bit rotation で構成され、\(O(c+n\lg n)\) gates、\(O(c+n)\) depth。
modular scale-add は shift-and-add で、\(n\) 回の modular add/offset と \(2n-2\) 回程度の double/halve を使う。したがって \(O(c+n^2\lg n)\) gates、\(O(c+n^2)\) depth。
modular bimultiplication は3回の modular scale-add、swap、negation からなり、\(O(c+n^2\lg n)\) gates、\(O(c+n^2)\) depth。
period finding では \(p\in\Theta(n)\) 個の制御乗算を使うため、全体で \(O(n^3\lg n)\) gates、\(O(n^3)\) depth。

\[ \Theta(n)\ \text{multiplications} \times O(n^2\lg n)\ \text{gates per multiplication} = O(n^3\lg n). \]

ここでいう gates は、multi-control / multi-target operations を NOT, CNOT, CCNOT（Toffoli）などの定数サイズ gate へ落とした後の漸近数である。T gate synthesis や error-corrected architecture の routing cost は本論文の最適化対象ではない。

5. 回路カタログ: qubit 数・ancilla・計算量一覧

下表は論文中の全主要構成を、図番号、作用、使用 register、追加 ancilla、gate 数、depth、条件で整理したものである。control qubits は “追加 ancilla” ではなく、呼び出し元の既存 wire として数えている。

検索 / filter

図	回路 / 作用	使用 qubits / registers	追加 ancilla	gates	depth	条件
Fig. 2	高レベル period finding / modular exponentiation 位相レジスタの値 A に対し work を \( \|1\rangle \mapsto \|B^A \bmod R\rangle \) にする。最後に inverse QFT と測定で周期を推定する。	概念図では phase \(p\) 本 + work \(n\) 本。乗算サブルーチンの背後に \(n\) 本の補助レジスタが必要。	乗算のために \(n-1\) dirty + 1 clean。	最終構成を使うと \(O(n^3\lg n)\)。	\(O(n^3)\)。	\(p\in\Theta(n)\)、\(B\) は \(R\) と互いに素。
Fig. 3	1量子ビット phase-estimation period finding 半古典的 QFT により、phase register 全体を保持せず、1本を測定・リセット・再利用する。	phase 1本 + work \(n\) 本 + 乗算用 \(n\) 本補助。	乗算ごとに \(n-1\) dirty + 1 clean を借りる。	図4の最終 bimultiplication 構成で \(O(n^3\lg n)\)。	図4の最終構成で \(O(n^3)\)。	測定結果に応じた X-axis rotation と reset を許す。
Fig. 4	最終 period finding with dirty bimultiplications 各制御乗算を paired inverse multiplication に置換し、最後に測定した work の値から dirty register を復元する。	phase 1 + work \(n\) + 補助 register \(n\)。補助 register の MSB は clean、残り \(n-1\) は dirty。	追加なし。総計 clean \(n+2\)、dirty \(n-1\)、total \(2n+1\)。	\(O(n^3\lg n)\)。	\(O(n^3)\)。	\(R\) は奇数、全 modular 入力は \(
Fig. 5	Controlled modular bimultiplication \((x,y)\mapsto (xK,\;yK^{-1})\pmod R\)。	control \(c\) + 2つの \(n\)-bit registers、合計 \(c+2n\) 本。	追加なし。内部の modular negation は 2 dirty を要するが、他方の register の空き線を借りる。	\(O(c+n^2\lg n)\)。	\(O(c+n^2)\)。	\(K^{-1}\pmod R\) が存在すること。存在しなければ \(K\) と \(R\) は非自明 gcd を持つ。
Fig. 6	Controlled modular scaled-addition \((x,y)\mapsto (x,\;y+Kx\bmod R)\)。	control \(c\) + input \(n\) + target \(n\)、合計 \(c+2n\) 本。	追加なし。subroutine が必要とする dirty は未使用線から満たされる。	\(O(c+n^2\lg n)\)。	\(O(c+n^2)\)。	\(R\) は奇数。
Fig. 7	Controlled modular doubling \(x\mapsto 2x\pmod R\)。逆は modular halving。	control \(c\) + target \(n\)、追加 dirty 1本。総計 \(c+n+1\) 本。	1 dirty。	\(O(c+n\lg n)\)。	\(O(c+n)\)。	\(R\) は奇数。入力は \(
Fig. 8	Pivot-flip with enregistered pivot pivot \(A\) 未満の target states だけを反転: \(\|i\rangle\mapsto \|A-i-1\rangle\) for \(i	control \(c\) + pivot input \(n\) + target \(m=n+e\)。target は pivot より小さくできない。	2 dirty。総計 \(c+n+m+2\) 本。	\(O(c+m\lg m)\)。	\(O(c+m)\)。	\(m\ge n\)。
Fig. 9	Pivot-flip with constant pivot 定数 pivot \(K\) 未満だけを反転する \(\mathrm{PivotFlip}_K\)。	control \(c\) + target \(n\)。	2 dirty。総計 \(c+n+2\) 本。	\(O(c+n\lg n)\)。	\(O(c+n)\)。	\(0\le K\le 2^n\)。
Fig. 10-11	Controlled modular addition \((a,x)\mapsto(a,\;x+a\bmod R)\)。図10の原理は pivot \(R-A, R, A\) の3回。	control \(c\) + input \(n\) + target \(n\)。	\(\max(0,2-c)\) dirty。control 自身を dirty として借りられる。	\(O(c+n\lg n)\)。	\(O(c+n)\)。	\(A\le R\)、modular 入力は \(
Fig. 12	Controlled modular offset \(x\mapsto x+K\pmod R\) for compile-time constant \(K\)。	control \(c\) + target \(n\)。	2 dirty。control があっても constant 版では2 dirty が必要。総計 \(c+n+2\)。	\(O(c+n\lg n)\)。	\(O(c+n)\)。	入力 \(
Fig. 13	Controlled modular negation \(x\mapsto -x\pmod R\)。	control \(c\) + target \(n\)。	2 dirty。総計 \(c+n+2\)。	\(O(c+n\lg n)\)。	\(O(c+n)\)。	入力 \(
Fig. 14	Controlled comparison 入力関係、例 \(B	register-register なら control \(c\)+2つの \(n\)-bit input+target bit。constant 比較なら input \(n\)+target bit。	register-register: uncontrolled は0、controlled は1 dirty。constant 比較はさらに1 dirty、図14の汎用表記は2 dirty。	register-register: \(O(c+n)\)。constant 比較: \(O(c+n\lg n)\)。	\(O(c+n)\)。	overflow bit だけを残し、加算後に小さな減算で uncompute する。
Fig. 15	Same-size adder \((a,b)\mapsto(a,\;b+a\bmod 2^n)\)。	input \(n\)+target \(n\)、合計 \(2n\)。	0。	\(O(n)\)。	\(O(n)\)。	input と target が同じサイズ。target が小さい場合は上位 bit を overflow として無視できる。
Fig. 16	Offset circuit \(x\mapsto x+K\bmod 2^n\) for compile-time constant \(K\)。	target \(n+e\)、\(e\in\{0,1\}\)。	1 dirty。総計 \(n+e+1\)。	\(O(n\lg n)\)。	\(O(n)\) by overlapping recursive cases。	constant offset。
Fig. 17	Adder with larger target \((a,b)\mapsto(a,\;b+a)\) where target has extra high bits。	input \(n\)+target \(n+e\)。	追加0。increment/decrement は未使用線を dirty として借りる。	\(O(n)\)。	\(O(n)\)。	larger target。increment 構成は same-size adder だけを内部で使い、循環依存を避ける。
Fig. 18	Controlled addition / controlled offset via commutator control が on のときだけ \(+A\) または \(+K\) を作用させる。	control \(c\)+input \(n\)+target \(m\) for addition; offset は input 不要。	controlled addition: 1 dirty。controlled offset: 2 dirty。	addition: \(O(c+m)\)。offset: \(O(c+m\lg m)\)。	\(O(c+m)\)。	\(m>n\) の larger-target addition にも適用。
Fig. 19	Increment using n dirty bits \(t\mapsto t+1\bmod 2^n\)。	target \(n\)+dirty \(n\)。	n dirty。	\(O(n)\)。	\(O(n)\)。	任意の dirty register \(x\) を借りられる。
Fig. 20	Controlled increment with one dirty bit control が on のとき \(t\mapsto t+1\bmod 2^n\)。	control \(c\)+target \(n\)+dirty 1。	1 dirty。	\(O(c+n)\)。	\(O(c+n)\)。	odd-size register の構成を基本に、even-size は LSB を分離して残りを controlled increment し、LSB を toggle。
Fig. 21	Quantum bootstrap for increment phase-gradient を使って increment の dirty ancilla 要求を量子操作で bootstrapping する。	target register と phase-gradient 用の一時操作。	bottleneck では不要な改善。classical では1 dirty 最小だが quantum では ancilla なしが可能。	小角 rotation 合成のため asymptotic と定数が悪化し得る。論文の主コスト集計には採用しない。	構成依存。	\(Z^{2^{-k}}\) 型の小角位相 gate を使う。
Fig. 22	Controlled bit rotation / bit swap bit order の rotation または swap。	control \(c\)+target \(n\)。	0。	\(O(c+n)\)。	\(O(c+n)\)。	controlled の場合は実 gate が必要。uncontrolled permutation は wire relabeling で済むことが多い。
Fig. 23	Inline controlled bit order reversal odd \(n=2k+1\) または even \(n=2k+2\) の register で bit order を反転。	control \(c\)+target \(n\)。	0。	\(O(c+n)\)。	\(O(c+n)\)。	XOR 操作は独立 CNOT の列。input と output の endian が逆。
Fig. 24	Many-control many-target CNOT 全 controls が on のとき、複数 target をまとめて toggle。	control \(c\)+target \(t\)。	0。	\(O(c+t)\)。	\(O(c+t)\)、toggle を賢く拡散すれば \(O(c+\lg t)\)。	まず1 target に many-control NOT を作用させ、その toggle を CNOT 群で広げる。
Fig. 25	Many-control NOT to Toffoli gates \(c\)-control NOT を constant-size Toffoli gates に分解。	control \(c\)+target 1 + dirty \(c-2\)。	\(c-2\) dirty。1 dirty だけで2倍程度の Toffoli 数にする方法もあるが本構成では不要。	明示値 \(4c-8\) Toffoli gates。	線形規模。	period finding 文脈では十分な未使用 qubits を借りられる。

6. 各回路の詳細説明

6.1 dependency graph の全体像

論文の Figure 1 は、上位 operation がどの下位構成に依存するかを示す。依存はおおむね次の階層である。

左のノードをクリックすると、依存関係とコスト上の役割を表示する。

6.2 回路ごとの詳細カード

Fig. 2 高レベル period finding / modular exponentiation

作用

位相レジスタの値 A に対し work を \( |1\rangle \mapsto |B^A \bmod R\rangle \) にする。最後に inverse QFT と測定で周期を推定する。

量子ビット / register

概念図では phase \(p\) 本 + work \(n\) 本。乗算サブルーチンの背後に \(n\) 本の補助レジスタが必要。

ancilla

乗算のために \(n-1\) dirty + 1 clean。

計算量

gates: 最終構成を使うと \(O(n^3\lg n)\)。
depth: \(O(n^3)\)。

条件・注意

\(p\in\Theta(n)\)、\(B\) は \(R\) と互いに素。

図2は概念図で、図3・図4で phase register を1量子ビットにリサイクルする。

Fig. 3 1量子ビット phase-estimation period finding

作用

半古典的 QFT により、phase register 全体を保持せず、1本を測定・リセット・再利用する。

量子ビット / register

phase 1本 + work \(n\) 本 + 乗算用 \(n\) 本補助。

ancilla

乗算ごとに \(n-1\) dirty + 1 clean を借りる。

計算量

gates: 図4の最終 bimultiplication 構成で \(O(n^3\lg n)\)。
depth: 図4の最終構成で \(O(n^3)\)。

条件・注意

測定結果に応じた X-axis rotation と reset を許す。

X-axis control は Hadamard で挟んだ通常 control と同値で、\((|0\rangle-|1\rangle)/\sqrt2\) に条件付ける。

Fig. 4 最終 period finding with dirty bimultiplications

作用

各制御乗算を paired inverse multiplication に置換し、最後に測定した work の値から dirty register を復元する。

量子ビット / register

phase 1 + work \(n\) + 補助 register \(n\)。補助 register の MSB は clean、残り \(n-1\) は dirty。

ancilla

追加なし。総計 clean \(n+2\)、dirty \(n-1\)、total \(2n+1\)。

計算量

gates: \(O(n^3\lg n)\)。
depth: \(O(n^3)\)。

条件・注意

\(R\) は奇数、全 modular 入力は \(

本論文の主結果。通常なら捨てる work register を測定して fixup factor を得る。

Fig. 5 Controlled modular bimultiplication

作用

\((x,y)\mapsto (xK,\;yK^{-1})\pmod R\)。

量子ビット / register

control \(c\) + 2つの \(n\)-bit registers、合計 \(c+2n\) 本。

ancilla

追加なし。内部の modular negation は 2 dirty を要するが、他方の register の空き線を借りる。

計算量

gates: \(O(c+n^2\lg n)\)。
depth: \(O(c+n^2)\)。

条件・注意

\(K^{-1}\pmod R\) が存在すること。存在しなければ \(K\) と \(R\) は非自明 gcd を持つ。

3回の modular scale-add と swap と negation で実装。dirty register に逆倍率をかける点が核心。

Fig. 6 Controlled modular scaled-addition

作用

\((x,y)\mapsto (x,\;y+Kx\bmod R)\)。

量子ビット / register

control \(c\) + input \(n\) + target \(n\)、合計 \(c+2n\) 本。

ancilla

追加なし。subroutine が必要とする dirty は未使用線から満たされる。

計算量

gates: \(O(c+n^2\lg n)\)。
depth: \(O(c+n^2)\)。

条件・注意

\(R\) は奇数。

\(n-1\) 回の modular halving、\(n\) 回の条件付き modular add/offset、\(n-1\) 回の modular doubling による shift-and-add。

Fig. 7 Controlled modular doubling

作用

\(x\mapsto 2x\pmod R\)。逆は modular halving。

量子ビット / register

control \(c\) + target \(n\)、追加 dirty 1本。総計 \(c+n+1\) 本。

ancilla

1 dirty。

計算量

gates: \(O(c+n\lg n)\)。
depth: \(O(c+n)\)。

条件・注意

\(R\) は奇数。入力は \(

範囲を offset で整列させ、MSB toggle と bit rotation で上半分・下半分を interleave する。

Fig. 8 Pivot-flip with enregistered pivot

作用

pivot \(A\) 未満の target states だけを反転: \(|i\rangle\mapsto |A-i-1\rangle\) for \(i

量子ビット / register

control \(c\) + pivot input \(n\) + target \(m=n+e\)。target は pivot より小さくできない。

ancilla

2 dirty。総計 \(c+n+m+2\) 本。

計算量

gates: \(O(c+m\lg m)\)。
depth: \(O(c+m)\)。

条件・注意

\(m\ge n\)。

bi-flip と比較を toggle-control で組み合わせ、pivot 未満にだけ bi-flip を1回作用させる。

Fig. 9 Pivot-flip with constant pivot

作用

定数 pivot \(K\) 未満だけを反転する \(\mathrm{PivotFlip}_K\)。

量子ビット / register

control \(c\) + target \(n\)。

ancilla

2 dirty。総計 \(c+n+2\) 本。

計算量

gates: \(O(c+n\lg n)\)。
depth: \(O(c+n)\)。

条件・注意

\(0\le K\le 2^n\)。

constant comparison と offset を使うため、constant 版は \(\lg n\) overhead を持つ。

Fig. 10-11 Controlled modular addition

作用

\((a,x)\mapsto(a,\;x+a\bmod R)\)。図10の原理は pivot \(R-A, R, A\) の3回。

量子ビット / register

control \(c\) + input \(n\) + target \(n\)。

ancilla

\(\max(0,2-c)\) dirty。control 自身を dirty として借りられる。

計算量

gates: \(O(c+n\lg n)\)。
depth: \(O(c+n)\)。

条件・注意

\(A\le R\)、modular 入力は \(

一時的に input register は \(x\) から \(R-x\) を格納する形へ移る。

Fig. 12 Controlled modular offset

作用

\(x\mapsto x+K\pmod R\) for compile-time constant \(K\)。

量子ビット / register

control \(c\) + target \(n\)。

ancilla

2 dirty。control があっても constant 版では2 dirty が必要。総計 \(c+n+2\)。

計算量

gates: \(O(c+n\lg n)\)。
depth: \(O(c+n)\)。

条件・注意

入力 \(

3つの constant pivot-flip: \(R-K\), \(R\), \(K\)。

Fig. 13 Controlled modular negation

作用

\(x\mapsto -x\pmod R\)。

量子ビット / register

control \(c\) + target \(n\)。

ancilla

2 dirty。総計 \(c+n+2\)。

計算量

gates: \(O(c+n\lg n)\)。
depth: \(O(c+n)\)。

条件・注意

入力 \(

decrement で \(|0\rangle\) を退避し、pivot \(R-1\) で flip し、increment で戻す。

Fig. 14 Controlled comparison

作用

入力関係、例 \(B

量子ビット / register

ancilla

計算量

gates: register-register: \(O(c+n)\)。constant 比較: \(O(c+n\lg n)\)。
depth: \(O(c+n)\)。

条件・注意

overflow bit だけを残し、加算後に小さな減算で uncompute する。

dirty \(n\) 本があれば Häner et al. の overflow-predicting 構成で定数因子を改善できる。

Fig. 15 Same-size adder

作用

\((a,b)\mapsto(a,\;b+a\bmod 2^n)\)。

量子ビット / register

input \(n\)+target \(n\)、合計 \(2n\)。

ancilla

0。

計算量

gates: \(O(n)\)。
depth: \(O(n)\)。

条件・注意

input と target が同じサイズ。target が小さい場合は上位 bit を overflow として無視できる。

Takahashi-Kunihiro / Van Rentergem-De Vos 型の ancilla-free adder。

Fig. 16 Offset circuit

作用

\(x\mapsto x+K\bmod 2^n\) for compile-time constant \(K\)。

量子ビット / register

target \(n+e\)、\(e\in\{0,1\}\)。

ancilla

1 dirty。総計 \(n+e+1\)。

計算量

gates: \(O(n\lg n)\)。
depth: \(O(n)\) by overlapping recursive cases。

条件・注意

constant offset。

Häner-Roetteler-Svore の offset circuit。constant 加算は register 加算より高価。

Fig. 17 Adder with larger target

作用

\((a,b)\mapsto(a,\;b+a)\) where target has extra high bits。

量子ビット / register

input \(n\)+target \(n+e\)。

ancilla

追加0。increment/decrement は未使用線を dirty として借りる。

計算量

gates: \(O(n)\)。
depth: \(O(n)\)。

条件・注意

larger target。increment 構成は same-size adder だけを内部で使い、循環依存を避ける。

carry-propagating CNOT を controlled increment に置換し、MSB 由来の誤った LSB increment を補正する。

Fig. 18 Controlled addition / controlled offset via commutator

作用

control が on のときだけ \(+A\) または \(+K\) を作用させる。

量子ビット / register

control \(c\)+input \(n\)+target \(m\) for addition; offset は input 不要。

ancilla

controlled addition: 1 dirty。controlled offset: 2 dirty。

計算量

gates: addition: \(O(c+m)\)。offset: \(O(c+m\lg m)\)。
depth: \(O(c+m)\)。

条件・注意

\(m>n\) の larger-target addition にも適用。

\(H=X^{\otimes n}\) が加算を反転する性質から \([S_{-K},H]=S_{2K}\)。dirty LSB を一時的に付けて \(+K\) にする。

Fig. 19 Increment using n dirty bits

作用

\(t\mapsto t+1\bmod 2^n\)。

量子ビット / register

target \(n\)+dirty \(n\)。

ancilla

n dirty。

計算量

gates: \(O(n)\)。
depth: \(O(n)\)。

条件・注意

任意の dirty register \(x\) を借りられる。

任意の \(x\) について \(x\) と \(\lnot x=-x-1\) を両方引くと target が1増える。

Fig. 20 Controlled increment with one dirty bit

作用

control が on のとき \(t\mapsto t+1\bmod 2^n\)。

量子ビット / register

control \(c\)+target \(n\)+dirty 1。

ancilla

1 dirty。

計算量

gates: \(O(c+n)\)。
depth: \(O(c+n)\)。

条件・注意

odd-size register の構成を基本に、even-size は LSB を分離して残りを controlled increment し、LSB を toggle。

classical reversible incrementer では1 dirty が最小。量子操作を許すと parity barrier を回避可能。

Fig. 21 Quantum bootstrap for increment

作用

phase-gradient を使って increment の dirty ancilla 要求を量子操作で bootstrapping する。

量子ビット / register

target register と phase-gradient 用の一時操作。

ancilla

bottleneck では不要な改善。classical では1 dirty 最小だが quantum では ancilla なしが可能。

計算量

gates: 小角 rotation 合成のため asymptotic と定数が悪化し得る。論文の主コスト集計には採用しない。
depth: 構成依存。

条件・注意

\(Z^{2^{-k}}\) 型の小角位相 gate を使う。

\(|v\rangle\mapsto e^{i(\pi/2)v/2^d}|v\rangle\) の phase gradient を列で実装。

Fig. 22 Controlled bit rotation / bit swap

作用

bit order の rotation または swap。

量子ビット / register

control \(c\)+target \(n\)。

ancilla

0。

計算量

gates: \(O(c+n)\)。
depth: \(O(c+n)\)。

条件・注意

controlled の場合は実 gate が必要。uncontrolled permutation は wire relabeling で済むことが多い。

3つの controlled bit-reverse に還元。

Fig. 23 Inline controlled bit order reversal

作用

odd \(n=2k+1\) または even \(n=2k+2\) の register で bit order を反転。

量子ビット / register

control \(c\)+target \(n\)。

ancilla

0。

計算量

gates: \(O(c+n)\)。
depth: \(O(c+n)\)。

条件・注意

XOR 操作は独立 CNOT の列。input と output の endian が逆。

rotation/swap の subroutine。

Fig. 24 Many-control many-target CNOT

作用

全 controls が on のとき、複数 target をまとめて toggle。

量子ビット / register

control \(c\)+target \(t\)。

ancilla

0。

計算量

gates: \(O(c+t)\)。
depth: \(O(c+t)\)、toggle を賢く拡散すれば \(O(c+\lg t)\)。

条件・注意

まず1 target に many-control NOT を作用させ、その toggle を CNOT 群で広げる。

naive な \(O(ct)\) を避けるための基本テクニック。

Fig. 25 Many-control NOT to Toffoli gates

作用

\(c\)-control NOT を constant-size Toffoli gates に分解。

量子ビット / register

control \(c\)+target 1 + dirty \(c-2\)。

ancilla

\(c-2\) dirty。1 dirty だけで2倍程度の Toffoli 数にする方法もあるが本構成では不要。

計算量

gates: 明示値 \(4c-8\) Toffoli gates。
depth: 線形規模。

条件・注意

period finding 文脈では十分な未使用 qubits を借りられる。

これにより上位構成は NOT/CNOT/CCNOT まで落ちる。

6.3 主要構成の正しさの要点

Controlled modular bimultiplication

初期状態を \((x,y)\) とする。すべて \(\bmod R\) で計算する。

\[ \begin{aligned} (x,y) &\xrightarrow{\;y\leftarrow y+xK\;} (x,\;y+xK)\\ &\xrightarrow{\;x\leftarrow x-(y+xK)K^{-1}\;} (-yK^{-1},\;y+xK)\\ &\xrightarrow{\;y\leftarrow y+xK\;} (-yK^{-1},\;xK)\\ &\xrightarrow{\;\mathrm{swap}\;} (xK,\;-yK^{-1})\\ &\xrightarrow{\;\mathrm{negate}\;} (xK,\;yK^{-1}). \end{aligned} \]

ここで2回目の scale-add の “input” はすでに \(-yK^{-1}\) になっているため、target から元の \(y\) 成分が消える。

Pivot-flip と bi-flip

\(N=2^n\) とし、pivot-flip を

\[ \mathrm{PivotFlip}_K = \sum_{i=0}^{K-1}|K-i-1\rangle\langle i| + \sum_{i=K}^{N-1}|i\rangle\langle i| \]

で定義する。これは \(K\) 未満の状態だけを逆順にし、\(K\) 以上を固定する。実装の中心は bi-flip

\[ x\longmapsto \lnot(x-K) \]

である。これは \(x

Modular addition は3つの pivot-flip

\(A\le R\) のとき、\(+A\pmod R\) は pivot \(R-A\)、\(R\)、\(A\) の3つの pivot-flip で実現できる。図10の範囲図が示すように、wrapped になる区間と shifted になる区間を、反転操作の合成で所望の循環シフトに変える。\(R\) 以上の状態は undefined behavior として扱うため、正しいのは valid range \([0,R)\) 上である。

Incrementer の parity barrier

classical reversible な \(n\)-bit increment は、状態空間上の奇 permutation である。具体的には \(|2^n-1\rangle\) を最上位から最下位へ掃き寄せる \(2^n-1\) 個の swap と同等で、\(2^n-1\) は奇数である。一方、回路全体を覆わない classical gate が誘導する permutation は偶 permutation であるため、補助 bit なしに全 \(n\) bit を increment することはできない。したがって classical reversible incrementer では少なくとも1 dirty ancilla が必要であり、Figure 20 はこの下限に一致する。

7. Interactive 検証

7.1 Pivot-flip による modular addition

小さい \(N=2^b\) で、3つの pivot-flip が \(+A\pmod R\) と一致するか確認する。\(x\ge R\) は論文の modular circuits では undefined として表示する。

bits \(b\)

\(R\)

\(A\)

7.2 Bimultiplication の step-by-step

\(K^{-1}\bmod R\) が存在する場合のみ有効。各 step は Figure 5 の説明に対応する。

\(R\)

\(K\)

\(x\)

\(y\)

8. 先行研究との比較

論文 Figure 26 の比較を再掲する。\(M(n)\) は古典乗算の時間計算量で、\(M(n)\le n(\lg n)2^{O(\lg^* n)}\) が知られている。\(\epsilon\) は固定 universal gate set へ合成する際の最大誤差で、Draper addition のような frequency-space phase gradient を使う構成で漸近的に効く。

構成	年	depth	gates	clean qubits	total qubits
Shor	1994	\(\Theta(nM(n))\)	\(\Theta(nM(n))\)	\(\Theta(n)\)	\(\Theta(n)\)
Beckman et al.	1996	\(\Theta(n^3)\)	\(\Theta(n^3)\)	\(5n+1\)	\(5n+1\)
Vedral et al.	1996	\(\Theta(n^3)\)	\(\Theta(n^3)\)	\(4n+3\)	\(4n+3\)
Beauregard	2003	\(\Theta(n^3\lg(1/\epsilon))\)	\(\Theta(n^3\lg(n/\epsilon)\lg(1/\epsilon))\)	\(2n+3\)	\(2n+3\)
Takahashi et al.	2006	\(\Theta(n^3\lg(1/\epsilon))\)	\(\Theta(n^3\lg(n/\epsilon)\lg(1/\epsilon))\)	\(2n+2\)	\(2n+2\)
Zalka	2006	\(\Theta(n^3\lg(1/\epsilon))\)	\(\Theta(n^3\lg(n/\epsilon)\lg(1/\epsilon))\)	\(1.5n+O(1)\)	\(1.5n+O(1)\)
Häner et al.	2016	\(\Theta(n^3)\)	\(\Theta(n^3\lg n)\)	\(2n+2\)	\(2n+2\)
Gidney（本論文）	2017	\(\Theta(n^3)\)	\(\Theta(n^3\lg n)\)	\(n+2\)	\(2n+1\)

本論文の立ち位置は、total qubits 最小ではなく clean qubits 最小化である。clean qubits を \(n+O(1)\) に下げる一方、dirty を含めた total は \(2n+1\) である。

9. 新規性、改善点、限界

9.1 pivot-flip による modular addition

従来の modular addition は、wraparound が必要かどうかを clean ancilla に一時保存する構成が多かった。pivot-flip は dirty ancilla だけで済み、Shor の文脈では常に借りられる未使用 qubit がある。この改善により、Häner et al. 型の \(2n+2\) から \(2n+1\) へ1 qubit 分の削減が可能になる。

9.2 dirty bimultiplication

以前の modular multiplication は、補助 register が clean であること、または最終的に trash してよいことを要求した。ここでは補助 register に逆倍率をかけるため、途中では壊れるが、最後に work register の測定値から復元できる。この発想により、補助 register の \(n-1\) 本を dirty にできる。ただし MSB だけは clean にし、補助 register の値が常に \(

9.3 1 dirty ancilla の線形 incrementer

既存の published incrementer は、\(O(n^2)\) gates か、\(\omega(1)\) ancilla を必要としていた。Figure 20 の incrementer は classical reversible で \(O(n)\) gates/depth、1 dirty ancilla で済む。これは parity argument により classical では最小である。

9.4 限界

all-to-all connectivity を仮定し、量子コンピュータの幾何制約を扱わない。
T gate 数や surface-code layout を最適化していない。
dirty ancilla のための uncomputation と toggle/commutator control により、定数因子が大きい。
modular arithmetic は範囲外入力について未定義である。

10. 今後の方向

著者は、ほぼすべての arithmetic construction が2本以下の dirty ancilla で済むことを強調する。したがって全体 qubit 数をさらに下げるには、bottleneck である modular multiplication の最初の分解を改善する必要がある。

10.1 CRT 的分解

もし \(R=pq\) の因数分解を知っていれば、Chinese remainder theorem により

\[ x\bmod R \quad\leftrightarrow\quad (x\bmod p, x\bmod q) \]

で半サイズ register 2本へ表現できる。半サイズ乗算で補助 register を使い回せば、3本の半サイズ register で済む可能性がある。しかし \(R\) の因数分解を知ること自体が目的なので、そのままでは逆説的である。Zalka はこれに近い考えを、\(R\) の因数ではなく multiply-by value を法 \(R\) で分解する形で利用した。

10.2 Modular Fourier transform と commutator control

modular Fourier transform は modular multiplication の効果を反転する。

\[ \mathrm{QFT}_R\cdot (\times K\bmod R)\cdot \mathrm{QFT}_R^{-1} = (\times K^{-1}\bmod R). \]

この性質を使うと、bimultiplication を2回組み合わせて単一 register だけに作用する proper modular multiplication を作れる。また commutator control によって、control を modular multiplication から modular QFT 側へ移せる可能性がある。もし controlled modular QFT が controlled modular multiplication より少ない ancilla で済むなら、control qubit を借りることでさらに1 qubit 節約できる可能性がある。

11. 原論文ページ画像と図の位置

下のサムネイルは、添付 PDF の全14ページを自己完結的に埋め込んだものである。図の位置は次の通り。

ページ	主な図・内容
p.3	Figure 1 dependency graph、Figure 2 high-level period finding。
p.5	Figure 3 single phase-estimation qubit、Figure 4 dirty bimultiplication 付き最終 period finding。
p.6	Figure 5 bimultiplication、Figure 6 scale-add、Figure 7 modular doubling、Figure 8 enregistered pivot-flip。
p.7	Figure 9 constant pivot-flip、Figure 10 modular addition by pivots、Figure 11 modular addition、Figure 12 modular offset、Figure 13 modular negation。
p.8	Figure 14 comparison、Figure 15 same-size adder、Figure 16 offset circuit。
p.9	Figure 17 larger-target adder、Figure 18 controlled addition、Figure 19 n-dirty increment。
p.10	Figure 20 one-dirty controlled increment、Figure 21 quantum bootstrap、Figure 22 bit rotation、Figure 23 bit reversal。
p.11	Figure 24 many-control many-target CNOT、Figure 25 many-control NOT to Toffoli。
p.12	Figure 26 historical comparison table。

12. 参考文献メモ

論文末尾の19件の参考文献のうち、本レポートの理解に特に直結するものは、Shor の factoring、Beauregard の \(2n+3\) qubit circuit、Takahashi-Kunihiro の \(2n+2\) qubit circuit と no-ancilla adder、Häner-Roetteler-Svore の Toffoli-based modular multiplication、Zalka の fewer pure qubits、そして Barenco et al. の elementary gates である。

Barenco et al., “Elementary gates for quantum computation”, 1995.
Beauregard, “Circuit for Shor’s algorithm using 2n+3 qubits”, 2003.
Beckman et al., “Efficient networks for quantum factoring”, 1996.
Draper, “Addition on a Quantum Computer”, 2000.
ISO/IEC C11, undefined behavior.
Fürer, “Faster integer multiplication”, 2007.
Gidney, “Quirk”, 2016.
Häner, Roetteler, Svore, “Factoring using 2n+2 qubits with Toffoli based modular multiplication”, 2016.
Mosca and Ekert, hidden subgroup/eigenvalue estimation, 1999.
Parker and Plenio, single pure qubit factoring, 2000.
Van Rentergem and De Vos, reversible full adder, 2004.
Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, 1999.
Steiger, Häner, Troyer, “ProjectQ”, 2016.
Takahashi and Kunihiro, linear-size addition circuit with no ancillary qubits, 2005.
Takahashi and Kunihiro, Shor circuit using \(2n+2\) qubits, 2006.
Vedral, Barenco, Ekert, arithmetic quantum networks, 1996.
Brett Victor, “Media for thinking the unthinkable”, 2013.
Zalka, fast versions of Shor’s algorithm, 1998.
Zalka, “Shor’s algorithm with fewer (pure) qubits”, 2006.