論文の概要: Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

• arxiv url: http://arxiv.org/abs/2510.07808v1
• Date: Thu, 09 Oct 2025 05:34:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-10 17:54:14.886494
• Title: Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
• Title（参考訳）: 浅回路サンプリングによる量子アドバンテージ:マージナルの硬さを超えて
• Authors: Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, Kewen Wu,
• Abstract要約: 我々は$mathcalD_nn$を$mathcalD_n$以上$0, 1n$、深さ7$の量子回路群を構成する。 私たちのディストリビューションのファミリーは、Bravyi、Gosset、K"onig(Science)の作業をベースに構築された、Watts、Kothari、Schaeffer、およびTal(STOC, 2019)のParity Halving Problem of Watts、Kothari、Schaeffer、およびTal(STOC, 2019)に触発されたものです。
• 参考スコア（独自算出の注目度）: 6.252607743959949
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We construct a family of distributions $\{\mathcal{D}_n\}_n$ with $\mathcal{D}_n$ over $\{0, 1\}^n$ and a family of depth-$7$ quantum circuits $\{C_n\}_n$ such that $\mathcal{D}_n$ is produced exactly by $C_n$ with the all zeros state as input, yet any constant-depth classical circuit with bounded fan-in gates evaluated on any binary product distribution has total variation distance $1 - e^{-\Omega(n)}$ from $\mathcal{D}_n$. Moreover, the quantum circuits we construct are geometrically local and use a relatively standard gate set: Hadamard, controlled-phase, CNOT, and Toffoli gates. All previous separations of this type suffer from some undesirable constraint on the classical circuit model or the quantum circuits witnessing the separation. Our family of distributions is inspired by the Parity Halving Problem of Watts, Kothari, Schaeffer, and Tal (STOC, 2019), which built on the work of Bravyi, Gosset, and K\"onig (Science, 2018) to separate shallow quantum and classical circuits for relational problems.
• Abstract（参考訳）: 我々は、$\mathcal{D}_n\}_n$ with $\mathcal{D}_n$ over $\{0, 1\}^n$と深さ7$の量子回路の族$\{C_n\}_n$を構築し、$\mathcal{D}_n$は入力としてすべての零点状態を持つ$C_n$で正確に生成されるが、任意の二元積分布で評価された有界ファンインゲートを持つ任意の定深さ古典回路は、合計変動距離が 1 - e^{-\Omega(n)}$ である。 さらに、我々の構成する量子回路は幾何学的に局所的であり、比較的標準的なゲートセットであるアダマール、制御相、CNOT、トフォリゲートを用いる。 このタイプの以前の分離は、古典的な回路モデルや、分離を目撃する量子回路に対するいくつかの望ましくない制約に悩まされている。 私たちのディストリビューションのファミリーは、Bravyi、Gosset、K\"onig(Science、2018年)の業績に基づいて、リレーショナル問題のための浅い量子回路と古典回路を分離するために構築されたParity Halving Problem of Watts、Kothari、Schaeffer、およびTal(STOC、2019)にインスパイアされています。

関連論文リスト

• The power of shallow-depth Toffoli and qudit quantum circuits [3.212381039696143]
  量子回路複雑性の主な目的の1つは、量子浅層回路によって解くことができるが、古典的により多くの計算資源を必要とする問題を見つけることである。 我々は古典的回路と量子的定数深さ回路の分離を新たに証明する。 無限大ゲートセットの場合、高次元ヒルベルト空間に対するこれらの量子回路クラスは標準量子ビット実装に何の利点も与えない。
  論文  参考訳（メタデータ） (2024-04-28T07:44:27Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Unconditional Quantum Advantage for Sampling with Shallow Circuits [0.0]
  Bravyi、Gosset、Koenigによる最近の研究は、一定の深さの量子回路で解ける探索問題が存在することを示した。 この質問に対する答えは、古典回路に与えられるランダムな入力ビットの数が有界であるときにイエスであることが示される。 また、アドバイス付き定数深度量子回路と、ファンインとファンアウトの有界な古典回路との類似の分離を示す。
  論文  参考訳（メタデータ） (2023-01-03T08:07:55Z)
• 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)
• Annihilating Entanglement Between Cones [77.34726150561087]
  ローレンツ錐体は、ある種の強いレジリエンス特性を満たす対称基底を持つ唯一の円錐体であることを示す。 我々の証明はローレンツ・コーンの対称性を利用しており、エンタングルメント蒸留のプロトコルに類似した2つの構造を適用している。
  論文  参考訳（メタデータ） (2021-10-22T15:02:39Z)
• Quantum supremacy and hardness of estimating output probabilities of quantum circuits [0.0]
  我々は、出力確率を2-Omega(nlogn)$以内に近似する非集中階層の理論的な複雑さを証明している。 この硬さは、任意の(固定された)回路の任意の開近傍に拡張され、自明なゲートを持つ回路を含むことを示す。
  論文  参考訳（メタデータ） (2021-02-03T09:20:32Z)

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

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