Pseudoentanglement in constant depth: How trivial states can have non-trivial entanglement structure

本論文は、定数深さの量子回路が、Dense-Sparse LPN仮定に基づき、推定不可能なもつれエントロピーを持つ擬似もつれ状態を生成できることを示し、それによって浅い回路領域における擬似もつれと擬似ランダム性を分離し、局所ハミルトニアン基底状態の量子もつれ構造を学習することに対する量子的な困難性を確立するものである。

要約

ビッグアイデア：「単純な回路」の「魔法」

コイン（量子ビット）をたくさん用意し、それらを回転させて特定のパターンを作り出すマシンを想像してみてください。量子力学の世界では、このマシンのことを量子回路と呼びます。

通常、もしマシンが非常に単純で高速（科学者が「定数深さ（constant depth）」かつ「局所的（local）」と呼ぶもの）であれば、それは単純なパターンしか作り出すことができません。これは、レゴブロックで遊んでいる子供のようなものです。もし子供が一度に触れられるブロックが限られていて、高く積み上げることができないなら、複雑なお城を作ることはできません。ただ平坦で単純な形しか作れないのです。

量子物理学において、「単純な」形は**自明な状態（trivial states）と呼ばれます。これらは、システムの各部分が互いに深く結びついていないため、退屈なものです。一方で、「複雑な」形はもつれ状態（entangled states）**です。これは、たとえパーツ同士がどれほど離れていても、一方の変化が瞬時にもう一方に影響を与えるほど、パーツ同士が密接にリンクしている状態を指します。

この論文の主要な発見は、驚くべきことです： 著者は、非常に単純で高速なマシン（リーチの短い子供のようなもの）でありながら、信じられないほど複雑で深く結びついた状態を生み出す方法を見つけ出しました。

しかし、一つ注意点があります。マシン自体は単純であり、その手順（設計図）は公開されています（誰でもその仕組みを見ることができます）が、そこで生み出された**「つながりの量（もつれ／エンタングルメント）」**は、計算によって素早く解明することが事実上不可能な「秘密」なのです。

コアとなる概念：擬似もつれ（Pseudoentanglement）

これを理解するために、暗号学における2種類の「隠されたもの」を見てみましょう。

1. 擬似ランダム性（Pseudorandomness）： 完璧にシャッフルされた（ランダムな）トランプのデッキを想像してください。見た目は完全にランダムに見えますが、実は特定の単純なルールによって作られたものです。もしあなたがそのルールを知らなければ、このデッキが本当のランダムなデッキであるのか、それともルールに基づいたものなのかを区別できません。
2. 擬似もつれ（Pseudoentanglement - 今回の新しい発見）： カードの間に非常に特定の、複雑なパターンのつながりがあるように見えるデッキを想像してください。観察者にとって、そのデッキが「高い結合度」を持つパターンなのか、それとも「低い結合度」を持つパターンなのかを見分けることは不可能です。たとえそのデッキが非常に単純なマシンによって作られたとしても、です。

画期的な成果：
長い間、科学者たちは、もしマシンが十分に単純で、素早く「学習」できるもの（単純な量子マシンはそうです）であれば、何も隠すことはできないと考えてきました。マシンを見れば、その仕組みを理解でき、それが何をするのかを正確に知ることができるはずだと考えていたのです。

しかし、この論文は**「その考えは間違っている可能性がある」*ことを証明しています。マシンを見ても、それが単純であることを理解しても、出力される「つながり（エンタングルメント）」がどれほどであるかを計算することは、依然として完全に不可能なのです。マシンは公開されていますが、そのもつれ*は隠されています。

どうやって実現したのか：「秘密のコード」の比喩

著者は、**ランダム符号化（Randomized Encoding）**と呼ばれる巧妙なトリックを用いました。

メッセージ（計算）を友人に送りたいけれど、結果は受け取らせつつ、メッセージ自体は隠したいとします。

• 従来の方法： メッセージをスクランブル（暗号化）するために、巨大で複雑なマシンが必要でした。
• 新しい方法（本論文）： 単純で局所的なマシンを使用し、非常に特定の方法でメッセージに「ノイズ（ランダム性）」を加えます。

次のように考えてみてください：

1. 単純な数学の問題があります： $y = M \times x$。
2. 通常、数字が膨大であれば、これを計算するには深く複雑な回路が必要です。
3. 著者は、この「ラッパー（包み）」を作成しました（ランダム符号化）。このラッパーは、単純な入力とランダムなノイズを取り込み、それらを一連の小さな単純なスイッチ（CNOTゲート）のグリッドへと通していきます。
4. 出力は、ランダムなビットの混乱した塊のように見えます。
5. 魔法の正体： もしあなたが秘密の「デコーダー（復号器）」を知っていれば、その混乱を片付けて答えを得ることができます。しかし、単にその混乱した状態を見ただけでは、元の数学の問題が「簡単（低い結合度）」だったのか、「難しい（高い結合度）」だったのかを判別することはできません。

著者は、このラッパーが、すべてのスイッチが隣接する要素のみに触れるように（例えば、2Dグリッド上でメモを回し合う人々のように）設計しました。これにより、マシン全体が**定数深さ（constant depth）となり（サイズに関わらず同じ時間で終了する）、かつ局所的（local）**になります（長距離の配線がない）。

2つの結果：2Dと1D

この論文は、これが2つの異なる物理的セットアップで機能することを示しています。

1. 2Dグリッド（平らな床）：
   床が正方形のタイルで覆われている様子を想像してください。マシンはそのタイル上に構築されています。接続は、床上の隣人同士の間でのみ発生します。著者は、この単純な2Dの床の上であっても、「エンタングルメント・ギャップ（単純な状態と複雑な状態の差）」が非常に大きく、かつ誰もそれを測定できない状態を作り出せることを証明しました。

2. 1Dライン（線路）：
   タイルが線路のように、一本の線状に並んでいる様子を想像してください。通常、1Dラインは2Dグリッドよりも制約が強いものです。著者は、この2Dマシンを「平坦化」して長い線にし、そこに「履歴（マシンが行ったすべてのステップの記録）」を加えました。

   • 結果： この単純な1Dの世界においても、システムの基底状態（最低エネルギー状態）には、隠されたエンタングルメント・ギャップが存在します。
   • なぜ重要か： これは、最も制約の強い1Dの世界においてさえ、構築ルールを見ただけでは、システムがどれほど「量子的なのか」を簡単に予測することはできないということを証明しています。

「なぜこれが重要なのか？」（過剰な宣伝なしに）

この論文は、新しい電池を作ったり病気を治したりすると主張しているわけではありません。代わりに、コンピュータサイエンスと物理学における理論的なパズルを解決しています。

• 「ランダム性」と「もつれ」の分離： 「ブラックボックス（秘密のマシン）」を使わなくても、もつれを隠すことができることを証明しました。つまり、公開された単純なマシンであっても、その「もつれの強さ」を隠すことができるのです。これにより、「擬似ランダム性（状態全体を隠すこと）」と「擬似もつれ（結合の強さだけを隠すこと）」という概念を切り離しました。
• 学習の困難性： 特定のタイプの量子システム（具体的には「局所ハミルトニアン」によって記述されるもの）において、それらがどれほどもつれているかを学習することは、計算的に不可能であることを示しています。たとえシステムの設計図（ブループリント）を持っていたとしても、コンピュータは合理的な時間内で答えを導き出すことはできません。

一文でのまとめ

著者は、単純で公開されており、かつ高速な量子マシンを構築することで、粒子の「つながり」が計算不可能なほど複雑な状態を作り出し、最も単純な量子マシンであっても複雑な量子的秘密を隠し持てることを証明しました。

技術概要

技術要約：定数深さにおける擬似もつれ（Pseudoentanglement）

問題設定
もつれ（エンタングルメント）の研究は量子情報の中核であるが、量子状態のエンタングルメント・エントロピーを推定することは、量子コンピュータを用いても一般に計算量的に困難である。これが「擬似もつれ（pseudoentanglement）」という概念を動機づけている。これは、ある量子状態の族であり、その状態自体は効率的に準備可能であるにもかかわらず、そのエンタングルメント構造が異なるエンタングルメント・エントロピーを持つ状態と計算量的に区別できないものである。

重要な未解決問題は、擬似もつれと「擬似乱数性（pseudorandomness）」との関係にある。擬似乱数状態（PRS）や擬似乱数ユニタリ（PRU）は、準備回路を隠蔽するか、あるいは（学習を阻止するために）十分な回路深さを必要とするが、近年の結果によれば、定数深さの有界ファンイン量子回路（$QNC^0$）は、多項式個のサンプルから効率的に学習可能であることが示されている。この学習可能性は、$QNC^0$ において擬似乱数状態が存在することを否定している。しかし、このような浅い、幾何学的に局所的な回路によって「擬似もつれた」状態を準備できるかどうかは依然として不明である。具体的には、「自明な」状態（定数深さの回路で準備可能なもの）は、計算量的に推定が困難なエンタングルメント構造を持ち得るのだろうか。

手法
本論文では、擬似もつれた状態を出力する、2D局所的かつ定数深さの量子回路の族を構成する。この構成は、主に以下の3つの技術的要素に基づいている。

1. 暗号学的仮定： DaoとJain [DJ25] によって導入された Dense-Sparse Learning Parity with Noise (Dense-Sparse LPN) 問題の困難性。この仮定は、疎な入力に対して計算量的に区別不能であるが、異なるエントロピー特性を持つ一対の線形写像 $F_{low}$ と $F_{high}$ を提供する。具体的には、$F_{high}$ は疎な入力に対して単射であり（高エントロピー）、一方で $F_{low}$ は多対一である（低エントロピー）。
2. 有界ファンインによるランダム符号化： 密な線形写像 $x \mapsto Mx$ に対する、新しい 完全ランダム符号化（perfect randomized encoding）。これは本研究の主要な技術的貢献であり、従来の無界ファンアウト・ゲートを必要とする符号化とは異なり、有界ファンインおよび有界ファンアウト（具体的にはファンイン/ファンアウト $\le 3$）のみを使用する。
   • この符号化は、一様ランダムマスク $r$ と $s$ を導入する。
   • 出力されるビットは $w$ と $z$ であり、決定論的なデコーダによって $Mx$ を復元できる。
   • 決定的な特徴として、符号化された出力のエントロピーは、正確に $H(Mx)$に、行列$M$ に依存しない固定のマスク依存項を加えたものとなる。これにより、基礎となる線形写像の「low」と「high」の枝間のエントロピー・ギャップが保持される。
   • この符号化は、近傍CNOTゲートのみを用いた、定数サイズのプラケットからなる2Dグリッドによって実装されており、これにより回路は2D局所的かつ定数深さとなる。
3. 状態準備： 入力ビット（疎なベルヌーイ分布からサンプリングされたもの）とランダムマスクのコヒーレントな重ね合わせを準備する。その後、ランダム符号化回路をコヒーレントに適用する。入力レジスタとマスクレジスタをトレースアウトすることで、出力レジスタ上に、ランダム符号化のシャノン・エントロピーに等しい対角密度行列が得られる。エントロピー保存特性により、入力・出力間のカットにおけるエンタングルメント・エントロピーは、基礎となる線形写像のエントロピー・ギャップを反映する。

主な貢献と結果

• 定理 1.1（定数深さの擬似もつれ）： 量子多項式時間（QPT）アドバーサリに対する Dense-Sparse LPN の困難性を仮定すると、2D局所的な定数深さの回路 $C_{low}, C_{high}$ およびタプル $W$ の、効率的にサンプリング可能な分布が存在する。出力状態 $|\psi_{low}\rangle$ と $|\psi_{high}\rangle$ は、固定されたカット $W$ において $\omega(\log n)$ の加法的エンタングルメント・エントロピー・ギャップを持つが、その回路記述は計算量的に区別不能である。

  • 意義： これは、擬似乱数性が成立しない $QNC^0$ レジムにおいても、擬似もつれが可能であることを示している。これらの状態は「公開鍵型」の擬似もつれである。すなわち、その準備回路は公開されており浅いが、そのエンタングルメント構造は隠されている。

• 定理 1.2（ランダム符号化）： 本論文は、密な線形写像に対する有界ファンイン・有界ファンアウトのランダム符号化に関する形式的な証明を提供する。この符号化は、線形写像のエントロピーを加法的な定数を除いて正確に保持し、これは低次深さの暗号理論（例：ランダムコード仮定からの衝突耐性ハッシュの構成）においても独立した関心事である。

• 定理 1.3（2D ハミルトニアンの困難性）： 局所射影器を擬似もつれ回路で共役させることにより、著者らは定数スペクトルギャップ（ギャップ = 1）を持つ2D局所ハミルトニアンの族を構成する。これらのハミルトニアンの一意な基底状態はエンタングルメント・ギャップを継承しており、固定されたカットにおけるエンタングルメント・エントロピーを量子的に学習するタスクは困難となる。

• 定理 1.4（1D ハミルトニアンの困難性）： パディングされた1D Feynman–Kitaev ヒストリー状態構成を用いることで、著者らはこの結果を1D局所ハミルトニアンへと拡張する。これらのハミルトニアンは、逆多項式スペクトルギャップを持つ。一意な基底状態は（小さな加法的損失を除いて）エンタングルメント・ギャップを保持しており、ポスト量子コードに基づく仮定に基づいた1Dシステムにおける困難性を確立している。

意義と主張
本論文は、浅い回路のレジムにおいて、擬似乱数性と擬似もつれの間の鋭い分離を確立することを主張している。定数深さの回路は擬似乱数状態を生成することはできない（効率的な学習可能性のため）が、擬似もつれた状態を生成することは可能である。

• 公開鍵としての性質： 擬似乱数状態が準備回路の秘匿性を必要とするのに対し、これらの擬似もつれた状態は公開回路によって生成される。これにより、困難性の結果を、サンプル複雑性モデルではなく、計算量複雑性モデル（入力は回路やハミルトニアンの古典的記述である）において定式化することが可能になる。
• ポスト量子セキュリティ： 困難性は、量子アドバーサリに対しても安全であると考えられる Dense-Sparse LPN に依存している。これは、素因数分解（量子的に実行可能）に依存していた先行研究（例：[BZZ24]）とは対照的である。
• 限界： 著者らは限界についても明記している。「隠された」カットは固定されており、非幾何学的である（接続された空間領域ではなく、回路構造によって決定される）。したがって、この結果は量子重力におけるエリア則（area-law）対ボリューム則（volume-law）の区別に直接関連する幾何学的カットには直接言及していない。また、この構成はフォン・ノイマン（シャノン）エントロピーに特有のものであり、現在の損失関数解析から他のレニー・エントロピーへの拡張は保証されていない。

要約すると、本研究は、妥当なポスト量子暗号学的仮定を受け入れるならば、「自明な」状態（定数深さ、局所的）が、計算量的に隠された非自明なエンタングルメント構造を持ち得ることを示している。