論文の概要: Strong Selective and List-Decoding Direct Product Theorems for Quantum Query Complexity
- arxiv url: http://arxiv.org/abs/2609.26678v2
- Date: Wed, 30 Sep 2026 17:08:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-02 04:51:24.272884
- Title: Strong Selective and List-Decoding Direct Product Theorems for Quantum Query Complexity
- Title（参考訳）: 量子クエリ複雑性のための強選択型およびリスト復号型直積定理
- Abstract要約: 特定の函数に対する量子強直積定理は、20年近く前から知られている。
強いリスト復号直積定理は、乗法的逆数の特別な場合によって示唆される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum strong direct-product theorems for specific functions have been known for nearly two decades. These have been extended to general results for function computation and state generation. The proofs of these results use a version of the multiplicative adversary method that does not naturally extend to relations. Standard strong direct-product theorems apply when algorithms must correctly answer every given question. Prior work extended them to equivalent threshold direct-product theorems, which require answers to all questions but only require that most answers are correct. We focus on two further generalizations. Strong selective direct-products apply to algorithms that adaptively choose, based on what they learn from queries, which questions from a large list to answer. This generalization is relational and useful for proving time-space tradeoffs. We prove a quantum strong selective direct-product theorem for all functions using a relational formulation of the multiplicative adversary method by Jeffery and Zur which we prove, via an equivalent formulation, satisfies a strong selective direct product property and captures any query lower bound for functions proven by negative-weights adversaries. The second generalization is list-decoding direct product problems introduced by Ben-David and Blais for classical query complexity. These allow an algorithm to produce a large list of possible output vectors such that one of them is fully correct. They proved that such theorems hold for randomized complexity of all Boolean functions. We prove a quantum analogue of this theorem for all partial Boolean-valued functions. We show that strong list-decoding direct-product theorems are implied by a special case of multiplicative adversaries which we show, via a new reduction, can be obtained from negative-weights adversaries for any Boolean-valued function.
- Abstract（参考訳）: 特定の函数に対する量子強直積定理は、20年近く前から知られている。
これらは関数計算と状態生成の一般的な結果に拡張されている。
これらの結果の証明は、自然に関係に拡張しない乗法逆法のバージョンを使用する。
標準的な強い直積定理は、アルゴリズムが与えられた全ての質問に正しく答えなければならないときに適用される。
以前の研究は、全ての質問に対する答えを必要とするが、ほとんどの答えが正しいことを要求するような、等価なしきい値の直接積定理にまで拡張した。
我々はさらに2つの一般化に焦点を当てる。
強い選択的な直接生成物は、クエリから何を学ぶかに基づいて、適応的に選択するアルゴリズムに適用される。
この一般化はリレーショナルであり、時間空間のトレードオフを証明するのに有用である。
我々は、Jeffery と Zur による乗法逆法のリレーショナル定式化を用いて、すべての函数に対する量子強選択的直積定理を証明し、同値な定式化により、強い選択的直積特性を満足し、負重みの逆元によって証明される関数に対する下界のクエリを捕捉する。
第二の一般化は、古典的なクエリ複雑性のためにBen-DavidとBlaisによって導入されたリスト復号直積問題である。
これにより、アルゴリズムは可能な出力ベクトルの膨大なリストを生成でき、そのうちの1つは完全に正しい。
彼らはそのような定理がすべてのブール函数のランダム化複雑性に成り立つことを証明した。
すべての部分ブール値関数に対して、この定理の量子類似性を証明する。
強リスト復号直積定理は、新しい還元によって、ブール値関数の負重みの逆数から得られるような乗法的逆数の特別な場合によって暗示されることを示す。
関連論文リスト
- Yanasse: Finding New Proofs from Deep Vision's Analogies, Part 1 [51.56484100374058]
システムはマドリブの27の上位領域の戦術的利用分布を抽出する。
zスコアを計算して、ソースエリアで多用されるが、ターゲットエリアで稀または欠落している戦術を特定する。
これは、GPUアクセラレーションされたNPハードアナログを用いて、ソースとターゲットの証明状態と一致する。
論文 参考訳（メタデータ） (2026-04-19T03:27:16Z) - Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order [0.8192907805418583]
計算モデルは一般に、操作が一定の順序で適用されると仮定する。
近年、固定因果構造を持たない計算を考慮し、この仮定を緩和する研究がいくつか行われている。
正確なクエリの複雑さの分離は、今のところ発見されていない。
論文 参考訳（メタデータ） (2025-06-05T16:00:36Z) - ATG: Benchmarking Automated Theorem Generation for Generative Language Models [83.93978859348313]
人間はより広範に複雑な数学的結果を探求するために新しい定理を開発することができる。
現在の生成言語モデル(LM)は、定理の自動証明において著しく改善されている。
本稿では,エージェントが価値ある(あるいは新しい)定理を自動生成できるかどうかを評価する自動定理生成ベンチマークを提案する。
論文 参考訳（メタデータ） (2024-05-05T02:06:37Z) - Beyond Operator Systems [0.0]
作用素系は作用素代数、自由半代数幾何学、量子情報理論を結合する。
この研究において、作用素系とその定理の多くを一般化する。
論文 参考訳（メタデータ） (2023-12-21T16:16:27Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Neural Unification for Logic Reasoning over Natural Language [0.28675177318965034]
自動定理証明(Automated Theorem Proving)は、いくつかの予想(クエリ)が一連の公理(事実と規則)の論理的な結果であることを示すことができるコンピュータプログラムの開発を扱う。
近年のアプローチでは、自然言語(英語)で表される公理の予想を導出するトランスフォーマーに基づくアーキテクチャが提案されている。
本研究は, 一般化の項における最先端結果を実現するニューラルユニファイザという, 新たなアーキテクチャを提案する。
論文 参考訳（メタデータ） (2021-09-17T10:48:39Z) - multiPRover: Generating Multiple Proofs for Improved Interpretability in
Rule Reasoning [73.09791959325204]
我々は、自然言語の事実と規則の形で明示的な知識を推論することを目的としている言語形式推論の一種に焦点を当てる。
PRoverという名前の最近の研究は、質問に答え、答えを説明する証明グラフを生成することによって、そのような推論を行う。
本研究では,自然言語規則ベースの推論のために複数の証明グラフを生成するという,新たな課題に対処する。
論文 参考訳（メタデータ） (2021-06-02T17:58:35Z) - Deriving Theorems in Implicational Linear Logic, Declaratively [0.0]
命題直観主義線形論理の含意的断片において、与えられた大きさのすべての定理を生成する方法を示す。
応用として、線形論理定理証明器の正確性とスケーラビリティ試験のためのデータセットを生成し、定理証明問題に取り組むニューラルネットワークのトレーニングデータを生成する。
論文 参考訳（メタデータ） (2020-09-22T00:48:45Z) - Superposition for Lambda-Free Higher-Order Logic [62.997667081978825]
本稿では,意図的および拡張的クラス数$lambda$-free高階論理に対して,難解な完全重ね合わせ計算を導入する。
計算は完全単調でなくてもよい項順でパラメタ化され、$lambda$フリーの高次語彙パスとKnuth-Bendixの順序を使うことができる。
論文 参考訳（メタデータ） (2020-05-05T12:10:21Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。