論文の概要: Randomized SearchRank: A Semiclassical Approach to a Quantum Search
Engine
- arxiv url: http://arxiv.org/abs/2401.01554v1
- Date: Wed, 3 Jan 2024 06:00:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-04 14:56:29.277239
- Title: Randomized SearchRank: A Semiclassical Approach to a Quantum Search
Engine
- Title（参考訳）: ランダム化サーチランク:量子検索エンジンへの半古典的アプローチ
- Authors: Sergio A. Ortega, Miguel A. Martin-Delgado
- Abstract要約: 量子検索Rankアルゴリズムは、PageRank量子化に基づく将来の量子検索エンジンにとって有望なツールである。
本稿では,基礎となるSzegedy量子ウォークを半古典的なウォークに置き換えたアルゴリズムの修正を提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The quantum SearchRank algorithm is a promising tool for a future quantum
search engine based on PageRank quantization. However, this algorithm loses its
functionality when the $N/M$ ratio between the network size $N$ and the number
of marked nodes $M$ is sufficiently large. We propose a modification of the
algorithm, replacing the underlying Szegedy quantum walk with a semiclassical
walk. To maintain the same time complexity as the quantum SearchRank algorithm
we propose a simplification of the algorithm. This new algorithm is called
Randomized SearchRank, since it corresponds to a quantum walk over a randomized
mixed state. The performance of the SearchRank algorithms is first analyzed on
an example network, and then statistically on a set of different networks of
increasing size and different number of marked nodes. On the one hand, to test
the search ability of the algorithms, it is computed how the probability of
measuring the marked nodes decreases with $N/M$ for the quantum SearchRank, but
remarkably it remains at a high value around $0.9$ for our semiclassical
algorithms, solving the quantum SearchRank problem. The time complexity of the
algorithms is also analyzed, obtaining a quadratic speedup with respect to the
classical ones. On the other hand, the ranking functionality of the algorithms
has been investigated, obtaining a good agreement with the classical PageRank
distribution. Finally, the dependence of these algorithms on the intrinsic
PageRank damping parameter has been clarified. Our results suggest that this
parameter should be below a threshold so that the execution time does not
increase drastically.
- Abstract（参考訳）: 量子検索Rankアルゴリズムは、PageRank量子化に基づく将来の量子検索エンジンにとって有望なツールである。
しかし、ネットワークサイズ$n$とマークされたノード数$m$の比が十分大きいと、このアルゴリズムは機能を失う。
本稿では,基礎となるSzegedy量子ウォークを半古典的なウォークに置き換えたアルゴリズムの修正を提案する。
量子サーチランクアルゴリズムと同じ時間の複雑さを維持するために,アルゴリズムの単純化を提案する。
このアルゴリズムはランダム化検索Rankと呼ばれ、ランダム化混合状態上の量子ウォークに対応する。
検索ランクアルゴリズムのパフォーマンスは、まずサンプルネットワーク上で解析され、その後、サイズとマークされたノード数の異なるネットワーク群で統計的に解析される。
一方、アルゴリズムの探索能力をテストするために、マークされたノードを測定する確率が量子検索Rankに対して$N/M$と小さくなるかを計算するが、量子検索Rank問題を解くことで、我々の半古典的アルゴリズムに対して$0.9$の高値のままである。
アルゴリズムの時間複雑性も解析され、古典的なアルゴリズムに対する2次的なスピードアップが得られる。
一方,アルゴリズムのランキング機能について検討し,従来のPageRank分布とよく一致している。
最後に、これらのアルゴリズムが本質的なPageRank減衰パラメータに依存することを明らかにする。
その結果,このパラメータはしきい値以下であるべきであり,実行時間が大幅に増加しないことが示唆された。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。
この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
論文 参考訳（メタデータ） (2023-11-17T20:38:38Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Experimentally demonstrating indefinite causal order algorithms to solve
the generalized Deutsch's problem [4.555392897705548]
Deutschのアルゴリズムは、古典的アルゴリズムよりも優位性を示す最初の量子アルゴリズムである。
この問題を解決するために、不明確な因果順序を持つ新しい量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-05-09T13:04:28Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Generalized Quantum Google PageRank Algorithm with Arbitrary Phase
Rotations [0.0]
本稿では、Szegedyの量子ウォークに任意の位相回転(APR)を導入する量子PageRankの修正を提案する。
そこで我々は,新しいアルゴリズムの挙動を解析し,位相の減少がPageRankの標準偏差を減少させることを示した。
我々は、PageRank分布が古典的アルゴリズムに似ている新しいアルゴリズムの1つが、元の量子アルゴリズムに類似した安定性があることを発見した。
論文 参考訳（メタデータ） (2022-09-27T15:15:54Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
既存の量子ウォークに基づく探索アルゴリズムは、サッフル問題に悩まされている。
量子スピードアップを犠牲にすることなくロバスト性を実現する新しい量子ウォークベースの探索フレームワークを提案する。
論文 参考訳（メタデータ） (2021-11-17T10:04:44Z) - Hardware Efficient Quantum Search Algorithm [17.74233101199813]
本稿では,この課題を克服するために,ハードウェアの効率的な量子探索アルゴリズムを提案する。
我々の鍵となる考え方は、グローバル拡散操作を低コストな局所拡散に置き換えることである。
回路コストの削減は、システムの成功率を著しく向上させる。
論文 参考訳（メタデータ） (2021-03-26T01:08:50Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - TensorFlow Solver for Quantum PageRank in Large-Scale Networks [12.937513443750804]
本稿では, 並列計算を用いて, 行列次元を O(N2) に減少させるために, Runge-Kutta 法による量子ページランクの効率的な解法を提案する。
従来のPageRankソルバと比較して、必要なメモリと時間をそれぞれ1%と0.2%に劇的に削減し、100秒未満で4～8GBのメモリを持つ通常のコンピュータで動作できるようにする。
論文 参考訳（メタデータ） (2020-03-10T18:58:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。