論文の概要: The Complexity of NISQ

• arxiv url: http://arxiv.org/abs/2210.07234v1
• Date: Thu, 13 Oct 2022 17:58:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-14 17:53:14.324631
• Title: The Complexity of NISQ
• Title（参考訳）: NISQの複雑さ
• Authors: Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li
• Abstract要約: NISQデバイスは、その計算能力を理解するために必須である。 本稿では、複雑性クラス $textsfNISQ $ を定義し、研究する。 3つのよく研究された問題に対して$textsfNISQ$のパワーを考慮する。
• 参考スコア（独自算出の注目度）: 15.842125145638693
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The recent proliferation of NISQ devices has made it imperative to understand their computational power. In this work, we define and study the complexity class $\textsf{NISQ} $, which is intended to encapsulate problems that can be efficiently solved by a classical computer with access to a NISQ device. To model existing devices, we assume the device can (1) noisily initialize all qubits, (2) apply many noisy quantum gates, and (3) perform a noisy measurement on all qubits. We first give evidence that $\textsf{BPP}\subsetneq \textsf{NISQ}\subsetneq \textsf{BQP}$, by demonstrating super-polynomial oracle separations among the three classes, based on modifications of Simon's problem. We then consider the power of $\textsf{NISQ}$ for three well-studied problems. For unstructured search, we prove that $\textsf{NISQ}$ cannot achieve a Grover-like quadratic speedup over $\textsf{BPP}$. For the Bernstein-Vazirani problem, we show that $\textsf{NISQ}$ only needs a number of queries logarithmic in what is required for $\textsf{BPP}$. Finally, for a quantum state learning problem, we prove that $\textsf{NISQ}$ is exponentially weaker than classical computation with access to noiseless constant-depth quantum circuits.
• Abstract（参考訳）: 最近のNISQデバイスの普及により、その計算能力を理解することが不可欠になっている。 本研究では,nisqデバイスにアクセスして古典的コンピュータで効率的に解くことができる問題をカプセル化する,複雑性クラス $\textsf{nisq} $ を定義し,検討する。 既存の装置をモデル化するために,(1)すべての量子ビットを任意に初期化し,(2)多くのノイズ量子ゲートを適用し,(3)すべての量子ビットに対してノイズの測定を行うことができると仮定する。 最初に、シモンの問題の修正に基づいて、3つのクラスの間で超多項式的オラクル分離を示すことによって、$\textsf{BPP}\subsetneq \textsf{NISQ}\subsetneq \textsf{BQP}$を証明した。 次に、よく研究された3つの問題に対して$\textsf{NISQ}$のパワーを考える。 非構造化探索の場合、$\textsf{NISQ}$は$\textsf{BPP}$以上のグロバーのような二次的スピードアップを達成できない。 Bernstein-Vazirani 問題に対して、$\textsf{NISQ}$ は $\textsf{BPP}$ に必要なクエリ対数しか必要としないことを示す。 最後に、量子状態学習問題に対して、$\textsf{nisq}$ が、ノイズのない定数深さ量子回路へのアクセスを持つ古典計算よりも指数関数的に弱いことを証明する。

関連論文リスト

• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [63.01248796170617]
  最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。 次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
  論文  参考訳（メタデータ） (2024-11-21T17:41:09Z)
• Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
  量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。 驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。 約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
  論文  参考訳（メタデータ） (2024-11-01T18:00:56Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• On the Role of Entanglement and Statistics in Learning [3.729242965449096]
  我々は,絡み合った,分離可能な,統計的に測定された学習モデルと学習モデルとの関係を理解することを進める。 我々は、QSQ学習と量子学習を交絡測定で指数関数的に分離するクラスC$を示す。 我々は,純度テスト,シャドウトモグラフィ,アベリア隠れ部分群問題,次数2$関数,植込み双斜め状態,クリフォード深度回路の出力状態について,超ポリノミカルQSQの下界を証明した。
  論文  参考訳（メタデータ） (2023-06-05T18:16:03Z)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。 我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
  論文  参考訳（メタデータ） (2023-03-20T08:17:32Z)
• Quantum free games [2.298932494750101]
  我々は、$n$変数上の3SATのベルQMA(2)プロトコルを示し、通信総量は$tildeO(sqrtn)である。
  論文  参考訳（メタデータ） (2023-02-08T20:32:24Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Quantum algorithm for learning secret strings and its experimental demonstration [2.924463125497859]
  教師-学生設定における秘密弦学習問題について考察する。 我々は,$n$クエリを用いて任意の$s$を学習する古典的決定論的アルゴリズムを提案する。 我々は,n$-bit秘密文字列$s$を確実に学習する量子アルゴリズムを得る。
  論文  参考訳（メタデータ） (2022-06-22T17:15:45Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)

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

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