論文の概要: 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)$ となる。
関連論文リスト
- Efficiency of k-Local Quantum Search and its Adiabatic Variant on Random
k-SAT [0.0]
本稿では、$k$-local quantum searchと呼ばれる、構造化量子探索アルゴリズムのファミリーを紹介する。
最大$k$-SSATは、平均ケース複雑性理論に基づく$m=Omega(n2+epsilon)$が平均であることを証明する。
論文 参考訳(メタデータ) (2024-03-05T15:03:47Z) - Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。
また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文 参考訳(メタデータ) (2023-06-30T20:36:44Z) - On sampling determinantal and Pfaffian point processes on a quantum
computer [49.1574468325115]
DPPは1970年代の量子光学のモデルとしてマッキによって導入された。
ほとんどのアプリケーションはDPPからのサンプリングを必要としており、その量子起源を考えると、古典的なコンピュータでDPPをサンプリングするのは古典的なものよりも簡単かどうか疑問に思うのが自然である。
バニラサンプリングは、各コスト$mathcalO(N3)$と$mathcalO(Nr2)$の2つのステップから構成される。
論文 参考訳(メタデータ) (2023-05-25T08:43:11Z) - 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) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳(メタデータ) (2021-06-04T02:32:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。