論文の概要: Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
- arxiv url: http://arxiv.org/abs/2305.10277v4
- Date: Fri, 29 Mar 2024 23:55:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-02 16:04:03.510287
- Title: Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
- Title（参考訳）: 近似安定化器ランクの二次下限:確率論的アプローチ
- Authors: Saeed Mehraban, Mehrdad Tahmasbi,
- Abstract要約: 量子状態の近似安定化器ランクは、その状態の任意の近似分解における最小の項数である。
我々は近似ランクの下位境界を、近似パラメータの広い範囲に対して$tilde Omega(sqrt n)$に改善する。
- 参考スコア（独自算出の注目度）: 6.169364905804677
- 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. For the "approximate" rank, which is more realistically related to the cost of simulating quantum circuits, no lower bound better than $\tilde \Omega(\sqrt n)$ has been known. In this paper, we improve the lower bound on the approximate rank to $\tilde \Omega (n^2)$ for a wide range of the approximation parameters. An immediate corollary of our result is the existence of polynomial time computable functions which require a super-linear number of terms in any decomposition into exponentials of quadratic forms over $\mathbb{F}_2$, resolving a question in [Wil18]. Our approach is based on a strong lower bound on the approximate rank of a quantum state sampled from the Haar measure, a step-by-step analysis of the approximate rank of a magic-state teleportation protocol to sample from the Haar measure, and a result about trading Clifford operations with $T$ gates by [LKS18].
- Abstract（参考訳）: 量子状態の近似安定化器ランクは、その状態の任意の近似分解における最小の項数である。
Bravyi と Gosset は、$|T\rangle^{\otimes n}$ のようないわゆる「魔術的」状態の近似安定化ランクは、多項式因子まで、クリフォードゲートと$n$$$T$ゲートを持つ任意の量子回路をシミュレートするのに必要となる古典的な演算の回数の上限であることを示した。
結果として、この量に対する指数的な下界は避けられないように思われる。
この直観にもかかわらず、様々な手法を用いたいくつかの試みは、状態を正確に生成する分解の最小サイズを意味する${|T\rangle}^{\otimes n}$の「厳密な」ランクの線形下界よりも良い結果には至らなかった。
量子回路をシミュレートするコストとより現実的に関係している「近似」ランクについて、$\tilde \Omega(\sqrt n)$より低い境界は知られていない。
本論文では,近似パラメータの広い範囲に対して,近似ランクの下位境界を$\tilde \Omega (n^2)$に改善する。
我々の結果の直近の系は多項式時間計算可能関数の存在であり、これは任意の分解において、$\mathbb{F}_2$ 上の二次形式の指数関数への超線型項数を必要とし、[Wil18] の問題を解く。
提案手法は,Haar測度からサンプリングされた量子状態の近似ランクに基づく強い下界,Haar測度からサンプリングされたマジック状態テレポーテーションプロトコルの近似ランクのステップバイステップ解析,および[LKS18]で$T$ゲートでClifford演算を取引する結果に基づく。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。