論文の概要: Dissipative search of an unstructured database
- arxiv url: http://arxiv.org/abs/2106.02703v2
- Date: Mon, 4 Apr 2022 06:39:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-27 21:03:15.569449
- Title: Dissipative search of an unstructured database
- Title(参考訳): 非構造化データベースの散逸探索
- Authors: Armen E. Allahverdyan and David Petrosyan
- Abstract要約: 構造化されていないデータベースの検索は、$N$要素から特定のプロパティを持つ1つの要素を見つけることに相当する。
量子探索のためのグロバーアルゴリズムとそのユニタリハミルトン進化アナログは、$mathcalO (sqrtN)$タイムステップで探索的に最適を達成する。
スペクトルの適切な選択と、エネルギーレベル間の物理的に許容される長距離遷移速度により、システムは、求めている要素に対応する基底状態に緩和され、時間$mathcalO (ln N)$となる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The search of an unstructured database amounts to finding one element having
a certain property out of $N$ elements. The classical search with an oracle
checking one element at a time requires on average $N/2$ steps. The Grover
algorithm for the quantum search, and its unitary Hamiltonian evolution
analogue, accomplish the search asymptotically optimally in $\mathcal{O}
(\sqrt{N})$ time steps. We reformulate the search problem as a dissipative
Markov process acting on an $N$-level system weakly coupled to a thermal bath.
Assuming that the energy levels of the system represent the database elements,
we show that, with a proper choice of the spectrum and physically admissible,
long-range transition rates between the energy levels, the system relaxes to
the ground state, corresponding to the sought element, in time $\mathcal{O}
(\ln N)$.
- Abstract(参考訳): 非構造化データベースの検索は、$n$要素から特定のプロパティを持つ1つの要素を見つけるのに等しい。
oracleが1つの要素を一度にチェックする古典的な検索は、平均で$n/2$のステップを必要とする。
量子探索のグローバーアルゴリズムとそのユニタリハミルトニアン進化の類似物は、$\mathcal{o} (\sqrt{n})$ の時間ステップで漸近的に最適に探索を達成する。
熱浴に弱結合したN$レベルのシステムに作用する散逸的マルコフ過程として探索問題を再構成する。
システムのエネルギーレベルがデータベース要素を表すと仮定すると、エネルギーレベル間のスペクトルと物理的に許容可能な長距離遷移率を適切に選択することで、システムは要求される要素に対応する基底状態へと緩和し、時間$\mathcal{o} (\ln n)$ となる。
関連論文リスト
- Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
関数の階数$f$は、単層トランスフォーマーデコーダで要求される思考の連鎖の最小値に対応することを示す。
また、ブール列における1の$k$-thの発生位置を同定する問題を解析し、$k$CoTステップが必要であることを証明した。
論文 参考訳(メタデータ) (2025-01-22T16:30:58Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳(メタデータ) (2024-09-07T06:37:23Z) - Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms [48.869199703062606]
量子多体物理学における基本的な問題は、局所ハミルトニアンの基底状態を見つけることである。
基底状態特性を学習するためのシステムサイズ$n$とは無関係に,一定のサンプル複雑性を実現する2つのアプローチを導入する。
論文 参考訳(メタデータ) (2024-05-28T18:00:32Z) - Accelerated quantum search using partial oracles and Grover's algorithm [0.0]
グロバーのアルゴリズム(英: Grover's algorithm)は、順序のないデータベースを探索する手段として考案されたアルゴリズムであり、量子計算によって生成される結果集合から解を抽出するためにも用いられる。
マッチング条件の各ビットに個別のオラクルを関連付け、独立にテスト可能な複数の部分的なオラクル関数を得るという考え方を探求する。
アルゴリズムは最も単純な検索シナリオに対して検証され、入力されたインデックスビットは置換演算を用いてスクランブルされる。
論文 参考訳(メタデータ) (2024-03-19T11:32:02Z) - Quantum algorithm for position weight matrix matching [0.9404723842159504]
バイオインフォマティクス, 位置重み行列(PWM)マッチングにおける問題に対する2つの量子アルゴリズムを提案する。
提案した2つのアルゴリズム、ナイーブ法とモンテカルロ法は、生物学的配列のエントリへの分子アクセスを考慮し、一致したセグメントを出力する。
論文 参考訳(メタデータ) (2023-03-07T00:34:16Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳(メタデータ) (2023-03-03T18:23:20Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳(メタデータ) (2023-02-13T22:51:07Z) - Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer [2.487445341407889]
Depth-First SearchとGroverのアルゴリズムを組み合わせてDepth-First Grover Search(DFGS)を生成する
DFGSは未知の解数で非構造化データベース上の複数解探索問題を処理する。
新しいアルゴリズムは$mathcalO(msqrtN)$の平均複雑さを達成し、通常のGrover Searchと同じくらい効率的に機能する。
論文 参考訳(メタデータ) (2022-10-10T13:10:28Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - Quadratic Quantum Speedup for Perceptron Training [0.0]
バイナリ分類を行うパーセプトロンは、ニューラルネットワークの基本的な構成要素である。
パーセプトロンのためのオラクルを構築するためのクエリの複雑さは、古典的手法よりも2次的に改善されていることを示す。
我々のアルゴリズムはニューラルネットワークのようなより複雑な機械学習モデルを訓練するために一般化することができる。
論文 参考訳(メタデータ) (2021-09-10T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。