情報の側から見ると：ゲートの数は情報量で下から押さえられる

相対エントロピーから情報と物理を組み立てる　第6部 第1章 §6.1.4　★★ $L$ 個のゲートの並びは $L\log_2K$ ビットで書けてしまう。見分けたいユニタリの数がそれより多ければ書き分けられないので、ほとんどのユニタリは $4^n$ に比例する数のゲートを要する

数え上げの議論

万能なゲート集合があれば、どんなユニタリも作れる。では、何個のゲートが要るか。上からの見積もりは2節と3節の構成で $4^n$ 程度だった。下からの見積もりは、構成を工夫しても避けられない限界で、数を数えるだけで得られる。

1回に当てるゲートの選び方が $K$ 通りあるとする。たとえば $\{H,T,\mathrm{CNOT}\}$ を $n$ 量子ビットに当てるなら、$H$ と $T$ はどの量子ビットに当てるかで $2n$ 通り、CNOT は制御と標的の順序つきの対で $n(n-1)$ 通りあり、$K=n^2+n$ である。$L$ 個のゲートの回路は高々 $K^L$ 通りしかない。ここで情報の言葉に直す。回路を1つ指定するのに要るのは、各段で $K$ 通りのどれを選んだかを書いた列で、長さは $L\log_2K$ ビットである。

一方、精度 $\varepsilon$ で互いに見分けたいユニタリの数を数える。全体の位相を除いた $n$ 量子ビットのユニタリは $d_n=4^n-1$ 次元の集合で、互いに $2\varepsilon$ 以上離れた点を詰め込むと、およそ $(c/\varepsilon )^{d_n}$ 個入る（$c$ は $n$ によるが $\varepsilon$ によらない数）。$d$ 次元の箱を幅 $\varepsilon$ の小さな箱に切ると $\varepsilon ^{-d}$ 個に分かれるのと同じ勘定である。これらの点のどの2つも、同じ回路で精度 $\varepsilon$ に近似することはできない。したがって、すべてを近似するには回路の数がそれ以上要り、$K^L\gtrsim(c/\varepsilon )^{d_n}$、すなわち

$$L\log_2K\ \gtrsim\ (4^n-1)\log_2\frac1\varepsilon +(\varepsilon \text{ によらない項}).\tag{6.1.7}$$

左辺は回路を書くのに使えるビット数、右辺は見分けたいユニタリの1つを名指すのに要るビット数である。名指すべきものの数が書ける文字列の数より多ければ、どう工夫しても書き分けられない。第1部第5章（第1部第5章）のデータ圧縮で、$2^\ell$ 個より多くのものを $\ell$ ビットで誤りなく書けないと言ったのと同じ理屈である。

この議論は Knill¹1E. Knill (1995), arXiv:quant-ph/9508006。下の脚注へ閉じるによる。3節の図 6.1.2 で最小距離が異なる元の数の $-1/3$ 乗で下がったのは、1量子ビットの場合 $d_1=3$ だからで、$N$ 個の点で3次元を覆えば1点あたりの持ち分の体積は $1/N$、その幅は $N^{-1/3}$ になる。$\{H,T\}$ の語は1文字ごとに約 $1.30$ 倍に増えたので、1文字で書ける情報量は $\log_21.30=0.38$ ビットにとどまった。

何が分かり、何が分からないか

定理 6.1.11 は、量子計算機で速く解ける問題が「どのユニタリでもよい」問題ではないことを示している。$n=50$ なら $4^{50}=1.27\times10^{30}$ で、1秒に $10^9$ 個のゲートを当てても $10^{21}$ 秒を超え、宇宙の年齢（およそ $4.4\times10^{17}$ 秒）よりはるかに長い。Shor のアルゴリズム（第6部第3章）や量子 Fourier 変換（第6部第2章）が少ないゲートで書けるのは、それらが特別な構造を持つユニタリだからである。

ただし、この議論は「ほとんど」について述べるだけで、特定のユニタリに多くのゲートが要ることは何も言わない。具体的なユニタリについて大きな下限を証明することは、古典の回路の下限と同じく難しく、一般にはできていない。数え上げで得られるのは、存在の議論としての下限である。

逆向きの見方もある。Clifford 群のゲートだけの回路は、状態を $n$ 個のスタビライザーの生成元で書いたままたどることができる。生成元1つは Pauli 行列の列（$2n$ ビット）と符号（$1$ ビット）で書けるので、状態全体は $n(2n+1)$ ビットで足りる。状態ベクトルの $2^n$ 個の複素数を持たなくてよいので、古典の計算機で効率よく真似できる（Gottesman–Knill の定理）。書くのに要るビット数が少ない状態しか通らない回路は、古典の計算を超えない。$T$ ゲートはこの「少ないビットで書ける」性質を壊す。