論文の概要: Lower bounds on the Approximate Stabilizer Rank: A Probabilistic
Approach
- arxiv url: http://arxiv.org/abs/2305.10277v1
- Date: Wed, 17 May 2023 15:09:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-18 15:23:34.527707
- Title: Lower bounds on the Approximate Stabilizer Rank: A Probabilistic
Approach
- Title（参考訳）: 近似安定化器ランクの下位境界-確率論的アプローチ
- Authors: Saeed Mehraban and Mehrdad Tahmasbi
- Abstract要約: 量子状態の近似安定化器ランクは、その状態の任意の近似分解における最小の項数である。
$tilde Omega(sqrt n)$よりも低い境界は、近似階数で知られている。
- 参考スコア（独自算出の注目度）: 13.858624044986815
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The approximate stabilizer rank of a quantum state is the minimum number of
terms in any approximate decomposition of that state into stabilizer states.
Bravyi and Gosset showed that the approximate stabilizer rank of a so-called
"magic" state like $|T\rangle^{\otimes n}$, up to polynomial factors, is an
upper bound on the number of classical operations required to simulate an
arbitrary quantum circuit with Clifford gates and $n$ number of $T$ gates. As a
result, an exponential lower bound on this quantity seems inevitable. Despite
this intuition, several attempts using various techniques could not lead to a
better than a linear lower bound on the "exact" rank of $|T\rangle^{\otimes
n}$, meaning the minimal size of a decomposition that exactly produces the
state. However, an "approximate" rank is more realistically related to the cost
of simulating quantum circuits because exact rank is not robust to errors;
there are quantum states with exponentially large exact ranks but constant
approximate ranks even with arbitrarily small approximation parameters. No
lower bound better than $\tilde \Omega(\sqrt n)$ has been known for the
approximate rank. In this paper, we improve this lower bound to $\tilde \Omega
(n)$ for a wide range of the approximation parameters. Our approach is based on
a strong lower bound on the approximate rank of a quantum state sampled from
the Haar measure and a step-by-step analysis of the approximate rank of a
magic-state teleportation protocol to sample from the Haar measure.
- Abstract（参考訳）: 量子状態の近似安定化器ランクは、その状態の任意の近似分解における最小の項数である。
Bravyi と Gosset は、$|T\rangle^{\otimes n}$ のようないわゆる「魔術的」状態の近似安定化ランクは、多項式因子まで、クリフォードゲートと$n$$$T$ゲートを持つ任意の量子回路をシミュレートするのに必要となる古典的な演算の回数の上限であることを示した。
その結果、この量に対する指数関数的な下限は避けられないように思える。
この直観にもかかわらず、様々な技法を使ったいくつかの試みは、状態を正確に生成する分解の最小サイズである$|t\rangle^{\otimes n}$の「実」ランクの線形下限よりも良い結果をもたらすことができなかった。
しかし、「近似」ランクは、正確なランクが誤差に対して堅牢ではないため、量子回路をシミュレートするコストとより現実的に関連している。
$\tilde \Omega(\sqrt n)$よりも低い境界は、近似ランクで知られている。
本稿では,近似パラメータの広い範囲に対して,この下限を$\tilde \Omega (n)$に改善する。
本手法は、ハール測度からサンプリングされた量子状態の近似ランクの強い下限と、ハール測度からサンプルするためのマジック状態テレポーテーションプロトコルの近似ランクのステップ・バイ・ステップ解析に基づいている。
関連論文リスト
- Improved bounds for testing low stabilizer complexity states [6.169364905804677]
安定化状態の耐久試験における最先端パラメータの改善について検討する。
また、安定度が低い状態をテストする問題についても検討する。
論文 参考訳（メタデータ） (2024-10-31T17:56:57Z) - Pseudoentanglement Ain't Cheap [0.43123403062068827]
エントロピーの$t$ビットのギャップを持つ任意の擬アンタングル状態アンサンブルは、準備するために$Omega(t)$非クリフォードゲートが必要であることを示す。
これは、線形時間安全擬似ランダム関数が存在する場合の多元対数因子に強く依存する。
論文 参考訳（メタデータ） (2024-03-29T19:39:59Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Quantum Lower Bounds for Finding Stationary Points of Nonconvex
Functions [8.495749905129278]
非最適化に対する古典的な下界の進歩にもかかわらず、これらの境界は依然として広く開である。
最初の設定について、Omegabig(frac-1+ppp)$。
第二設定については、おめがの()$。
Omega()$ if 勾配関数は滑らかである。
Omega()$ if 勾配関数は滑らかである。
Omega()$ if 勾配関数は滑らかである。
Omega()$ if 勾配関数は滑らかである。
論文 参考訳（メタデータ） (2022-12-07T19:02:36Z) - Average-case Speedup for Product Formulas [69.68937033275746]
製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。
我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。
我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
論文 参考訳（メタデータ） (2021-11-09T18:49:48Z) - Improved Graph Formalism for Quantum Circuit Simulation [77.34726150561087]
我々は、安定化状態から正準形式への効率よく単純化する方法を示す。
内積の対称性を明らかにするために, 線形依存三重項を特徴付ける。
新たな制御付きPauli $Z$アルゴリズムを用いて、内部積計算のランタイムを$O(n3)$から$O(nd2)$に改善します。
論文 参考訳（メタデータ） (2021-09-20T05:56:25Z) - Lower Bounds on Stabilizer Rank [3.265773263570237]
十分小さな定数$deltaの場合、それらの状態に対して$$-closeの任意の状態の安定化ランクが$Omega(sqrtn/log n)$であることを証明する。
これは、近似安定化器ランクに対する最初の非自明な下界である。
論文 参考訳（メタデータ） (2021-06-06T19:27:51Z) - Improved Strong Simulation of Universal Quantum Circuits [0.0]
12kbitのテンソル付きT$ゲートマジック状態の安定化器ランクのスケールダウンを見出した。
これにより、2sim 0.463 t$に制限される。
これはクリフォード+$T$ゲートセットの最も効率的な強シミュレーションを構成的に生成する。
論文 参考訳（メタデータ） (2020-12-21T23:13:20Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。