論文の概要: Searching via nonlinear quantum walk on the 2D-grid
- arxiv url: http://arxiv.org/abs/2009.07800v3
- Date: Fri, 13 Nov 2020 16:36:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-02 02:18:42.748806
- Title: Searching via nonlinear quantum walk on the 2D-grid
- Title（参考訳）: 2次元グリッド上の非線形量子ウォークによる探索
- Authors: Basile Herzog and Giuseppe Di Molfetta
- Abstract要約: Wong and Meyer citemeyer2013nonlinearによって導入された非線形探索アルゴリズムは,有限次元格子に拡張可能であることを示す。
また,時間計測精度がアルゴリズムの複雑性探索時間に影響を与えることを避けるために,歩行パラメータの最適選択が存在することも証明した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide numerical evidence that the nonlinear searching algorithm
introduced by Wong and Meyer \cite{meyer2013nonlinear}, rephrased in terms of
quantum walks with effective nonlinear phase, can be extended to the finite
2-dimensional grid, keeping the same computational advantage \BHg{with} respect
to the classical algorithms. For this purpose, we have considered the free
lattice Hamiltonian, with linear dispersion relation introduced by Childs and
Ge \cite{Childs_2014}. The numerical simulations showed that the walker finds
the marked vertex in $O(N^{1/4} \log^{3/4} N) $ steps, with probability
$O(1/\log N)$, for an overall complexity of $O(N^{1/4}\log^{7/4}N)$. We also
proved that there exists an optimal choice of the walker parameters to avoid
that the time measurement precision affects the complexity searching time of
the algorithm.
- Abstract（参考訳）: Wong と Meyer \cite{meyer2013nonlinear} が導入した非線形探索アルゴリズムは、有効な非線形位相を持つ量子ウォークの言葉で言い換えれば、有限2次元格子に拡張でき、古典的アルゴリズムに関しても同様の計算上の優位性を持つことを示す。
この目的のために、Childs と Ge \cite{Childs_2014} により線形分散関係が導入された自由格子ハミルトニアンを考える。
数値シミュレーションにより、ウォーカーがマークされた頂点を$O(N^{1/4} \log^{3/4} N) $ Step, with probability $O(1/\log N)$, for a overall complexity of $O(N^{1/4}\log^{7/4}N)$とした。
また,時間計測精度がアルゴリズムの複雑性探索時間に影響を与えることを避けるために,歩行パラメータの最適選択が存在することも証明した。
関連論文リスト
- Unstructured Adiabatic Quantum Optimization: Optimality with Limitations [0.06022769903412461]
本研究では,非構造探索手法を用いた断熱的量子最適化により,古典的局所スピンハミルトニアンのクラスに対する下界と一致するランニング時間が得られることを示す。
回避された交差の位置は、ハミルトニアン問題の退化と逆ギャップに依存し、低加算精度でも計算し難い量によってほぼ与えられることを示す。
論文 参考訳（メタデータ） (2024-11-08T17:51:18Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Scalable network reconstruction in subquadratic time [0.0]
本稿では,この2次ベースラインを大幅に上回る広範囲の再構成問題に適用可能な一般アルゴリズムを提案する。
我々のアルゴリズムは、高い確率で最適なエッジ候補を生成する第2の隣人探索に依存している。
本アルゴリズムは2次ベースラインよりも桁違いに高速な性能を実現する。
論文 参考訳（メタデータ） (2024-01-02T19:00:13Z) - Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian [0.5097809301149342]
我々は、我々の分割と形式主義の征服を通じて、大きな$Lambda$の量子化よりも優れたスケーリングと量子化を得られることを示す。
また,マルチコントロールされたXゲート群を実装する新しい方法を含む,ゲート最適化のための新しいアルゴリズムおよび回路レベル技術も提供する。
論文 参考訳（メタデータ） (2023-06-19T23:20:30Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
We show that Greedy-GQ algorithm converges fast-time error。
我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
論文 参考訳（メタデータ） (2022-09-06T15:04:57Z) - Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
連続時間量子ウォークは、空間探索として知られるグラフ内のマークされたノードの集合の中のノードを見つけるという根本的な問題に取り組むためのフレームワークを提供する。
連続時間量子ウォーク探索アルゴリズムでは,任意のノード数を持つグラフにおいて,従来のランダムウォークよりも2次的に高速なマークノードを見つけることができる。
論文 参考訳（メタデータ） (2021-12-23T17:57:49Z) - Sample Complexity Bounds for Two Timescale Value-based Reinforcement
Learning Algorithms [65.09383385484007]
2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。
本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
論文 参考訳（メタデータ） (2020-11-10T11:36:30Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。
格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。
NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
論文 参考訳（メタデータ） (2020-02-25T19:18:36Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。