論文の概要: Parallel repetition with a threshold in quantum interactive proofs
- arxiv url: http://arxiv.org/abs/2008.07445v1
- Date: Mon, 17 Aug 2020 16:06:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-06 00:58:45.917171
- Title: Parallel repetition with a threshold in quantum interactive proofs
- Title(参考訳): 量子インタラクティブ証明におけるしきい値付き並列反復
- Authors: Abel Molina
- Abstract要約: O(log (1/epsilon)$ rounds of parallel repetition with a threshold suffice to reduce completeness and soundness error to $epsilon$ for single-proer quantum interactive proof systems。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this note, we show that $O(\log (1/\epsilon))$ rounds of parallel
repetition with a threshold suffice to reduce completeness and soundness error
to $\epsilon$ for single-prover quantum interactive proof systems. This
improves on a previous $O(\log (1/\epsilon) \log \log (1/\epsilon))$ bound from
Hornby (2018), while also simplifying its proof. A key element in our proof is
a concentration bound from Impagliazzo and Kabanets (2010).
- Abstract(参考訳): 本稿では, 1 個の量子対話型証明系に対して $o(\log (1/\epsilon))$ の完全性と音質誤差を$\epsilon$ に減らすためにしきい値が十分である並列繰り返しを繰り返すことを示す。
これは、以前の$O(\log (1/\epsilon) \log \log (1/\epsilon))$ bound from Hornby (2018)で改善され、証明も単純化された。
私たちの証明の重要な要素は、Impagliazzo と Kabanets (2010) から束縛された濃度である。
関連論文リスト
- Quantum state preparation with optimal T-count [2.1386090295255333]
任意の$n$-qubit量子状態を誤差$varepsilon$に近似するために、Tゲートがいくつ必要かを示す。
また、これは任意の対角線$n$-qubitユニタリをエラー$varepsilon$に実装するための最適なTカウントであることを示す。
論文 参考訳(メタデータ) (2024-11-07T15:29:33Z) - Testing multipartite productness is easier than testing bipartite productness [0.0]
我々は$Omega(n / log n)$コピーが必要であることを示す(固定$epsilon leq frac12$の場合)。
本稿では, グラフ状態のテストと, エンタングルメントの一般化幾何測度を計算することの意味について論じる。
論文 参考訳(メタデータ) (2024-06-24T17:36:57Z) - More Efficient $k$-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities [0.10241134756773229]
我々は、$tildeO(nkcdot log (1/varepsilon))$ random $3$-bit gates is $varepsilon$-aqua $k$-wise independentという可逆回路によって計算された置換が証明される。
私たちのバウンダリは、近似エラー$varepsilon$が小さすぎる場合に、政権内の現在知られているバウンダリを改善します。
論文 参考訳(メタデータ) (2024-05-08T22:38:35Z) - Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
低エネルギー部分空間内のハミルトン$H$の下で時間発展をシミュレートする作業を考える。
我々は,$O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$クエリを,任意の$Gamma$に対するブロックエンコーディングに使用する量子アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-04-04T17:58:01Z) - Tetrationally Compact Entanglement Purification [0.03922370499388702]
本論文は, 極めて少ない貯蔵量で, 絡み合いを浄化できることを示唆する。
対象不忠実な$epsilon$のアンタングルペアは、$tildeO(log frac1epsilon)$ timeで作成できる。
論文 参考訳(メタデータ) (2023-11-18T04:39:50Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳(メタデータ) (2023-03-03T18:23:20Z) - Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling [30.53587208999909]
我々は、ゼロサムゲームにおける$epsilon$-approximate Nash平衡を、有界なエントリを持つ$m倍n$ペイオフ行列で計算するための量子アルゴリズムを与える。
ペイオフ行列にアクセスするための標準的な量子オラクルが与えられたとき、我々のアルゴリズムは$widetildeO(sqrtm + ncdot epsilon-2.5 + epsilon-3)$で実行され、$epsilon$-approximate Nash平衡の古典的な表現を出力する。
論文 参考訳(メタデータ) (2023-01-10T02:56:49Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳(メタデータ) (2022-01-31T22:19:49Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳(メタデータ) (2021-11-29T19:26:28Z) - 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) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳(メタデータ) (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。