論文の概要: Quantum Approximate Counting with Bernoulli Oracles

• arxiv url: http://arxiv.org/abs/2609.07604v1
• Date: Mon, 07 Sep 2026 15:13:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-11 21:39:04.650178
• Title: Quantum Approximate Counting with Bernoulli Oracles
• Title（参考訳）: Bernoulli Oraclesによる量子近似数
• Abstract要約: 我々は$tildeO!big(fracsqrt+frac1sqrtbig)$クエリの上限を証明し、古典的なサンプリングよりも2次的なスピードアップを達成する。 この上界を、量子逆法に対する新しい合成定理により、ほぼ一致する$(sqrt/())$の下界で補う。
• 参考スコア（独自算出の注目度）: 3.8743350688734988
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given $m$ Bernoulli distributions with unknown biases $p_1,\dots,p_m$ and a gap parameter $Δ$, the goal is to estimate the fraction $ρ$ of \emph{positive} distributions ($p_i\ge1/2+Δ$) to within additive error $ε$. We prove an upper bound of $\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)$ queries, achieving a quadratic speedup over the classical sample complexity. % of $Θ(ρ/Δ^2ε^2)$. Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of $Ω(\sqrtρ/(Δε))$ via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap $Δ=Θ(1)$, which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to $\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)$ and $Ω(\frac{\sqrtρ}ε)$, thereby characterizing the query complexity of quantum counting with bounded-error oracles.
• Abstract（参考訳）: 量子カウント(Quantum counting)は、古典的なサンプリングよりも2次的なスピードアップを達成し、メンバシップオラクルを用いてマークされた要素の分数を推定する基本的な量子アルゴリズムである。 しかし、メンバーシップオラクルは各要素の正確なラベル付けを仮定するが、この仮定はラベルが本質的に確率的であるときに失敗する。 我々は \emph{Bernoulli oracles} を用いて量子カウントを研究し、ここでは、未知のバイアスを持つ $m$ Bernoulli 分布 $p_1,\dots,p_m$ とギャップパラメータ $Δ$ を与えられる。 上限が$\tilde{O}\! \big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)$クエリは、古典的なサンプルの複雑さに対して二次的なスピードアップを達成する。 %(ρ/Δ^2ε^2)$。 我々のアルゴリズムはまず量子特異値変換(QSVT)を用いて分布上の重ね合わせを損なうことなくバイアスギャップをコヒーレントに増幅し、2段階適応振幅推定を適用する。 我々はこの上界を、ブール対平均ケース方向の量子逆法に対する新しい合成定理により、$Ω(\sqrtρ/(Δε))$の近似下界で補う。 各クエリが正しいラベルを一定の確率で返却する有界エラーオラクルに対応する定数ギャップ$Δ=a(1)$の特別の場合、我々の境界は$\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)$と$Ω(\frac{\sqrtρ}ε)$に特殊化され、したがって有界エラーオラクルによる量子カウントのクエリ複雑性を特徴づける。

関連論文リスト

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Quantum Multi-Level Estimation of Functionals of Discrete Distributions [23.53427184324404]
  離散分布の関数 $sum_i=1n f(p_i)$ に対する量子多値推定フレームワークを提案する。 離散分布の$q$-Tsallisエントロピーに対する効率的な量子推定器を提案する。
  論文  参考訳（メタデータ） (2026-05-05T12:25:17Z)
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
  確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。 我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。 クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-25T15:32:37Z)
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation [13.810917492304565]
  離散確率分布の特性を推定するための統一量子アルゴリズムフレームワークを提案する。 我々のフレームワークは、$alpha$-R'enyi entropy $H_alpha(p)$を、少なくとも2/3$の確率で加算エラー$epsilon$内で推定する。
  論文  参考訳（メタデータ） (2022-12-03T08:01:55Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• 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)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。 十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。 ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
  論文  参考訳（メタデータ） (2021-11-29T19:26:28Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)

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

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