Shadow bootstrapping: Nearly minimal-setting pure-state tomography with shallow Clifford measurements

技術要約：準最小設定におけるシャドウ・ブートストラップを用いた純粋状態トモグラフィー

問題提起
量子状態トモグラフィー（QST）は、未知の量子状態を測定データから再構成することを目的としている。$n$ 量子ビットの純粋状態 $|\psi\rangle$ （次元 $d=2^n$）に対し、忠実度の誤差 $1 - |\langle \hat{\psi}|\psi\rangle|^2 \le \epsilon$ を達成するための最適なサンプル複雑性は $\Theta(d/\epsilon)$ 個のコピーであることが知られている。このサンプル複雑度は様々なプロトコルによって達成されてきたが、依然として大きなボトルネックとなっているのは、必要とされる異なる測定設定の数である。既存の多くの手法では、設定数が $1/\epsilon$ に対して多項式的に、あるいは $d$ に対して線形に増大するため、回路コンパイルや制御プログラムの変更に伴う大幅な実験的オーバーヘッドが生じる。さらに、膨大な数のショットの生の結果（raw measurement outcomes）を保存することは、メモリ集約的である。本研究の目標は、最適なサンプル複雑性を達成しつつ、ほぼ最小限の測定設定数（理想的には $d$ に依存せず、$1/\epsilon$ に対して多項式対数オーダー）を用い、かつコンパクトなデータ表現からの効率的な古典的後処理を維持することである。

手法
本論文では、非適応的なシングルコピーの浅いクリフォード測定と、「シャドウ・ブートストラップ（shadow bootstrapping）」と呼ばれる斬新な手法を用いた2段階のアルゴリズムを提案している。

1. 測定アンサンブル: プロトコルは2層のクリフォード・アンサンブルを使用する。回路は、$k$ 量子ビットのブロック（ここで $k = \Theta(\log n)$）上で作用する局所的なクリフォードユニタリの交互の層で構成される。これにより、回路深さは $O(\log n)$ が保証される。
2. データ表現: 生のビット列リストを保存する代わりに、アルゴリズムは測定結果を基底ごとのヒストグラムへと集計する。これにより、メモリ要件が削減され、古典的後処理の入力として機能する。
3. 初期化（ツリー再構成）:
   • アルゴリズムは、ターゲットとなる状態 $|\psi\rangle$ と一定の重なり（$\ge 1/2$）を持つ初期推定値 $|\sigma_0\rangle$ をまず構築する。
   • これは、バイナリツリーの葉から根に向かって状態を構築する再帰的再構成フレームワーク（[GGH+26]に着想を得たもの）を通じて達成される（ここでは、接頭辞の測定後の条件付き状態を表す）。
   • 各ノードにおいて、$2 \times 2$ の「再構成行列」がシャドウ推定量を用いてヒストグラムから推定される。この行列の最大固有ベクトルが、子となる推定値を結合するための係数を提供する。
   • この段階では $O(d)$ 個のコピーと $O(n^3)$ 個の測定設定を使用し、初期推定値が次の段階をブートストラップするのに十分な精度であることを保証する。
4. シャドウ・ブートストラップ（反復精緻化）:
   • 中核となる革新技術は、一定数の「新しい」測定設定のみを使用して、各段階でターゲットとする忠実度の誤差を半分にする反復的な精緻化プロセスである。
   • 分散減少: 標準的なシャドウ推定量は、測定基底のランダムな選択により変動する。シャドウ・ブートストラップは、現在の推定値 $|\sigma_{t-1}\rangle$ を参照用として用いることで、これを軽減する。
   • 残差推定: 新しいバッチの測定に対して、アルゴリズムは $|\sigma_{t-1}\rangle$ に基づく理論的な予測と、経験的なシャドウ推定量との差として定義される「残差推定量」を計算する。
   • 参照状態 $|\sigma_{t-1}\rangle$ が真の状態に近いことから、予測は観測された頻度と密接に一致し、その結果、残差の分散は全次元ではなく、現在の誤差のスケールに従うようになる。
   • アルゴリズムは、平均的な残差を前の状態ベクトルに加えて正規化することで、推定値を更新する。
   • このプロセスは $J = O(\log(1/\epsilon))$ ステージ繰り返される。ショットノイズを抑制するために、1基底あたりのショット数 $S_t$ は指数関数的に増加する（$S_t \propto 2^t$）一方で、各ステージにおける新しい基底の数 $N_t$ は一定（$N_t = O(1)$）に保たれる。
5. 古典的後処理:
   • アルゴリズムは、高密度の $d \times d$ シャドウ行列を形成することを回避する。代わりに、クリフォード・アンサンブルの構造とワルシュ・アダマール変換を利用して、ベクトルに対して直接逆シャドウチャネルを適用する。
   • これにより、ヒストグラムから直接、ベクトルの更新および計算を $\tilde{O}(d)$ の時間とメモリで行うことが可能になる。

主な貢献

• シャドウ・ブートストラップ: 現在の状態推定値を用いて、後続の残差推定量の分散を低減させ、一定数の新しい測定設定を用いて高精度な再構成を可能にする技術。
• 準最小の設定: 本アルゴリズムは、最適なサンプル複雑性 $O(d/\epsilon)$ を達成しつつ、$\tilde{O}(1)$ 個（具体的には $O(n^3 + \log(1/\epsilon))$ 個）の異なる測定基底のみを使用する。これは、精度や次元に依存して設定数が増大する従来の手法に対する大幅な改善である。
• 効率的なヒストグラム処理: ヒストグラムから直接、近似線形時間（$\tilde{O}(d)$）の古典的後処理を行う方法を提示し、高密度の行列構築を回避する。
• 浅い回路: プロトコルは、深さ $O(\log n)$ の非適応的なクリフォード測定を利用しており、近未来のデバイス（NISQデバイス等）への適用が可能である。

結果
本論文は、$n$ 量子ビットの純粋状態 $|\psi\rangle$ および目標忠実度 $\epsilon$ に対し、以下の理論的保証を確立している：

• サンプル複雑性: $T = O(d \log(1/\delta) / \epsilon)$ 個のコピー。これは対数因子を除いて最適である。
• 測定設定数: $N = \tilde{O}(1)$ （具体的には $O(n^3 + \log(1/\epsilon))$ 個）。
• 回路深さ: $O(\log n)$。
• 古典的実行時間: 基底ごとのヒストグラムが与えられた場合、$\tilde{O}(d)$ 時間（$d, 1/\epsilon, 1/\delta$ に関する多項式対数因子は無視できる）。
• 成功確率: アルゴリズムは、確率少なくとも $1-\delta$ で $1 - |\langle \hat{\psi}|\psi\rangle|^2 \le \epsilon$ を満たす状態 $|\hat{\psi}\rangle$ を出力する。

意義
著者らは、これが以下のすべてを同時に達成する最初のアルゴリズムであると主張している：

1. 最適なサンプル複雑性 ($O(d/\epsilon)$)。
2. （次元 $d$ に依存せず、$1/\epsilon$ に対して多項式対数オーダーの）準最小の測定設定数。
3. コンパクトなヒストグラムデータからの、近似線形な古典的後処理時間。
4. 浅い測定回路 ($O(\log n)$ 深さ)。

測定設定の数を精度や次元から切り離すことにより、本研究は回路コンパイルや制御のオーバーヘッドの問題に対処している。さらに、ヒストグラムと効率的なベクトルベースの更新を用いることで、古典的な再構成のメモリおよび計算負荷を軽減し、高精度な純粋状態トモグラフィーのスケールアップを可能にしている。また、シャドウ・ブートストラップの技術は、低ランク混合状態のトモグラフィーやチャネル学習への応用も期待されている。