論文の概要: Random Garbage Separates XOR from Forward-Only Queries

• arxiv url: http://arxiv.org/abs/2609.03628v2
• Date: Mon, 07 Sep 2026 13:27:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-09 14:43:41.884434
• Title: Random Garbage Separates XOR from Forward-Only Queries
• Title（参考訳）: Random GarbageがフォワードオンリークエリからXORを分離
• Authors: Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray,
• Abstract要約: 我々は、標準XORインタフェースと2つのフォワードオンリーインタフェースとの間に指数関数的な量子クエリ分離を与える。 結果として得られる問題は、最大$n+2$の標準XORクエリで解決可能であるが、クエリの複雑さを前方から評価する$(sqrt N)$がある。
• 参考スコア（独自算出の注目度）: 0.3415532231770058
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give exponential quantum query separations between the standard XOR interface and two forward-only interfaces that supply neither an adjoint nor an inverse oracle. Let $X=\F_2^n$, $N=|X|$, and $f_{h,r}(x)=(h(x),x,r_x)$, where $h:X\to X$ is promised to be either a permutation or a Simon two-to-one function, and $r$ is a fixed table of $n$-bit tags, unrestricted by the promise and reused on every query. The resulting problem is solvable with at most $n+2$ standard XOR queries, but has forward-erasing query complexity $Θ(\sqrt N)$. This answers affirmatively open question 11 in [Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4):14:1-14:9, 2021] . We also embed these instances into permutations. The detailed construction retains the copy of $x$ in each prescribed output, but for these promises that copy can be replaced by one bit that distinguishes the two inputs in every Simon pair. This gives a permutation domain of size $L=4N^2$ and a permutation problem with the same standard-query upper bound and forward-only in-place query complexity $Θ(\sqrt N)=Θ(L^{1/4})$. Both lower bounds remain valid with a clean coherent bypass. The common lower bound uses an analysis-only recording replacement. In the replacement computation, tracing out the fixed random tag table after $T$ calls gives a sum of positive-semidefinite operator contributions, each depending on $h$ at no more than $T$ addresses. On such a set, the restrictions induced by random permutations and random Simon functions differ only if the set contains a hidden Simon pair, an event of probability $O(T^2/N)$.
• Abstract（参考訳）: 標準XORインタフェースと2つのフォワードオンリーインタフェースの間に指数関数的な量子クエリ分離を与える。 X=\F_2^n$, $N=|X|$, and $f_{h,r}(x)=(h(x,x,r_x)$, where $h:X\to X$ は置換かシモン2対1関数のいずれかで、$r$ は$n$-bitタグの固定テーブルで、約束に縛られ、全てのクエリで再利用される。 結果として得られる問題は、少なくとも$n+2$の標準XORクエリで解決できるが、クエリの複雑さを前向きに評価する$(\sqrt N)$がある。 affirmatively open question 11 in [Scott Aaronson. open problem related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4):14:1-14:9, 2021] また、これらのインスタンスを置換に埋め込む。 詳細な構成では、所定の出力ごとに$x$のコピーを保持するが、これらの約束では、コピーはサイモン対の2つの入力を区別する1ビットに置き換えることができる。 これにより、サイズ$L=4N^2$の置換領域と、同じ標準クエリの上界とフォワードのみのクエリ複雑性を持つ置換問題が与えられる。 どちらの下界もクリーンなコヒーレントバイパスで有効である。 一般的な下限は解析のみのレコード置換である。 置換計算では、$T$呼び出しの後、固定されたランダムタグテーブルをトレースすると、肯定的な演算子コントリビューションの合計が得られ、それぞれが$h$を$T$アドレス以上に依存している。 そのような集合において、ランダムな置換とランダムなシモン函数によって引き起こされる制限は、集合が隠れたシモン対、確率$O(T^2/N)$の事象を含む場合にのみ異なる。

関連論文リスト

• Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
  メモリが$m$ の単位球上の$d$ 次元 1$-Lipschitz 凸関数を最小化する。 まず、そのようなアルゴリズムは、$tilde(fracd2sqrtm)$ Oracle queryを作らなければならないことを示す。 決定論的最適化アルゴリズムでは$tilde(mind1.6,fracd8/3m2/3)$クエリが必要である。
  論文  参考訳（メタデータ） (2026-07-21T00:40:59Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
  論文  参考訳（メタデータ） (2023-02-20T19:11:44Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Quantum Complexity of Permutations [0.0]
  論理ゲートとして$sigma, tau, tau-1$を用いて, 置換の量子複雑性について検討した。 我々は、$S_n$ のほとんどすべての置換が、$nrightarrow infty$ のときの2次量子複雑性を下限とすることを示した。
  論文  参考訳（メタデータ） (2022-07-21T23:18:54Z)
• 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)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Towards Optimal Separations between Quantum and Randomized Query Complexities [0.30458514384586394]
  入力に対して2O(k)$クエリを行うことで量子アルゴリズムを解くことができることを示す。 任意の定数 $varepsilon>0$ に対して、$O(1)$ 対 $N2/3-varepsilon$ 分離を与える。
  論文  参考訳（メタデータ） (2019-12-29T01:42:31Z)

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

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