論文の概要: Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method
- arxiv url: http://arxiv.org/abs/2609.09804v1
- Date: Wed, 09 Sep 2026 07:01:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-10 19:44:08.925833
- Title: Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method
- Title（参考訳）: 乗法逆法による小バイアス量子近似計数
- Abstract要約: 量子近似カウントの2重決定版について検討する。
オラクルが$xin0,1N$にアクセスすると、$|x|=M$と$|x|=M+$を区別する。
乗法逆法を用いて、$left(maxleftsqrt(N-M)(M+)/,sqrtN/rightright)$を証明する。
- 参考スコア（独自算出の注目度）: 1.2799130177714182
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the two-weight decision version of quantum approximate counting: given oracle access to $x\in\{0,1\}^N$, distinguish $|x|=M$ from $|x|=M+Δ$ with success probability $1/2+ζ$. Using the multiplicative adversary method, we prove $Ω\left(\max\left\{ζ\sqrt{(N-M)(M+Δ)}/Δ,\sqrt{ζN/Δ}\right\}\right)$. The same parameter dependence follows from the polynomial-method characterization of the two-layer symmetric function by Podder, Yao, and Ye. Our contribution is a multiplicative-adversary derivation that tracks the progress produced by individual oracle queries. For the first term, after complementing the input if necessary, we assume $M+Δ\le N-M$. We use the Hamming-layer subspaces from the eigenspace method of Ambainis, Spalek, and de Wolf and compose their adjacent-layer unitary maps to relate the two nonadjacent promise layers. After fixing the queried coordinate, the analysis block-diagonalizes into four-dimensional subspaces. An exact calculation of the one-query progress ratio gives the first lower bound. The same estimate also implies $\left\|(I-\widehatΠ_{\mathrm{bad}})\lvertΨ^T\rangle\right\|^2=O\left(T^2Δ^2/((N-M)(M+Δ))\right)$ for the coherent input superposition used in the adversary argument. For the second term, we prove directly using a three-eigenvalue multiplicative adversary that unique OR on $n$ bits with success probability $1/2+ζ$ requires $Ω(\sqrt{ζn})$ queries, and then reduce unique OR to the two-weight counting problem.
- Abstract（参考訳）: 量子近似カウントの2重決定バージョンについて検討する:$x\in\{0,1\}^N$ へのオラクルアクセスを与えられた場合、$|x|=M$ と $|x|=M+Δ$ と区別する。
乗法逆法を用いて、$Ω\left(\max\left\{'\sqrt{(N-M)(M+Δ)}/Δ,\sqrt{'N/Δ}\right\right)$を証明する。
同じパラメータ依存は、Podder, Yao, Ye による二層対称関数の多項式-メソッド特性から従う。
我々の貢献は、個々のオラクルクエリによって生成される進捗を追跡する乗法-逆微分である。
まず、必要であれば入力を補完した後、$M+Δ\le N-M$と仮定する。
我々は、アムバイニス、スパレック、デ・ウルフの固有空間法からハミング層部分空間を用いて、隣接層ユニタリ写像を構成し、2つの非隣接層を関連づける。
クエリされた座標を固定した後、解析ブロックは4次元の部分空間に分割する。
1-クエリの進行率の正確な計算は、第1の下位境界を与える。
同じ推定は、逆引数で使われるコヒーレントな入力重ね合わせに対して、$\left\|(I-\widehat _{\mathrm{bad}})\lverti^T\rangle\right\|^2=O\left(T^2Δ^2/((N-M)(M+Δ))\right)$も意味する。
第二項では、成功確率が 1/2 以上の$n$ ビット上の一意ORが$Ω(\sqrt{an})$クエリを必要とする3固有値乗法逆数を用いて直接証明し、2重カウント問題に一意ORを還元する。
関連論文リスト
- Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。
我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
論文 参考訳（メタデータ） (2026-03-20T01:53:44Z) - Diffusion Computation versus Quantum Computation: A Comparative Model for Order Finding and Factoring [0.0]
本稿では,有限グラフ上の拡散過程にのみアクセス可能な,整数分解のハイブリッド計算モデルについて検討する。
Shor のアルゴリズムとの比較は,概念的およびモデルベースである。
デジタルステップと拡散ステップの2つのコスト尺度で複雑性を報告する。
論文 参考訳（メタデータ） (2026-01-05T19:45:38Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems [8.0153031008486]
有限和共役方程式 $Gx = 0$ を解くために, 分散還元を伴う高速クラスクラスKrasnoselkii-Mann 法を提案する。
我々のアルゴリズムは単一ループであり、より広範なルートフィンディングアルゴリズムのために特別に設計された、偏りのない分散還元推定器の新たなファミリーを利用する。
数値実験は我々のアルゴリズムを検証し、最先端の手法と比較して有望な性能を示す。
論文 参考訳（メタデータ） (2024-06-04T15:23:29Z) - Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams [34.7582575446942]
準多項式依存のMDSに対する最初の近似アルゴリズムをDeltaに与える。
本アルゴリズムは,シェラリ・アダムスLPの条件付きラウンドリングの幾何学的認識に基づく新しい解析法である。
論文 参考訳（メタデータ） (2023-11-29T17:42:05Z) - Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。
我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。
新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
論文 参考訳（メタデータ） (2023-04-04T04:32:29Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。