論文の概要: Quantum Advantage with Shallow Circuits Under Arbitrary Corruption
- arxiv url: http://arxiv.org/abs/2105.00603v3
- Date: Thu, 12 May 2022 14:04:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-01 18:02:47.877371
- Title: Quantum Advantage with Shallow Circuits Under Arbitrary Corruption
- Title(参考訳): 任意破壊下における浅回路の量子アドバンテージ
- Authors: Atsuya Hasegawa and Fran\c{c}ois Le Gall
- Abstract要約: 近年の研究では、量子回路と古典回路の計算能力の分離が示されている。
本稿では、任意の定数の量子ビットが任意に破壊される場合について考察する。
この困難な環境でも、量子的優位性を確立するための第一歩を踏み出します。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent works by Bravyi, Gosset and K\"onig (Science 2018), Bene Watts et al.
(STOC 2019), Coudron, Stark and Vidick (QIP 2019) and Le Gall (CCC 2019) have
shown unconditional separations between the computational powers of shallow
(i.e., small-depth) quantum and classical circuits: quantum circuits can solve
in constant depth computational problems that require logarithmic depth to
solve with classical circuits. Using quantum error correction, Bravyi, Gosset,
K\"onig and Tomamichel (Nature Physics 2020) further proved that a similar
separation still persists even if quantum circuits are subject to local
stochastic noise.
In this paper, we consider the case where any constant fraction of the qubits
(for instance, huge blocks of qubits) may be arbitrarily corrupted at the end
of the computation. We make a first step forward towards establishing a quantum
advantage even in this extremely challenging setting: we show that there exists
a computational problem that can be solved in constant depth by a quantum
circuit but such that even solving any large subproblem of this problem
requires logarithmic depth with bounded fan-in classical circuits. This gives
another compelling evidence of the computational power of quantum shallow
circuits.
In order to show our result, we consider the Graph State Sampling problem
(which was also used in prior works) on expander graphs. We exploit the
"robustness" of expander graphs against vertex corruption to show that a
subproblem hard for small-depth classical circuits can still be extracted from
the output of the corrupted quantum circuit.
- Abstract(参考訳): bravyi, gosset, k\"onig (science 2018), bene watts et al. (stoc 2019), coudron, stark and vidick (qip 2019) および le gall (ccc 2019) による最近の研究では、浅い(すなわち、小さな深さの)量子回路と古典回路の計算能力の無条件分離が示されている。
Using quantum error correction, Bravyi, Gosset, K\"onig and Tomamichel (Nature Physics 2020) further proved that a similar separation still persists even if quantum circuits are subject to local stochastic noise. In this paper, we consider the case where any constant fraction of the qubits (for instance, huge blocks of qubits) may be arbitrarily corrupted at the end of the computation. We make a first step forward towards establishing a quantum advantage even in this extremely challenging setting: we show that there exists a computational problem that can be solved in constant depth by a quantum circuit but such that even solving any large subproblem of this problem requires logarithmic depth with bounded fan-in classical circuits. This gives another compelling evidence of the computational power of quantum shallow circuits. In order to show our result, we consider the Graph State Sampling problem (which was also used in prior works) on expander graphs. We exploit the "robustness" of expander graphs against vertex corruption to show that a subproblem hard for small-depth classical circuits can still be extracted from the output of the corrupted quantum circuit.
関連論文リスト
- State preparation by shallow circuits using feed forward [0.0]
我々は,1量子ビットゲートと隣り合う2量子ビットゲートを実行する,短い,一定の深さの量子回路を強化するための4段階のスキームを利用する。
LAQCC回路は、一定の深さの量子回路では達成できない長距離相互作用を創出できることを示す。
我々は、任意の数の状態に対する一様重ね合わせのための3つの新しい状態準備プロトコルを作成する。
論文 参考訳(メタデータ) (2023-07-27T13:20:21Z) - Limitations of Noisy Quantum Devices in Computational and Entangling
Power [5.178527492542246]
回路深さが$O(log n)$以上のノイズ量子デバイスは、いかなる量子アルゴリズムにも利点がないことを示す。
また、ノイズ量子デバイスが1次元および2次元の量子ビット接続の下で生成できる最大エンタングルメントについても検討する。
論文 参考訳(メタデータ) (2023-06-05T12:29:55Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳(メタデータ) (2022-10-12T17:54:02Z) - Gaussian initializations help deep variational quantum circuits escape
from the barren plateau [87.04438831673063]
近年、変分量子回路は量子シミュレーションや量子機械学習に広く用いられている。
しかし、ランダムな構造を持つ量子回路は、回路深さと量子ビット数に関して指数関数的に消える勾配のため、トレーニング容易性が低い。
この結果、ディープ量子回路は実用的なタスクでは実現できないという一般的な信念が導かれる。
論文 参考訳(メタデータ) (2022-03-17T15:06:40Z) - $i$-QER: An Intelligent Approach towards Quantum Error Reduction [5.055934439032756]
量子回路のエラーを評価するスケーラブルな機械学習ベースのアプローチである$i$-QERを導入する。
i$-QERは、教師付き学習モデルを使用して、与えられた量子回路で可能なエラーを予測する。
これにより、大きな量子回路を2つの小さなサブ回路に分割する。
論文 参考訳(メタデータ) (2021-10-12T20:45:03Z) - Configurable sublinear circuits for quantum state preparation [1.9279780052245203]
量子回路で$O(sqrtN)$の幅と深さと絡み合った情報をアシラリー量子ビットで符号化する構成を示す。
5つの量子コンピュータ上で原理実証を行い、その結果を比較した。
論文 参考訳(メタデータ) (2021-08-23T13:52:43Z) - Demonstrating robust simulation of driven-dissipative problems on
near-term quantum computers [53.20999552522241]
量子コンピュータは物理学と化学における量子力学系のシミュレーションに革命をもたらす。
現在の量子コンピュータは、訂正されていないノイズ、ゲートエラー、デコヒーレンスのためにアルゴリズムを不完全に実行している。
ここでは、量子力学における最も難しい問題の1つとして、駆動散逸多体問題の解法が本質的にエラーに対して堅牢であることを示す。
論文 参考訳(メタデータ) (2021-08-02T21:36:37Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳(メタデータ) (2021-06-11T09:43:09Z) - Fault-tolerant quantum speedup from constant depth quantum circuits [0.0]
出力分布に応じて$poly(n)$ timeでサンプリングできる古典的アルゴリズムは存在しないことを示す。
我々は2つの構成を提示し、それぞれ$poly(n)$ physical qubitsを持ち、そのうちのいくつかはノイズの多い魔法の状態で準備される。
論文 参考訳(メタデータ) (2020-05-23T13:53:27Z) - Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
Googleの最近の量子超越性実験は、量子コンピューティングがランダムな回路サンプリングという計算タスクを実行する遷移点を示している。
観測された量子ランタイムの利点の制約を、より多くの量子ビットとゲートで検討する。
論文 参考訳(メタデータ) (2020-05-05T20:11:53Z) - Estimating the entropy of shallow circuit outputs is hard [77.34726150561087]
シャノンエントロピー推定の意思決定問題バージョンはエントロピー差分(ED)である
量子回路(QED)の類似の問題
オラクルと比較して、これらの問題は指数関数的に大きい回路と同等に難しいものではないことを示す。
論文 参考訳(メタデータ) (2020-02-27T15:32:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。