論文の概要: Quantum walk search on a two-dimensional grid with extra edges
- arxiv url: http://arxiv.org/abs/2503.04016v1
- Date: Thu, 06 Mar 2025 02:11:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-07 15:59:09.610584
- Title: Quantum walk search on a two-dimensional grid with extra edges
- Title（参考訳）: 余分なエッジを持つ2次元格子上の量子ウォークサーチ
- Authors: Pulak Ranjan Giri,
- Abstract要約: 量子ウォークは、データベースの要素として識別された頂点を持つグラフ上のターゲットの探索に成功している。
我々は,長距離エッジを持つ2次元周期格子上の量子探索において,一定の成功確率を持つ$mathcalO(sqrtN/M)$の最適時間複雑性が達成可能であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Quantum walk has been successfully used to search for targets on graphs with vertices identified as the elements of a database. This spacial search on a two-dimensional periodic grid takes $\mathcal{O}\left(\sqrt{N\log N}\right)$ oracle consultations to find a target vertex from $N$ number of vertices with $\mathcal{O}(1)$ success probability, while reaching optimal speed of $\mathcal{O}(\sqrt{N})$ on $d \geq 3$ dimensional square lattice. Our numerical analysis based on lackadaisical quantum walks searches $M$ vertices on a 2-dimensional grid with optimal speed of $\mathcal{O}(\sqrt{N/M})$, provided the grid is attached with additional long range edges. Based on the numerical analysis performed with multiple sets of randomly generated targets for a wide range of $N$ and $M$ we suggest that the optimal time complexity of $\mathcal{O}(\sqrt{N/M})$ with constant success probability can be achieved for quantum search on a two-dimensional periodic grid with long-range edges.
- Abstract（参考訳）: 量子ウォークは、データベースの要素として識別された頂点を持つグラフ上のターゲットの探索に成功している。
2次元周期格子上のこの空間探索は、$\mathcal{O}\left(\sqrt{N\log N}\right)$ oracle consultations を用いて、$\mathcal{O}(1)$成功確率で$N$の頂点数からターゲット頂点を見つけ、$d \geq 3$の平方格子上で$\mathcal{O}(\sqrt{N})$の最適速度に達する。
量子ウォークの欠如に基づく数値解析では, 最適速度が$\mathcal{O}(\sqrt{N/M})$の2次元格子上の頂点を$M$で探索する。
N$ および$M$ の範囲でランダムに生成されたターゲットの複数セットを用いて実行される数値解析に基づいて、一定の成功確率を持つ $\mathcal{O}(\sqrt{N/M})$ の最適時間複雑性が、長距離エッジを持つ2次元周期格子上の量子探索において達成可能であることを示唆する。
関連論文リスト
- Quantum spatial search with multiple excitations [0.28675177318965045]
我々は、$n$スピンの$k$-励起部分空間における連続時間量子ウォークが、時間$O(sqrtn)$の忠実さでマークされた$k$のバイナリ文字列を決定することができることを示した。
数値的には、このアルゴリズムは1/ralpha$で崩壊し、$r$はスピン間距離、$alpha$は現在のイオントラップシステムで容易に利用可能である。
論文 参考訳（メタデータ） (2024-10-08T11:53:57Z) - Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。
我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。
我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - 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) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
任意のグラフ上の連続時間量子ウォークによる空間探索の計算複雑性を決定するためのフレームワークについて述べる。
量子ウォークは、マークされた頂点の存在によって修正されたグラフの隣接行列に由来するハミルトン行列によって駆動される。
論文 参考訳（メタデータ） (2022-03-27T20:22:17Z) - A framework for optimal quantum spatial search using alternating
phase-walks [0.0]
我々は、マーク頂点位相シフトと連続時間量子ウォークの交互適用により、Childs & Goldstone(mathcalCG$)アルゴリズムを一般化する。
様々なグラフ上の$mathcalO(sqrtN)$検索にアルゴリズムを適用することで,アルゴリズムの有効性を実証する。
論文 参考訳（メタデータ） (2021-09-29T11:16:52Z) - Lackadaisical quantum walks on 2D grids with multiple marked vertices [0.0]
ラカダシカル量子ウォーク(英: Lackadaisical quantum walk、LQW)は、古典的な遅延ウォークの量子アナログである。
我々は,LQWによる三角形,長方形,ハニカムの2次元格子の探索について数値解析を行った。
論文 参考訳（メタデータ） (2021-04-20T13:33:16Z) - Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。
低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
論文 参考訳（メタデータ） (2020-10-13T17:26:09Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。