Learning Sparse Quantum States

技術要約：疎な量子状態の学習

問題提起
本論文は、$k$-疎（$k$-sparse）な量子状態に対する量子状態トモグラフィーの問題を扱う。古典的な分布学習アルゴリズムは、サポートサイズ $k$ に対して効率的にスケールするが、標準的な量子状態トモグラフィーアルゴリズムは、状態が特定の基底（具体的には計算基底）において疎な構造を持っているかどうかにかかわらず、一般に全ヒルベルト空間の次元（$2^n$）または密度行列のランクに依存してスケールしてしまう。著者は、サンプルおよび時間計算量が $2^n$ ではなく、疎性 $k$（および混合状態の場合はランク $r$）に対してニア線形にスケールするアルゴリズムを開発することで、このギャップを埋めることを目的としている。

手法
本論文は、位相状態から一般的な純粋状態、そして最終的に混合状態へと進む、疎な状態を学習するための統一的なアプローチを提示している。

1. 疎な位相状態の学習:
   著者はまず、$k$-疎な位相状態 $|\psi\rangle = \frac{1}{\sqrt{k}}\sum_{x \in S} e^{i\theta_x}|x\rangle$ （ここで $|S|=k$）を取り扱う。アルゴリズムは2つの段階で進行する：

   • サポートの特定: サポート集合 $S$ は、クーポンの収集者問題（coupon collector argument）を利用して、計算基底で状態を $O(k \log k)$ 回近似的に測定することによって学習される。
   • 位相回復: サポートが既知となった後、アルゴリズムは相対位相 $\theta_x$ を学習する。これは、頂点が基底状態であり、エッジが学習可能な相対位相を表すグラフを構築することによって達成される。著者は、$\mathbb{F}_2$ 上のランダムな線形関数（ハッシュ関数）の集合を用いて、基底状態のペアを同じ出力にマッピングする。ハッシュレジスタを測定することで、状態は2つの基底状態の重ね合わせ $|x_1\rangle + e^{i(\theta_{x_2}-\theta_{x_1})}|x_2\rangle$ に射影され、これにより単一量子ビットのトモグラフィーを通じて相対位相を推定することが可能になる。
   • グラフの連結性: 主要な技術的貢献は、少数の（$O(\log k)$ 個の）ランダムな線形関数が、直径 $O(\log k)$ のグラフを生成するのに十分であることを証明した点である。これにより、任意の基底状態の位相を、学習された相対位相の短いパスを経由して参照状態に対して決定できることが保証される。

2. 一般的な疎な純粋状態の学習:
   一般的な $k$-疎な純粋状態 $|\psi\rangle = \sum_{x \in S} \sqrt{p_x}e^{i\theta_x}|x\rangle$ について、確率は非一様である。著者は、古典的な分布学習からの「バケツ分け（bucketing）技術」を用いて、位相状態のアルゴリズムを適応させる：

   • 前処理: 古典的な分布学習アルゴリズムが、サポートを特定し、各基底状態を確率レベル（確率が近似的に一様となる区分）ごとに「バケツ」に分割する。
   • バケット化された位相学習: 位相グラフの構築は、各バケツに対して個別に適用される。極めて重要な点として、グローバルな位相の一貫性を確保するために、共通の参照状態（最も確率の高い基底状態）がすべてのバケツに含まれる。
   • 誤差の割り当て: サンプル複雑性は、各バケツの確率質量に比例して割り当てられる。低確率の状態は、低い精度で学習される。これは、全体のフィデリティへの寄与度と一致しており、位相グラフにおける単一のエッジが過剰なサンプルを必要とする「低確率ボトルネック」を防ぐものである。

3. 疎な混合状態の学習:
   $k$-疎なランク $r$ の混合状態に対して、著者は**ランダム純粋化チャネル（random purification channel）**の手法を用いる。

   • 簡約: 混合状態 $\rho$ の $m$ 個のコピーを、$m$ 個の一様にランダムな純粋化 $|\rho\rangle$ に変換する量子チャネルを利用する。
   • 疎性の保存: $\rho$ が $k$-疎かつランク $r$ である場合、そのランダム純粋化は $kr$-疎な純粋状態になることが示されている。
   • アルゴリズム: その後、これらの純粋化されたサンプルに対して純粋状態トモグラフィーアルゴリズムを適用し、混合状態を再構成する。

主要な結果と計算量境界
本論文は、以下の計算量境界を確立している（$k, n, 1/\epsilon$ の多項式対数因子を省略）：

• 純粋状態: 未知の $n$ 量子ビット $k$-疎純粋状態に対し、アルゴリズムは $|\langle \psi | \hat{\psi} \rangle|^2 \geq 1 - \epsilon$ となる推定値 $|\hat{\psi}\rangle$ を以下の量を用いて出力する：

  • サンプル複雑性: $\tilde{O}(k/\epsilon)$ 個のコピー。
  • 時間複雑性: $\tilde{O}(kn/\epsilon)$。
    これらの境界は、多項式対数因子を除いて最適であり、$k \ll 2^n$ の場合に一般的なトモグラフィーよりも指数関数的に改善されている。

• 混合状態: 未知の $n$ 量子ビット $k$-疎ランク $r$ 混合状態に対し、アルゴリズムは $F(\rho, \hat{\rho}) \geq 1 - \epsilon$ となる推定値 $\hat{\rho}$ を以下の量を用いて出力する：

  • サンプル複雑性: $\tilde{O}(kr/\epsilon)$ 個のコピー。
  • 時間複雑性: $\text{poly}(m, n)$、ここで $m$ はサンプル複雑性である。
    サンプル複雑性はニア最適である。しかし、時間複雑性は $r > 1$ の場合、現在はランダム純粋化チャネルの実装（Schur変換に依存）によって支配されているため、まだ最適ではない。

意義と主張
著者は、本研究が、疎な量子状態を学習するための初のニア最適アルゴリズムを提供し、次元 $2^n$ ではなくサポートサイズ $k$ にスケールするサンプルおよび時間複雑性を達成したと主張している。

• 最適性: 純粋状態アルゴリズムは、$n, k, 1/\epsilon$ のパラメータにおいて、サンプルおよび時間の両面で（対数因子を除いて）最適であることが示されている。
• 多項式時間学習: これらの結果は、効率的に計算可能な基底において疎な状態（$k = \text{poly}(n)$）の場合、学習が多項式時間で行えることを意味する。これは、スタビライザー状態や行列積状態を超えて、効率的に学習可能な量子状態の範囲を広げるものである。
• 堅牢性: アルゴリズムは微小なノイズに対して堅牢であり、正確な疎性パラメータ $k$ を入力として厳密に必要としない。上限値を用いるか、動的にサポートを学習することで機能する。
• 未解決問題: 本論文は、主要な未解決問題として、ランダム純粋化チャネルの改良による、$k$ および $r$ に対して効率的にスケールする混合状態トモグラフィーのための時間最適アルゴリズムの取得を挙げている。また、純粋状態の時間複雑性における多項式対数因子の除去も、今後の課題として残されている。

本研究は、特定のクラスの状態（例：GHZ、W、ディケ、および疎な位相状態）の学習や、擬似ランダム量子状態のセキュリティ分析といった理論的な含意を除き、新しい実験的セットアップや具体的な応用を提案するものではない。