論文の概要: Improved Stabilizer Estimation via Bell Difference Sampling
- arxiv url: http://arxiv.org/abs/2304.13915v2
- Date: Fri, 29 Sep 2023 17:37:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-02 18:57:14.108293
- Title: Improved Stabilizer Estimation via Bell Difference Sampling
- Title（参考訳）: ベル差分サンプリングによる安定化器推定の改善
- Authors: Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
- Abstract要約: 安定化器の形式性に関して,様々なモデルにおける量子状態の学習の複雑さについて検討する。
Omega(n)$$T$gates は任意の Clifford+$T$ 回路で擬ランダム量子状態を作るのに必要であることを示す。
- 参考スコア（独自算出の注目度）: 0.47109219881156844
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the complexity of learning quantum states in various models with
respect to the stabilizer formalism and obtain the following results:
- We prove that $\Omega(n)$ $T$-gates are necessary for any Clifford+$T$
circuit to prepare computationally pseudorandom quantum states, an exponential
improvement over the previously known bound. This bound is asymptotically tight
if linear-time quantum-secure pseudorandom functions exist.
- Given an $n$-qubit pure quantum state $|\psi\rangle$ that has fidelity at
least $\tau$ with some stabilizer state, we give an algorithm that outputs a
succinct description of a stabilizer state that witnesses fidelity at least
$\tau - \varepsilon$. The algorithm uses $O(n/(\varepsilon^2\tau^4))$ samples
and $\exp\left(O(n/\tau^4)\right) / \varepsilon^2$ time. In the regime of
$\tau$ constant, this algorithm estimates stabilizer fidelity substantially
faster than the na\"ive $\exp(O(n^2))$-time brute-force algorithm over all
stabilizer states.
- In the special case of $\tau > \cos^2(\pi/8)$, we show that a modification
of the above algorithm runs in polynomial time.
- We improve the soundness analysis of the stabilizer state property testing
algorithm due to Gross, Nezami, and Walter [Comms. Math. Phys. 385 (2021)]. As
an application, we exhibit a tolerant property testing algorithm for stabilizer
states.
The underlying algorithmic primitive in all of our results is Bell difference
sampling. To prove our results, we establish and/or strengthen connections
between Bell difference sampling, symplectic Fourier analysis, and graph
theory.
- Abstract（参考訳）: 安定化器の定式化に関して、量子状態の学習の複雑さについて研究し、以下の結果を得る。 - 計算的に擬似ランダムな量子状態を作成するためには、任意のクリフォード+T$回路に$\Omega(n)$$T$-gatesが必要であることを証明します。
この境界は、線形時間量子安全な擬ランダム関数が存在する場合、漸近的に厳密である。
-n$-qubit の純粋な量子状態 $|\psi\rangle$ が与えられたとき、少なくとも$\tau$ と安定化状態との忠実性を持つアルゴリズムを与え、少なくとも $\tau - \varepsilon$ の忠実性を示す安定化状態の簡潔な記述を出力する。
このアルゴリズムは、$O(n/(\varepsilon^2\tau^4))$サンプルと$\exp\left(O(n/\tau^4)\right) / \varepsilon^2$ timeを使用する。
このアルゴリズムは、$\tau$定数の状態では、全ての安定化状態におけるna\"ive $\exp(o(n^2))$-time brute-forceアルゴリズムよりもかなり高速に安定化器の忠実度を推定する。
-$\tau > \cos^2(\pi/8)$の特殊な場合、上記のアルゴリズムの修正は多項式時間で実行されることを示す。
-Gross,Nezami,Walter[Comms. Math. Phys. 385 (2021)]による安定化状態特性試験アルゴリズムの音質解析を改善した。
適用例として、安定化状態に対する耐久性試験アルゴリズムを示す。
すべての結果の基本的なアルゴリズムプリミティブはベル差分サンプリングです。
この結果を証明するために,ベル差分サンプリング,シンプレクティックフーリエ解析,グラフ理論の接続を確立および/または強化する。
関連論文リスト
- Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer [7.319050391449301]
量子状態の近接性の基本的な尺度として、トレース距離と不完全性は、一般に量子状態の識別、認証、トモグラフィーに使用される。
本稿では, 純状態間のトレース距離と平方根の忠実度を, 同一コピーへのサンプルアクセスを条件として, 加算誤差$varepsilon$で推定する量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-10-28T16:48:21Z) - Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。
PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
論文 参考訳（メタデータ） (2024-10-10T06:15:42Z) - Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits [0.824969449883056]
ベルサンプリングは、次元$d>2$のクエンフィットで使用すると失敗する。
キューディットにおけるベルサンプリングの回避を目的とした新しい量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-10T09:44:23Z) - Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。
我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。
クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-25T15:32:37Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - 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 Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳（メタデータ） (2020-12-29T14:06:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。