量子ビットを一つずつ測って、どの量子ビットどうしが結びついた状態なのかを調べたい。測り方を最初にすべて決める場合と、結果を見ながら次の測り方を変える場合とでは、必要な試行数に差が出るのでしょうか。
2026年11月12日公開のMatteo De Francescoによるプレプリントは、結びつきをグラフで表す「グラフ状態」について、この違いを理論的に調べました。測り方を変える利点を示したのは、二つの組に分けられるなどの条件を満たすグラフです。すべての量子状態で測定を減らせるという結果ではありません。
簡単にまとめると?
- 測り方を事前に固定すると、疎なグラフ状態の学習には、各頂点のつながりの数に対して二乗で増える量の試行が必要になります。
- 特定の二部グラフでは、先に得た結果から次に測る頂点の組を選び、必要な試行数を抑えられます。二つの組の分け方を最初から知っていれば、さらに少ない試行で済みます。
- 扱うのは理想的な状態を繰り返し用意できる場合の試行数です。実機の雑音への強さや、古典計算を含む総実行時間の短縮は別の問題です。
未知なのは、グラフ状態を表す辺の組合せ
グラフ状態では、番号の付いた量子ビットを頂点、状態を作る際の結びつきを辺で表します。測定を使って量子計算を進める方式や、量子誤り訂正でも使われる状態の一種です。ここで学習したいのは、理想的なグラフ状態の辺の組合せであり、装置内の物理配線を直接撮影することではありません。
論文は、同じ未知の状態を独立に何度も準備できると仮定します。この一回分を「コピー」と数えます。未知の量子状態を勝手に複製する操作を許すという意味ではなく、同じ準備手順を繰り返す設定です。一回の試行では、各量子ビットをX・Y・Zという三つの測定方向のいずれかで測ります。
量子ビット数をn、各頂点につながる辺の数をdとします。すべての頂点でdが同じなら「d正則グラフ」です。求めるのは、対象となるどのグラフに対しても、少なくとも3分の2の確率で正しい辺を特定できる試行数です。平均的な一例だけで成功する条件とは異なります。
一度測るだけでは、すべての結びつきが見えるわけではない
測定結果そのものはランダムでも、適切な方向を選ぶと、いくつかの結果を合わせた偶奇が必ず一致することがあります。この固定された関係を表すのが「スタビライザー」です。
たとえば、A―B―Cという三つの頂点の鎖を説明用に考えます。中央のBをX、両隣をZで測り、結果の符号を0・1に直すと、Bの値は両隣の値の足し算を2で割った余りに一致します。この鎖は後で述べる正則グラフの定理の例ではありませんが、隣接関係が測定結果の偶奇として現れる仕組みを説明できます。
実際の学習では、Bの隣が誰なのかが分かりません。隣接する頂点の候補を並べ、何度も測った結果とつじつまが合わない候補を除きます。真の隣接関係なら、この偶奇の関係を毎回満たします。
ただし、隣り合う頂点を同時にXで測ると、上の単純な読み取り方は使えなくなります。論文はXだけでなくYを含む測定も扱い、一回の結果から得られる情報を、隣接行列の一部から作る連立方程式の自由度で上から抑えました。これは、どの測り方でも同じ量の情報が得られるわけではない、という制約を数式にしたものです。
事前に固定する測定では、dの二乗が避けられない範囲がある
測定方向を最初にすべて決め、途中の結果を使わない方式を「非適応」と呼びます。ランダムに決めてもよく、試行どうしの測り方に相関を持たせても構いません。禁止しているのは、得られた結果に応じて後の測り方を変えることです。
先行研究では、必要な試行数がd² log n程度で済む方式が知られていました。今回の主な新しさは、この増え方が必要でもあることを示した点です。十分大きいn、d≧2、ndが偶数、d³ ln n≦nという範囲で、非適応な単一量子ビットのパウリ測定にはΘ(d² log n)回が必要になります。Θは定数倍を除けば上限と下限が同じ増え方である、という記号です。
この下限は、測定後の古典計算を強力にしても残ります。測定で取り出せなかった情報を、後処理だけで補うことはできないためです。また、少しだけ辺を間違えてよいとしても、十分小さい一定割合の誤りを許す範囲では、同じ増え方の下限が残ります。
この結果を、dがどれほど大きくても成り立つ式として使うことはできません。特にd³ ln n≦nという条件は、グラフが十分に疎であることを要求しています。
二部グラフなら、分かった層を足場に次の測定を選べる
適応的な方式が役立つ例として、論文は二部グラフを扱います。頂点を二つの組に分けられ、同じ組の中には辺がなく、辺は組をまたぐ場合だけに存在するグラフです。ただし学習者には、どの頂点がどちらの組に属するかを教えません。
もし辺でつながっていない頂点の集まりが分かれば、その集まりを一斉にX、残りをZで測れます。集まりの各頂点について、隣接関係を並行して読み取る準備が整うのです。
そこで一つの頂点から始め、その隣、そのまた隣という順に調べる幅優先探索を使います。二部グラフでは、出発点からの最短距離が同じ頂点どうしには辺がありません。すでに分かった一層をXで測る対象にして、その隣接関係から次の層を見つけます。毎回別に準備した状態を使い、前の層の結果で次の測定方向を決めます。
対象は、つながったd正則の二部グラフで、任意の二頂点を結ぶ最短経路の最大長、すなわち「直径」が十分短いものです。定理では、十分大きい偶数n、d≧⌈ln n⌉、d³ ln n≦nに加えて、直径が⌈16 ln n/ln ln n⌉以下という条件を置きます。一般のグラフでは同じ層に辺があり得るため、この手順をそのまま使う保証はありません。
| この二部グラフの条件での方式 | 最初に分かること | 必要な試行数の増え方 |
|---|---|---|
| 非適応なX・Y・Z測定 | 二つの組の分け方は不明 | Θ(d² log n) |
| 層ごとに変えるX・Z測定 | 分け方は不明。結果から探索 | O(d log² n/log log n) |
| 固定したX・Z測定 | 二つの組を最初から知っている | Θ(d log n) |
表は原論文の条件と結果を整理したものです。Oは、示された手順でその程度の試行数に収まるという上限です。適応方式の行では、これ以上減らせないという最適性まで証明したわけではありません。
測り方を変える効果と、事前知識の価値を分ける
二つの組が最初から分かるなら、一方をX、もう一方をZで測る同じ設定を繰り返すだけで、すべての辺を調べられます。途中で測り方を変える仕組みそのものが常に必要なのではなく、知らなかった構造を測定から発見するために役立つ、という関係です。
適応方式の改善幅も、dがnとともにどう増えるかで変わります。たとえばdがnの4分の1乗程度となる範囲では、非適応のΘ(nの2分の1乗×log n)に対し、構成された適応方式はO(nの4分の1乗×log² n/log log n)となります。これは大規模になったときの増え方の比較であり、特定の量子装置で何回測ればよいかを直接与える数値ではありません。
試行数が減っても、実験全体が速くなるとは限らない
まず、この論文は雑音のないグラフ状態を仮定しています。辺を少し間違えてよいという許容条件は、準備や測定に雑音が混ざっても同じ保証があることを意味しません。状態の忠実度や、未知の測定結果を予測する精度も、辺の特定とは別の評価です。
次に、提示された学習手順は隣接関係の候補を網羅的に調べます。古典計算の時間はnのO(d)乗となり得るため、試行数の節約と計算時間の節約は一致しません。前の結果を処理し、次の状態の測定設定へ反映する時間も、実装では考える必要があります。
さらに、今回の中心となる適応は、一回の状態を測っている途中で次の量子ビットの測り方を変えるものではなく、独立に準備した状態と状態の間で行います。任意の測定方向や、複数のコピーを結合して測る方法は、比較する資源が違います。
論文が示す判断材料は、測定方向を事前に固定するコストと、対象の構造を知る価値です。実験に取り込むなら、対象がこの二部グラフの条件を満たすか、雑音をどう扱うか、候補探索の古典計算が間に合うかを合わせて確かめる必要があります。一般の疎な正則グラフでも適応が有効か、また適応方式の最適な試行数はどこまで下がるかは、未解決のままです。
出典
- Matteo De Francesco, Learning Sparse Graph States with Local Pauli Measurements: Tight Nonadaptive Bounds and an Adaptive Separation, arXiv:2611.16456v1、2026年11月12日公開。定理1〜3・14、命題15、表1、議論と付録A〜Eを参照。プレプリント。原資料はCC BY 4.0。本文と比較表は条件を選び直して日本語で説明したもので、原文の翻訳全文や原表の複製ではありません。
