論文の概要: Even-Cycle Detection in the Randomized and Quantum CONGEST Model
- arxiv url: http://arxiv.org/abs/2402.12018v1
- Date: Mon, 19 Feb 2024 10:23:37 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-20 17:01:15.091822
- Title: Even-Cycle Detection in the Randomized and Quantum CONGEST Model
- Title（参考訳）: ランダム化および量子ConGESTモデルにおける偶数サイクル検出
- Authors: Pierre Fraigniaud, Mael Luce, Frederic Magniez, Ioan Todinca
- Abstract要約: すべての$kgeq 2$に対して、$C_2k$-freenessは、CONGESTモデルで$O(n1-1/k)$ラウンドで決定できることを示す。
また、量子設定において、円複雑度$tilde O(nfrac12-frac12k)$を達成するためのアルゴリズムの量子化方法を示す。
- 参考スコア（独自算出の注目度）: 1.5566524830295314
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We show that, for every $k\geq 2$, $C_{2k}$-freeness can be decided in
$O(n^{1-1/k})$ rounds in the \CONGEST{} model by a randomized Monte-Carlo
distributed algorithm with one-sided error probability $1/3$. This matches the
best round-complexities of previously known algorithms for $k\in\{2,3,4,5\}$ by
Drucker et al. [PODC'14] and Censor-Hillel et al. [DISC'20], but improves the
complexities of the known algorithms for $k>5$ by Eden et al. [DISC'19], which
were essentially of the form $\tilde O(n^{1-2/k^2})$. Our algorithm uses
colored BFS-explorations with threshold, but with an original \emph{global}
approach that enables to overcome a recent impossibility result by Fraigniaud
et al. [SIROCCO'23] about using colored BFS-exploration with \emph{local}
threshold for detecting cycles.
We also show how to quantize our algorithm for achieving a round-complexity
$\tilde O(n^{\frac{1}{2}-\frac{1}{2k}})$ in the quantum setting for deciding
$C_{2k}$ freeness. Furthermore, this allows us to improve the known quantum
complexities of the simpler problem of detecting cycles of length \emph{at
most}~$2k$ by van Apeldoorn and de Vos [PODC'22]. Our quantization is in two
steps. First, the congestion of our randomized algorithm is reduced, to the
cost of reducing its success probability too. Second, the success probability
is boosted using a new quantum framework derived from sequential algorithms,
namely Monte-Carlo quantum amplification.
- Abstract（参考訳）: 各$k\geq 2$, $c_{2k}$-freeness について、一面誤差確率$1/3$のランダム化モンテカルロ分散アルゴリズムにより、\congest{} モデルの$o(n^{1-1/k})$ round で決定できることを示す。
これはDruckerらによる$k\in\{2,3,4,5\}$に対する既知アルゴリズムの最も複雑なラウンドコンプレックスと一致する。
[podc'14] と censor-hillel et al。
[DISC'20]だが、Edenらによって、既知のアルゴリズムの複雑さを$k>5$で改善する。
[DISC'19]は基本的に$\tilde O(n^{1-2/k^2})$である。
このアルゴリズムはしきい値付きカラーbfs探索を用いるが、fraigniaudらによる最近の不可能性を克服できるオリジナルの \emph{global} アプローチを採用している。
SIROCCO'23] では, サイクル検出に "emph{local} threshold" を用いた色付きBFS探索を行った。
また,ラウンド複雑度$\tilde o(n^{\frac{1}{2}-\frac{1}{2k}}) を量子化することで,自由度$c_{2k} を決定する方法を示す。
さらに、ファン・アペルドールンとド・ヴォスによる長さ \emph{at most}~$2k$のサイクルを検出するというより単純な問題の既知の量子複雑性を改善することができる。
我々の量子化は2つの段階にある。
まず、ランダム化アルゴリズムの混雑を減らし、その成功確率も低減する。
第二に、逐次アルゴリズムから派生した新しい量子フレームワーク、モンテカルロ量子増幅を用いて成功確率を高める。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - 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) - Finding many Collisions via Reusable Quantum Walks [1.376408511310322]
衝突発見は暗号解析におけるユビキタスな問題である。
本稿では,この問題に対するアルゴリズムを改良し,特に許容可能なパラメータの範囲を広げる。
応用として、最短ベクトル問題に対する量子シービングアルゴリズムを改善する。
論文 参考訳（メタデータ） (2022-05-27T14:50:45Z) - Quantum Approximate Counting for Markov Chains and Application to
Collision Counting [0.0]
我々は,ブラザード,ホイヤー,タップ(ICALP 1998)によって開発された量子近似計数法を一般化し,マルコフ連鎖のマーク状態の数を推定する方法を示す。
これにより、Magniez、Nayak、Roland、Santhaによって確立された強力な"量子ウォークベースサーチ"フレームワークに基づいて、量子検索アルゴリズムから量子近似カウントアルゴリズムを構築することができる。
論文 参考訳（メタデータ） (2022-04-06T03:04:42Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳（メタデータ） (2021-06-10T16:28:23Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。