論文の概要: Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions
- arxiv url: http://arxiv.org/abs/2611.09809v1
- Date: Fri, 06 Nov 2026 17:58:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-10 12:00:36.752334
- Title: Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions
- Title(参考訳): n/2$Thresholdを超える:ハミングウェイトと対称性関数を計算するための量子クエリ複雑性
- Abstract要約: oracle-interrogationアルゴリズムは、$n/2+O(sqrt n)$量子クエリを使って、有界誤差を持つすべての$n$ビットブール関数を計算する。
parityは$lceil n/2rceil$クエリを使って正確に計算できるが、単一のBoolean出力に対して$n/2$を超える追加のオーバーヘッドが必要かどうかは未定である。
- 参考スコア(独自算出の注目度): 66.4427591916051
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The oracle-interrogation algorithm [van Dam, FOCS '98] computes every $n$-bit Boolean function with bounded error using $n/2+O(\sqrt n)$ quantum queries. In contrast, parity can be computed exactly using $\lceil n/2\rceil$ queries, but whether an additive overhead beyond $n/2$ is necessary for a single Boolean output has remained open. In this work, we construct an explicit family of symmetric Boolean functions requiring $n/2+Ω(n^{1/3})$ quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using $n/2+O(n^{1/3})$ quantum queries with bounded error, and therefore computes every symmetric Boolean function within the same query bound. Together, these results determine the optimal additive order for Hamming weight recovery and for the worst case over symmetric Boolean functions at sufficiently small constant error.
- Abstract(参考訳): オラクル-インターロゲーションアルゴリズム[van Dam, FOCS '98]は、$n/2+O(\sqrt n)$量子クエリを使って、有界誤差を持つすべての$n$ビットブール関数を計算する。
対照的に、parityは$\lceil n/2\rceil$クエリを使って正確に計算できるが、単一のBoolean出力に対して$n/2$を超える加算オーバーヘッドが必要かどうかはまだ未定である。
本研究では、固定正定値誤差で$n/2+Ω(n^{1/3})$量子クエリを必要とする対称ブール関数の明示的な族を構築する。
また、有界誤差を持つ$n/2+O(n^{1/3})$量子クエリを用いて、正確なハミング重みを復元するアルゴリズムを与え、従って、同じクエリ境界内のすべての対称ブール関数を計算する。
これらの結果は、ハミング重み回復のための最適加法順序と、対称ブール関数に対する最悪の場合を十分に小さな一定の誤差で決定する。
関連論文リスト
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity [0.0]
ブール関数全体の証明複雑性$C(f)$が、そのランダム化および量子化クエリの複雑さと比較してどれだけ大きいかを研究する。
同じ関数に対して、完全およびゼロエラー量子クエリ複雑度は、$widetilde O(sqrtC(F))$である。
論文 参考訳(メタデータ) (2026-09-10T15:04:28Z) - Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
メモリが$m$ の単位球上の$d$ 次元 1$-Lipschitz 凸関数を最小化する。
まず、そのようなアルゴリズムは、$tilde(fracd2sqrtm)$ Oracle queryを作らなければならないことを示す。
決定論的最適化アルゴリズムでは$tilde(mind1.6,fracd8/3m2/3)$クエリが必要である。
論文 参考訳(メタデータ) (2026-07-21T00:40:59Z) - Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。
フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文 参考訳(メタデータ) (2026-07-08T17:49:40Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳(メタデータ) (2024-01-17T18:59:38Z) - On the Fine-Grained Query Complexity of Symmetric Functions [4.956977275061968]
本稿では、Watrous予想のきめ細かいバージョンについて考察する。
確率が任意に1/2ドルに近いランダム化および量子化アルゴリズムを含む。
論文 参考訳(メタデータ) (2023-09-20T13:04:45Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳(メタデータ) (2022-12-03T02:45:23Z) - Exact quantum query complexity of computing Hamming weight modulo powers
of two and three [2.1349209400003932]
この問題の正確な量子クエリ複雑性は、$leftlceil n (1 − 1/m) rightil$であることを示す。
上界は、主成分がよく知られた1-クエリ量子アルゴリズムである反復クエリアルゴリズムによって構成される。
論文 参考訳(メタデータ) (2021-12-29T17:57:41Z) - Testing Boolean Functions Properties [1.5924410290166868]
関数のプロパティテストの分野での目標は、与えられたブラックボックスのブール関数が特定のプロパティを持っているか、あるいはそのプロパティが持たない$varepsilon$-farであるかどうかを決定することである。
ここでは、Deutsch-Jozsaアルゴリズムを用いてブール関数(同一性、相関、平衡性)のテストを行ういくつかの性質について検討する。
論文 参考訳(メタデータ) (2021-09-14T15:27:38Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。