Complexity of graph-state preparation by Clifford circuits

あなたは、目に見えない光るブロックを使って、巨大で複雑な彫刻を作ろうとしていると想像してください。量子コンピューティングの世界では、これらのブロックは「量子ビット（qubit）」と呼ばれ、それらを使って構築される特別な構造は「グラフ状態」と呼ばれます。グラフ状態とは、接続のマップのようなものです。すべてのブロックは点であり、2つのブロックが特別な量子的な「握手」によって「リンク」されるたびに、その間に線が引かれます。これらの構造は、非常に強力な量子コンピュータのための秘伝のソースであり、いつか暗号を解いたり新しい薬をシミュレーションしたりできる計算を行うための原材料となります。しかし、ここに落とし穴があります。これらのブロックを繋ぎ合わせるための「糊（のり）」を作ることは困難です。この糊とは、「2量子ビット・クリフォード演算」（多くの場合CZゲートと呼ばれるもの）という特定の種類の量子操作です。現実の世界では、この糊を塗る作業はコストがかかり、時間がかかり、エラーが発生しやすいのです。そこで、科学者たちは極めて重要な問いを投げかけます。特定の形を作るために必要な「糊」の絶対的な最小量はどれくらいか？ もし、複雑に絡み合ったネットワークがあったとしても、何百万滴もの糊が必要なのか、それとも賢く立ち回ればわずかな量で済ませられるのか？

桑部総、森隆平、および吉村雄星によるこの論文は、この問いを深く掘り下げています。彼らはこの問題をパズルとして扱い、許可されたツール（単一量子ビットの反転、測定、そしてあの貴重な2量子ビットの糊）だけを使って、いかに効率的にこれらの量子的な形を構築できるかを問うています。彼らは、答えは単に図の中に描かれた線の数を数えることではなく、その形の隠れた「骨格」にあることを発見しました。彼らは、任意のグラフ状態の変換を、点の削除、局所的な近傍の反転、そしていくつかの特定の「エッジ・トグリング（端子の切り替え）」といった一連の動きを用いて記述する巧妙な方法を見出しました。この新しい言語を用いることで、彼らは、グラフを構築する難易度は「ランク幅（rank-width）」と呼ばれる数学的特性と密接に関連していることを証明しました。もしグラフが低いランク幅（つまり、単純な樹形構造に近い構造）を持っていれば、非常に効率的に構築できます。しかし、グラフが乱雑で複雑であれば、必要な糊の量は増えていきます。彼らはさらに、「区間グラフ（interval graphs）」や「円グラフ（circle graphs）」のような非常にトリッキーな形状であっても、依然として驚くほど少ない操作数、具体的には $O(n)$ および $O(\log n)$ の操作で構築できることを示しました。

量子の糊のパズル

まずは基本から始めましょう。手元に、接続されていない空の量子ドットがたくさんあると想像してください。あなたの目標は、それらを特定の接続パターン、すなわち「グラフ状態」へと変えることです。量子の世界では、2つのドットをただパチンと繋ぐことはできません。2つのドットを繋ぐために、あなたは「クリフォード演算」と呼ばれる特定のダンスを行わなければなりません。このダンスの中で最もコストがかかる部分は、2つのドットをリンクさせる「2量子ビット演算」です。著者らは、これをグラフを構築するための「CZ複雑性（CZ-complexity）」と呼んでいます。これは、グラフの「値札」のようなもので、実行しなければならない高価な2ドット間のリンクの数で測定されます。

論文は、よくある誤解を明確にすることから始まります。複雑な形を作るには、単にマップ上のすべての線を引けばよいと思うかもしれません。エッジ（辺）の数が $m$ であるグラフの場合、それは $m$ 回の操作を必要とします。しかし、著者らは、もっと賢い方法があることを示しています。まるで、平らな図面にある線の数よりも少ない折り目で複雑な折り紙の鶴を作るように、あなたは「局所クリフォード演算」（これは、新しい糊を加えることなく、紙を折ったり捻ったりするようなものです）を使用して、作業を開始する前に形を簡略化することができるのです。

チームは、これを考える新しい方法を導入しました。単にエッジの数を数えるのではなく、グラフを以下の3つの特定の動きを使ってどのように変換できるかに注目します：

1. 頂点の削除： マップからドットを取り除く。
2. 局所補完（local complementation）： あるドットの近傍の接続を反転させる高度な動き（もし隣人同士が接続されていたら切断し、接続されていなければ接続する）。
3. 基本エッジ補完（elementary edge-complementation）： これが実際の「糊」の動きです。これには3つの種類があります：単一のエッジを切り替える、ドットとその隣人の隣人たちの間のすべてのエッジを切り替える、あるいは、2つの別々の近傍グループ間のエッジを切り替える。

ここでの大きな発見は、組合せ論的な特徴付けです。著者らは、もしあるグラフを、最大 $t$ 回のこれらの「糊」の動き（および無料の折り曲げや削除の動き）を用いて別のグラフに変換できるならば、その2つのグラフは非常に特定の数学的な関係にあることを証明しました。これは、グラフを構築する「コスト」が、単純な空のグラフからターゲットとなる形状へと変換するために必要な、これら特定の「エッジ・トグリング」の最小回数と正確に一致することを意味しています。

隠れた骨格：ランク幅

では、あらゆる可能な動きの組み合わせを試すことなく、どのようにしてこのコストを予測できるのでしょうか？ 著者らは「ランク幅」という概念に目を向けました。グラフを絡まった毛糸玉だと想像してください。ランク幅とは、その毛糸玉がどれほど「樹形図（ツリー）に近いか」を示す尺度です。ランク幅が低いグラフは、整理された整然とした木のようなものです。ランク幅が高いグラフは、混沌とした、結び目の多い塊です。

論文は、この「絡まり具合」とグラフ構築のコストとの間の強力な関係を確立しています。彼らは、頂点数 $n$ とランク幅 $r$ を持つ任意のグラフについて、以下を証明しました：

• 上限（Upper Bound）： グラフは常に、およそ $O(rn)$回の操作で構築できます。グラフが単純（$r$ が低い）であれば、コストは低くなります。
• 下限（Lower Bound）： グラフが連結されている場合、これより少ない $n + r - 2$ 回の操作で構築することはできません。

これは非常に重要なことです。なぜなら、これは私たちに厳しい限界を与えるからです。これは、私たちのアルゴリズムがいかに巧妙であっても、これらの数値を打ち破ることはできないということを教えてくれます。例えば、ランク幅が1のグラフ（多くの単純な樹形構造が含まれます）の場合、コストは正確に $n - 1$ です。これは、単純なドットの列を構築するコストと一致しており、これらの形状については、最も単純な方法よりも優れた方法は存在しないことを証明しています。

しかし、著者らは、非常に複雑なグラフではコストが高くなることも示しています。彼らは、カウントの議論を用いて、コストが少なくとも $rn / \log n$ に比例するグラフが存在することを示しました。これは、グラフが複雑になる（ランク幅が高くなる）につれて、必要な「糊の滴」の数が著しく増加することを意味しています。

特殊なケース：ルールが変わる時

論文は一般的なルールを述べるだけでなく、厄介であることで知られる特定のタイプのグラフについても取り組んでいます。

• 区間グラフ（Interval Graphs）： これらは、直線上の重なり合う区間（会議のスケジュールのよう）を表すグラフです。これらは高いランク幅を持つことがありますが（つまり複雑ですが）、著者らはこれらをわずか $2n - 2$ 回の操作で構築する方法を見つけました。これは線形なコストであり、非常に効率的です。
• 円グラフ（Circle Graphs）： これらは円上の弦を表します。これらはさらに複雑ですが、著者らはこれらが約 $1.262 \cdot (n - 1) \log_2(n + 1)$ 回の操作で構築できることを示しました。これは単純な直線よりは多いものの、最悪のケースと比較すればはるかに優れた数値です。

著者らはまた、「ワーキング・量子ビット（working qubits）」に関する微妙な点についても言及しています。一部の量子アルゴリズムでは、構造を構築するために追加の一時的なドットを使用し、その後それらを捨てることがあります。論文では、この追加のドットの使用を許容するように複雑性の尺度を定義していますが、彼らの例においては、これらを使用してもコストが下がらないようであると述べています。彼らは、これらの寛大な設定においても下限を証明しており、彼らの結果が非常に堅牢であることを示しています。

なぜこれが重要なのか

なぜ、好奇心旺盛なティーンエイジャーが「量子の糊の滴」を数えることに興味を持つ必要があるのでしょうか？ それは、現実の世界において、量子コンピュータは非常に脆弱だからです。2量子ビット演算を行うたびに、エラーを導入するリスクが生じます。もし、ある状態を構築するために1,000回の操作が必要であれば、あなたのコンピュータは完了する前に停止してしまうでしょう。もし、わずか10回の操作でそれを構築する方法が見つかれば、成功する可能性は格段に高まります。

この論文は、その効率性のための設計図を提供しています。グラフ状態の構築コストをランク幅に結びつけることで、エンジニアに対して、「これは難しい」あるいは「これは簡単だ」と即座に判断できる手段を与えています。これは、問題の構造そのものが、解決の難易度を決定しているということを教えてくれます。もし、機能する量子コンピュータを作りたいのであれば、問題のランク幅を低く設計するか、あるいは複雑な形状をより単純なパーツに分解する巧妙な方法を見つける必要があります。

著者らは単にこれらの数値を推測したのではなく、数学的に証明しました。連結グラフについては、コストが少なくとも $n + r - 2$ であることを示し、特定のグラフについては、これらの限界に達する正確なアルゴリズムを提供しました。彼らは宇宙のあらゆる可能なグラフを解いたわけではありませんが、ほとんどのグラフ状態の複雑さを理解するための道具を与えてくれました。それは、まさに、どのような地形を通過する際にも正確にどれくらいの燃料が必要かを教えてくれる地図を持っているようなものであり、量子という目的地に到達する前にガス欠にならないことを保証してくれるのです。