論文の概要: Lower Bounds on Stabilizer Rank
- arxiv url: http://arxiv.org/abs/2106.03214v2
- Date: Thu, 10 Feb 2022 08:54:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-27 11:30:30.577328
- Title: Lower Bounds on Stabilizer Rank
- Title（参考訳）: スタビライザランクの下限
- Authors: Shir Peleg, Amir Shpilka, Ben Lee Volk
- Abstract要約: 十分小さな定数$deltaの場合、それらの状態に対して$$-closeの任意の状態の安定化ランクが$Omega(sqrtn/log n)$であることを証明する。
これは、近似安定化器ランクに対する最初の非自明な下界である。
- 参考スコア（独自算出の注目度）: 3.265773263570237
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The stabilizer rank of a quantum state $\psi$ is the minimal $r$ such that
$\left| \psi \right \rangle = \sum_{j=1}^r c_j \left|\varphi_j \right\rangle$
for $c_j \in \mathbb{C}$ and stabilizer states $\varphi_j$. The running time of
several classical simulation methods for quantum circuits is determined by the
stabilizer rank of the $n$-th tensor power of single-qubit magic states.
We prove a lower bound of $\Omega(n)$ on the stabilizer rank of such states,
improving a previous lower bound of $\Omega(\sqrt{n})$ of Bravyi, Smith and
Smolin (arXiv:1506.01396). Further, we prove that for a sufficiently small
constant $\delta$, the stabilizer rank of any state which is $\delta$-close to
those states is $\Omega(\sqrt{n}/\log n)$. This is the first non-trivial lower
bound for approximate stabilizer rank.
Our techniques rely on the representation of stabilizer states as quadratic
functions over affine subspaces of $\mathbb{F}_2^n$, and we use tools from
analysis of boolean functions and complexity theory. The proof of the first
result involves a careful analysis of directional derivatives of quadratic
polynomials, whereas the proof of the second result uses Razborov-Smolensky low
degree polynomial approximations and correlation bounds against the majority
function.
- Abstract（参考訳）: 量子状態 $\psi$ の安定化ランクは最小$r$ であり、$\left| \psi \right \rangle = \sum_{j=1}^r c_j \left|\varphi_j \right\rangle$ for $c_j \in \mathbb{C}$ および安定化状態 $\varphi_j$ である。
量子回路の古典的シミュレーション手法の実行時間は、シングルキュービットマジック状態の$n$-thテンソルパワーの安定化器ランクによって決定される。
そのような状態の安定化子ランクで$\omega(n)$の下限が証明され、以前の$\omega(\sqrt{n})$ of bravyi, smith and smolin (arxiv:1506.01396)が改善される。
さらに、十分小さな定数$\delta$に対して、それらの状態に対して$\delta$-クロースである任意の状態の安定化ランクは$\Omega(\sqrt{n}/\log n)$であることを示す。
これは近似安定子階に対する最初の非自明な下限である。
我々の手法は、$\mathbb{F}_2^n$ のアフィン部分空間上の二次函数としての安定化状態の表現に依存し、ブール関数の解析と複雑性理論のツールを使用する。
第1の結果の証明は二次多項式の方向微分の注意深い解析を含むが、第2の結果の証明はラズボロフ・スモレンスキーの低次多項式近似と多数関数に対する相関境界を用いる。
関連論文リスト
- Overcomplete Tensor Decomposition via Koszul-Young Flattenings [63.01248796170617]
最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。
次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
論文 参考訳（メタデータ） (2024-11-21T17:41:09Z) - A note on polynomial-time tolerant testing stabilizer states [6.458742319938316]
Gowers-$3$ of $n$-qubit quantum state $|psirangle に対して改良された逆定理を示す。
すべての$gammageq 0$に対して、$textsfGowers(|psi rangle,3)8 geq gamma ならば、$|psirangle$の安定化器忠実度は、ある定数$C>1$に対して少なくとも$gammaC$である。
論文 参考訳（メタデータ） (2024-10-29T16:49:33Z) - Polynomial-time tolerant testing stabilizer states [4.65004369765875]
アルゴリズムは未知の$n$-qubit量子状態 $|psirangle promise $(i)$ $|psirangle$のコピーを与える。
すべての$varepsilon_1>0$と$varepsilonleq varepsilon_C$に対して、どちらが正しいかを決定する$textsfpolyが存在することを示す。
我々の証明には、量子状態に対するガウワーズノルムの新しい定義、量子状態のガウワーズ-3$のノルムに対する逆定理、および安定化器被覆に対する新しい境界が含まれる。
論文 参考訳（メタデータ） (2024-08-12T16:56:33Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach [6.169364905804677]
量子状態の近似安定化器ランクは、その状態の任意の近似分解における最小の項数である。
我々は近似ランクの下位境界を、近似パラメータの広い範囲に対して$tilde Omega(sqrt n)$に改善する。
論文 参考訳（メタデータ） (2023-05-17T15:09:41Z) - Improved Stabilizer Estimation via Bell Difference Sampling [0.43123403062068827]
安定化器の形式性に関して,様々なモデルにおける量子状態の学習の複雑さについて検討する。
Omega(n)$$T$gates は任意の Clifford+$T$ 回路で擬ランダム量子状態を作るのに必要であることを示す。
上記のアルゴリズムの修正は時間内に行われることを示す。
論文 参考訳（メタデータ） (2023-04-27T01:58:28Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Improved Graph Formalism for Quantum Circuit Simulation [77.34726150561087]
我々は、安定化状態から正準形式への効率よく単純化する方法を示す。
内積の対称性を明らかにするために, 線形依存三重項を特徴付ける。
新たな制御付きPauli $Z$アルゴリズムを用いて、内部積計算のランタイムを$O(n3)$から$O(nd2)$に改善します。
論文 参考訳（メタデータ） (2021-09-20T05:56:25Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。