論文の概要: Exponential lower bounds on the fermionic Gaussian rank of magic states and the bosonic coherent state rank of Fock states

• arxiv url: http://arxiv.org/abs/2610.03699v1
• Date: Fri, 02 Oct 2026 17:55:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:14:30.555335
• Title: Exponential lower bounds on the fermionic Gaussian rank of magic states and the bosonic coherent state rank of Fock states
• Title（参考訳）: フェルミオンガウスのマジック状態のランクとフォック状態のボゾンコヒーレント状態ランクの指数的下界
• Abstract要約: 我々は、$lvert Mrangleotimes k$ のフェルミオンガウス分解が $(1.4k)$ 項からなることを証明している。 また、基本的に同じ状態の$$-approximateランクの値に一致する境界を証明し、正確なランクの値と同じ量でそれを下限する。 正確なフェルミオンガウスランクに関する我々の結果は、非ガウス状態の$k$固定パリティの任意の積に直接適用される。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent algorithms for classical simulation of quantum mechanics have runtime whose superpolynomial component is given by a linear dependence on the number of terms required to write large tensor products of certain "magic" states as superpositions of "free" states (which may be stabilizer states, fermionic Gaussian states or others). Surprisingly little is known about the number of terms in such decompositions, called ranks (e.g. the stabilizer rank, fermionic-Gaussian rank etc.). For complexity theoretic reasons they are expected to grow exponentially in the number of tensor factors but, while exponential upper bounds are known for both the stabilizer and fermionic-Gaussian rank of magic states; the best known lower bounds on the stabiliser rank are quadratic, and no bounds on the fermionic-Gaussian rank are known beyond fixed constants. In this work we prove that any fermionic Gaussian decomposition of $\lvert M\rangle^{\otimes k}$ consists of $Ω(1.4^k)$ terms. Here $\lvert M\rangle$ is the most standard magic state for fermionic linear optics: the $4$ qubit state that may be consumed to implement a swap gate. We also prove essentially matching bounds on the $δ$-approximate rank of the same state, lower bounding it by the same quantity that bounds the exact rank, multiplied by a factor of $1-δ^2$. Our results on exact fermionic Gaussian rank apply directly to any product of $k$ fixed parity non-Gaussian states, although the same is not true of the approximate rank. Finally, we prove that the coherent state border rank of an $n$-mode bosonic Fock state with $m_j$ bosons in mode $j$ is exactly $\prod_{j}(1+m_j)$, answering a conjecture of Ref. [1] and obtain lower bounds on the approximate coherent state rank given by the same quantity multiplied by a function of the fidelity of the approximation, emphasizing the broad applicability of the method we employ.
• Abstract（参考訳）: 最近の量子力学の古典的シミュレーションのアルゴリズムでは、超ポリノミカル成分は、ある「魔法」状態の大きいテンソル積を「自由」状態(安定化状態、フェルミオンガウス状態など)の重ね合わせとして書くのに必要な項数に線形依存することで与えられる。 このような分解において、階数(例えば、安定化位数、フェルミオン-ガウス位数など)と呼ばれる用語の数について、驚くべきことにほとんど知られていない。 複雑性理論上の理由から、テンソル因子の数で指数関数的に増加することが期待されているが、指数的な上界は安定度とフェルミオン-ガウス級のマジック状態の両方で知られており、スタビライザー級数の最もよく知られた下界は二次的であり、フェルミオン-ガウス級数の境界は固定定数を超えては知られていない。 この研究において、$\lvert M\rangle^{\otimes k}$ のフェルミオンガウス分解は $Ω(1.4^k)$ 項からなることを証明している。 ここで、$\lvert M\rangle$はフェルミオンリニア光学の最も標準的なマジックステートである。 また、同じ状態の$δ$-アポキシメート階数に本質的に一致する境界を証明し、それを正階数と同じ量で下限し、1-δ^2$の係数で乗算する。 正確なフェルミオンガウス階数に関する我々の結果は、近似階数に関して同じではないが、$k$固定パリティ非ガウス状態の任意の積に直接適用される。 最後に、m_j$ Bosons in mode $j$はちょうど$\prod_{j}(1+m_j)$であり、Refの予想に答える。 [1] と、近似の忠実性の関数に乗じて、同じ量で与えられる近似コヒーレントな状態ランクの下位境界を求め、我々が採用する手法の広範な適用性を強調する。

関連論文リスト

• An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
  単位球面上の最適化問題の総和緩和を解析するためのargmax原理を開発する。 私たちの指導原則は、最大値が丸みを帯びた候補であることです。
  論文  参考訳（メタデータ） (2026-08-03T17:58:00Z)
• The Kikuchi Hierarchy is Sharp for $k$XOR [46.26532142699448]
  菊池階層の正規化された変種は、対数損失のない鋭い予想されたトレードオフを、全てのアーティ$kge3$で達成することを示す。 また、同じモデルで一致した下界を証明し、推論と難解な上界はより一般的な植林法や述語に遷移する。
  論文  参考訳（メタデータ） (2026-07-31T17:54:11Z)
• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  ハミルトニアン$H = sum_j h_j$ の場合、ゲート上の下界と量子コンピュータ上の時間発展をシミュレートするクエリの複雑さを証明できる。 任意の項ノルムのホールドは$|h_j|$, time $t$, trace-distance error $$である。
  論文  参考訳（メタデータ） (2026-07-22T07:41:32Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Efficient conversion from fermionic Gaussian states to matrix product states [48.225436651971805]
  フェミオンガウス状態から行列積状態に変換する高効率なアルゴリズムを提案する。 翻訳不変性のない有限サイズ系に対しては定式化できるが、無限系に適用すると特に魅力的になる。 この手法のポテンシャルは、2つのキラルスピン液体の数値計算によって示される。
  論文  参考訳（メタデータ） (2024-08-02T10:15:26Z)
• Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach [6.169364905804677]
  量子状態の近似安定化器ランクは、その状態の任意の近似分解における最小の項数である。 我々は近似ランクの下位境界を、近似パラメータの広い範囲に対して$tilde Omega(sqrt n)$に改善する。
  論文  参考訳（メタデータ） (2023-05-17T15:09:41Z)
• Lower Bounds on Stabilizer Rank [3.265773263570237]
  十分小さな定数$deltaの場合、それらの状態に対して$$-closeの任意の状態の安定化ランクが$Omega(sqrtn/log n)$であることを証明する。 これは、近似安定化器ランクに対する最初の非自明な下界である。
  論文  参考訳（メタデータ） (2021-06-06T19:27:51Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。