論文の概要: Implementation of Continuous-Time Quantum Walk on Sparse Graph
- arxiv url: http://arxiv.org/abs/2408.10553v1
- Date: Tue, 20 Aug 2024 05:20:55 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-21 15:03:52.608882
- Title: Implementation of Continuous-Time Quantum Walk on Sparse Graph
- Title（参考訳）: スパースグラフを用いた連続時間量子ウォークの実現
- Authors: Zhaoyang Chen, Guanzhong Li, Lvzhou Li,
- Abstract要約: 連続時間量子ウォーク(CTQW)は、量子コンピューティングにおいて重要な役割を果たす。
CTQWを効率的に実装する方法は難しい問題である。
本稿では,スパースグラフ上でのCTQWの実装について検討する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing, especially for designing quantum algorithms. However, how to efficiently implement CTQWs is a challenging issue. In this paper, we study implementation of CTQWs on sparse graphs, i.e., constructing efficient quantum circuits for implementing the unitary operator $e^{-iHt}$, where $H=\gamma A$ ($\gamma$ is a constant and $A$ corresponds to the adjacency matrix of a graph). Our result is, for a $d$-sparse graph with $N$ vertices and evolution time $t$, we can approximate $e^{-iHt}$ by a quantum circuit with gate complexity $(d^3 \|H\| t N \log N)^{1+o(1)}$, compared to the general Pauli decomposition, which scales like $(\|H\| t N^4 \log N)^{1+o(1)}$. For sparse graphs, for instance, $d=O(1)$, we obtain a noticeable improvement. Interestingly, our technique is related to graph decomposition. More specifically, we decompose the graph into a union of star graphs, and correspondingly, the Hamiltonian $H$ can be represented as the sum of some Hamiltonians $H_j$, where each $e^{-iH_jt}$ is a CTQW on a star graph which can be implemented efficiently.
- Abstract（参考訳）: 連続時間量子ウォーク(CTQW)は、特に量子アルゴリズムの設計において、量子コンピューティングにおいて重要な役割を果たす。
しかし、CTQWを効率的に実装する方法は難しい問題である。
本稿では,分散グラフ上でのCTQWの実装,すなわち,単位演算子$e^{-iHt}$を実装するための効率的な量子回路の構築について検討する。
我々の結果は、$N$頂点と進化時間$t$を持つ$d$スパースグラフに対して、ゲート複雑性を持つ量子回路$(d^3 \|H\| t N \log N)^{1+o(1)}$を、$(\|H\| t N^4 \log N)^{1+o(1)}$のようにスケールする一般的なパウリ分解と比較して近似することができる。
スパースグラフ、例えば$d=O(1)$の場合、顕著な改善が得られる。
興味深いことに,本手法はグラフ分解に関係している。
より具体的には、グラフを星グラフの和に分解し、それに対応するハミルトニアン$H$は、いくつかのハミルトニアン$H_j$の和として表すことができ、それぞれ$e^{-iH_jt}$は、効率的に実装できる星グラフ上のCTQWである。
関連論文リスト
- Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
低エネルギー部分空間内のハミルトン$H$の下で時間発展をシミュレートする作業を考える。
我々は,$O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$クエリを,任意の$Gamma$に対するブロックエンコーディングに使用する量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-04T17:58:01Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits [0.0]
量子回路におけるパターンマッチングを同時に行うアルゴリズムを提案する。
量子回路の場合、量子ビットの最大数から得られる境界を表現することができる。
論文 参考訳（メタデータ） (2023-02-13T22:09:02Z) - From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。
このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
論文 参考訳（メタデータ） (2023-02-06T15:14:34Z) - The Exact Class of Graph Functions Generated by Graph Neural Networks [43.25172578943894]
グラフ関数と出力が同一のグラフニューラルネットワーク(GNN)?
本稿では,この疑問に完全に答え,GNNで表現可能なグラフ問題のクラスを特徴付ける。
この条件は2次的に多くの制約をチェックすることで効率よく検証できることを示す。
論文 参考訳（メタデータ） (2022-02-17T18:54:27Z) - Solving Hamiltonian Cycle Problem using Quantum $\mathbb{Z}_2$ Lattice
Gauge Theory [9.83302372715731]
グラフ理論におけるハミルトンサイクル(HC)問題は、よく知られたNP完全問題である。
グラフを双対とする格子上で定義される$mathbbZ$格子ゲージ理論の観点でアプローチを提案する。
小さなグラフのランダムなサンプルでは、$sqrtN_hc$における$g_c$、$N_hc$がHCの数であり、$Nにおける$frac1g_c$の平均値に依存することが示される。
論文 参考訳（メタデータ） (2022-02-17T18:39:42Z) - Robust Estimation for Random Graphs [47.07886511972046]
我々は、$n$ノード上のErdHos-R'enyiランダムグラフのパラメータ$p$を頑健に推定する問題について検討する。
情報理論の限界であるすべての$gamma 1/2$に対して、同様の精度で非効率なアルゴリズムを与える。
論文 参考訳（メタデータ） (2021-11-09T18:43:25Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum
Security of iMHFs [6.305950347749109]
本稿では,量子コンピューティングにおけるNo-Deletion Theoremによる追加制約を捉える並列可逆ペブブリングゲームを提案する。
我々は、いくつかの重要なグラフの可逆空間時間複雑性を解析するために、新しい可逆ペブブリングゲームを適用した。
論文 参考訳（メタデータ） (2021-10-08T15:24:31Z) - A framework for optimal quantum spatial search using alternating
phase-walks [0.0]
我々は、マーク頂点位相シフトと連続時間量子ウォークの交互適用により、Childs & Goldstone(mathcalCG$)アルゴリズムを一般化する。
様々なグラフ上の$mathcalO(sqrtN)$検索にアルゴリズムを適用することで,アルゴリズムの有効性を実証する。
論文 参考訳（メタデータ） (2021-09-29T11:16:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。