量子計算では、途中の答えを書き込む補助ビットを、使い終わったら0に戻したい場面があります。ただし、普通のメモリーのように消去すれば元どおり、とは限りません。補助ビットに「どの入力から来たか」という記録が残ると、計算に使いたい成分同士の干渉が変わるからです。
その記録を、計算の手順を逆にたどって取り除く操作をアンコンピュートと呼びます。単に捨てる場合との違いを、2量子ビットの理想計算で確かめます。さらに、必要な出力を残しながら作業用の領域を片付けるとき、何が残り、何が消えるのかを分けます。
簡単にまとめると？
- 入力に応じた記録が補助ビットへ残ると、それを無視した計算対象では、干渉に必要な成分間の関係が失われる場合があります。
- 測定や破棄をする前に逆操作をかければ、余分な記録を取り除けます。補助ビットを強制的に0へリセットすることとは違います。
- 必要な出力を別領域へ残してから逆計算する方法もあります。ただし出力との相関は残り、追加の量子ビットと操作が必要です。
補助ビットに入力の記録が残る
計算対象Aを|+⟩＝(|0⟩＋|1⟩)/√2、補助ビットWを|0⟩に準備します。Aが1の成分にだけWを反転する制御NOT、CNOTをかけると、全体は(|00⟩＋|11⟩)/√2になります。左がA、右がWです。Wを測ればAの0・1に対応する値が分かる状態になりました。
これは|+⟩を二つに複製した状態ではありません。二つの|+⟩の積なら00・01・10・11の四つの成分が現れますが、ここには00と11しかありません。計算基底の値を対応させるCNOTと、未知の量子状態を丸ごと複製する操作を区別する必要があります。[1]
ここでWを使わないことにすると、Aだけの状態は、0と1が半々の混合状態です。最初の|+⟩も0・1では半々なので、この測定だけでは違いが見えません。そこでAにアダマール操作Hをかけてから測ります。最初の|+⟩なら0が確率1で出ますが、Wへ記録を残した後は0と1が半々になります。干渉を確かめる読み出しを選ぶと差が現れます。
逆操作とリセットは、同じ「0へ戻す」ではない
Wをまだ測定も破棄もしていなければ、同じCNOTをもう一度かけられます。00は00のまま、11は10へ戻り、全体は(|00⟩＋|10⟩)/√2＝|+⟩|0⟩になります。Wは0へ戻り、AのH後の0確率も1へ戻ります。CNOTは自分自身が逆操作なので、この例では同じ操作を繰り返せばよいのです。
一方、Wを捨てて新しい|0⟩を用意するリセットでは、Aは半々の混合状態のままです。AとWの関係を使って元へ戻す前に、関係を捨ててしまったためです。Wが0になったという局所的な確認だけでは、Aの干渉が戻ったとはいえません。
同じ計算を、A＝cos(t)|0⟩＋sin(t)|1⟩という入力でも確かめました。逆CNOTは、tを変えても準備した積状態へ戻します。リセットと逆計算の差は、半々の特別な入力だけに依存するものではありません。ただしAが最初から0または1に確定している場合には、この回路で失われる重ね合わせの干渉はなく、H後の確率も差を示しません。
必要な答えを残し、作業領域だけ片付ける
途中の計算を全部逆にすると、欲しかった答えまで消えるように見えます。可逆な関数計算では、まず入力Xと作業領域Wで答えを計算し、その計算基底で表された値を出力領域YへCNOTなどで写してから、XとWの計算だけを逆にたどる方法が使えます。原論文はこの「計算・出力への加算・逆計算」を、作業領域を0へ戻す構成として示しています。[1]
最も小さな例では、AをWへCNOTで写し、次にWを出力Yへ写し、最後にAからWへのCNOTをもう一度かけます。入力|+⟩|0⟩|0⟩は、ビット順A・W・Yで(|000⟩＋|101⟩)/√2になります。Wは確かに0ですが、AとYの相関は残っています。Aだけを見ればまだ混合状態です。アンコンピュートは、保持すると決めた出力との相関まで消す操作ではありません。
一般には、入力xに応じた途中記録g(x)を残すと、異なる入力成分を見分ける情報が作業領域へ漏れます。作業領域を無視したとき、どの成分間の関係が残るかは、その記録が同じか、区別できるかで変わります。必要なのは「全部の相関をなくす」ことではなく、次の計算に不要な途中記録を残さない設計です。
回路の比較では、片付けの費用も数える
アンコンピュートには、元の入力と、逆にできる手順が必要です。一般のユニタリ操作UではUの逆、U†を用い、回路の操作順も逆にします。すべてのゲートがCNOTのように自分自身で逆になるわけではありません。すでに測定・破棄した未知の記録を、逆ゲートだけで必ず取り戻せるという意味でもありません。
回路の必要量を比べるときは、答えを計算する部分だけでなく、出力を残す操作、逆計算、使い回せる補助ビット数を同じ範囲で数えます。メモリーを再利用できても、追加のゲート数、深さ、装置上の誤差は無料になりません。原論文の操作数も、そこで定めた可逆ゲートのモデルに対する値であり、そのまま実機の実行時間ではありません。
確認すべき点は、作業領域が0へ戻ったか、計算対象と不要な相関が残っていないか、残した出力との相関が意図したものか、の三つです。今回の理想例はその区別を示すもので、誤りのある装置での回復性能や計算速度の実証ではありません。
参考資料
- [1] A. Yu. Kitaev, Quantum measurements and the Abelian Stabilizer Problem, arXiv:quant-ph/9511026v1（1995年11月20日）。2.2節の可逆計算・補題1と、2.4.5節の補助記録とコヒーレンスを参照。本文のCNOT・リセット比較と3ビットの例、図は定義に基づく独自計算です。