論文の概要: Optimal Quantum Junta Testing without Inverse Queries

• arxiv url: http://arxiv.org/abs/2609.37926v1
• Date: Tue, 29 Sep 2026 16:16:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-30 21:28:47.733203
• Title: Optimal Quantum Junta Testing without Inverse Queries
• Title（参考訳）: 逆クエリを伴わない最適量子ユタテスト
• Abstract要約: 未知の$n$-qubitユニタリまたは量子チャネルが与えられた場合、その目標は、それが少なくとも$k$ qubitsで非自明に作用するか、またはそのような操作の全てから$varepsilon$-farであるかを判断することである。 ユニタリおよびチャネルユンタテストの両方に厳密な境界を与える。
• 参考スコア（独自算出の注目度）: 10.042684323264202
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the query complexity of testing quantum juntas. Given an unknown $n$-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most $k$ qubits or is $\varepsilon$-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to $U$, but not to $U^\dagger$ or controlled-$U$. We give tight bounds for both unitary and channel junta testing. For sufficiently large $k$, $n \ge 2k$, and a broad range of $\varepsilon$, both problems have query complexity $Θ\left(k/(\varepsilon^2\log k)\right)$. Our upper bounds are achieved by simple nonadaptive testers using product inputs and single-qubit measurements. For junta channels, this closes the gap by Bao and Yao (COLT 23, TPAMI 2025) between an $\widetilde{O}(k)$ upper bound and a $\widetildeΩ(\sqrt{k})$ lower bound at constant $\varepsilon$, establishing the optimal $Θ(k/\log k)$ query complexity. At the heart of both bounds is a strong connection between quantum junta testing and classical support-size testing. For the upper bounds, we reduce quantum junta testing to a generalized support-size problem for distributions over random subsets, and develop a new tester with improved sample complexity. For the lower bounds, we proceed in the reverse direction, reducing classical support-size testing to quantum junta testing through a phase-masked hard ensemble and showing that forward quantum queries can be exactly classicalized on average. Together, these reductions identify support-size testing as the classical core of quantum junta testing and yield matching lower bounds. At constant $\varepsilon$, they also give a separation between $Θ(k/\log k)$ forward queries and $\widetilde{O}(\sqrt{k})$ queries with inverse access.
• Abstract（参考訳）: 量子ジャンタを試験する際のクエリ複雑性について検討する。 未知の$n$-qubitユニタリまたは量子チャネルが与えられた場合、その目標は、それが少なくとも$k$ qubitsで非自明に作用するか、またはそのような操作から$\varepsilon$-farであるかを判断することである。 単体テストでは、テスターが$U$にアクセスできるが、$U^\dagger$や Control-$U$にはアクセスできない。 ユニタリおよびチャネルユンタテストの両方に厳密な境界を与える。 十分に大きな$k$、$n \ge 2k$、および広範囲の$\varepsilon$に対して、どちらの問題もクエリの複雑さが$\left(k/(\varepsilon^2\log k)\right)$である。 私たちの上限は、プロダクトインプットとシングルキュービット測定を使用して、単純な非適応テスターによって達成されます。 ジャンタチャネルの場合、これはBao と Yao (COLT 23 TPAMI 2025) による、$\widetilde{O}(k)$上界と$\widetildeΩ(\sqrt{k})$下界とのギャップを埋める。 両方の境界の中心には、量子ユンタテストと古典的なサポートサイズテストの強い関係がある。 上界では、ランダム部分集合上の分布に対する一般化されたサポートサイズ問題に量子ユタ試験を還元し、サンプルの複雑さを改善した新しいテスタを開発する。 下位境界については、古典的なサポートサイズテストから、位相整合型ハードアンサンブルによる量子ユンタテストまで、逆方向に進み、前方量子クエリが平均的に完全に古典化可能であることを示す。 これらの還元により、サポートサイズテストは量子ユンタテストの古典的なコアとして特定され、一致する下界を得る。 定数$\varepsilon$では、$(k/\log k)$ forwardクエリと$\widetilde{O}(\sqrt{k})$逆アクセスのクエリを分離する。

関連論文リスト

• Quantum Advantage in Tolerant Junta Testing [0.5442955439283729]
  適応設定において、許容値$k$-juntaテスト問題に対する最初の超多項式量子優位性を確立する。 特定のパラメータ体系内では、高い精度で寛容な$k$-juntaテストが$mathrmpoly(k)$quantumquantumquantum(k)$で解けることを示す。
  論文  参考訳（メタデータ） (2026-06-22T11:42:39Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• 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)
• 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)
• 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)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)

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

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