論文の概要: Interactive quantum advantage with noisy, shallow Clifford circuits
- arxiv url: http://arxiv.org/abs/2102.06833v2
- Date: Mon, 27 Sep 2021 22:48:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-11 06:14:04.785186
- Title: Interactive quantum advantage with noisy, shallow Clifford circuits
- Title（参考訳）: ノイズの少ない浅層クリフォード回路を用いたインタラクティブ量子アドバンテージ
- Authors: Daniel Grier, Nathan Ju, Luke Schaeffer
- Abstract要約: 本稿では,Grier と Schaeffer の対話プロトコルに耐雑音性を加えるための戦略を示す。
この削減の重要な要素は、古典的なシミュレーションタスクにおける平均ケースの硬さを示すことである。
シュミレートするために$oplus$L-hardの量子タスクでさえそうであることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent work by Bravyi et al. constructs a relation problem that a noisy
constant-depth quantum circuit (QNC$^0$) can solve with near certainty
(probability $1 - o(1)$), but that any bounded fan-in constant-depth classical
circuit (NC$^0$) fails with some constant probability. We show that this
robustness to noise can be achieved in the other low-depth quantum/classical
circuit separations in this area. In particular, we show a general strategy for
adding noise tolerance to the interactive protocols of Grier and Schaeffer. As
a consequence, we obtain an unconditional separation between noisy QNC$^0$
circuits and AC$^0[p]$ circuits for all primes $p \geq 2$, and a conditional
separation between noisy QNC$^0$ circuits and log-space classical machines
under a plausible complexity-theoretic conjecture.
A key component of this reduction is showing average-case hardness for the
classical simulation tasks -- that is, showing that a classical simulation of
the quantum interactive task is still powerful even if it is allowed to err
with constant probability over a uniformly random input. We show that is true
even for quantum tasks which are $\oplus$L-hard to simulate. To do this, we
borrow techniques from randomized encodings used in cryptography.
- Abstract（参考訳）: Bravyiらによる最近の研究は、ノイズの多い定数深度量子回路(QNC$^0$)がほぼ確実性(確率1 - o(1)$)で解けるという関係問題を構築するが、任意の有界ファンイン定数深度古典回路(NC$^0$)は一定の確率で失敗する。
この雑音に対するロバスト性は、この領域における他の低深さ量子/古典回路分離によって達成できることを示す。
特に、GrierとSchaefferの対話プロトコルに耐雑音性を加えるための一般的な戦略を示す。
その結果、すべての素数$p \geq 2$に対するノイズQNC$^0$回路とAC$^0[p]$回路の非条件分離と、可算複雑性理論の予想の下でノイズQNC$^0$回路とログスペース古典機械との条件分離が得られる。
この縮小の重要な要素は、古典的なシミュレーションタスクの平均ケース硬さである。量子インタラクティブタスクの古典的なシミュレーションは、一様ランダムな入力に対して一定の確率で振る舞うことを許されたとしても、まだ強力であることを示している。
これは、シミュレーションが難しい$\oplus$l-hardの量子タスクでも当てはまります。
これを実現するために、暗号で使われるランダムエンコーディングのテクニックを借用します。
関連論文リスト
- A polynomial-time classical algorithm for noisy quantum circuits [1.2708457954150887]
雑音量子回路のための時空古典的アルゴリズムを提供する。
我々のアプローチは、雑音が非局所的相関を指数的に減衰させるという直感に基づいている。
定音率の場合、ほとんどの入力状態において誤差緩和が効率的である任意の量子回路は、古典的にはほとんどの入力状態においてシミュレート可能である。
論文 参考訳（メタデータ） (2024-07-17T17:48:39Z) - Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth [0.5188841610098435]
雑音の除去や非偏極化を行う任意のIQP回路の場合、出力分布は古典的コンピュータで効率的にサンプリング可能であることを示す。
我々は、IQP回路が対角ゲートの深い部分を持つという事実を利用して、ノイズが予測可能となり、回路内の絡み合いの大規模な分解を誘発する。
論文 参考訳（メタデータ） (2024-03-21T17:55:26Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - On the power of geometrically-local classical and quantum circuits [6.011628409537168]
マジックスクエアゲームの並列反復に基づいて、確率を指数関数的に1ドル近い確率で解くことができる関係を示す。
我々は、指数的に小さな成功確率で、同じ関係を解くことはできないことを示した。
NISQ時代に検証可能な量子優位性を実証できるプロトコルを提案する。
論文 参考訳（メタデータ） (2023-10-02T18:27:53Z) - Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach [1.806183113759115]
大規模変動量子アルゴリズムは量子優位性を達成するための潜在的な経路として広く認識されている。
本稿では,可観測物のバックプロパゲーションの積分経路に基づく新しい$gammaPPP法を提案する。
我々は,IBMの127量子ビットイーグルプロセッサにおけるゼロノード化実験結果の古典的シミュレーションを行う。
論文 参考訳（メタデータ） (2023-06-09T10:42:07Z) - Unconditional Quantum Advantage for Sampling with Shallow Circuits [0.0]
Bravyi、Gosset、Koenigによる最近の研究は、一定の深さの量子回路で解ける探索問題が存在することを示した。
この質問に対する答えは、古典回路に与えられるランダムな入力ビットの数が有界であるときにイエスであることが示される。
また、アドバイス付き定数深度量子回路と、ファンインとファンアウトの有界な古典回路との類似の分離を示す。
論文 参考訳（メタデータ） (2023-01-03T08:07:55Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - 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) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳（メタデータ） (2020-11-24T18:44:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。