論文の概要: Exact Quantum Query Complexity of the Five-Bit Symmetric Boolean Function $\Exact^5_{3,4}$
- arxiv url: http://arxiv.org/abs/2610.24518v1
- Date: Sat, 17 Oct 2026 07:28:45 GMT
- ステータス: 情報取得中
- システム内更新日: 2026-10-20 11:43:16.695956
- Title: Exact Quantum Query Complexity of the Five-Bit Symmetric Boolean Function $\Exact^5_{3,4}$
- Title（参考訳）: 5ビット対称ブール関数 $\Exact^5_{3,4}$ の特殊量子クエリ複雑性
- Abstract要約: 以前の数値研究では、3つのクエリを使って1つに近い成功確率が報告された。
本稿では (f) の正確な量子クエリ複雑性が (4) であることを証明する。
- 参考スコア（独自算出の注目度）: 4.531310738989808
- License:
- Abstract: Let \(f = \text{EXACT}^5_{3,4}\) be the Boolean function that equals 1 exactly on inputs of Hamming weight 3 or 4. Earlier numerical studies reported success probabilities close to one using three queries, but the existence of an exact three-query algorithm had remained unresolved. This paper settles this problem by proving that the exact quantum query complexity of \(f\) is \(4\). For the lower bound, we express every three-query algorithm through layer-by-layer Gram matrices of low-degree Fourier coefficients. We then construct a fixed rational dual certificate whose slack matrices are all positive definite. This certificate separates the necessary Gram-matrix region from the exact-output condition and therefore rules out every exact algorithm using at most three queries in the stated model. The positivity verification reduces to five small rational matrices and Sylvester's criterion. For the upper bound, we invoke the previously known four-query algorithm for the seven-bit function \(\text{EXACT}^7_{3,4}\) and apply the standard padding reduction. To quantify the near-exact behavior, we use the same certificate to derive a valid, though not claimed tight, lower bound \(\frac{25600}{43779488192449}>0\) on the worst-case error of every algorithm using at most three queries. This positive error gap is compatible with the near-unit success probabilities reported in earlier numerical studies, which do not establish exact computation.
- Abstract（参考訳）: f = \text{EXACT}^5_{3,4}\) をハミングウェイト 3 または 4 の入力に対してちょうど 1 に等しいブール函数とする。
以前の数値研究では、3つのクエリを使って1つに近い成功確率を報告したが、正確な3つのクエリーアルゴリズムの存在は未解決のままであった。
本論文は, 量子クエリの正確な複雑性が \(4\) であることを証明することによって, この問題を解決した。
低次フーリエ係数の層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・層・フーリエ係数による3つのアルゴリズムを表現する。
次に、スラック行列がすべて正定値である固定有理双対証明を構築する。
この証明書は、必要なグラム行列領域を正確な出力条件から切り離し、従って、記述されたモデルの少なくとも3つのクエリを使用して、全ての正確なアルゴリズムを規則化する。
正の検証は5つの小さな有理行列とシルヴェスターの基準に還元される。
上界に対しては、7ビット関数 \(\text{EXACT}^7_{3,4}\) に対して、既知の4クエリアルゴリズムを呼び出し、標準パディング還元を適用する。
ほぼ正確な振る舞いを定量化するために、我々は同じ証明を用いて、少なくとも3つのクエリを使用して、アルゴリズムの最悪のエラーに対して、厳密で低い境界 \(\frac{25600}{43779488192449}>0\) を主張していないが、有効な証明を導出する。
この正の誤差ギャップは、正確な計算が確立されていない初期の数値研究で報告された準単位成功確率と互換性がある。
関連論文リスト
- Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Fast exact recovery of noisy matrix from few entries: the infinity norm approach [0.0]
データサイエンスの中心的な問題である行列回復問題は、比較的小さなエントリのサンプルから行列A$を回収することである。
そのようなタスクは一般には不可能であるが、ランダムなエントリのサブセットから正確な時間で$A$を高い確率で回収できることが示されている。
基底行列が有界な精度を持つことを考えると、雑音の場合においても正確な回復が達成できることが示される。
論文 参考訳（メタデータ） (2025-01-31T15:31:01Z) - Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems [2.3721580767877257]
提案手法は,非強弱畳み込みミニマックス問題の解法である。
提案アルゴリズムは$tell内の上位定常点であることが証明された。
エル
$.
$.
$.
$.
$.
$.
$.
$.
$.
$.
$.
$.
$.
$.
$.
$.
$
論文 参考訳（メタデータ） (2024-11-24T09:46:36Z) - A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems [7.986462867854411]
凸凹極小最適化問題の解法として,Lipschitz-free Cubal regularization (LF-CR)アルゴリズムを提案する。
また,この問題のパラメータを必要としない完全パラメータフリー立方正則化(FF-CR)アルゴリズムを提案する。
我々の知る限りでは、FF-CRアルゴリズムは完全にパラメータフリーの2次アルゴリズムである。
論文 参考訳（メタデータ） (2024-07-04T01:46:07Z) - An efficient algorithm for the $\ell_{p}$ norm based metric nearness
problem [4.700135257490953]
本稿では, 半平滑なニュートン型近位拡張ラグランジアン法(PALM)で解いた各サブプロブレムを用いた遅延制約生成法を提案する。
我々のアルゴリズムの喜ばしい側面は、最大108ドルの変数と1013ドルの制約を含むこれらの問題を解決することができることである。
論文 参考訳（メタデータ） (2022-11-02T16:29:05Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。