Fugu-MT 論文翻訳(概要): Quantum Algorithm for the Longest Trail Problem

論文の概要: Quantum Algorithm for the Longest Trail Problem

arxiv url: http://arxiv.org/abs/2112.13847v1
Date: Mon, 27 Dec 2021 09:42:19 GMT
ステータス: 処理完了
システム内更新日: 2023-03-03 03:46:00.002848
Title: Quantum Algorithm for the Longest Trail Problem
Title（参考訳）: 最も長い経路問題に対する量子アルゴリズム
Authors: Kamil Khadiev and Ruslan Kapralov
Abstract要約: 最長経路問題に対する量子アルゴリズムを提案する。アルゴリズムの実行時間は$O* (1.728m)$である。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We present the quantum algorithm for the Longest Trail Problem. The problem is to search the longest edge-simple path for a graph with $n$ vertexes and $m$ edges. Here edge-simple means no edge occurs in the path twice, but vertexes can occur several times. The running time of our algorithm is $O^*(1.728^m)$.
Abstract（参考訳）: 我々は,最も長い追跡問題に対する量子アルゴリズムを提案する。問題は、$n$の頂点と$m$の辺を持つグラフの最長の辺単純パスを検索することだ。ここでは、エッジは2回も経路内では発生しないが、頂点は数回発生することがある。アルゴリズムの実行時間は$O^*(1.728^m)$である。

関連論文リスト

Advances in quantum algorithms for the shortest path problem [0.18416014644193066]
我々は、構造化インスタンスの問題を解くために、隣接リストモデルに2つの有界エラー量子アルゴリズムを与える。最初のアプローチは、量子フロー状態をサンプリングし、より小さな問題に対して古典的なアルゴリズムを実行することによって、元のグラフをスパース化することに基づいている。 2つ目のアプローチは、$tildeO(lsqrtm)$ stepsで最も短いパスを出力する分割および征服手順に基づいている。
論文参考訳（メタデータ） (2024-08-19T21:30:02Z)
Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文参考訳（メタデータ） (2024-05-02T10:29:06Z)
A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文参考訳（メタデータ） (2024-02-09T19:01:48Z)
Exponential speedup of quantum algorithms for the pathfinding problem [5.260626311429307]
非重みのないグラフで$s, t$が与えられたとき、パスフィンディング問題の目標は、$s$-$t$パスを見つけることである。溶接木に基づいてグラフ$G$を構築し、隣接リスト oracle $O$ でパスフィニング問題を定義する。古典的なアルゴリズムが確率の高い指数時間で$s$-$t$パスを見つけることはできないことを証明している。
論文参考訳（メタデータ） (2023-07-24T02:50:34Z)
Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem [2.107421958337625]
有限グラフ $(X,E)$ に対する逆問題を考える。この問題には特定の条件下でのユニークな解法があることを示し、量子計算法を開発した。
論文参考訳（メタデータ） (2023-06-08T14:48:48Z)
Quantum Algorithm for Dynamic Programming Approach for DAGs and Applications [0.0]
有向非巡回グラフ(DAG)問題に対する動的プログラミング手法のための量子アルゴリズムを提案する。 OR, AND, NAND, MAX, MIN 関数を主な遷移ステップとする問題を解くことができることを示す。
論文参考訳（メタデータ） (2022-12-29T19:07:39Z)
Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文参考訳（メタデータ） (2022-12-03T02:45:23Z)
Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文参考訳（メタデータ） (2022-04-13T22:18:47Z)
Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis [69.08838724594584]
グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
論文参考訳（メタデータ） (2021-12-08T08:23:37Z)
Leveraging Unknown Structure in Quantum Query Algorithms [0.0]
本研究では,事前の約束がなくても,これらのスピードアップが持続することを示すために,修正されたスパンプログラムアルゴリズムを示す。我々のアルゴリズムは、$tildeO(sqrtkn)$クエリを使って、少なくとも$k$のエッジを持つパスがある場合、この問題を解決する。
論文参考訳（メタデータ） (2020-12-02T15:32:52Z)
Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文参考訳（メタデータ） (2020-02-20T17:52:18Z)

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