論文の概要: 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.

関連論文リスト

• The power of shallow-depth Toffoli and qudit quantum circuits [3.212381039696143]
  量子回路複雑性の主な目的の1つは、量子浅層回路によって解くことができるが、古典的により多くの計算資源を必要とする問題を見つけることである。 我々は古典的回路と量子的定数深さ回路の分離を新たに証明する。 無限大ゲートセットの場合、高次元ヒルベルト空間に対するこれらの量子回路クラスは標準量子ビット実装に何の利点も与えない。
  論文  参考訳（メタデータ） (2024-04-28T07:44:27Z)
• State preparation by shallow circuits using feed forward [0.0]
  我々は,この4ステップ方式を用いて,フォールトトレラントな計算を行わず,短い,一定の深さの量子回路を強化する。 LAQCC回路は、一定の深さの量子回路では達成できない長距離相互作用を創出できることを示す。 我々は、任意の数の状態に対する一様重ね合わせのための3つの新しい状態準備プロトコルを作成する。
  論文  参考訳（メタデータ） (2023-07-27T13:20:21Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• 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)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。