論文の概要: Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems

• arxiv url: http://arxiv.org/abs/2311.07372v3
• Date: Sat, 12 Oct 2024 18:40:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-15 21:41:21.234491
• Title: Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems
• Title（参考訳）: 多次元電気ネットワークとそのグラフ問題に対する指数速度アップへの応用
• Authors: Jianqiang Li, Sebastian Zur,
• Abstract要約: 我々は、オルタナティブ・キルヒホフの法則とオルタナティブ・オームの法則を定義することで、新しい多次元電気ネットワークを開発する。 正規グラフの一種におけるパスフィンディング問題に対する指数的量子スピードアップを示す。
• 参考スコア（独自算出の注目度）: 4.452997212927429
• License:
• Abstract: Recently, Apers and Piddock [TQC '23] strengthened the connection between quantum walks and electrical networks via Kirchhoff's Law and Ohm's Law. In this work, we develop a new multidimensional electrical network by defining Alternative Kirchhoff's Law and Alternative Ohm's Law based on the multidimensional quantum walk framework by Jeffery and Zur [STOC '23]. In analogy to the connection between the incidence matrix of a graph and Kirchhoff's Law and Ohm's Law in an electrical network, we rebuild the connection between the alternative incidence matrix and Alternative Kirchhoff's Law and Alternative Ohm's Law. This new framework enables generating an alternative electrical flow over the edges on graphs, which has the potential to be applied to a broader range of graph problems, benefiting both quantum and classical algorithm design. We first use this framework to generate quantum alternative electrical flow states and use it to find a marked vertex in one-dimensional random hierarchical graphs as defined by Balasubramanian, Li, and Harrow [arXiv '23]. In this work, they generalised the exponential quantum-classical separation of the welded tree graph by Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman [STOC '03] to random hierarchical graphs. Our result partially recovers their results with an arguably simpler analysis. Furthermore, this framework also allows us to demonstrate an exponential quantum speedup for the pathfinding problem in a type of regular graph, which we name the welded tree circuit graph. The exponential quantum advantage is obtained by efficiently generating quantum alternative electrical flow states and then sampling from them to find an s-t path in the welded tree circuit graph. By comparison, Li [arXiv '23] constructed a non-regular graph based on welded trees and used the degree information to achieve a similar speedup.
• Abstract（参考訳）: 近年、Apers と Piddock [TQC '23] はキルヒホフの法則とオームの法則を通じて量子ウォークと電気ネットワークの接続を強化した。 本研究では,Jeffery と Zur [STOC '23] の多次元量子ウォークフレームワークに基づいて,代替キルヒホフの法則と代替オルタナティブオームの法則を定義することにより,新しい多次元電気ネットワークを開発する。 グラフの出現行列とキルヒホフの法則と電気ネットワークにおけるオームの法則との接続に類似して、代替キルヒホフの法則とオルタナティブキルヒホフの法則とオルタナティブキルヒホフの法則との接続を再構築する。 この新たなフレームワークは、グラフ上のエッジ上の別の電気フローを生成することが可能であり、より広い範囲のグラフ問題に適用できる可能性があり、量子および古典的なアルゴリズム設計の恩恵を受けることができる。 まず、この枠組みを用いて量子オルタナティブな電気流状態を生成し、バラスラマン、Li、Harrow [arXiv '23] で定義される1次元ランダム階層グラフのマークされた頂点を見つける。 この研究で、彼らはChilds, Cleve, Deotto, Farhi, Gutmann, Spielman [STOC '03] による溶接木グラフの指数的量子古典的分離をランダム階層グラフに一般化した。 この結果は, より単純な解析によって部分的に回復する。 さらに、このフレームワークは、溶接木回路グラフと呼ばれる正規グラフの一種において、パスフィンディング問題に対する指数的な量子スピードアップを実証することを可能にする。 指数的量子優位性は、効率よく量子オルタナティブな電気流状態を生成し、そこからサンプリングして溶接されたツリー回路グラフにs-t経路を見つけることによって得られる。 比較してLi[arXiv '23]は溶接木に基づく非正則グラフを構築し、その次数情報を用いて同様の高速化を実現した。

関連論文リスト

• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies [0.9500919522633157]
  我々は[Nguyen et al., PRX Quantum 4, 010316 (2023) で提案された符号化スキームの量子力学について検討する。 論文では,アディバティックプロトコルに沿ったシステムサイズによる最小ギャップスケーリングについて検討する。 このような局所化とその正解を求める成功確率への影響を観察する。
  論文  参考訳（メタデータ） (2024-11-07T12:10:01Z)
• Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
  本稿では、離散時間量子ウォークによる溶接木問題に対する最適線形打撃時間の簡単な証明を行う。 同じ手法は他の1次元階層グラフにも適用できる。
  論文  参考訳（メタデータ） (2024-04-30T11:45:49Z)
• Graph Transformer GANs with Graph Masked Modeling for Architectural Layout Generation [153.92387500677023]
  本稿では,グラフノード関係を効果的に学習するために,GTGAN(Graph Transformer Generative Adversarial Network)を提案する。 提案したグラフ変換器エンコーダは、局所的およびグローバルな相互作用をモデル化するために、Transformer内のグラフ畳み込みと自己アテンションを組み合わせる。 また,グラフ表現学習のための自己指導型事前学習手法を提案する。
  論文  参考訳（メタデータ） (2024-01-15T14:36:38Z)
• Path convergence of Markov chains on large graphs [3.693375843298262]
  グラフのサイズが無限大になるにつれて、プロセスのランダムな軌跡は測度値グラフの空間上の決定論的曲線に収束することを示す。 このアプローチの新たな特徴は、ある制限状態におけるメトロポリス連鎖に対して正確な指数収束速度を提供することである。
  論文  参考訳（メタデータ） (2023-08-18T00:13:59Z)
• Exponential speedups for quantum walks in random hierarchical graphs [8.984888893275713]
  量子ウォークを階層グラフのクラスに一般化する方法を示す。 これらのグラフ上の量子ウォークのヒット時間は、特定の乱れた強結合ハミルトニアンにおけるゼロモードの局在特性に関係している。
  論文  参考訳（メタデータ） (2023-07-27T17:59:58Z)
• You Only Transfer What You Share: Intersection-Induced Graph Transfer Learning for Link Prediction [79.15394378571132]
  従来見過ごされていた現象を調査し、多くの場合、元のグラフに対して密に連結された補グラフを見つけることができる。 より密度の高いグラフは、選択的で有意義な知識を伝達するための自然なブリッジを提供する元のグラフとノードを共有することができる。 この設定をグラフインターセクション誘導トランスファーラーニング(GITL)とみなし,eコマースや学術共同オーサシップ予測の実践的応用に動機づけられた。
  論文  参考訳（メタデータ） (2023-02-27T22:56:06Z)
• Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
  本稿では,高レベル言語で記述された量子回路から,アルゴリズム固有のグラフ状態を作成する量子回路コンパイラを提案する。 この計算は、このグラフ状態に関する一連の非パウリ測度を用いて実装することができる。
  論文  参考訳（メタデータ） (2022-09-15T14:52:31Z)
• From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
  まず、量子力学とグラフ理論の相関関係について、量子コンピュータが有用な解を生成できることを示す。 本稿では,その実践性と適用性について,一般的なグラフ学習手法について概説する。 今後の研究の触媒として期待される量子グラフ学習のスナップショットを提供する。
  論文  参考訳（メタデータ） (2022-02-19T02:56:47Z)
• Simplifying Continuous-Time Quantum Walks on Dynamic Graphs [0.0]
  動的グラフ上の連続時間量子ウォークは、グラフのエッジを符号化するハミルトンの列でシュル「オーディンガーの方程式によって進化する。 本稿では,動的グラフを単純化可能な6つのシナリオを提案する。
  論文  参考訳（メタデータ） (2021-06-10T19:24:32Z)
• Generation and Robustness of Quantum Entanglement in Spin Graphs [0.0]
  絡み合いは量子情報処理にとって重要な資源である。 グラフ構造を用いて高忠実な絡み合った状態を生成する方法を示す。 また,製造誤差が絡み合い発生プロトコルに与える影響についても検討する。
  論文  参考訳（メタデータ） (2020-02-18T16:11:57Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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