論文の概要: Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem

• arxiv url: http://arxiv.org/abs/2610.06789v1
• Date: Mon, 05 Oct 2026 17:48:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 22:48:40.59257
• Title: Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem
• Title（参考訳）: ブール隠れマッチング問題の一般化のための量子アドバンテージのキャラクタリゼーション
• Abstract要約: 本稿では,$f$-Boolean Hidden 分割問題の一方的な通信複雑性について検討する。 古典的および量子的通信境界を$f$-Boolean Hidden Partitionに対して確立する。
• 参考スコア（独自算出の注目度）: 5.457853441330696
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the one-way communication complexity of the $f$-Boolean Hidden Partition problem. Here, Alice is given an $n$-bit string and Bob is given $Ω(n)$ disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of $f$ on these blocks either agree with all of the labels or disagree with all of them, Bob must determine which is the case using a single message from Alice. This problem generalizes the Boolean Hidden Matching and Hidden Hypermatching problems, which capture the special case where $f$ is the parity function. We establish classical and quantum communication bounds for $f$-Boolean Hidden Partition in terms of the sign degree $d$ of $f$, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when $d \le 1$ and quantum protocols when $d \le 2$, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every $f$ of sign degree $d \ge 2$, the randomized classical communication complexity of this problem is $Θ(n^{1-1/d})$ while its quantum communication complexity lies between $Ω(n^{1-2/d})$ and $\bO{n^{1-1/\lceil d/2 \rceil} \log n}$. This completely characterizes the functions $f$ admitting polynomial quantum advantage as those for which $d \ge 2$, with a new infinite family of exponential separations given by the case $d = 2$.
• Abstract（参考訳）: 本稿では,$f$-Boolean Hidden 分割問題の一方的な通信複雑性について検討する。 ここで、アリスは$n$-ビットの文字列を与えられ、ボブはラベルの列と共にインデックスの$Ω(n)$不随行ブロックを与えられる。 これらのブロックに対する$f$の評価がすべてのラベルと一致しているか、あるいはすべてのラベルと一致しないという約束の下で、Bob氏はAliceの1つのメッセージを使ってどれがケースであるかを判断しなければならない。 この問題はブール・ハイデンマッチングとハイデン・ハイパーマッチングの問題を一般化し、$f$がパリティ関数である特別なケースを捉える。 我々は、ドル===================================================================================================================================================================================================================。 彼らの以前の研究は、$d \le 1$のときの古典的プロトコルと$d \le 2$のときの量子プロトコルの対数的通信上界と、より大きい符号次数を持つある構造化函数の多項式下界を与えた。 符号次数$d \ge 2$のすべての$f$に対して、この問題のランダム化された古典的通信複雑性は$(n^{1-1/d})$であり、その量子的通信複雑性は$Ω(n^{1-2/d})$と$\bO{n^{1-1/\lceil d/2 \rceil} \log n}$の間にある。 これは、$d \ge 2$ の多項式量子優位性を認める函数 $f$ を、$d = 2$ の場合に与えられる新しい無限の指数的分離族を持つ函数として完全に特徴づける。

関連論文リスト

• Quantum Search With Generalized Wildcards [0.4310167974376404]
  我々は、コスト$O(sqrtn log n)$の量子アルゴリズムと、ほぼ一致する$Omega(sqrtn)$の低い境界を示す。 以下に示すように、$calQ$が有界サイズセット、連続ブロック、プレフィックス、フルセットのみである場合に、ほぼタイトなバウンダリを表示する。
  論文  参考訳（メタデータ） (2025-11-06T18:55:05Z)
• Magic and communication complexity [0.6533091401094101]
  量子回路におけるマジックと通信複雑性の間の新しい接続を確立する。 低魔法で計算可能な関数は通信コストが低いことを示す。
  論文  参考訳（メタデータ） (2025-10-08T17:14:25Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
  2つの単調素関数 $f:0,1n to 0,1$ と $g:0,1n to 0,1$ が与えられたとき、双対化問題は$g$が$f$の双対かどうかを決定することである。 本稿では,双対化問題の決定版を時間内に解く量子コンピューティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-08-28T18:12:54Z)
• Matching upper bounds on symmetric predicates in quantum communication complexity [0.0]
  共役共役が許されるとき、f circ G = f(G)mathrmQCC_mathrmE(G)) という形の関数の量子通信複雑性に焦点を当てる。 我々は,同じ文が共用絡み合いを持たないことを示し,その結果を一般化する。
  論文  参考訳（メタデータ） (2023-01-01T08:30:35Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• 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)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)
• Exponential quantum communication reductions from generalizations of the Boolean Hidden Matching problem [0.05076419064097732]
  指数的古典量子通信分離を示す一方向モデルにおける最初の通信問題 効率的な通信プロトコルは、$f$の符号度に応じて提示される。
  論文  参考訳（メタデータ） (2020-01-15T21:05:32Z)

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

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