Fugu-MT 論文翻訳(概要): Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers

論文の概要: Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers

arxiv url: http://arxiv.org/abs/2407.20452v1
Date: Mon, 29 Jul 2024 23:16:23 GMT
ステータス: 処理完了
システム内更新日: 2024-07-31 18:38:42.413345
Title: Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers
Title（参考訳）: Quantum HodgeRank: 量子コンピュータにおけるトポロジに基づくランクアグリゲーション
Authors: Caesnan M. G. Leditto, Angus Southwell, Behnam Tonekaboni, Muhammad Usman, Kavan Modi,
Abstract要約: 我々は,HodgeRank解に比例した量子状態を出力する量子アルゴリズムを開発した。また、出力量子状態から有意義な情報を抽出する効率的なアルゴリズムを提案する。提案手法は,高次ネットワークや離散外部計算の研究において,量子コンピューティングが実りある応用を見出すことができることを示唆している。
参考スコア（独自算出の注目度）: 0.5490714603843316
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Rank aggregation techniques play a crucial role in identifying the best alternatives, but the inherent imbalance and incompleteness of real-world data pose significant challenges. The HodgeRank algorithm, which utilizes discrete exterior calculus on a graph, can overcome these issues and output a consistent global ranking of alternatives. Recently, higher-order networks have been employed to analyze complex multipartite interactions in network data. Extending HodgeRank to ranking on higher-order networks, however, requires computational costs that are exponential in the network dimension. To address this challenge, we develop a quantum algorithm that outputs a quantum state proportional to the HodgeRank solution. By incorporating quantum singular value transformation and tools from quantum topological data analysis, our approach achieves time complexity independent of the network dimension, avoiding the need for quantum random access memory or sparse access input models. We also present efficient algorithms and heuristics to extract meaningful information from the output quantum state, including an algorithm to compute the consistency of the ranking. Using our algorithm, the consistency measure estimation has the potential to achieve superpolynomial quantum speedups for higher-order network data with specific structures. Beyond ranking tasks, our methods suggest that quantum computing could find fruitful applications in studying higher-order networks and discrete exterior calculus.
Abstract（参考訳）: ランクアグリゲーション技術は、最良の選択肢を特定する上で重要な役割を担っているが、現実世界のデータの本質的な不均衡と不完全性は重大な課題を生んでいる。グラフ上の離散外部計算を利用するHodgeRankアルゴリズムは、これらの問題を克服し、一貫したグローバルな選択肢ランキングを出力することができる。近年,ネットワークデータの複雑なマルチパート間相互作用の解析に高次ネットワークが採用されている。しかし、HodgeRankを高階ネットワークのランキングに拡張するには、ネットワーク次元で指数関数的な計算コストが必要となる。この課題に対処するため,HodgeRank法に比例した量子状態を出力する量子アルゴリズムを開発した。量子特異値変換とツールを量子トポロジカルデータ解析から取り入れることで、量子ランダムアクセスメモリやスパースアクセス入力モデルの必要性を回避し、ネットワーク次元に依存しない時間複雑性を実現する。また、出力量子状態から有意な情報を抽出する効率的なアルゴリズムとヒューリスティックスを示し、ランキングの整合性を計算するアルゴリズムを含む。このアルゴリズムを用いることで、特定の構造を持つ高次ネットワークデータに対する超ポリノミカル量子スピードアップを実現することができる。ランク付けタスク以外にも、量子コンピューティングは高次ネットワークや離散外部計算の研究において実りある応用を見出すことができることを示唆している。

関連論文リスト

Discrete-Time Open Quantum Walks for Vertex Ranking in Graphs [0.0]
本稿では離散時間オープンな量子ウォークを用いたグラフ上の新しい量子PageRankアルゴリズムを提案する。 GoogleのPageRankは、古典的な計算でWorld Wide Web上のWebページをアレンジするための重要なアルゴリズムである。
論文参考訳（メタデータ） (2024-04-23T06:15:17Z)
Randomized SearchRank: A Semiclassical Approach to a Quantum Search Engine [0.0]
量子検索Rankアルゴリズムは、PageRank量子化に基づく将来の量子検索エンジンにとって有望なツールである。本稿では,基礎となるSzegedy量子ウォークを半古典的なウォークに置き換えたアルゴリズムの修正を提案する。
論文参考訳（メタデータ） (2024-01-03T06:00:23Z)
Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文参考訳（メタデータ） (2023-06-21T17:03:22Z)
Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。我々は距離の計算を高速化するために量子現象を利用する。我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文参考訳（メタデータ） (2022-12-13T16:04:16Z)
Exploring the role of parameters in variational quantum algorithms [59.20947681019466]
動的リー代数の階数を用いた変分量子回路のキャラクタリゼーションのための量子制御に着想を得た手法を提案する。有望な接続は、リーランク、計算されたエネルギーの精度、および所定の回路アーキテクチャを介して目標状態を達成するために必要な深さとの間のものである。
論文参考訳（メタデータ） (2022-09-28T20:24:53Z)
Quantum density peak clustering [5.8010446129208155]
最小値探索のための量子ルーチン上に構築された密度ピーククラスタリングアルゴリズムの量子バージョンを導入する。我々は,データセットの構造に応じて,密度ピーククラスタリングの決定版に対する量子スピードアップを証明した。
論文参考訳（メタデータ） (2022-07-21T15:58:40Z)
Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
論文参考訳（メタデータ） (2021-11-19T12:35:26Z)
Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文参考訳（メタデータ） (2021-05-23T19:21:55Z)
Quantum Ensemble for Classification [2.064612766965483]
機械学習のパフォーマンスを改善する強力な方法は、複数のモデルの予測を組み合わせたアンサンブルを構築することである。量子重ね合わせ,絡み合い,干渉を利用して分類モデルのアンサンブルを構築する新しい量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-07-02T11:26:54Z)
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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。