QiskitのMulti-controlled gateの実装に関するメモ

調べた日: 2021年7月中旬
調べたリポジトリ: https://github.com/Qiskit/qiskit-terra

定義されているmulti-controledゲート

QuantumCircuitクラス内で定義されているmulti-controlledゲートたち

• mcp
  • library.standard_gates.p.MCPhaseGate を回路に引っ付ける
• mcu1
  • library.standard_gates.u1.MCU1Gate を回路に引っ付ける
• mcx
  • 実装が複数あり、オプション引数のmodeで実装を選択する
  • "noancilla" (デフォルト)
    • library.standard_gates.x.MCXGrayCode を回路にくっつける
  • "recursion"
    • library.standard_gates.x.MCXRecursive を回路にくっつける
  • "v-chain"
    • library.standard_gates.x.MCXVChain を回路にくっつける。dirty_ancillasオプションはFalse
  • "v-chain-dirty"
    • library.standard_gates.x.MCXVChain を回路にくっつける。dirty_ancillasオプションはTrue
  • 互換性のために残されている古いもの
    • "advanced" → "recursion"
    • "basic"→ "v-chain"
    • "basic-dirty-ancilla" → "v-chain-dirty"
• mct
  • mcxと同じ (multi-controlled Toffoli?)

QuantumCircuitクラスの外で定義されているmulti-controlledゲートたち

library.standard_gates.multi_control_rotation_gates内で、

• mcrx
• mcry
• mcrz

がQuantumCircuitクラスを拡張する形で定義されている。ややメンテされていないっぽく感じる。

Gate.controlによるmulti-controlled gate

このような方法も提供している。

この方法を利用するとadd_control(source)が呼び出される。

なお、ゲートによっては、Gate.controlを再実装しているものもあるが、主には、control版のゲートがある場合はGate.controlを呼び出さずにそちらを使うというもので、概ねadd_controlが呼ばれると考えて問題ない。

QuantumCircuit.controlによるmulti-controlled gate

Gate.controlが間接的に呼び出される。

実装

基本的には、グレイコードによる実装になっているものが多い。グレイコードによる実装はこの記事にある。
グレイコードによる実装では、controlビットの数に応じて、指数関数的に回路が長くなることに注意が必要である。
ただし、mcrx, mcry, mcrz以外は、その場では展開されず、展開するかしないかは(ちゃんと調べていないが、恐らく)バックエンドに委ねられるので、シミュレータであれば、巨大なmulti-controlledな何かを使った方が有利な可能性が高い。

mcxについては、"recursive", "v-chain", "v-chain-dirty"によって、ancillaを使うことで指数関数的な回路増加を避ける方法を提供している。

実機が対象で、controlビットが多いなら、他のものもmcxを使って書いた方が回路が短くなるかもしれない。だが、ネガティブなことを言うと、実機で巨大なmulti-controlledゲートが必要になっている時点で、そもそも動かない可能性を考えたほうがいい。

mcpの実装

Pゲート(位相ゲート)は

$$
P(\lambda) = \begin{pmatrix}
1 & 0 \\
0 & e^{i\lambda}
\end{pmatrix}
$$

で定義されていて、mcpゲートはそのmulti-control版です。

MCPhaseGate._defineにて、そのグレイコード実装があります。(ちゃんと調べていないですが、この実装を使うかどうかはバックエンド依存で、実機などではこれが使われるのではないかと思われます)

mcu1の実装

QiskitにおけるU1ゲートは、Pゲートと同じなので、mcpゲートと同様にMCU1Gate._defineが定義されています。

mcx, mctの実装

mctはmcxと同じです。また、各オプションごとに実装が分かれます。

"noancilla"

MCXGrayCode._defineに実装があります。なお、MCXGate._defineはMCXGrayCode._defineを呼び出すようなっています。
実装としては、MCU1ゲート(将来的にMCPゲートに変わると思われます)の標的の前後にHゲートをあてたものになります。

"recursion"

まず、C3X, C4Xは予め用意されており、これらはグレイコードやそれに近い実装でancillaなしに作られています。
制御ビットが4つ以内なら、既存の実装を使います。

制御ビットが5以上の場合、ancillaを1つ利用し、再帰的に回路を作ります。
MCX(controls, target, ancilla)のような表記をし、以下にMCX(qs, t, a)の実装を示します。

• qsの長さが3または4なら、C3X, C4Xの回路を返します
  • 以下を注意して読むと、qsの長さは3を下回らないことが分かりますが、特にそれ自体は大切ではないと思います。(1や2だったらCXやcCXを返せばいいだけ)
• 制御ビットを前半分と後ろ半分に分けます(端数が出た場合は、前半分をひとつ大きくします)
  • これをqs0, qs1と表記することにします
• 回路にMCX(qs0, a, qs1[0])をつなげます
• 回路にMCX(qs1 + [a], t, qs0[-1]) をつなげます
• 回路にMCX(qs0, a, qs1[0])をつなげます
• 回路にMCX(qs1 + [a], t, qs0[-1])をつなげます
• できあがった回路を返します

ここで、ancillaにqs0[-1]やqs1[0]を雑に指定していますが、これをしても困らない(ancillaが0でなくていい)ことを示すには、やや根性ビット演算を要します。

"v-chain"

MCXVChain._defineに実装があります。
基本的には、(制御ビット数 - 2)のancillaを使ってトフォリゲートをつなげたものですが、トフォリゲートと相対位相を除いて等価で、分解時にゲート数が少なくて済むRCCXゲートが代わりに使われます。

"v-chain-dirty"

MCXVChain._defineに実装があります。ancillaが|0>になっていなくても動くようにしていて、この論文やこの論文を元にしているようです。必要なancilla数はv-chainと変わりませんが、回路はv-chainよりも長くなります。

mcrx, mcry, mcrz

最近の記法と相性が悪く、メンテされていないっぽく感じます。次のように使います。

qc = QuantumCircuit(4)
qc.mcrx(0.5, qc.qregs[0][:3], qc.qregs[0][3])
qc.draw()

mcxなどのように、ゲートを一つ付け加えるのではなく、呼び出し時にゲートが展開される手法になっています。
実装はグレイコードにより行われています。

Gate.control

概ね、ゲートの種類ごとにif文で分けてmulti-controlled版を使っている実装になっています。
xやcxはmcxを、zはh + mcx + hを使うなどの工夫はされています。

印象

mcxだけえらいがんばってる印象を受けました。Gate.controlは機能として面白いですが、実装はやっぱりこのへんが落とし所なんだろうなという感想になりました。