論文の概要: Electrostatic Limits on Quantum Spatial Search

• arxiv url: http://arxiv.org/abs/2610.23560v1
• Date: Fri, 16 Oct 2026 14:49:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-20 00:56:07.975639
• Title: Electrostatic Limits on Quantum Spatial Search
• Title（参考訳）: 量子空間探索における静電限界
• Abstract要約: 我々は、量子ウォーカーがグロバーの$O(sqrt N)$時間で2次元格子を探索できないことを証明した。 我々の証明は古典的な静電気との驚くべき対応に基づいている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove that a quantum walker cannot search a two-dimensional lattice in Grover's $O(\sqrt N)$ time, resolving the long-standing open question posed by Aaronson and Ambainis in 2003. A walker that hops between neighbouring sites of an $L\times L$ lattice, $N=L^2$, needs $Ω(\sqrt{N\log N})$ local steps at least to find a marked vertex, even with unlimited memory and free queries. Hence, Tulsi's algorithm is asymptotically optimal. Our proof rests on a surprising correspondence with classical electrostatics. We treat the marked vertex as a point charge and weight the overlap between the walker's states with and without the mark by the potential drop, which vanishes where queries act. Only local steps change this weighted overlap, at a rate limited by the field energy, so the lower bound is set by the self-potential of the charge. In the plane this self-potential grows logarithmically with system size, like the Coulomb potential, leading to the extra root-logarithmic factor. Several marked vertices turn the charge into a conductor, and the lower bound depends on their arrangement through its capacitance.
• Abstract（参考訳）: 我々は、量子ウォーカーがグロバーの$O(\sqrt N)$時間で2次元格子を探索できないことを証明する。 近くの$L\times L$ lattice, $N=L^2$のサイト間をホップするウォーカーは、少なくともメモリが無制限でもマークされた頂点を見つけるために$Ω(\sqrt{N\log N})$ローカルステップを必要とする。 したがって、タルシのアルゴリズムは漸近的に最適である。 我々の証明は古典的な静電気との驚くべき対応に基づいている。 我々は、マークされた頂点を点電荷として扱い、ウォーカー状態間の重なりを潜在的なドロップによるマークなしで重み付けする。 局所的なステップだけがこの重み付き重なりを磁場エネルギーによって制限された速度で変化させるので、下限は電荷の自己ポテンシャルによって設定される。 平面では、この自己ポテンシャルはクーロンポテンシャルのようなシステムサイズと対数的に成長し、余分な根対数係数をもたらす。 いくつかのマークされた頂点は電荷を導体に変え、下限はその容量を通して配置に依存する。

関連論文リスト

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval [59.859592671274704]
  $dtimes d$ リニアメモリストアはいくつのキー値アソシエーションが可能ですか? この答えは、メモリマトリックスの$d2$自由度だけでなく、検索基準にも依存する。
  論文  参考訳（メタデータ） (2026-05-06T17:53:20Z)
• Quantum Walk on a Line with Absorbing Boundaries [0.0]
  対称的な構成を考えると、2つのシンクが$N$と$-N$で、量子ウォーカーが中央から始まる。 吸収は、コイン角とは別に、初期状態がコイン作用素の固有状態の1つである確率にのみ依存することが示されている。
  論文  参考訳（メタデータ） (2025-08-18T19:04:20Z)
• Optimal spatial searches with long-range tunneling [0.0]
  グラバーの最適スケーリングは、長距離相互作用粒子の格子上に低次元で到達可能であることを示す。 我々の研究は、長距離システムの臨界度と短距離システムの臨界度を正確に関連付けている。
  論文  参考訳（メタデータ） (2025-01-14T14:25:02Z)
• Free fermions with dephasing and boundary driving: Bethe Ansatz results [0.0]
  We use the Bethe ansatz to diagonalize the Liouvillian $mathcal Lscriptscriptstyle(2)$ the dynamics of the correlator。 正確には、$L(L-1)/2$複素エネルギーは、自明なシフトを除いて、デファーズに依存しない。 長時間の力学は、多数のレベルを含む実エネルギーのバンドによって支配される。
  論文  参考訳（メタデータ） (2023-09-22T16:18:41Z)
• Small-time controllability for the nonlinear Schr\"odinger equation on $\mathbb{R}^N$ via bilinear electromagnetic fields [55.2480439325792]
  非線形シュラー・オーディンガー方程式(NLS)の磁場および電場の存在下での最小時間制御可能性問題に対処する。 詳細は、十分に大きな制御信号によって、所望の速度で(NLS)のダイナミクスを制御できる時期について調べる。
  論文  参考訳（メタデータ） (2023-07-28T21:30:44Z)
• Walking on Vertices and Edges by Continuous-Time Quantum Walk [0.0]
  私たちは、歩行者が頂点から端までホップできる連続時間量子ウォークのバージョンを定義します。 両部グラフ上の空間探索アルゴリズムをハミルトン版の修正により解析する。
  論文  参考訳（メタデータ） (2022-06-07T15:10:18Z)
• Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
  連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。 低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
  論文  参考訳（メタデータ） (2020-05-13T14:53:36Z)

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

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