量子回路生成における補助量子ビット削減
はじめに
めっちゃ久しぶりの投稿＋初めてのアドベントカレンダー参加です！！
2021年３月に大学を卒業し、普段は関西の企業でインフラエンジニアとして働いています。
量子コンピュータは卒論のためにちょっとかじっただけですで、３年ほど全く触っていないですが、ここいらで卒論の供養をしておこうかなと思いました。
（最近、趣味としてパラグライダーを始めたんですが、今日も行こうと思っていたら、この土日スクールがお休みで。。。暇で暇で、なにか書物をしようかなと。。）
理解が間違ったことや・大雑把なことを書くと思いますが，大目に見てください（とはいえ，間違いは指摘していただけると修正はしていきたいと思います。）
卒論の概要
量子コンピュータを使い問題を解く場合（量子ゲート方式）、量子コンピュータ特有の処理の他に、古典コンピュータと同様の論理計算を実現する必要があります。
量子コンピュータでアルゴリズムを考える場合。ほとんどの場合では論理計算を行う回路は量子コンピュータの特有の処理から切り離されて、神託回路（オラクル) として与えられ、入力に対して結果が１ステップで返ってくる回路 として扱うことが多いです。
しかし，神託回路が本当に神から託されることなどありえないわけで、実際は量子回路で論理計算を実装する必要があります。
アルゴリズム研究が目的であるならば、簡単な論理計算を小規模な量子回路（2，3ゲート程度）を作成し，量子アルゴリズムの検証を行うことが普通ですが、量子コンピュータの実用を考えると大規模でかつ複雑な論理計算を量子回路で実現する必要があります。
卒業論文では神託回路のような論理計算を行う量子回路を生成する（量子回路合成）において、量子ビットの観測操作を利用する回路を発展させて補助量子ビットを削減する手法を提案しました。
量子回路における論理計算回路
古典コンピュータはレジスタに対して不可逆な操作を行うのとは違い、量子回路では、量子ビットレジスタに対しては可逆操作を実施します。
可逆操作とは、操作後の状態から操作前の状態に一意に戻すことができる操作のことを言います。
古典コンピュータにおけるANDゲートを考えてみると以下の様になり
０が出力されたときに、２つの入力の状態を一意に決定することができないため古典コンピュータにおけるANDゲートは不可逆なゲートということになります。
古典コンピュータにおける論理演算はNOTゲートを除き不可逆ゲートで構成されることが多いです。
では、可逆ゲートにするにはどうしたらいいかというと、入力のビットも一緒に出力すればいいわけです。
量子回路でAND演算を実現するには、以下のToffoliゲートと言われる量子ゲートを利用します。
式としては以下のように表されます。
上記の x_2(ターゲットビット) の状態が |0> の場合
となり、3つ目のターゲットビットにコントロールビット（x_0,x_1)のANDの状態を作ることができます。
※ 量子回路合成においてTゲートのコストが重いためT-count:Tゲートの個数、T-depth:並列操作できないTゲートの個数 が回路評価の指標になります。
※ Toffoliゲートを分解すると、7つのTゲートが必要な操作のために比較的、コストが大きいものになります。
ちなみにToffoliゲートは以下のようにちゃんと可逆演算です。
| x_0 | x_1 | x_2 | x_0·x_1⊕x_2 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
量子コンピュータでは量子回路全体も可逆性を保持する必要があります。そのためにToffoliゲートのターゲットビットのように一時的に状態を記憶するための量子ビットが必要になったり、以下の図のように一時保存に利用した量子ビットを再度利用できるように逆計算を行い、初期状態に戻したりする必要があります。
作り出した目的状態をCNOT ゲートで他の量子ビットにコピーしたあと，逆計算を行うことで量子ビットの状態をゲート作用前の状態に戻す．図2.4 では，右側のX ゲート，Toffoli ゲート，CNOT ゲートで逆計算を行い量子状態をゲート作用前の状態に戻している．
Toffoliゲートの逆計算には、再度Toffoliゲートが必要になり、また7つのTゲートが必要になってしまいます。
論理演算の回路合成と量子状態の観測による初期化
先程、Toffoliゲートは７つのTゲートを利用した量子回路に分解できると書いたのですが、ToffoliゲートをAND演算に利用する（x_2の状態が |0>である制約）の場合以下のように４Tゲートにコストを削ることができます。
（４Tゲート以下では実現できないことは証明されているらしいです。
Cody Jones. Low-overhead constructions for the fault-tolerant toffoli gate. Physical Review A, Vol. 87, No. 2, p. 022328, 2013.）
逆計算については、ターゲットビットの状態が|0>ではないため低コストなToffoliゲートを利用することはできないのですが、量子ビットの状態の観測操作をうまく使ってあげることで以下のようにTゲートを使わずに補助量子ビットの初期化をすることができます。
改めて詳しく書く気力はなかったため以下卒論の引用です。(というより、時間が経ちすぎて半分近く忘れていたので。。。）
図3.2 の逆計算前の量子ビットの状態は式3.1 のように表される．コン
トロールビットである2 つの量子ビットが|11⟩である時，ターゲットビッ
トが|1⟩となり，コントロールビットである2 つの量子ビットが(|00⟩+
|01⟩+ |10⟩) である時，ターゲットビットが|0⟩となる．|11⟩= A1，|00⟩+
|01⟩+|10⟩= A0 とおくと，式3.1 は，式3.2 のように表すことができる．
|x0,x1,x0 ·x1⟩= (|00⟩+ |01⟩+ |10⟩) |0⟩+ |11⟩|1⟩ (3.1)
= |A0⟩|0⟩+ |A1⟩|1⟩ (3.2)
次に，3 量子ビット目のターゲットビットにH ゲートを作用させる．H
ゲートを作用させると式3.3 の状態になる．式3.3 では全ての基底状態の
確率振幅は等しいため省略している．
|A0⟩|0⟩+ |A1⟩|1⟩−→H |A0⟩ 1√2(|0⟩+ |1⟩) + |A1⟩ 1√2(|0⟩−|1⟩)
= (|A0⟩+ |A1⟩) |0⟩+ (|A0⟩−|A1⟩) |1⟩ (3.3)
式3.3 の状態で，ターゲットビットを観測する．観測した結果，ターゲッ
トビットの状態が|0⟩の場合，3 つの量子ビットの状態は式3.4 のように
なり，AND 演算を実現するToffoli ゲートが作用する前の状態に戻る．
(|A0⟩+ |A1⟩) |0⟩= |000⟩+ |010⟩+ |100⟩+ |110⟩ (3.4)
一方で観測した結果，ターゲットビットの状態が|1⟩の場合，3 つの量子
ビットの状態は式3.5 のようになる．これは，AND 演算を実現するToffoli
ゲートが作用する前の状態からは，補助量子ビットであるターゲットビッ
トが|1⟩になり，A1 の量子状態の位相が反転している状態である．
(|A0⟩−|A1⟩) |1⟩= (|00⟩+ |01⟩+ |10⟩−|11⟩) |1⟩ (3.5)
量子状態を元に戻すために，式3.6 のように，観測したターゲットビット
にX ゲートを作用させる．次に式3.7 のように，2 つのコントロールビッ
トにCZ ゲートを作用させることで，Toffoli ゲートを作用させる前の量子
状態に戻る．
(|00⟩+ |01⟩+ |10⟩−|11⟩) |1⟩−→X (|00⟩+ |01⟩+ |10⟩−|11⟩) |0⟩ (3.6)
−−→CZ (|00⟩+ |01⟩+ |10⟩+ |11⟩) |0⟩ (3.7)
以上より，|0⟩の状態で初期化された補助量子ビットをターゲットビット
にToffoli ゲートの合成を行うと，合計で4T ゲートでToffoli ゲートを合
成，逆計算することができる
上記の観測によりToffoli回路の逆計算の手法は
Craig Gidney. Halving the cost of quantum addition. Quantum, Vol. 2, p. 74, 2018
にて提案されています。
発展回路
卒論のテーマを考えているときに読んだ論文で、この観測を利用することでTゲートなしにToffoliゲートを逆計算できる手法に感動しました。
なにか他にも同じように観測を利用することで逆計算をできるものがないかとQiskitで色々遊んでいると以下のToffoliゲートとCNOTゲートの回路も観測を利用する逆計算を行えることがわかり、卒論のテーマにしようと考えました。
（TODO：余力が出てきたらきちんと式を使って説明する。。）
上記の観測を利用した逆計算回路を利用すると、以下のような回路合成をすることができ必要になる量子ビットの数を減らすことができます。
（正確には使わなくなった補助量子ビットの初期化を早くに行えるため後続の計算で利用ができるようになり、量子ビットの数を減らすことができます。）
卒論では大規模な量子論理回路生成を目的に開発されている C++ライブラリcaterpillar (https://github.com/gmeuli/caterpillar) に手を入れ、どの程度出力する量子回路のコストが変化するかを確認しました。
今となっては少し結果を公開する自信もないため、ここに書いておくのはやめておきますm(_ _)m
結果の概要としてはロジックネットワークの作りにもよりますが、EPFLで公開されている組み合わせ論理式でAND 演算が最小になるように最適化されたもの（https://github.com/lsils/date2020_experiments) を入力として既存のXAG mapping strategyと比較して平均qubiの数が95%、T-depthが108％の結果となりました。
（気になる方は個人的に連絡をください。卒論のPDFとプログラム共有できると思います。あまり信用できないコードだと思いますが。）
まとめ
3年前に書いた卒論の内容を振り返りました。
かなり忘れている部分もありましたが、当時考えていたことを「あーそういえばこんなことあったな」を思い出せて、とても懐かしかったです。
そろそろ大学生の方は卒業論文の時期だと思うので皆さんがんばってください！！
間違いや、説明不足の部分が多々あると思います、気になったところがありましたらコメント、質問ください。
なにぶん３年前に書いたものなので説明できるかわからないですが、もう一度考えて修正・回答しようと思います。
（＋式の部分は気力がなく説明を端折ってしまったので、気力が湧いててきたら追記します。。）