論文の概要: TensorFlow Solver for Quantum PageRank in Large-Scale Networks
- arxiv url: http://arxiv.org/abs/2003.04930v1
- Date: Tue, 10 Mar 2020 18:58:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-30 00:56:01.621453
- Title: TensorFlow Solver for Quantum PageRank in Large-Scale Networks
- Title(参考訳): 大規模ネットワークにおける量子ページランクのためのTensorFlowソルバー
- Authors: Hao Tang, Tian-Shen He, Ruo-Xi Shi, Yan-Yan Zhu, Marcus Lee, Tian-Yu
Wang, Xian-Min Jin
- Abstract要約: 本稿では, 並列計算を用いて, 行列次元を O(N2) に減少させるために, Runge-Kutta 法による量子ページランクの効率的な解法を提案する。
従来のPageRankソルバと比較して、必要なメモリと時間をそれぞれ1%と0.2%に劇的に削減し、100秒未満で4~8GBのメモリを持つ通常のコンピュータで動作できるようにする。
- 参考スコア(独自算出の注目度): 12.937513443750804
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Google PageRank is a prevalent and useful algorithm for ranking the
significance of nodes or websites in a network, and a recent quantum
counterpart for PageRank algorithm has been raised to suggest a higher accuracy
of ranking comparing to Google PageRank. The quantum PageRank algorithm is
essentially based on quantum stochastic walks and can be expressed using
Lindblad master equation, which, however, needs to solve the Kronecker products
of an O(N^4) dimension and requires severely large memory and time when the
number of nodes N in a network increases above 150. Here, we present an
efficient solver for quantum PageRank by using the Runge-Kutta method to reduce
the matrix dimension to O(N^2) and employing TensorFlow to conduct GPU parallel
computing. We demonstrate its performance in solving quantum PageRank for the
USA major airline network with up to 922 nodes. Compared with the previous
quantum PageRank solver, our solver dramatically reduces the required memory
and time to only 1% and 0.2%, respectively, making it practical to work in a
normal computer with a memory of 4-8 GB in no more than 100 seconds. This
efficient solver for large-scale quantum PageRank and quantum stochastic walks
would greatly facilitate studies of quantum information in real-life
applications.
- Abstract(参考訳): Google PageRankは、ネットワーク内のノードやWebサイトの重要度をランク付けするための一般的かつ有用なアルゴリズムである。
量子ページランクアルゴリズムは本質的に量子確率的ウォークに基づいており、リンドブラッドマスター方程式を用いて表現することができるが、これはo(n^4)次元のクロネッカー積を解く必要があり、ネットワーク内のノードn数が150を超える場合、非常に大きなメモリと時間を必要とする。
本稿では,Lange-Kutta法を用いて行列次元をO(N^2)に減らし,TensorFlowを用いてGPU並列計算を行うことにより,量子PageRankの効率的な解法を提案する。
最大922ノードを持つ米国の主要航空会社ネットワークに対して、量子PageRankを解く際の性能を実証する。
従来の量子ページランクソルバと比較して,100秒未満でメモリ4-8gbの通常のコンピュータで動作するためには,必要なメモリと時間を1%と0.2%に劇的に削減できる。
この大規模量子PageRankと量子確率ウォークの効率的な解法は、現実の応用における量子情報の研究を大いに促進する。
関連論文リスト
- QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum
Circuits [82.50620782471485]
QuantumSEAはノイズ適応型量子回路のインタイムスパース探索である。
1)トレーニング中の暗黙の回路容量と(2)雑音の頑健さの2つの主要な目標を達成することを目的としている。
提案手法は, 量子ゲート数の半減と回路実行の2倍の時間節約で, 最先端の計算結果を確立する。
論文 参考訳(メタデータ) (2024-01-10T22:33:00Z) - Randomized SearchRank: A Semiclassical Approach to a Quantum Search
Engine [0.0]
量子検索Rankアルゴリズムは、PageRank量子化に基づく将来の量子検索エンジンにとって有望なツールである。
本稿では,基礎となるSzegedy量子ウォークを半古典的なウォークに置き換えたアルゴリズムの修正を提案する。
論文 参考訳(メタデータ) (2024-01-03T06:00:23Z) - 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) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳(メタデータ) (2023-04-18T11:57:15Z) - 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) - Quantum Speedup for Higher-Order Unconstrained Binary Optimization and
MIMO Maximum Likelihood Detection [2.5272389610447856]
実数値の高次非制約二項最適化問題をサポートする量子アルゴリズムを提案する。
提案アルゴリズムは,古典的領域におけるクエリの複雑さを低減し,量子領域における2次高速化を実現する。
論文 参考訳(メタデータ) (2022-05-31T00:14:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Spatial search by continuous-time quantum walks on renormalized Internet
networks [0.0]
実世界の複雑なネットワーク上での連続的な量子ウォークを用いた空間探索について検討する。
実世界の複素ネットワーク上での量子空間探索アルゴリズムの挙動を初めて推測する。
論文 参考訳(メタデータ) (2022-05-04T15:46:14Z) - Quantum Search for Scaled Hash Function Preimages [1.3299507495084417]
本稿では,Groverのアルゴリズムを量子シミュレーターに実装し,2つのスケールしたハッシュ関数の前像の量子探索を行う。
我々は,Groverのアルゴリズムのいくつかのステップの後に量子レジスタをサンプリングしてショートカットを提案する戦略は,誤差軽減の観点からは限界的な実用的優位性しか得られないことを示した。
論文 参考訳(メタデータ) (2020-09-01T18:00:02Z) - Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
Googleの最近の量子超越性実験は、量子コンピューティングがランダムな回路サンプリングという計算タスクを実行する遷移点を示している。
観測された量子ランタイムの利点の制約を、より多くの量子ビットとゲートで検討する。
論文 参考訳(メタデータ) (2020-05-05T20:11:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。