論文の概要: 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つの曲線がホモトピー的に同値でないかどうかを確認することに応用できる。
関連論文リスト
- Quantum Algorithms for the Pathwise Lasso [1.9374282535132377]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
論文 参考訳(メタデータ) (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 [44.99833362998488]
本稿では,3次元非拘束二項最適化(QUBO)問題と準拘束非拘束離散最適化(QUDO)問題を一方の相互作用で解くアルゴリズムを提案する。
提案手法は, 仮想時間進化を適用し, 最大振幅を得るために一連の部分的トレースを行う量子状態のシミュレーションに基づく。
論文 参考訳(メタデータ) (2023-09-19T10:45:15Z) - Classically efficient regimes in measurement based quantum computation
performed using diagonal two qubit gates and cluster measurements [0.0]
これにより、CZゲートを越えてarXiv:2201.07655v2の計算を拡張できる。
任意の有限次グラフに対して、純粋な絡み合った量子状態の2つのパラメータ族を記述することができる。
論文 参考訳(メタデータ) (2023-07-04T16:09:24Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳(メタデータ) (2022-12-13T16:04:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Quantum Persistent Homology for Time Series [0.9023847175654603]
永続ホモロジー(Persistent homology)は、異なるスケールの変化をまたいだトポロジ的特徴を追跡することによって、データの形状を要約する。
永続ホモロジーの2つの量子アルゴリズムは、2つの異なるアプローチに基づいて開発されている。
本稿では,量子ケインの遅延埋め込みアルゴリズムを構築し,時系列を点雲に変換する。
この時間列から点雲への量子変換を持つと、点雲から位相的特徴を抽出するために量子永続ホモロジーアルゴリズムを用いることができる。
論文 参考訳(メタデータ) (2022-11-08T18:58:18Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳(メタデータ) (2022-10-12T19:10:43Z) - Quantum algorithms for grid-based variational time evolution [36.136619420474766]
本稿では,第1量子化における量子力学の実行のための変分量子アルゴリズムを提案する。
シミュレーションでは,従来観測されていた変動時間伝播手法の数値不安定性を示す。
論文 参考訳(メタデータ) (2022-03-04T19:00:45Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。