論文の概要: Quantum algorithms for Hopcroft's problem

• arxiv url: http://arxiv.org/abs/2405.01160v1
• Date: Thu, 2 May 2024 10:29:06 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-03 16:54:18.397014
• Title: Quantum algorithms for Hopcroft's problem
• Title（参考訳）: ホップクロフト問題に対する量子アルゴリズム
• Authors: Vladimirs Andrejevs, Aleksandrs Belovs, Jevgēnijs Vihrovs,
• Abstract要約: 計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
• 参考スコア（独自算出の注目度）: 45.45456673484445
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work we study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. Given $n$ points and $n$ lines in the plane, the task is to determine whether there is a point-line incidence. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n^{4/3})$ time, with matching lower bounds in some restricted settings. Our results are two different quantum algorithms with time complexity $\widetilde O(n^{5/6})$. The first algorithm is based on partition trees and the quantum backtracking algorithm. The second algorithm uses a quantum walk together with a history-independent dynamic data structure for storing line arrangement which supports efficient point location queries. In the setting where the number of points and lines differ, the quantum walk-based algorithm is asymptotically faster. The quantum speedups for the aforementioned data structures may be useful for other geometric problems.
• Abstract（参考訳）: 本研究では,計算幾何学の基本問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 平面上の$n$ポイントと$n$ラインが与えられたとき、そのタスクはポイントラインインシデントがあるかどうかを決定することである。 この問題の古典的な複雑さはよく研究されており、最もよく知られたアルゴリズムは$O(n^{4/3})$時間で実行され、いくつかの制限された設定では低い境界が一致する。 我々の結果は、時間複雑性が$\widetilde O(n^{5/6})$の2つの異なる量子アルゴリズムである。 最初のアルゴリズムはパーティションツリーと量子バックトラックアルゴリズムに基づいている。 第2のアルゴリズムは、効率的なポイントロケーションクエリをサポートするラインアレンジメントを格納するために、歴史に依存しない動的データ構造とともに量子ウォークを使用する。 点数と線数が異なる場合、量子ウォークベースのアルゴリズムは漸近的に高速である。 上記のデータ構造に対する量子スピードアップは他の幾何学的問題に有用かもしれない。

関連論文リスト

• 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)
• Quantum optimization algorithm based on multistep quantum computation [0.0]
  本稿では,多段階量子計算に基づく関数の最小値を求める量子アルゴリズムを提案する。 このアルゴリズムでは、問題の探索空間の次元を指数関数的に段階的に減らすことができる。 連続的なテスト関数のアルゴリズムを検証した。
  論文  参考訳（メタデータ） (2023-06-30T01:58:23Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Manifold Learning for Dimensionality Reduction: Quantum Isomap algorithm [15.622577797491788]
  イソマプアルゴリズムは、ニューロイメージング、スペクトル分析、その他の分野で広く用いられている。 本稿では,2つのサブアルゴリズムからなる量子イソマプアルゴリズムを提案する。 量子イソマップアルゴリズムの時間複雑性は$O(dNpolylogN)$である。
  論文  参考訳（メタデータ） (2022-12-07T12:29:41Z)
• Quantum algorithms and the power of forgetting [1.5791732557395555]
  本研究では,効率の良い量子アルゴリズムの自然なクラスは,ENTRANCEからEXITへの経路を確実に見つけることができないことを示す。 このことは、効率的に経路を見つける量子アルゴリズムの可能性を排除するものではないが、アルゴリズムがこの振る舞いからどのような恩恵を受けるかは定かではない。
  論文  参考訳（メタデータ） (2022-11-22T18:04:10Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• 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)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。 本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
  論文  参考訳（メタデータ） (2021-06-11T09:43:09Z)
• Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
  量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。 本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
  論文  参考訳（メタデータ） (2021-05-18T06:51:11Z)

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

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