論文の概要: 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)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Quantum Advantage in Tolerant Junta Testing [0.5442955439283729]
  適応設定において、許容値$k$-juntaテスト問題に対する最初の超多項式量子優位性を確立する。 特定のパラメータ体系内では、高い精度で寛容な$k$-juntaテストが$mathrmpoly(k)$quantumquantumquantum(k)$で解けることを示す。
  論文  参考訳（メタデータ） (2026-06-22T11:42:39Z)
• Quantum Multi-Level Estimation of Functionals of Discrete Distributions [23.53427184324404]
  離散分布の関数 $sum_i=1n f(p_i)$ に対する量子多値推定フレームワークを提案する。 離散分布の$q$-Tsallisエントロピーに対する効率的な量子推定器を提案する。
  論文  参考訳（メタデータ） (2026-05-05T12:25:17Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Quantum phase discrimination with applications to quantum search on graphs [0.0]
  本稿では,この課題に対して量子位相判別(QPD)という量子アルゴリズムを提案する。 QPDを用いることで、Li と Zur が提案するパスフィニングアルゴリズムのクエリ複雑性を低減できる。 グラフ上の量子探索に2つの応用を提案する。
  論文  参考訳（メタデータ） (2025-04-21T16:06:43Z)
• Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
  確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。 我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。 我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
  論文  参考訳（メタデータ） (2024-11-20T02:46:15Z)
• 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)

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

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