論文の概要: Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order

• arxiv url: http://arxiv.org/abs/2506.05187v1
• Date: Thu, 05 Jun 2025 16:00:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-06 21:53:49.804024
• Title: Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
• Title（参考訳）: 不定因数順序の下でのブール関数の古典的および量子的クエリ複雑性
• Authors: Alastair A. Abbott, Mehdi Mhalla, Pierre Pocreau,
• Abstract要約: 計算モデルは一般に、操作が一定の順序で適用されると仮定する。 近年、固定因果構造を持たない計算を考慮し、この仮定を緩和する研究がいくつか行われている。 正確なクエリの複雑さの分離は、今のところ発見されていない。
• 参考スコア（独自算出の注目度）: 0.8192907805418583
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Computational models typically assume that operations are applied in a fixed sequential order. In recent years several works have looked at relaxing this assumption, considering computations without any fixed causal structure and showing that such ''causally indefinite'' computations can provide advantages in various tasks. Recently, the quantum query complexity of Boolean functions has been used as a tool to probe their computational power in a standard complexity theoretic framework, but no separation in exact query complexity has thus-far been found. In this paper, we investigate this problem starting with the simpler and fully classical notion of deterministic query complexity of Boolean functions, and using classical-deterministic processes -- which may exhibit causal indefiniteness -- as a generalised computational framework. We first show that the standard polynomial and certificate lower bounds of deterministic query complexity also hold in such generalised models. Then, we formulate a Boolean function for which causal indefiniteness permits a reduction in query complexity and show that this advantage can be amplified into a polynomial separation. Finally, with the insights gained in the classical-deterministic setting, we give a Boolean function whose quantum query complexity is reduced by causally indefinite computations.
• Abstract（参考訳）: 計算モデルは一般に、操作が一定の順序で適用されると仮定する。 近年では、固定因果構造を持たない計算を考慮し、そのような「因果不確定」計算が様々なタスクにおいて有利であることを示すなど、この仮定を緩和することを検討している。 近年、Boolean関数の量子クエリ複雑性は、標準的な複雑性理論フレームワークで計算パワーを探索するツールとして使われてきたが、正確なクエリ複雑性の分離は発見されていない。 本稿では,ブール関数の決定論的クエリ複雑性の単純で古典的な概念から始まり,因果不確定性を示す古典的決定論的プロセスを一般化された計算フレームワークとして利用することから,この問題を考察する。 まず、標準的な多項式と証明値の低い決定論的クエリ複雑性が、そのような一般化されたモデルでも成り立つことを示す。 そして、因果不確定性がクエリの複雑さの低減を許容するブール関数を定式化し、この利点を多項式分離に増幅できることを示す。 最後に、古典的-決定論的設定で得られた知見により、因果不確定な計算によって量子クエリの複雑さが減少するブール関数を与える。

関連論文リスト

• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。 不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。 無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
  論文  参考訳（メタデータ） (2023-12-18T18:29:01Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Quantum Query Complexity of Boolean Functions under Indefinite Causal Order [0.9208007322096533]
  一般高次量子計算におけるブール関数の問合せ複雑性について検討する。 最近導入された因果順序の量子制御を持つ量子回路のクラスは、クエリの複雑さを減らすことは不可能である。 因果不確定なスーパーマップを利用する場合、2つのクエリで計算できる最小誤差が厳密に低い関数がいくつか見つかる。
  論文  参考訳（メタデータ） (2023-07-18T13:12:55Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。 アルファベットのサイズについては、定値対分離の複雑さがある。
  論文  参考訳（メタデータ） (2023-01-22T22:08:28Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)

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

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