Fugu-MT 論文翻訳(概要): Quantum Algorithm for Path-Edge Sampling

論文の概要: Quantum Algorithm for Path-Edge Sampling

arxiv url: http://arxiv.org/abs/2303.03319v1
Date: Mon, 6 Mar 2023 17:45:12 GMT
ステータス: 処理完了
システム内更新日: 2023-03-07 15:10:55.888218
Title: Quantum Algorithm for Path-Edge Sampling
Title（参考訳）: パスエッジサンプリングのための量子アルゴリズム
Authors: Stacey Jeffery, Shelby Kimmel, Alvaro Piedrafita
Abstract要約: 隣接行列として与えられる無向グラフにおいて、2つのノード s と t の間の経路上のエッジをサンプリングする量子アルゴリズムを提案する。我々は,この経路サンプリングアルゴリズムを,特定のケースにおいてst-path検索およびst-cut-set発見アルゴリズムのサブルーチンとして利用する。
参考スコア（独自算出の注目度）: 0.9990687944474739
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We present a quantum algorithm for sampling an edge on a path between two nodes s and t in an undirected graph given as an adjacency matrix, and show that this can be done in query complexity that is asymptotically the same, up to log factors, as the query complexity of detecting a path between s and t. We use this path sampling algorithm as a subroutine for st-path finding and st-cut-set finding algorithms in some specific cases. Our main technical contribution is an algorithm for generating a quantum state that is proportional to the positive witness vector of a span program.
Abstract（参考訳）: 隣接行列として与えられる無向グラフにおいて、2つのノード s と t の間の経路上のエッジをサンプリングする量子アルゴリズムを提案し、これは s と t の間の経路を検出するクエリの複雑さとして、漸近的に同じクエリの複雑さで実現できることを示す。我々はこの経路サンプリングアルゴリズムを,特定のケースにおいてst-path検索およびst-cut-set発見アルゴリズムのサブルーチンとして利用する。我々の主な技術的貢献は、スパンプログラムの正の証人ベクトルに比例する量子状態を生成するアルゴリズムである。

関連論文リスト

A quantum algorithm for advection-diffusion equation by a probabilistic imaginary-time evolution operator [0.0]
本稿では, 線形対流拡散方程式を, 新しい近似確率的想像時間進化(PITE)演算子を用いて解く量子アルゴリズムを提案する。我々は, 対流拡散方程式から得られるハミルトニアンの想像時間進化を実現するために, 明示的な量子回路を構築した。我々のアルゴリズムは、Harrow-Hassidim-Lloyd (HHL)アルゴリズムに匹敵する結果を与える。
論文参考訳（メタデータ） (2024-09-27T08:56:21Z)
Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。 3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文参考訳（メタデータ） (2023-11-19T00:06:11Z)
Quantum-Based Feature Selection for Multi-classification Problem in Complex Systems with Edge Computing [15.894122816099133]
マルチクラス化問題,すなわちQReliefFに対する量子ベースの特徴選択アルゴリズムを提案する。我々のアルゴリズムは、O(M) から O(sqrt(M)) への複雑さを減らし、最も近い隣人を見つけるのに優れている。
論文参考訳（メタデータ） (2023-10-01T03:57:13Z)
On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。 A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
論文参考訳（メタデータ） (2023-08-23T08:38:53Z)
Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文参考訳（メタデータ） (2023-06-21T17:03:22Z)
Locality-aware Qubit Routing for the Grid Architecture [1.4459640831465588]
本稿では,グラフ理論に基づく局所性を考慮した量子ビットルーティングアルゴリズムを提案する。我々のアルゴリズムはグリッドとある種の"グリッドのような"アーキテクチャのために設計されている。
論文参考訳（メタデータ） (2022-03-21T20:46:39Z)
Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
論文参考訳（メタデータ） (2021-11-19T12:35:26Z)
Quantum Algorithms for Prediction Based on Ridge Regression [0.7612218105739107]
本稿では,リッジ回帰モデルに基づく量子アルゴリズムを提案する。提案アルゴリズムは幅広い応用範囲を持ち,提案アルゴリズムは他の量子アルゴリズムのサブルーチンとして利用することができる。
論文参考訳（メタデータ） (2021-04-27T11:03:52Z)
Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文参考訳（メタデータ） (2020-07-01T18:43:32Z)
Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
データの次元にほぼ線形なサンプル複雑性を持つ量子化損失関数の行サンプリングアルゴリズムを提案する。行サンプリングアルゴリズムに基づいて、量子レグレッションの最も高速なアルゴリズムと、バランスの取れた有向グラフのグラフスペーシフィケーションアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-06-15T13:40:07Z)
A Heuristic Based on Randomized Greedy Algorithms for the Clustered Shortest-Path Tree Problem [2.099922236065961]
本稿では, RGA とショート・パス・ツリー・アルゴリズム (SPTA) の主な特徴を組み合わせたクラスタ・ショート・パス・ツリー問題 (CluSPT) を扱うアルゴリズムを提案する。提案アルゴリズムの性能を評価するため,ユークリッドベンチマークが選択される。
論文参考訳（メタデータ） (2020-05-05T08:34:58Z)

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