Fugu-MT 論文翻訳(概要): Comment to Spatial Search by Quantum Walk is Optimal for Almost all Graphs

論文の概要: Comment to Spatial Search by Quantum Walk is Optimal for Almost all Graphs

arxiv url: http://arxiv.org/abs/2009.13309v1
Date: Mon, 28 Sep 2020 13:26:53 GMT
ステータス: 処理完了
システム内更新日: 2023-04-30 18:51:08.757086
Title: Comment to Spatial Search by Quantum Walk is Optimal for Almost all Graphs
Title（参考訳）: 量子ウォークによる空間探索へのコメントは、ほぼすべてのグラフに最適である
Authors: Ryszard Kukulski, Adam Glos
Abstract要約: このコメントは、エルドホス=ルネニグラフの量子空間探索の最適性の証明を正すものである。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This comment is to correct the proof of optimality of quantum spatial search for Erd\H{o}s-R\'enyi graphs presented in `Spatial Search by Quantum Walk is Optimal for Almost all Graphs' (https://doi.org/10.1103/PhysRevLett.116.100501). The authors claim that if $p\geq \frac{\log^{3/2}(n)}{n}$, then the CTQW-based search is optimal for almost all graphs. Below we point the issues found in the main paper, and propose corrections, which in fact improve the result to $p=\omega(\log(n)/n)$ in case of transition rate $\gamma = 1/\lambda_1$. In the case of the proof for simplified transition rate $1/(np)$ we pointed a possible issue with applying perturbation theory.
Abstract（参考訳）: 量子ウォークによる空間探索は、ほぼすべてのグラフに対して最適である」(https://doi.org/10.1103/physrevlett.116.100501)。著者らは、$p\geq \frac{\log^{3/2}(n)}{n}$の場合、CTQWベースの探索はほとんど全てのグラフに対して最適であると主張している。以下では、メインの論文にある問題を指摘し、実際の結果が$p=\omega(\log(n)/n)$になるよう修正を提案する。単純化された遷移率 1/(np)$ の証明の場合、摂動理論を適用する際の問題の可能性を指摘した。

関連論文リスト

Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
連続時間量子ウォーク(CTQW)は、量子コンピューティングにおいて重要な役割を果たす。 CTQWを効率的に実装する方法は難しい問題である。本稿では,スパースグラフ上でのCTQWの実装について検討する。
論文参考訳（メタデータ） (2024-08-20T05:20:55Z)
Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文参考訳（メタデータ） (2023-04-17T10:38:08Z)
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)
Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
論文参考訳（メタデータ） (2022-10-04T04:36:15Z)
Solving Hamiltonian Cycle Problem using Quantum $\mathbb{Z}_2$ Lattice Gauge Theory [9.83302372715731]
グラフ理論におけるハミルトンサイクル(HC)問題は、よく知られたNP完全問題である。グラフを双対とする格子上で定義される$mathbbZ$格子ゲージ理論の観点でアプローチを提案する。小さなグラフのランダムなサンプルでは、$sqrtN_hc$における$g_c$、$N_hc$がHCの数であり、$Nにおける$frac1g_c$の平均値に依存することが示される。
論文参考訳（メタデータ） (2022-02-17T18:39:42Z)
Robust Estimation for Random Graphs [47.07886511972046]
我々は、$n$ノード上のErdHos-R'enyiランダムグラフのパラメータ$p$を頑健に推定する問題について検討する。情報理論の限界であるすべての$gamma 1/2$に対して、同様の精度で非効率なアルゴリズムを与える。
論文参考訳（メタデータ） (2021-11-09T18:43:25Z)
A framework for optimal quantum spatial search using alternating phase-walks [0.0]
我々は、マーク頂点位相シフトと連続時間量子ウォークの交互適用により、Childs & Goldstone(mathcalCG$)アルゴリズムを一般化する。様々なグラフ上の$mathcalO(sqrtN)$検索にアルゴリズムを適用することで,アルゴリズムの有効性を実証する。
論文参考訳（メタデータ） (2021-09-29T11:16:52Z)
Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk [0.0]
連続時間量子ウォークによるジョンソングラフ上の空間探索は、固定径毎に1ドル程度の成功確率を持つ下界の$pisqrtN/2$を達成することを示す。この証明は数学的に厳密であり、他のグラフクラスにも利用できる。
論文参考訳（メタデータ） (2021-08-04T12:16:24Z)
Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
論文参考訳（メタデータ） (2021-04-06T15:34:14Z)
Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文参考訳（メタデータ） (2021-03-02T06:53:44Z)
On the optimality of spatial search by continuous-time quantum walk [0.0]
我々は、この量子探索アルゴリズムの性能を予測するハミルトン運動のスペクトル特性に依存する一般表現を導出する。例えば、スペクトルギャップが$n-1/2$よりもかなり大きいハミルトニアンの予測は有効である。
論文参考訳（メタデータ） (2020-04-27T10:05:55Z)

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