論文の概要: 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) から束縛された濃度である。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳(メタデータ) (2024-01-17T18:59:38Z) - Tetrationally Compact Entanglement Purification [0.03922370499388702]
本論文は, 極めて少ない貯蔵量で, 絡み合いを浄化できることを示唆する。
対象不忠実な$epsilon$のアンタングルペアは、$tildeO(log frac1epsilon)$ timeで作成できる。
論文 参考訳(メタデータ) (2023-11-18T04:39:50Z) - A Note on Quantum Phase Estimation [0.0]
より単純で自己完結したクエリローバウンドの証明を示す。
具体的には,ブール関数解析や逆法の知識を使わずに,基本線型代数から成り立つ。
論文 参考訳(メタデータ) (2023-04-05T06:05:42Z) - 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) - Improved Quantum Hypercontractivity Inequality for the Qubit
Depolarizing Channel [2.9443230571766845]
Psi_t$は、$|Psi_totimes n(X)|_pleq |X|_q$が$pgeq q> 1$と$tgeq ln sqrtfracp-1q-1$であるとする。
まず、改善された量子対数-ソボレフ不等式を証明し、次に、対数-ソボレフ超収縮度不等式のよく知られた等価性を用いて、主要な結果を得る。
論文 参考訳(メタデータ) (2021-05-02T13:04:17Z) - Improved spectral gaps for random quantum circuits: large local
dimensions and all-to-all interactions [0.0]
我々は、$D$のランダム量子回路がスペクトルギャップスケーリングを$Omega(n-1)$とすることを示し、$t$が局所次元と比較して小さいことを仮定する:$t2leq O(q)$。
2つ目の結果は、全ての相互作用を持つランダム量子回路に対して、以下に$Omega(n-1log-1(n) t-alpha(q))$で有界な非条件スペクトルギャップである。
論文 参考訳(メタデータ) (2020-12-09T19:00:50Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。