論文の概要: Constant-time Quantum Algorithm for Homology Detection in Closed Curves

• arxiv url: http://arxiv.org/abs/2209.12298v1
• Date: Sun, 25 Sep 2022 18:57:46 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-25 05:29:13.788938
• Title: Constant-time Quantum Algorithm for Homology Detection in Closed Curves
• Title（参考訳）: 閉曲線におけるホモロジー検出のための定数時間量子アルゴリズム
• Authors: Nhat A. Nghiem, Xianfeng David Gu, Tzu-Chieh Wei
• Abstract要約: 我々は、一定の実行時間でホモロジー検出のための量子アルゴリズムを設計する。 我々のアルゴリズムは、2つの閉ループが同じホモロジークラスに属するかどうかを確認するために拡張することができる。 これはホモトピー検出の特定の問題、すなわち閉2次元多様体上で2つの曲線がホモトピー的に同値でないかどうかを確認することに応用できる。
• 参考スコア（独自算出の注目度）: 1.392250707100996
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a loop or more generally 1-cycle $r$ on a closed two-dimensional manifold or surface, represented by a triangulated mesh, a question in computational topology asks whether or not it is homologous to zero. We frame and tackle this problem in the quantum setting. Given an oracle that one can use to query the inclusion of edges on a closed curve, we design a quantum algorithm for such a homology detection with a constant running time, with respect to the size or the number of edges on the loop $r$. In contrast, classical algorithms take a linear time. Our quantum algorithm can be extended to check whether two closed loops belong to the same homology class. Furthermore, it can be applied to a specific problem in the homotopy detection, namely, checking whether two curves are not homotopically equivalent on a closed two-dimensional manifold.
• Abstract（参考訳）: 閉2次元多様体または曲面上のループあるいはより一般に1-サイクル$r$が三角メッシュで表されるとき、計算トポロジーの問題は、それが零にホモロジーであるかどうかを問うものである。 我々はこの問題を量子的に解決し解決する。 閉曲線上の辺の包含を問合せに使用できる神託を考えると、ループ $r$ 上の辺のサイズまたは数に関して、一定の実行時間を持つそのようなホモロジー検出のための量子アルゴリズムを設計する。 対照的に、古典的なアルゴリズムは線形時間を要する。 我々の量子アルゴリズムは、2つの閉ループが同じホモロジークラスに属するかどうかを確認するために拡張することができる。 さらに、ホモトピー検出の特定の問題、すなわち閉2次元多様体上で2つの曲線がホモトピー的に同値でないかどうかを確認することに応用できる。

関連論文リスト

• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations [0.06022769903412461]
  本研究では,非構造探索手法を用いた断熱的量子最適化により,古典的局所スピンハミルトニアンのクラスに対する下界と一致するランニング時間が得られることを示す。 回避された交差の位置は、ハミルトニアン問題の退化と逆ギャップに依存し、低加算精度でも計算し難い量によってほぼ与えられることを示す。
  論文  参考訳（メタデータ） (2024-11-08T17:51:18Z)
• Constant-Time Quantum Search with a Many-Body Quantum System [39.58317527488534]
  並列クエリに自然に影響を及ぼす多体量子システムを考える。 パラメータを一定時間でデータベースを検索するように調整できることが示される。
  論文  参考訳（メタデータ） (2024-08-09T22:57:59Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
  古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。 我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。 我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
  論文  参考訳（メタデータ） (2023-12-21T18:57:54Z)
• The Power of Adaptivity in Quantum Query Algorithms [0.5702169790677977]
  問合せモデルにおける深度計算のトレードオフについて検討し、その深さは適応的な問合せラウンドの数と1ラウンド当たりの並列クエリ数に対応する。 我々は、量子アルゴリズム間の最も強力な分離を$r$対$r-1$の適応性を持つラウンドで達成する。
  論文  参考訳（メタデータ） (2023-11-27T18:21:32Z)
• Polynomial-time Solver of Tridiagonal QUBO and QUDO problems with Tensor Networks [41.94295877935867]
  本稿では,3次元非拘束二項最適化(QUBO)問題と準拘束非拘束離散最適化(QUDO)問題を一方の相互作用で解くアルゴリズムを提案する。 提案手法は, 仮想時間進化を適用し, 最大振幅を得るために一連の部分的トレースを行う量子状態のシミュレーションに基づく。
  論文  参考訳（メタデータ） (2023-09-19T10:45:15Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Quantum Persistent Homology for Time Series [0.9023847175654603]
  永続ホモロジー(Persistent homology)は、異なるスケールの変化をまたいだトポロジ的特徴を追跡することによって、データの形状を要約する。 永続ホモロジーの2つの量子アルゴリズムは、2つの異なるアプローチに基づいて開発されている。 本稿では,量子ケインの遅延埋め込みアルゴリズムを構築し,時系列を点雲に変換する。 この時間列から点雲への量子変換を持つと、点雲から位相的特徴を抽出するために量子永続ホモロジーアルゴリズムを用いることができる。
  論文  参考訳（メタデータ） (2022-11-08T18:58:18Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  量子計算の2つのモデル: CQ_dとQC_d。 CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。 CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
  論文  参考訳（メタデータ） (2022-01-06T03:10:53Z)
• 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)

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

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