ここで、先に進む前に書籍の中でしれっと登場する “逆演算” (uncomputation) について調べておきたい。量子コンピューティング 基本アルゴリズムから量子機械学習まで | Ohmsha では、p.39 で「補助量子ビットと逆演算」として説明がされている。但しあまり具体的に説明されているようには思わない。textbook の 量子コンピューター上の古典計算 の中では
「逆計算」と呼ばれる手法
の部分が該当する。英語版 Classical Computation on a Quantum Computer では
a method known as 'uncomputation'
となっている。これを押さえておくのが良いと思われる。
textbook の書き方もよく分からないのだが、オラクル $f$ と問い合わせ用の $U_f$ がある時に、
$$
\begin{align*}
U_f \sum_{x} |x, \bar{0} \rangle = \sum_x \ket{x, f(x)} \rightsquigarrow \sum_x | x, \bar{0} \rangle
\tag{1}
\end{align*}
$$
をしたいケースを考えている。次に適用のさせかたの分かっている $V_f$ つまり、ゲートの構成が分かっているので、$V^\dagger = V_f^{-1}$ が作れるようなものを持ってくる。（$U_f$ はオラクルの詳細が分かっていないので、$U_f^\dagger$ を作れない）
ここから先はやや抽象的で、簡単な $U_f, V_f$ を考えて問題点を探っているように見える。$V_f$ がビットを 3 つ要求するゲートの場合で、第 1 ビットと第 2 ビットの間、および第 1 ビットと第 3 ビットの間に何かしら制御ゲートが作用しているケースを考えているようだ。つまり、$V_f | x, \bar{0}, \bar{0} \rangle = | x, f(x), g(x) \rangle$ のようなものをを考えているように見える。共役についても $V_f^\dagger | x, f(x), \bar{0} \rangle = | x, \bar{0}, g(x) \rangle$ のようになることを考えていると思われる。たぶんこういうケースが 1 つの典型だと言うのだろう。
補助用のビットを 1 つ追加して（ここでは右に $\otimes | \bar{0} \rangle$ として追加した）、
$$
\begin{align*}
|x,\bar{0} \rangle \otimes | \bar{0} \rangle \xrightarrow{U_f} |x,f(x) \rangle \otimes | \bar{0} \rangle = |x,f(x),\bar{0} \rangle \xrightarrow{V_f^\dagger} |x, \bar{0}, g(x) \rangle
\end{align*}
$$
とすると、ゴミとして $g(x)$ が残ってしまい、(1) 式のようなことができないのでもっと工夫したいといった内容が書かれている。
これを乗り越える方法として、“欲しい情報を複製して格納する” ための補助ビットを追加した上で $V_f$ を適用するらしい:
$$
\begin{align*}
|x, \bar{0}, \bar{0} \rangle \otimes | \bar{0} \rangle \xrightarrow{V_f} |x, f(x), g(x) \rangle \otimes | \bar{0} \rangle
\end{align*}
$$
textbook のこの辺で突如
if you have heard of the no-cloning theorem, note that this is not the same process
と出てくる。非常に困惑させる一言なので、非クローン化定理 - らんだむな記憶 で触れることにした。no-cloning theorem は任意の状態を複製できるようなユニタリ操作は存在しないという主張の定理なので、今回はこの回路の構成と入力の元ではビット 2 の内容をビット 4 に複製できるような $U_{2,4}^{cp}$ という操作をとることにする。（常にとれるのかは知らない）
この時:
$$
\begin{align*}
|x, f(x), g(x) \rangle \otimes | \bar{0} \rangle \xrightarrow{U_{2,4}^{cp}} |x, f(x), g(x) \rangle \otimes | f(x) \rangle
\end{align*}
$$
となる。そして、最後に第 1 〜 3 ビットに関わる $V_f^\dagger$ を適用してビット 2 と 3 を初期状態に戻す。ここの textbook の記述は間違っているように見える:
$$
\begin{align*}
|x, f(x), g(x) \rangle \otimes | f(x) \rangle \xrightarrow{V_f^\dagger} |x, \bar{0}, \bar{0} \rangle \otimes | f(x) \rangle
\end{align*}
$$
すべてをまとめると:
$$
\begin{align*}
|x, \bar{0}, \bar{0} \rangle \otimes | \bar{0} \rangle \xrightarrow{V_f^\dagger U_{2,4}^{cp} V_f} |x, \bar{0}, \bar{0} \rangle \otimes | f(x) \rangle
\end{align*}
$$
となる。ビット 1 〜 3 でメインの演算を行なって、欲しい情報だけ補助ビットに逃しておいて、ビット 1 〜 3 に逆演算を適用して初期状態に戻す、ということのようだ。よって、第 2 〜 3 の補助ビットのことを見ないことにすると、(1) 式のようなことができていることになる。
この辺の話はちょっと抽象化して述べられているので、具体的なケースで都度その回路の事情で眺めたほうが良いだろう。
