論文の概要: Quantum-Classical Equivalence for AND-Functions

• arxiv url: http://arxiv.org/abs/2606.03249v1
• Date: Tue, 02 Jun 2026 07:10:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-03 22:00:04.826939
• Title: Quantum-Classical Equivalence for AND-Functions
• Title（参考訳）: and-functionに対する量子古典的等価性
• Authors: Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett,
• Abstract要約: 量子通信複雑性の大きな問題は、量子プロトコルが古典的プロトコルよりも指数関数的に効率的であるかどうかである。 各ブール関数$f$に対して、有界エラー量子および古典的通信複雑性は決定論的に関連していることを示す。
• 参考スコア（独自算出の注目度）: 4.0075720392218335
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form $$ F(x,y) = f(x_1 \land y_1, \ldots, x_n \land y_n), $$ when the outer function $f$ is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors. In this work, we settle this problem in a strong way. We show that for every Boolean function $f$, the bounded-error quantum and classical deterministic communication complexities of the function $f \circ \mathrm{AND}_2$ are polynomially related, up to polylogarithmic factors in $n$. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of $f$. Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.
• Abstract（参考訳）: 量子通信複雑性の大きな問題は、量子プロトコルが全ブール関数を計算するための古典的プロトコルよりも指数関数的に効率的であるかどうかである。 F(x,y) = f(x_1 \land y_1, \ldots, x_n \land y_n), $$ は外函数 $f$ が対称であるときに、その有界な量子と古典的な通信複雑性が多項式的に関連していることを証明する。 それ以来、この結果を全ての AND-函数に拡張し続け、いくつかの著者によって提案されている。 本研究では,この問題を強固な方法で解決する。 任意のブール関数 $f$ に対して、関数 $f \circ \mathrm{AND}_2$ の有界エラー量子および古典的決定論的通信複雑性は、$n$ の多対数因子まで多項式関係であることが示される。 このことは、ド・モーガン空間の対数$f$で、多項式損失の最大値を示すことによって証明する。 この結果はChattopadhyay, Dahiya, Lovett (2025) の非スパースブール関数の構造的特徴に基づくものである。

関連論文リスト

• DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians [20.990700912031773]
  正規化トレース 2-nTr[f(A)]$ を対数局所ハミルトニアン$A$ で$n$ qubits に作用させることの計算複雑性について検討する。 この問題は自然に DQC1 モデルで生じるが、その複雑性は限定された函数のクラス$f(x)$に対してのみ理解される。 f(x)$ が近似次数 $(rm poly(n))$ の連続関数であれば、2-nTr[f(A)]$ を定数加法誤差まで見積もる。
  論文  参考訳（メタデータ） (2026-04-02T01:15:12Z)
• Quantum oracles for the finite element method [45.200826131319815]
  本研究では,N倍の剛性および質量行列のブロックエンコーディングに使用されるオラクルの実装に必要な量子ルーチンについて検討した。 本稿では, 要素幾何学, 平方根の計算, 条件演算の実装など, 必要なオラクルを構築する方法を示す。
  論文  参考訳（メタデータ） (2025-04-28T14:28:31Z)
• Quantum computational complexity of matrix functions [2.7488316163114823]
  2つの原始問題の計算複雑性について検討する。 単項関数、チェビシェフ関数、時間発展関数、逆関数の4つの関数を考える。 各関数に対する両問題のBQP完全形式を同定する。
  論文  参考訳（メタデータ） (2024-10-17T18:00:03Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• A one-query lower bound for unitary synthesis and breaking quantum cryptography [7.705803563459633]
  ユニタリ合成問題では、任意の$n$qubitのユニタリ$U$を、任意のブール関数$f$を計算するオラクルで拡張された効率的な量子$A$で実装できるかどうかを問う。 本研究は, 対向する$Af$の最大成功確率を解析することにより, 下位境界の証明を可能にする, 効率的なチャレンジャーアドゲームとしてのユニタリ合成を証明する。
  論文  参考訳（メタデータ） (2023-10-13T05:39:42Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Exponential quantum communication reductions from generalizations of the Boolean Hidden Matching problem [0.05076419064097732]
  指数的古典量子通信分離を示す一方向モデルにおける最初の通信問題 効率的な通信プロトコルは、$f$の符号度に応じて提示される。
  論文  参考訳（メタデータ） (2020-01-15T21:05:32Z)

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

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