論文の概要: Distributional Variants of the Aaronson-Ambainis Conjecture
- arxiv url: http://arxiv.org/abs/2609.35327v1
- Date: Mon, 28 Sep 2026 14:52:32 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-02 06:28:53.380873
- Title: Distributional Variants of the Aaronson-Ambainis Conjecture
- Title（参考訳）: アーロンソン-アンバイニス対流の分布変数
- Abstract要約: 均一な入力分布の下では、量子クエリアルゴリズムは古典的なアルゴリズムでシミュレートできる。
すべての固定$p inに対して、$_p$分布の下での量子クエリアルゴリズムは予想を許容し、同じが予想均一分布の下で成り立つ場合に限ることを示す。
アーロンソン・アンバイニス予想(アーロンソン・アンバイニスげん、英: Aaronson-Ambainis conjecture)は、この予想を示唆する強い言明であり、ハイパーキューブ上の有界な低次数で定式化されている。
- 参考スコア（独自算出の注目度）: 1.2366208723499545
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query algorithms. More precisely, the acceptance probability of any quantum query algorithm can be approximated, on average over uniformly random inputs, by a classical query algorithm, with only polynomial query overhead. The conjecture is central to understanding whether exponential quantum advantages for decision problems necessarily rely on additional structure. We study analogues of this conjecture under other natural input distributions and prove that they are all equivalent to the original uniform-distribution conjecture. We first consider the product distribution $μ_p$, where the input bits are independent Bernoulli variables with fixed bias $p$. We show that for every fixed $p \in (0, 1)$, quantum query algorithms under the $μ_p$ distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution $ν_p$ that is uniform over the slice of strings with Hamming weight $\lfloor pn \rfloor$ and prove a similar equivalence for the $ν_p$ distribution and the uniform distribution. The Aaronson-Ambainis conjecture is a stronger statement that implies the above-mentioned conjecture and is formulated in terms of bounded low-degree polynomials on the Boolean hypercube. It asserts that under the uniform distribution, any such polynomial with nonnegligible variance must have an influential variable. We formulate analogues of this conjecture, where the underlying distribution is a biased product distribution or a uniform distribution over a slice, and prove that all these variants are equivalent to the original Aaronson-Ambainis conjecture.
- Abstract（参考訳）: 量子複雑性理論における長年の予想は、均一な入力分布の下では、量子クエリアルゴリズムは古典的なクエリアルゴリズムによって多項式的にシミュレートできると主張している。
より正確には、任意の量子クエリアルゴリズムの受理確率は、多項式クエリオーバーヘッドのみを持つ古典的なクエリアルゴリズムによって、一様ランダムな入力に対して平均で近似することができる。
この予想は、決定問題に対する指数量子的優位性が必然的に追加構造に依存しているかどうかを理解するための中心である。
我々は、この予想の類似を他の自然な入力分布の下で研究し、これら全てが元の一様分布予想と同値であることを証明した。
まず、入出力ビットが固定バイアス$p$を持つ独立ベルヌーイ変数であるような積分布を$μ_p$とみなす。
固定された$p \in (0, 1)$に対して、$μ_p$分布の量子クエリアルゴリズムは多項式オーバーヘッド古典シミュレーションを許容する。
第二に、ハミング重み $\lfloor pn \rfloor$ の弦のスライス上で一様である分布 $ν_p$ を考え、$ν_p$ の分布と一様分布の同値性を証明する。
アーロンソン・アンバイニス予想(アーロンソン・アンバイニスげん、英: Aaronson-Ambainis conjecture)は、上記の予想を示唆する強い主張であり、ブールハイパーキューブ上の有界な低次多項式で定式化されている。
均一分布の下では、非無視的分散を持つ任意の多項式は、影響のある変数を持つ必要があると主張する。
この予想の類似式を定式化し、基礎となる分布は偏りのある積分布あるいはスライス上の一様分布であり、これらすべての変種が元のアーロンソン・アンバイニス予想と同値であることを証明する。
関連論文リスト
- On the SoS Certifiability of Log-Concave Distributions [51.56484100374058]
圏 $(Cm)m|v|m - mathbbE_Xsim Plangle X,vranglem$ は、すべての偶数 mge2$ に対する平方の和であり、$C>0$ は普遍定数である。
これにより、コタリとシュタインハルト(arXiv:1711.07465)の定理におけるポアンカレ定数への依存を排除し、対数凹面分布の最適モーメント境界を回復する。
論文 参考訳（メタデータ） (2026-09-24T16:48:02Z) - Robustness of Hidden-Variable Theories and Matrix Scaling [11.387099057151142]
量子基底と複雑性理論に動機づけられたアーロンソンは、シュルディンガーの提案に触発された隠れ変数理論を定式化した。
任意の量子状態とユニタリに対して、このシュルディンガー理論はシンクホーンアルゴリズムを介して合同確率分布を割り当てる。
我々は、指数的に近い純粋状態と2つのユニタリを構築するが、シュルディンガー理論によって割り当てられた合同確率分布は、少なくとも1つのエントリーにおける逆線型項と、全変動距離における定数によって異なる。
論文 参考訳（メタデータ） (2026-09-13T13:50:19Z) - All you need is log [0.42671348654734564]
次数 $in[0,infty]$ の Rényi の発散は、データ処理および独立製品への添加物の下でのユニークな族単調であることを示す。
多くの問題は一度に2つ以上の分布を比較する - マルチポピュレーションフェアネス、マルチプライオリPAC-Bayes境界、マルチヒポテシステスト。
レニイ族の右多分布一般化は開問題である。
論文 参考訳（メタデータ） (2026-06-25T17:54:49Z) - On the Complexity Theory of Masked Discrete Diffusion: From $\mathrm{poly}(1/ε)$ to Nearly $ε$-Free [49.34727933066799]
マスク付き離散拡散(マスク付き離散拡散)は、トークンが識別される前に特別なマスクシンボルによって劣化するテキスト生成のフレキシブルパラダイムである。
その結果,Eulerサンプルは,$tildeO(d2epsilon-3/2)$離散スコア評価で,総変量(TV)の$epsilon$-精度を達成できることが判明した。
そこで我々は,有界スコアの仮定を取り除き,偏りのない離散スコア近似を保ったMask-Aware Truncated Uniformization (MATU) アプローチを提案する。
論文 参考訳（メタデータ） (2025-09-26T03:50:17Z) - Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph [45.975805184376036]
局所的な差分プライバシーを満足するアルゴリズムを記述し、個人に対して$tildeO(k3/2)$非適応クエリを実行する。
また、Scheff'eグラフをダブする新しいオブジェクトを導入し、$Q$の分散間の差の構造をキャプチャする。
論文 参考訳（メタデータ） (2025-09-19T17:41:15Z) - Clustering Mixtures of Bounded Covariance Distributions Under Optimal
Separation [44.25945344950543]
境界共分散分布の混合に対するクラスタリング問題について検討する。
このクラスタリングタスクに対して,最初のポリ時間アルゴリズムを提案する。
我々のアルゴリズムは、対数外乱の$Omega(alpha)$-fractionに対して堅牢である。
論文 参考訳（メタデータ） (2023-12-19T01:01:53Z) - Matrix majorization in large samples [9.421843976231372]
あるモノトンが2つの間に厳密に順序づけられている場合、入力分布の$n$fold Kroneckerパワーを出力分布の$n$foldパワーに取る行列が存在することを示す。
このような触媒マトリックスの偏極化に必要かつ十分な条件が見つかる。
論文 参考訳（メタデータ） (2023-01-18T07:52:19Z) - Influence in Completely Bounded Block-multilinear Forms and Classical
Simulation of Quantum Algorithms [3.9156637371363874]
Aaronson-Ambainis予想を証明する(Theory of Computing '14)
すべての完全有界次数-$d$ブロック-多重線型形式において、常に影響が少なくとも1/mathrmpoly(d)$の変数が存在する。
我々は、量子アルゴリズムの特定のクラスに対する効率的な古典的ほぼすべてのところのシミュレーションを得る。
論文 参考訳（メタデータ） (2022-03-01T03:42:24Z) - Leveraged Matrix Completion with Noise [84.20092979053119]
未知の$ntimes n$ matrix of rank $r$ from just $mathcalO(nrlog2 (n))$ entry.
我々の証明は、ゴルフスキームに基づく十分な最適条件を記述する新しいアプローチによって支持されている。
論文 参考訳（メタデータ） (2020-11-11T16:25:45Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。