論文の概要: Quantum Query Complexity and Span Programs from Pre-Geometry

• arxiv url: http://arxiv.org/abs/2610.03914v1
• Date: Fri, 02 Oct 2026 18:25:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-13 04:28:07.076724
• Title: Quantum Query Complexity and Span Programs from Pre-Geometry
• Title（参考訳）: プリジオメトリによる量子クエリ複雑度とスパンプログラム
• Abstract要約: Spanプログラムは、量子クエリアルゴリズムを設計するための一般的な方法を提供する。 本研究では,クエリ問題によって決定される依存データと,スパンプログラムによって選択される依存構造とを分離する,この最適化のマトロイド構造を開発する。
• 参考スコア（独自算出の注目度）: 0.8668211481067458
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Span programs provide a general method for designing quantum query algorithms, and for Boolean coordinate queries their optimum cost agrees with the general adversary bound. We develop a matroidal organization of this optimization that separates dependence data determined by the query problem from the dependence structure chosen by a span program. The resulting source matroid records query dependence, target determination, and separation data, while a program matroid records dependencies among the target and response-labeled input elements of a candidate program. When a query problem admits a source matroid, we use its structure to organize adversary upper and lower bounds. For separating binary query sets in this setting, the global matroid-span-program optimum equals $\mathrm{Adv}^{\pm}_{\mathcal Q}(f)$. For a fixed regular program matroid, projective uniqueness reduces optimization over real representations to positive element weights. We express positive and negative costs as weighted basis ratios and derive exact $1$-, $2$-, and $3$-sum reductions, giving a compositional evaluation of the fixed-weight objective along a Seymour decomposition. For pointed $R_{10}$ closure, exact certificates give $3.9087553<\mathrm{Adv}^{\pm}_{\mathcal Q_R}(f_R)<3.9301$. The natural $R_{10}$ program has optimized cost $5$, while another regular program has cost at most $\sqrt{87/5}$. Recursive self-composition yields a family on $N$ input bits with randomized query complexity $Ω(N^{0.7324867\ldots})$, an explicit quantum algorithm using $O(N^{0.6500178\ldots})$ queries, and $Q(F)=Θ(N^α)$ for $0.6204277\ldots<α<0.6229063\ldots$.
• Abstract（参考訳）: Spanプログラムは、量子クエリアルゴリズムを設計するための一般的な方法を提供し、Boolean座標クエリの場合、それらの最適コストは、一般的な逆境と一致する。 本研究では,クエリ問題によって決定される依存データと,スパンプログラムによって選択される依存構造とを分離する,この最適化のマトロイド構造を開発する。 得られたソースマトロイドは、クエリ依存、ターゲット決定、分離データを記録し、プログラムマトロイドは、候補プログラムのターゲットおよびレスポンスラベルされた入力要素間の依存関係を記録する。 問合せ問題にソース・マトロイドが認められると、その構造を用いて逆上界と下界を整理する。 この設定でバイナリクエリセットを分離するために、グローバルなマトロイド・スパン・プログラム最適化は$\mathrm{Adv}^{\pm}_{\mathcal Q}(f)$に等しい。 固定正則プログラムマトロイドの場合、射影的一意性は実表現の最適化を正の要素重みに還元する。 我々は,重み付き基底比として正負のコストを表現し,厳密な1ドル,2ドル,3ドルの削減を導出する。 R_{10}$クロージャの場合、正確な証明書は$3.9087553<\mathrm{Adv}^{\pm}_{\mathcal Q_R}(f_R)<3.9301$である。 自然な$R_{10}$プログラムは5ドルを最適化し、他の通常のプログラムは最大$\sqrt{87/5}$を最適化した。 帰納的自己合成は、ランダムなクエリ複雑性を持つ$N$入力ビット上の族を$Ω(N^{0.7324867\ldots})$、$O(N^{0.6500178\ldots})$クエリと$Q(F) = (N^α)$ for $0.6204277\ldots<α<0.6229063\ldots$とする明示的な量子アルゴリズムである。

関連論文リスト

• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• Rand-SEMI-QAOA: Finite-Budget Depth-One MaxCut Ensembles on Compressed Quantum Registers [0.0]
  Rand-SEMI-QAOA は MaxCut の有限予算 QRAO-QAOA アンサンブルである。 このメソッドは、製品$X$ファミリから置き換えることなく、ラベルを均一にサンプリングする。 正確なゲージの恒等式は、積族ラベルが QRAO ハミルトニアンの軌道を生成することを示している。
  論文  参考訳（メタデータ） (2026-08-16T09:47:55Z)
• Learning Decision-Sufficient Representations for Linear Optimization [2.867517731896504]
  Bennounaらによる最近の研究は、本質的な決定関連次元$dstar$を通じて十分な決定データセット(SDD)の正確な幾何学的特徴を提供する。 我々は、$dstar$がNPハードであることを示し、データセットがグローバルに十分かどうかを判断することがコNPハードであることを示す硬度結果を確立する。 本稿では,決定関連方向をサンプル間で集約し,最大$dstar$で安定な圧縮スキームを生成する累積アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-03-19T07:07:48Z)
• Quantum Algorithms for Projection-Free Sparse Convex Optimization [32.34794896079469]
  ベクトル領域に対しては、$O(sqrtd/varepsilon)$のクエリ複雑性を持つ$varepsilon$-optimal解を求めるスパース制約に対する2つの量子アルゴリズムを提案する。 行列領域に対しては、時間複雑性を$tildeO(rd/varepsilon2)$と$tildeO(sqrtrd/varepsilon3)$に改善する2つの核ノルム制約の量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-11T12:43:58Z)
• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。 本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。 我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
  論文  参考訳（メタデータ） (2024-08-27T18:28:31Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。 3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。 我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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