論文の概要: Quantum Property Testing for Bounded-Degree Directed Graphs

• arxiv url: http://arxiv.org/abs/2604.07954v1
• Date: Thu, 09 Apr 2026 08:19:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-10 18:34:05.793151
• Title: Quantum Property Testing for Bounded-Degree Directed Graphs
• Title（参考訳）: 境界層指向グラフの量子特性試験
• Authors: Pan Peng, Jingyu Wu,
• Abstract要約: 我々は、ある普遍定数$d$で有界な最大等級と外等級を持つ有向グラフの量子特性試験について研究する。 近接パラメータ $varepsilon$ に対して、古典的双方向モデルで$O_varepsilon,d(1)$クエリでテスト可能なプロパティは、入出力エッジの両方にアクセス可能であることを示す。 これにより、一方向モデルにおける最もよく知られた古典的アルゴリズムよりも、ほぼ二次的な量子スピードアップが得られる。
• 参考スコア（独自算出の注目度）: 5.501204611528696
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study quantum property testing for directed graphs with maximum in-degree and out-degree bounded by some universal constant $d$. For a proximity parameter $\varepsilon$, we show that any property that can be tested with $O_{\varepsilon,d}(1)$ queries in the classical bidirectional model, where both incoming and outgoing edges are accessible, can also be tested in the quantum unidirectional model, where only outgoing edges are accessible, using $n^{1/2 - Ω_{\varepsilon,d}(1)}$ queries. This yields an almost quadratic quantum speedup over the best known classical algorithms in the unidirectional model. Moreover, we prove that our transformation is almost tight by giving an explicit property $P_\varepsilon$ that is $\varepsilon$-testable within $O_\varepsilon(1)$ classical queries in the bidirectional model, but requires $\widetildeΩ(n^{1/2-f'(\varepsilon)})$ quantum queries in the unidirectional model, where $f'(\varepsilon)$ is a function that approaches $0$ as $\varepsilon$ approaches $0$. As a byproduct, we show that in the unidirectional model, the number of occurrences of any constant-size subgraph $H$ can be approximated up to additive error $δn$ using $o(\sqrt{n})$ quantum queries.
• Abstract（参考訳）: 我々は、ある普遍定数$d$で有界な最大等級と外等級を持つ有向グラフの量子特性試験について研究する。 近接パラメータ $\varepsilon$ に対して、古典的双方向モデルにおいて$O_{\varepsilon,d}(1)でテスト可能なプロパティは、入出力エッジの両方にアクセス可能であり、量子一方向モデルでもテスト可能であることを示し、出出力エッジのみがアクセス可能であり、$n^{1/2 - Ω_{\varepsilon,d}(1)$クエリを使用する。 これにより、一方向モデルにおける最もよく知られた古典的アルゴリズムよりも、ほぼ二次的な量子スピードアップが得られる。 さらに、我々の変換は、明示的な性質として$P_\varepsilon$-testable in the $O_\varepsilon(1)$ classical query in the bidirectional model, but requires $\widetildeΩ(n^{1/2-f'(\varepsilon)})$ quantum query in the unitidirectional model, where $f'(\varepsilon)$ is a function with $0$ as $\varepsilon$ approaches $0$. 副生成物として、一方向モデルでは、任意の定数サイズの部分グラフ $H$ の出現回数を $o(\sqrt{n})$ を用いて加算誤差 $δn$ に近似できることを示す。

関連論文リスト

• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• 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)
• Improved Sample Upper and Lower Bounds for Trace Estimation of Quantum State Powers [9.136389487369117]
  上界と下界の両方で$operatornametr(rhoq)$を推定することで、サンプルの複雑さを大幅に改善する。 我々の上界は、弱いシュアサンプリングに基づく(プラグインでない)量子推定器によって得られる。
  論文  参考訳（メタデータ） (2025-05-14T17:06:33Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。 以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
  論文  参考訳（メタデータ） (2023-03-30T02:50:49Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
  論文  参考訳（メタデータ） (2021-09-21T13:19:04Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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