論文の概要: Quantum spatial search with multiple excitations
- arxiv url: http://arxiv.org/abs/2410.05945v1
- Date: Tue, 8 Oct 2024 11:53:57 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-01 12:00:27.534872
- Title: Quantum spatial search with multiple excitations
- Title（参考訳）: 多重励起による量子空間探索
- Authors: Dylan Lewis, Leonardo Banchi, Sougato Bose,
- Abstract要約: 我々は、$n$スピンの$k$-励起部分空間における連続時間量子ウォークが、時間$O(sqrtn)$の忠実さでマークされた$k$のバイナリ文字列を決定することができることを示した。
数値的には、このアルゴリズムは1/ralpha$で崩壊し、$r$はスピン間距離、$alpha$は現在のイオントラップシステムで容易に利用可能である。
- 参考スコア（独自算出の注目度）: 0.28675177318965045
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Spatial search is the problem of finding a marked vertex in a graph. A continuous-time quantum walk in the single-excitation subspace of an $n$ spin system solves the problem of spatial search by finding the marked vertex in $O(\sqrt{n})$ time. Here, we investigate a natural extension of the spatial search problem, marking multiple vertices of a graph, which are still marked with local fields. We prove that a continuous-time quantum walk in the $k$-excitation subspace of $n$ spins can determine the binary string of $k$ marked vertices with an asymptotic fidelity in time $O(\sqrt{n})$, despite the size of the state space growing as $O(n^k)$. Numerically, we show that this algorithm can be implemented with interactions that decay as $1/r^\alpha$, where $r$ is the distance between spins, and an $\alpha$ that is readily available in current ion trap systems.
- Abstract（参考訳）: 空間探索は、グラフにマークされた頂点を見つける問題である。
スピン系の単励起部分空間における連続時間量子ウォークは、$O(\sqrt{n})$時間でマークされた頂点を見つけることによって空間探索の問題を解く。
本稿では,空間探索問題の自然な拡張について検討し,局所フィールドでマークされたグラフの複数の頂点をマーキングする。
我々は、$n$スピンの$k$-励起部分空間における連続時間量子ウォークが、$O(\sqrt{n})$という状態空間のサイズが$O(n^k)$として大きくなるにもかかわらず、時間の漸近的忠実度を持つ$k$マークされた頂点のバイナリ列を決定することができることを証明した。
数値的には、このアルゴリズムは1/r^\alpha$として崩壊し、$r$はスピン間の距離であり、$\alpha$は現在のイオントラップシステムで容易に利用できる。
関連論文リスト
- 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) - On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。
PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。
UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文 参考訳（メタデータ） (2023-03-10T00:11:18Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - 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) - Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
任意のグラフ上の連続時間量子ウォークによる空間探索の計算複雑性を決定するためのフレームワークについて述べる。
量子ウォークは、マークされた頂点の存在によって修正されたグラフの隣接行列に由来するハミルトン行列によって駆動される。
論文 参考訳（メタデータ） (2022-03-27T20:22:17Z) - Universality of the fully connected vertex in Laplacian continuous-time
quantum walk problems [0.0]
連続時間量子ウォーク(CTQW)がハミルトニアン$H=ガンマ L$で、グラフ$G$に依存しないことを証明する。
本研究では,空間探索と量子輸送に本研究の結果を適用した。
論文 参考訳（メタデータ） (2022-02-28T14:33:44Z) - A framework for optimal quantum spatial search using alternating
phase-walks [0.0]
我々は、マーク頂点位相シフトと連続時間量子ウォークの交互適用により、Childs & Goldstone(mathcalCG$)アルゴリズムを一般化する。
様々なグラフ上の$mathcalO(sqrtN)$検索にアルゴリズムを適用することで,アルゴリズムの有効性を実証する。
論文 参考訳（メタデータ） (2021-09-29T11:16:52Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Unstructured Search by Random and Quantum Walk [0.0]
ソートされていない$N$要素のリストのエントリを探すと、古典的なコンピュータのオラクルに$O(N)$クエリーを取るのが有名である。
離散的かつ連続的なランダムウォークと量子ウォークがこの問題をいかに解決するかを導出する。
論文 参考訳（メタデータ） (2020-11-30T04:00:31Z) - Optimal quantum spatial search with one-dimensional long-range
interactions [0.5249805590164902]
連続時間量子ウォークは空間探索問題の解決に利用できる。
距離$r$の1/ralpha$で崩壊する長距離相互作用を持つ1次元スピン鎖において、最適空間探索が可能であることを証明した。
論文 参考訳（メタデータ） (2020-10-08T23:28:47Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。