論文の概要: Complement Sampling: Provable, Verifiable and NISQable Quantum Advantage in Sample Complexity

• arxiv url: http://arxiv.org/abs/2502.08721v1
• Date: Wed, 12 Feb 2025 19:00:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-14 13:48:07.318301
• Title: Complement Sampling: Provable, Verifiable and NISQable Quantum Advantage in Sample Complexity
• Title（参考訳）: 補充サンプリング: サンプル複雑度における確率的, 検証可能, NISQable 量子アドバンテージ
• Authors: Marcello Benedetti, Harry Buhrman, Jordi Weggemans,
• Abstract要約: 1つの量子サンプル(サブセットの要素上の一様重ね合わせの1つのコピー)のみを使用する単純な量子アルゴリズムを提供する。 サンプル対サンプルの設定では、量子計算は古典的な計算よりも最も大きな分離を達成できる。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Consider a fixed universe of $N=2^n$ elements and the uniform distribution over elements of some subset of size $K$. Given samples from this distribution, the task of complement sampling is to provide a sample from the complementary subset. We give a simple quantum algorithm that uses only a single quantum sample -- a single copy of the uniform superposition over elements of the subset. When $K=N/2$, we show that the quantum algorithm succeeds with probability $1$, whereas classically $\Theta(N)$ samples are required to succeed with bounded probability of error. This shows that in a sample-to-sample setting, quantum computation can achieve the largest possible separation over classical computation. Moreover, we show that the same bound can be lifted to prove average-case hardness. It follows that under the assumption of the existence of one-way functions, complement sampling gives provable, verifiable and NISQable quantum advantage in a sample complexity setting.
• Abstract（参考訳）: N=2^n$要素の固定宇宙と、ある大きさの集合の要素上の一様分布を考える。 この分布からサンプルが与えられた場合、補的サンプリングのタスクは補的部分集合からのサンプルを提供することである。 1つの量子サンプル(サブセットの要素上の一様重ね合わせの1つのコピー)のみを使用する単純な量子アルゴリズムを提供する。 K=N/2$の場合、量子アルゴリズムは確率$$1で成功するが、古典的には$\Theta(N)$サンプルは誤差の有界な確率で成功する必要がある。 これは、サンプル対サンプルの設定において、量子計算が古典的な計算よりも最も大きな分離を達成できることを示している。 さらに、平均ケース硬さを証明するために、同じ境界を持ち上げることができることを示す。 一方向関数の存在を前提として、補的サンプリングは、サンプル複雑性設定において証明可能、検証可能、およびNISQable量子上の優位性を与える。

関連論文リスト

• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions [13.16814860487575]
  非対数確率分布からサンプリングする量子アルゴリズムを提案する。 f$ は有限和 $f(x):= frac1Nsum_k=1N f_k(x)$ と書くことができる。
  論文  参考訳（メタデータ） (2023-10-17T17:55:32Z)
• Sampled Transformer for Point Sets [80.66097006145999]
  スパース変換器は、連続列列列関数の普遍近似器でありながら、自己アテンション層の計算複雑性を$O(n)$に下げることができる。 我々は、追加の帰納バイアスを伴わずに点集合要素を直接処理できる$O(n)$複雑性サンプリング変換器を提案する。
  論文  参考訳（メタデータ） (2023-02-28T06:38:05Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  我々は、係数に応じてハミルトン式からサンプリングしてランダムな積公式を構築するqDriftプロトコルを導入する。 サンプリング段階における個別のシミュレーションコストを考慮し、同じ精度でシミュレーションコストを削減可能であることを示す。 格子核効果場理論を用いて数値シミュレーションを行った結果, 実験結果が得られた。
  論文  参考訳（メタデータ） (2022-12-12T15:06:32Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Quantum supremacy with spin squeezed atomic ensembles [0.0]
  量子ビットのアンサンブルを用いた量子超越性を実現する手法を提案する。 各アンサンブルは全スピンでのみ制御可能であると仮定される。 最終測定値の確率分布は,Porter-Thomas分布に急速に近づくことを示す。
  論文  参考訳（メタデータ） (2022-04-25T16:42:37Z)
• Uncorrelated problem-specific samples of quantum states from zero-mean Wishart distributions [4.289102530380288]
  量子状態空間からサンプリングする2段階のアルゴリズムを提案する。 量子状態に対するウィッシュアート分布の明示的な形式を確立する。 このサンプリングアルゴリズムは1量子状態と2量子状態に対して非常に効率的であり、3量子状態に対しては合理的に効率的であることを示す。
  論文  参考訳（メタデータ） (2021-06-16T03:06:41Z)
• Learning k-qubit Quantum Operators via Pauli Decomposition [11.498089180181365]
  現在の量子系の量子ビット容量の制限により、量子サンプルの複雑さを$k$-qubit量子作用素で調べる。 我々は、$k$-qubitの量子演算の量子サンプルの複雑さが、その量子演算の古典的なサンプルの複雑さに匹敵することを示した。
  論文  参考訳（メタデータ） (2021-02-10T01:20:55Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)

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

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