論文の概要: Improved upper bounds on the stabilizer rank of magic states
- arxiv url: http://arxiv.org/abs/2106.07740v2
- Date: Wed, 15 Dec 2021 14:29:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-26 17:29:52.800296
- Title: Improved upper bounds on the stabilizer rank of magic states
- Title（参考訳）: マジック状態の安定化子ランクにおける上界の改善
- Authors: Hammam Qassim, Hakop Pashayan, David Gosset
- Abstract要約: 改良は、マジック状態 $|Trangle=sqrt2-1(|0rangle+eipi/4|1rangle)$ の安定化ランクに $m$ の上限で新しい上限を設定することで得られる。
Clifford ゲートと$m$のインスタンスからなる回路に対して,実行時 $textpoly(n,m) 2m/2$ のシングルキュービット $Z$-rotation ゲートの強いシミュレーションアルゴリズムを得る。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work we improve the runtime of recent classical algorithms for strong
simulation of quantum circuits composed of Clifford and T gates. The
improvement is obtained by establishing a new upper bound on the stabilizer
rank of $m$ copies of the magic state
$|T\rangle=\sqrt{2}^{-1}(|0\rangle+e^{i\pi/4}|1\rangle)$ in the limit of large
$m$. In particular, we show that $|T\rangle^{\otimes m}$ can be exactly
expressed as a superposition of at most $O(2^{\alpha m})$ stabilizer states,
where $\alpha\leq 0.3963$, improving on the best previously known bound $\alpha
\leq 0.463$. This furnishes, via known techniques, a classical algorithm which
approximates output probabilities of an $n$-qubit Clifford + T circuit $U$ with
$m$ uses of the T gate to within a given inverse polynomial relative error
using a runtime $\mathrm{poly}(n,m)2^{\alpha m}$. We also provide improved
upper bounds on the stabilizer rank of symmetric product states
$|\psi\rangle^{\otimes m}$ more generally; as a consequence we obtain a strong
simulation algorithm for circuits consisting of Clifford gates and $m$
instances of any (fixed) single-qubit $Z$-rotation gate with runtime
$\text{poly}(n,m) 2^{m/2}$. We suggest a method to further improve the upper
bounds by constructing linear codes with certain properties.
- Abstract（参考訳）: 本研究では,clifford と t gates からなる量子回路の強力なシミュレーションのために,最近の古典的アルゴリズムのランタイムを改善した。
この改善は、マジック状態$|t\rangle=\sqrt{2}^{-1}(|0\rangle+e^{i\pi/4}|1\rangle)$の安定化子ランクに、大きな$m$の制限で新しい上限を設定することによって得られる。
特に、$|T\rangle^{\otimes m}$が、少なくとも$O(2^{\alpha m})$安定化状態の重ね合わせとして正確に表現できることが示され、$\alpha\leq 0.3963$は、既知の最高の有界な$\alpha \leq 0.463$で改善される。
これは既知の手法を通じて、古典的なアルゴリズムで、$n$-qubit Clifford + T circuit $U$ の出力確率を、ランタイム $\mathrm{poly}(n,m)2^{\alpha m}$ を用いて与えられた逆多項式相対誤差に$m$ の T ゲートの使用で近似する。
また、対称積状態の安定化次数である ||\psi\rangle^{\otimes m}$ より一般的には、クリフォードゲートからなる回路に対する強いシミュレーションアルゴリズムと、実行時$\text{poly}(n,m) 2^{m/2}$を持つ任意の(固定された)シングルキュービット$z$-rotationゲートの$m$インスタンスを得る。
特定の特性を持つ線形コードを構築することにより,上界をさらに改善する手法を提案する。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Online Newton Method for Bandit Convex Optimisation [28.66596225688161]
ゼロ階帯域幅の最適化のための計算効率の良いアルゴリズムを提案する。
逆条件では、その後悔は少なくとも$d3.5 sqrtn Mathrmpolylog(n, d)$であり、d$が時間的地平線である確率が高いことを証明している。
設定において、バウンダリは$M d2 sqrtn Mathrmpolylog(n, d)$に改善され、[d-1/2, d-1 / 4]$は$Mとなる。
論文 参考訳（メタデータ） (2024-06-10T17:44:11Z) - Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳（メタデータ） (2023-12-14T12:53:34Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Lower Bounds on Stabilizer Rank [3.265773263570237]
十分小さな定数$deltaの場合、それらの状態に対して$$-closeの任意の状態の安定化ランクが$Omega(sqrtn/log n)$であることを証明する。
これは、近似安定化器ランクに対する最初の非自明な下界である。
論文 参考訳（メタデータ） (2021-06-06T19:27:51Z) - Improved Weak Simulation of Universal Quantum Circuits by Correlated
$L_1$ Sampling [0.0]
弱シミュレーションはしばしば弱いシミュレーションと呼ばれ、量子的優位性をいつ求めるかを決定する方法である。
最低の$L_$ノルムサンプリングコストの上限を$mathcal O(xit delta-2)$から$t$の次の順序に構築的に締め付ける。
これは、我々の知識の最悪の場合において、この境界の有限t$への依存を下げた最初の弱いシミュレーションアルゴリズムである。
論文 参考訳（メタデータ） (2021-04-15T05:50:11Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。