論文の概要: 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)]による安定化状態特性試験アルゴリズムの音質解析を改善した。
適用例として、安定化状態に対する耐久性試験アルゴリズムを示す。
すべての結果の基本的なアルゴリズムプリミティブはベル差分サンプリングです。
この結果を証明するために,ベル差分サンプリング,シンプレクティックフーリエ解析,グラフ理論の接続を確立および/または強化する。
関連論文リスト
- Efficient Learning of Quantum States Prepared With Few Non-Clifford
Gates [0.47109219881156844]
我々はクリフォードゲートと$O(log(n))$非クリフォードゲートで用意された量子状態を効率的に学習するアルゴリズムを与える。
具体的には、$n$-qubit state $lvert psi rangle$に対して、$mathsfpoly(n,2t,1/epsilon)$ time and copy of $lvert psi rangle$ sufficeを示す。
論文 参考訳(メタデータ) (2023-05-22T18:49:52Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳(メタデータ) (2023-02-16T13:57:19Z) - Robustness of Quantum Algorithms for Nonconvex Optimization [7.191453718557392]
量子アルゴリズムは多対数あるいは指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができることを示す。
また、量子アルゴリズムが多対数または指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができる領域を特徴付ける。
論文 参考訳(メタデータ) (2022-12-05T19:10:32Z) - 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) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳(メタデータ) (2021-12-15T21:44:05Z) - 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) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
論文 参考訳(メタデータ) (2020-09-09T18:00:09Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。