論文の概要: Quantum Walks on Simplicial Complexes and Harmonic Homology: Application to Topological Data Analysis with Superpolynomial Speedups
- arxiv url: http://arxiv.org/abs/2404.15407v1
- Date: Tue, 23 Apr 2024 18:00:17 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-25 15:32:53.996001
- Title: Quantum Walks on Simplicial Complexes and Harmonic Homology: Application to Topological Data Analysis with Superpolynomial Speedups
- Title(参考訳): 単純コンプレックスの量子ウォークと調和ホモロジー:スーパーポリノミカルスピードアップを用いたトポロジカルデータ解析への応用
- Authors: Ryu Hayakawa, Kuo-Chin Chen, Min-Hsiu Hsieh,
- Abstract要約: ラプラシアン(Laplacian)は、スペクトル特性が基礎となる単体錯体を反映する重要な数学的対象である。
以上の結果から,大規模データセットの量子オラクルを必要とせずに,量子ウォークによる超ポリノミカル量子スピードアップを実現した。
- 参考スコア(独自算出の注目度): 9.538251541300028
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Incorporating higher-order interactions in information processing enables us to build more accurate models, gain deeper insights into complex systems, and address real-world challenges more effectively. However, existing methods, such as random walks on oriented simplices and homology, which capture these interactions, are not known to be efficient. This work investigates whether quantum walks on simplicial complexes exhibit quantum advantages. We introduce a novel quantum walk that encodes the combinatorial Laplacian, a key mathematical object whose spectral properties reflect the topology of the underlying simplicial complex. Furthermore, we construct a unitary encoding that projects onto the kernel of the Laplacian, representing the space of harmonic cycles in the complex's homology. Combined with the efficient construction of quantum walk unitaries for clique complexes that we present, this paves the way for utilizing quantum walks to explore higher-order interactions within topological structures. Our results achieve superpolynomial quantum speedup with quantum walks without relying on quantum oracles for large datasets. Crucially, the walk operates on a state space encompassing both positively and negatively oriented simplices, effectively doubling its size compared to unoriented approaches. Through coherent interference of these paired simplices, we are able to successfully encode the combinatorial Laplacian, which would otherwise be impossible. This observation constitutes our major technical contribution. We also extend the framework by constructing variant quantum walks. These variants enable us to: (1) estimate the normalized persistent Betti numbers, capturing topological information throughout a deformation process, and (2) verify a specific QMA$_1$-hard problem, showcasing potential applications in computational complexity theory.
- Abstract(参考訳): 情報処理に高次のインタラクションを組み込むことで、より正確なモデルの構築、複雑なシステムに対する深い洞察の獲得、現実の課題へのより効果的な対処が可能になる。
しかし、これらの相互作用をとらえるランダムウォークやホモロジーのような既存の手法は効率的ではない。
本研究は, 単純錯体上の量子ウォークが量子的優位性を示すかどうかを考察する。
合成ラプラシアン(Laplacian)を符号化する新しい量子ウォークを導入する。これは、スペクトル特性が基礎となる単体複合体の位相を反映する重要な数学的対象である。
さらに、複素体のホモロジーにおける調和サイクルの空間を表すラプラシアンの核に射影するユニタリ符号化を構築する。
私たちが提示した斜め複体に対する量子ウォークユニタリの効率的な構築と組み合わせることで、この方法では、トポロジカル構造内の高次相互作用を量子ウォークを利用することができる。
以上の結果から,大規模データセットの量子オラクルを必要とせずに,量子ウォークによる超ポリノミカル量子スピードアップを実現した。
重要なことに、ウォークは正の向きと負の向きの両方を包含する状態空間で動作し、非向きのアプローチと比較してそのサイズを効果的に倍増させる。
これらの対の単純さのコヒーレントな干渉により、組み合わせラプラシアンをエンコードすることができ、そうでなければ不可能である。
この観察は我々の主要な技術的貢献を構成する。
また、可変量子ウォークを構築することで、フレームワークを拡張します。
これらの変種は、(1)正規化された持続ベッチ数を推定し、変形過程を通して位相情報をキャプチャし、(2)特定のQMA$_1$-hard問題を検証することにより、計算複雑性理論における潜在的な応用を示す。
関連論文リスト
- Complex-Phase Extensions of Szegedy Quantum Walk on Graphs [0.0]
この研究は、リンク位相と局所任意位相回転(APR)を組み込んだグラフ相Szegedyの量子ウォークを導入する。
我々はこれらの進歩に量子回路を適応させる方法を示し、計算実用性を保証する位相パターンを実現する。
我々の発見は、より汎用的で強力な量子コンピューティングパラダイムへの道のりを照らしている。
論文 参考訳(メタデータ) (2024-10-29T12:57:31Z) - Complexity of Quantum-Mechanical Evolutions from Probability Amplitudes [0.0]
本研究では,フビニ・スタディ計量を備えたブロッホ球面上の任意のソースとターゲット状態とを接続する時間-最適および時間-最適量子ハミルトン進化の複雑さについて検討する。
論文 参考訳(メタデータ) (2024-08-26T12:54:51Z) - Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳(メタデータ) (2024-08-22T08:21:28Z) - Quantum walk on simplicial complexes for simplicial community detection [0.0]
単純コミュニティと呼ばれる高次コミュニティ構造を検出するための量子ウォークアルゴリズムを提案する。
我々の量子アルゴリズムのポテンシャルは、ザカリーの空手部ネットワークでテストされている。
論文 参考訳(メタデータ) (2024-01-01T08:43:43Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳(メタデータ) (2023-10-04T17:53:55Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳(メタデータ) (2022-03-30T02:02:16Z) - Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice [1.286202369590401]
2次元正方格子上の単一原子の連続時間量子ウォークについて検討する。
これらのウォークを用いた空間探索の実証実験を行う。
より多くの粒子にスケールすると、ここで示される能力は、量子情報科学の様々な問題を研究するために拡張することができる。
論文 参考訳(メタデータ) (2022-02-02T18:56:11Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳(メタデータ) (2021-08-03T17:49:09Z) - Learning quantum phases via single-qubit disentanglement [4.266508670102269]
本稿では、強化学習最適化変分量子回路による解離を利用した、新しい、効率的な量子位相遷移を提案する。
提案手法は, 分離回路の性能に基づく位相遷移を同定するだけでなく, 拡張性にも優れ, より大規模で複雑な量子システムへの応用が促進される。
論文 参考訳(メタデータ) (2021-07-08T00:15:31Z) - Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。
量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。
我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
論文 参考訳(メタデータ) (2021-06-11T18:00:09Z) - Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
53量子ビット量子プロセッサにおける量子スクランブルのダイナミクスを実験的に検討する。
演算子の拡散は効率的な古典的モデルによって捉えられるが、演算子の絡み合いは指数関数的にスケールされた計算資源を必要とする。
論文 参考訳(メタデータ) (2021-01-21T22:18:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。