論文の概要: The power of quantum circuits in sampling

• arxiv url: http://arxiv.org/abs/2510.03645v1
• Date: Sat, 04 Oct 2025 03:19:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 16:52:59.175097
• Title: The power of quantum circuits in sampling
• Title（参考訳）: サンプリングにおける量子回路のパワー
• Authors: Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan,
• Abstract要約: ランダムなオラクルと比較して、量子サイズの回路は、サブ指数サイズの古典的な回路では近似できない分布をサンプリングできることが示される。 本証明の鍵となる要素は,山川区(2022年)探索問題における古典的な問合せ複雑性に対する新しい硬度増幅補題である。
• 参考スコア（独自算出の注目度）: 10.233615909288188
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give new evidence that quantum circuits are substantially more powerful than classical circuits. We show, relative to a random oracle, that polynomial-size quantum circuits can sample distributions that subexponential-size classical circuits cannot approximate even to TV distance $1-o(1)$. Prior work of Aaronson and Arkhipov (2011) showed such a separation for the case of exact sampling (i.e. TV distance $0$), but separations for approximate sampling were only known for uniform algorithms. A key ingredient in our proof is a new hardness amplification lemma for the classical query complexity of the Yamakawa-Zhandry (2022) search problem. We show that the probability that any family of query algorithms collectively finds $k$ distinct solutions decays exponentially in $k$.
• Abstract（参考訳）: 量子回路は古典回路よりもかなり強力であることを示す新しい証拠を与える。 ランダムなオラクルと比較して、多項式サイズの量子回路は、テレビ距離が1-o(1)$のときでさえ、サブ指数サイズの古典回路では近似できない分布をサンプリングできることが示される。 Aaronson と Arkhipov (2011) の以前の研究は、正確なサンプリングの場合にはそのような分離(テレビ距離$0$)を示したが、近似サンプリングの分離は、一様アルゴリズムでのみ知られていた。 本証明の鍵となる要素は,山川区(2022年)探索問題における古典的な問合せ複雑性に対する新しい硬度増幅補題である。 問合せアルゴリズムの族が集合的に$k$異なる解を見つける確率は、$k$で指数関数的に減衰することを示す。

関連論文リスト

• On verifiable quantum advantage with peaked circuit sampling [9.551919087634522]
  このような回路から1/textpoly(n)$のピーク値を得るには、圧倒的な確率で$tau_p = Omega(tau_r/n)0.19)$が必要である。 また、このモデルでは非自明なピーク性も可能であるという数値的な証拠を与える。
  論文  参考訳（メタデータ） (2024-04-22T18:00:06Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。 次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
  論文  参考訳（メタデータ） (2023-11-07T04:59:02Z)
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach [1.806183113759115]
  大規模変動量子アルゴリズムは量子優位性を達成するための潜在的な経路として広く認識されている。 本稿では,可観測物のバックプロパゲーションの積分経路に基づく新しい$gammaPPP法を提案する。 我々は,IBMの127量子ビットイーグルプロセッサにおけるゼロノード化実験結果の古典的シミュレーションを行う。
  論文  参考訳（メタデータ） (2023-06-09T10:42:07Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T08:04:15Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Classical Sampling of Random Quantum Circuits with Bounded Fidelity [0.5735035463793007]
  任意のランダム量子回路の確率分布を生成するための古典的なサンプリングアルゴリズムを提案する。 古典的には、シカモア53量子ビットチップの20サイクル回路に基づいて、その忠実度を0.2%に制限した100万のサンプルを生成した。 我々は,Zuchongzhi 56-qubit 20-cycle 回路では,Selene スーパーコンピュータを用いて,忠実度 0.066% の 1M サンプルを生成可能であると推定した。
  論文  参考訳（メタデータ） (2021-12-30T14:51:39Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)

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

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