論文の概要: The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
- arxiv url: http://arxiv.org/abs/2302.06717v2
- Date: Wed, 21 Feb 2024 06:48:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-22 21:31:04.861802
- Title: The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
- Title（参考訳）: ポートグラフと量子回路に対する部分グラフ同型問題
- Authors: Luca Mondada and Pablo Andr\'es-Mart\'inez
- Abstract要約: 量子回路におけるパターンマッチングを同時に行うアルゴリズムを提案する。
量子回路の場合、量子ビットの最大数から得られる境界を表現することができる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a variant of the subgraph isomorphism problem that is of high
interest to the quantum computing community. Our results give an algorithm to
perform pattern matching in quantum circuits for many patterns simultaneously,
independently of the number of patterns. After a pre-computation step in which
the patterns are compiled into a decision tree, the running time is linear in
the size of the input quantum circuit.
More generally, we consider connected port graphs, in which every edge $e$
incident to $v$ has a label $L_v(e)$ unique in $v$. Jiang and Bunke showed that
the subgraph isomorphism problem $H \subseteq G$ for such graphs can be solved
in time $O(|V(G)| \cdot |V(H)|)$. We show that if in addition the graphs are
directed acyclic, then the subgraph isomorphism problem can be solved for an
unbounded number of patterns simultaneously. We enumerate all $m$ pattern
matches in time $O(P)^{P+3/2} \cdot |V(G)| + O(m)$, where $P$ is the number of
vertices of the largest pattern. In the case of quantum circuits, we can
express the bound obtained in terms of the maximum number of qubits $N$ and
depth $\delta$ of the patterns : $O(N)^{N + 1/2} \cdot \delta \log \delta \cdot
|V(G)| + O(m)$.
- Abstract（参考訳）: 我々は,量子コンピューティングコミュニティに高い関心を持つ部分グラフ同型問題(subgraph isomorphism problem)の変種について検討する。
この結果から,パターン数とは独立に,多数のパターンを同時に量子回路でパターンマッチングを行うアルゴリズムが得られた。
パターンを決定木にコンパイルした事前計算ステップの後、実行時間は入力量子回路のサイズで線形となる。
より一般に、接続されたポートグラフを考えると、すべてのエッジ$e$インシデントから$v$へのラベル$l_v(e)$は$v$である。
Jiang と Bunke は、そのようなグラフに対する部分グラフ同型問題 $H \subseteq G$ は時間$O(|V(G)| \cdot |V(H)|)$ で解けることを示した。
さらに, グラフが有向非巡回であれば, 部分グラフ同型問題は非有界数のパターンに対して同時に解くことができることを示した。
O(P)^{P+3/2} \cdot |V(G)| + O(m)$, ここで$P$は最大のパターンの頂点の数である。
量子回路の場合、パターンの最大数$N$とdeep $\delta$の項で得られる境界を表現することができる:$O(N)^{N + 1/2} \cdot \delta \log \delta \cdot |V(G)| + O(m)$。
関連論文リスト
- Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
連続時間量子ウォーク(CTQW)は、量子コンピューティングにおいて重要な役割を果たす。
CTQWを効率的に実装する方法は難しい問題である。
本稿では,スパースグラフ上でのCTQWの実装について検討する。
論文 参考訳（メタデータ） (2024-08-20T05:20:55Z) - Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。
我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。
提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文 参考訳（メタデータ） (2024-08-03T20:08:02Z) - Scalable Pattern Matching in Computation Graphs [0.0]
グラフの書き直しは、グラフ表現の最適化と修正に人気のあるツールである。
ポートグラフにおけるパターンマッチングの新しい解法を提案する。
我々のアルゴリズムは、10万の現実世界のパターンのデータセット上での現在の実装の20倍のスピードアップを提供する。
論文 参考訳（メタデータ） (2024-02-20T15:02:24Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Quantum computing algorithms for inverse problems on graphs and an
NP-complete inverse problem [2.107421958337625]
有限グラフ $(X,E)$ に対する逆問題を考える。
この問題には特定の条件下でのユニークな解法があることを示し、量子計算法を開発した。
論文 参考訳（メタデータ） (2023-06-08T14:48:48Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。
PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。
UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文 参考訳（メタデータ） (2023-03-10T00:11:18Z) - From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。
このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
論文 参考訳（メタデータ） (2023-02-06T15:14:34Z) - Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
我々は、Ksubseteq G$ の部分群に基づく境界の体系的な扱いを、バルクの Kokuev 量子倍 D(G)$ モデルで提供する。
境界サイトは$*$-subalgebra $Xisubseteq D(G)$の表現であり、その構造を強い$*$-準ホップ代数として説明する。
治療の応用として、水平方向の$K=G$と垂直方向の$K=e$に基づく境界付きパッチを調査し、量子コンピュータでどのように使用できるかを示す。
論文 参考訳（メタデータ） (2022-08-12T15:05:07Z) - 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) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。