論文の概要: Improved bounds on stabilizer extent and Clifford rank
- arxiv url: http://arxiv.org/abs/2610.06819v1
- Date: Mon, 05 Oct 2026 17:56:34 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-08 22:24:50.94622
- Title: Improved bounds on stabilizer extent and Clifford rank
- Title（参考訳）: 安定度とクリフォードランク上の改善された境界
- Abstract要約: 安定度が最高$k$の全ての純粋な状態が、最低$2O(sqrtklog(k+1))$の安定化度を持つことを証明します。
また、安定化器のランクが最大$k$で、$poly(n)2O(sqrtklog(k+1)$時間とコピー複雑性を持つ状態のトモグラフィーアルゴリズムも取得する。
- 参考スコア（独自算出の注目度）: 1.4323566945483497
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We prove that every pure state of stabilizer rank at most $k$ has stabilizer extent at most $2^{O(\sqrt{k\log(k+1)})}$, and establish the analogous bound for the squared Clifford coefficient norm of Clifford-rank-$k$ operators. This implies stabilizer fidelity at least $2^{-O(\sqrt{k\log(k+1)})}$, resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an $Ω(n^2/\log n)$ lower bound for the approximate stabilizer rank of tensor powers of any non-stabilizer qubit state. The latter result generalizes the best-known lower bound for tensor powers of $T$-states (Mehraban-Tamasbi, STOC, 2024) to arbitrary non-stabilizer qubit states, including magic states. As a consequence of the Clifford rank--norm inequality, we obtain an $Ω(n^2/\log n)$ lower bound for exact representations of $n$-bit AND function by quadratic phases, improving the previous best-known linear bound. Further consequences rule out pseudorandom state and unitary ensembles with approximate stabilizer and Clifford rank $O((\log n)^2/\log\log n)$, respectively, a $\log n$ improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most $k$, with $poly(n)2^{O(\sqrt{k\log(k+1)})}$ time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.
- Abstract（参考訳）: 我々は、少なくとも$k$の安定化器ランクのすべての純粋な状態が、少なくとも$2^{O(\sqrt{k\log(k+1)})}$の安定化器範囲を持つことを証明し、クリフォード-ランク-$k$作用素の平方クリフォード係数ノルムの類似した境界を確立する。
これは、少なくとも 2^{-O(\sqrt{k\log(k+1)})}$ を安定化させ、(Mehraban-Tamasbi, STOC, 2025) の量的予想を解き、任意の非安定化子量子ビット状態のテンソルパワーの近似安定化ランクに対する$Ω(n^2/\log n)$下界を証明することを意味する。
後者の結果は、T$状態(Mehraban-Tamasbi, STOC, 2024)のテンソル力の最もよく知られた下界を、マジック状態を含む任意の非安定化量子状態に一般化する。
クリフォード階数-ノルムの不等式の結果、$Ω(n^2/\log n)$下界を$n$-bit の正確な表現と2次位相による函数とし、以前の最もよく知られた線型境界を改善する。
さらに、擬ランダム状態と近似安定化器を持つユニタリアンサンブルを除外し、Clifford rank $O((\log n)^2/\log \log n)$, $\log n$ を前処理よりも改善する(Kalra-Sinha, Quantum, 2026)。
また、安定化器ランクが最大$k$で、$poly(n)2^{O(\sqrt{k\log(k+1)})} が時間とコピーの複雑さを持つ状態に対するトモグラフィーアルゴリズムも得られる。
関連論文リスト
- Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise [55.29259818039367]
オンライン凸最適化を1ラウンドに1つの偏りのない下位段階と、未知の有限条件の雑音モーメントであるp$th, $1ple2$で検討する。
長さ$n$の固定区間$I$に対して、学習者は最適な全水平静的レートを含む1+log(T/n)$を達成する。
論文 参考訳（メタデータ） (2026-09-30T21:03:03Z) - Exact Critical Curve for Uniform Stabilizer-State Identification [38.8383517726785]
純粋な$n$-qubit安定化状態の均一アンサンブルに対する臨界交叉全体の解決を行う。
固定整数 $c$ の $k=n+c$ に対して、最適成功確率は明示的な正級数 $P_infty(c)$ に収束する。
論文 参考訳（メタデータ） (2026-09-24T10:10:03Z) - Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity [66.59610645394376]
実空間における非拡大作用素の固定点を求めるための単純慣性クラスノセル・スキーマン法(iKM)を解析する。
KM(Bravo and Cominetti, 2024)に慣性外挿を2つ加えるだけで, 1回に1回, バイアスのあるオラクルに1回呼び出すことができる。
また、KM[Bravo Cominetti, 2024]に対する、よく知られた$O(-4)$ランダムイテレート保証を改善している。
論文 参考訳（メタデータ） (2026-09-22T23:57:59Z) - A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - Optimal algorithms for materializing stabilizer states and Clifford gates from compact descriptions [5.706918315850497]
我々は、O(2n)$時間とO(2n)$空間で動作するアルゴリズムを与える。
その結果,標準チェック行列記述から安定化状態ベクトルを実現するための最適手順が得られた。
これらの結果は密度安定剤とクリフォードの物質化のギャップを埋める。
論文 参考訳（メタデータ） (2026-04-16T15:34:54Z) - Stabilizer Ranks, Barnes Wall Lattices and Magic Monotones [1.4323566945483497]
Kliuchnikov と Sch"onnenbeck はバーンズウォール格子、安定化状態、クリフォード演算の間の接続を示した。
安定化器の位置の関数として安定化器の忠実度に最初の定量的な下界を示す。
論文 参考訳（メタデータ） (2025-03-06T05:20:55Z) - Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。
我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。
我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
論文 参考訳（メタデータ） (2024-11-20T02:46:15Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - Improved upper bounds on the stabilizer rank of magic states [0.0]
改良は、マジック状態 $|Trangle=sqrt2-1(|0rangle+eipi/4|1rangle)$ の安定化ランクに $m$ の上限で新しい上限を設定することで得られる。
Clifford ゲートと$m$のインスタンスからなる回路に対して,実行時 $textpoly(n,m) 2m/2$ のシングルキュービット $Z$-rotation ゲートの強いシミュレーションアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-06-14T20:20:51Z) - Lower Bounds on Stabilizer Rank [3.265773263570237]
十分小さな定数$deltaの場合、それらの状態に対して$$-closeの任意の状態の安定化ランクが$Omega(sqrtn/log n)$であることを証明する。
これは、近似安定化器ランクに対する最初の非自明な下界である。
論文 参考訳（メタデータ） (2021-06-06T19:27:51Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。