論文の概要: Exponential Quantum Advantage in Testing Fourier Dimensionality

• arxiv url: http://arxiv.org/abs/2609.25816v3
• Date: Mon, 28 Sep 2026 09:10:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-29 21:31:51.636157
• Title: Exponential Quantum Advantage in Testing Fourier Dimensionality
• Title（参考訳）: フーリエ次元試験における指数量子アドバンテージ
• Abstract要約: この問題に対して$O(k/sqrt)$-Query 量子プロパティテスタが存在することを示す。 この結果を$tildeO(2k/2/)$classic Testerで補完し、以前のベストテスタよりも2次的に改善する。
• 参考スコア（独自算出の注目度）: 4.010371060637209
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A boolean function $f$ has Fourier dimension $k$ if its nonzero Fourier coefficients span a subspace of dimension $k$. We consider the property testing task of determining whether a function has Fourier dimension at most $k$, or is $ε$-far from being so. We show that there is a $O(k/\sqrtε)$-query quantum property tester for this problem, which we show to be almost optimal. Combined with Gopalan et al.'s classical lower bound of $Ω(2^{k/2})$, this demonstrates an exponential quantum advantage for this task \cite{DBLP:journals/siamcomp/GopalanOSSW11}. We complement this result with a $\tilde{O}(2^{k/2}/ε)$ classical tester, giving a quadratic improvement over the previous best tester, and essentially settling the classical query complexity.
• Abstract（参考訳）: ブール関数 $f$ がフーリエ次元 $k$ を持つとき、その非零フーリエ係数が次元 $k$ の部分空間にまたがる。 関数が少なくとも$k$のフーリエ次元を持つかどうかを判断するプロパティテストのタスクを考える。 この問題に対して$O(k/\sqrtε)$-queryの量子特性テスタがあることを示し、ほぼ最適であることを示す。 Gopalan et al の古典的下界 $Ω(2^{k/2})$ と組み合わせると、これはこのタスクの指数的量子的優位性を示す。 この結果を$\tilde{O}(2^{k/2}/ε)$ classical testerで補完し、以前のベストテスタよりも2次的に改善し、基本的には古典的なクエリの複雑さを解決します。

関連論文リスト

• Robust quantum state certification and uncertainty principles for total influence [5.7531205491708945]
  非適応的な単量子パウリ測定は、未知の$n$-qubit状態$$が$varepsilon$-close toか$O(varepsilon)$-farが理想的なターゲット状態$|rangle$であるかどうかをテストするのに十分であることを示す。 このテストでは、$O(varepsilon-2log (1/)$のコピーを使って1-$の信頼性を実現している。
  論文  参考訳（メタデータ） (2026-07-29T17:53:23Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Towards Minimax Estimation of High-Order Functionals by Quantum Arguments [13.491187998442596]
  本稿では,量子コンピューティングの観点から,高次関数の最小値推定に対する新しいアプローチを提案する。 我々の推定子は、量子プリミティブを用いて統一されたフレームワークで構築され、量子コンピュータ上で実行される。
  論文  参考訳（メタデータ） (2026-07-08T15:38:24Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Testing classical properties from quantum data [0.22940141855172033]
  関数状態 $|frangle propto sum_x|x,f(x)rangle$ のコピーの形で、量子データからのみ$f$の特性をテストする量子アルゴリズムを導入する。 モノトニック性、対称性、三角形自由性の3つの確立された特性について、古典的テスタをサンプルデータに制限した場合のスピードアップは、量子データからのみ動作する量子アルゴリズムによって回復可能であることを示す。
  論文  参考訳（メタデータ） (2024-11-19T18:52:55Z)
• The classical limit of Quantum Max-Cut [0.16385815610837165]
  我々は、大きな量子スピンの極限$S$は半古典的極限として理解されるべきであることを示した。 半定値プログラムの出力をブロッホコヒーレント状態の積に丸め、$mathrmQMaxCut_S$に対する古典近似アルゴリズムの2つのファミリを示す。
  論文  参考訳（メタデータ） (2024-01-23T18:53:34Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Convexity of a certain operator trace functional [1.1470070927586014]
  本稿では、演算子トレース関数 $ Lambda_r,s(A)[K, M] := operatornametr(K*Ar M Ar K)s$を導入し、その凸性と凸性について検討する。 この関数は、量子情報理論に現れるいくつかのよく研究された作用素トレース関数と直結している。
  論文  参考訳（メタデータ） (2021-09-23T17:51:46Z)
• Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
  我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。 規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
  論文  参考訳（メタデータ） (2021-05-31T16:10:49Z)

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

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