論文の概要: Quantum Advantage in Tolerant Junta Testing

• arxiv url: http://arxiv.org/abs/2606.23194v1
• Date: Mon, 22 Jun 2026 11:42:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-24 23:27:12.708669
• Title: Quantum Advantage in Tolerant Junta Testing
• Title（参考訳）: Tolerant Junta Testingにおける量子アドバンテージ
• Authors: Avishay Tal, Weiqiang Yuan,
• Abstract要約: 適応設定において、許容値$k$-juntaテスト問題に対する最初の超多項式量子優位性を確立する。 特定のパラメータ体系内では、高い精度で寛容な$k$-juntaテストが$mathrmpoly(k)$quantumquantumquantum(k)$で解けることを示す。
• 参考スコア（独自算出の注目度）: 0.5442955439283729
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant $k$-junta testing with high precision can be solved using $\mathrm{poly}(k)$ quantum queries, whereas any classical algorithm requires at least $k^{Ω(\log k)}$ queries. The problem of tolerant $k$-junta testing is as follows: given parameters $(k, ε_1, ε_2)$, with $0\le ε_1<ε_2 \le 1/2$, and black-box access to a Boolean function $f$ (defined on $n$ variables), distinguish whether $f$ is $ε_1$-close to some $k$-junta or $ε_2$-far from every $k$-junta. We show the quantum advantage for a range of parameters close to $1/2$, for example, $ε_1 = 1/2-1/k$ and $ε_2 = 1/2-1/(2k^2)$. The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most $ε_1$ to $k$-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick $k$ out of $n$ coordinates, and for each fixing of the $k$ coordinates, the $2^{n-k}$ values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to $k$-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making $k^{o(\log k)}$ queries.
• Abstract（参考訳）: 適応条件下での耐久ジャンタ試験問題に対する最初の超多項式量子優位性を確立する。 具体的には、あるパラメータ体系内では、高い精度で寛容な$k$-juntaテストは$\mathrm{poly}(k)$量子クエリで解けるが、古典的アルゴリズムでは少なくとも$k^{Ω(\log k)}$クエリを必要とする。 許容値 $(k, ε_1, ε_2)$, with $0\le ε_1<ε_2 \le 1/2$, and black-box access to a Boolean function $f$ ($n$変数で定義される) $f$は、ある$k$-juntaに対して$ε_1$-closeであるか、あるいは$ε_2$-farである。 例えば、$ε_1 = 1/2-1/k$ および $ε_2 = 1/2-1/(2k^2)$ である。 私たちが使用している(非適応的な)量子テスターは、Bao, Liu, Yao, Ye, Zhang (SOSA 2026)の最近の研究によって与えられた。 上記のパラメータ体系に保持されていることを示すために、分析を少し順応する。 一方、我々の古典的な下限は、かなり新しい考えを必要とする。 Chen と Patel (FOCS 2023) の下位境界技術に触発された新しいハード分布である ‘yes' のインスタンス (最大$ε_1$ to $k$-juntas) を導入し、これは ``approximate-junta'' の植え付けに基づくものである: 私たちはランダムに$k$を$n$座標から選択し、$k$座標のそれぞれの固定に対して、制限されたサブキューブの $2^{n-k}$値は、同じランダムビットを配置するエラー修正符号の点集合を除いてランダムに描画される。 この分布は一様分布よりも$k$-juntasに近いことを示すが、一方、$k^{o(\log k)}$クエリを作る古典的なアルゴリズムでは区別できない。

関連論文リスト

• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• Efficient Non-Adaptive Quantum Algorithms for Tolerant Junta Testing [18.89209417623036]
  我々は、$n$-qubitユニタリが$varepsilon$-close to some $k$-junta or $varepsilon$-far from every $k$-junta。 単一量子ビット演算のみを用いて実装される最初の2つの量子アルゴリズムに適応し、実験可能性を高める。
  論文  参考訳（メタデータ） (2025-08-24T11:15:40Z)
• Tolerant Quantum Junta Testing [0.0]
  耐久ジャンタテストは標準バージョンよりも一般的で難しい。 我々は、ユニタリが$epsilon$-juntaか、または任意の量子$k$-juntaから$epsilon$-farかを決定する最初のアルゴリズムを示す。
  論文  参考訳（メタデータ） (2024-11-04T16:34:50Z)
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
  確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。 我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。 クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-25T15:32:37Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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