論文の概要: Multidimensional Electrical Networks and their Application to
Exponential Speedups for Graph Problems
- arxiv url: http://arxiv.org/abs/2311.07372v1
- Date: Mon, 13 Nov 2023 14:39:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-14 14:15:38.050170
- Title: Multidimensional Electrical Networks and their Application to
Exponential Speedups for Graph Problems
- Title（参考訳）: 多次元電気ネットワークとそのグラフ問題に対する指数速度アップへの応用
- Authors: Jianqiang Li and Sebastian Zur
- Abstract要約: 我々は、Kirchhoffの代替法則とOhmの代替法則を、新しい多次元量子ウォークフレームワークに基づいて定義することにより、多次元電気ネットワークを開発する。
この枠組みは多次元量子ウォークアルゴリズムを用いて得られた電気の流れをサンプリングすることを可能にする。
この接続を確立することで、多次元電気ネットワークは量子ウォークを超えてより多くの応用が期待できる。
- 参考スコア（独自算出の注目度）: 5.260626311429307
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recently, Apers and Piddock [TQC '23] strengthened the natural connection
between quantum walks and electrical networks by considering Kirchhoff's Law
and Ohm's Law. In this work, we develop the multidimensional electrical network
by defining Kirchhoff's Alternative Law and Ohm's Alternative Law based on the
novel multidimensional quantum walk framework by Jeffery and Zur [STOC '23].
This multidimensional electrical network allows us to sample from the
electrical flow obtained via a multidimensional quantum walk algorithm and
achieve exponential quantum-classical separations for certain graph problems.
We first use this framework 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 well known exponential quantum-classical
separation of the welded tree problem 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, by
constructing a $3$-regular graph based on welded trees, this framework also
allows us to show an exponential speedup for the pathfinding problem. This
solves one of the open problems by Li [arXiv '23], where they construct a
non-regular graph and use the degree information to achieve a similar speedup.
In analogy to the connection between the (edge-vertex) incidence matrix of a
graph and Kirchhoff's Law and Ohm's Law in an electrical network, we also
rebuild the connection between the alternative incidence matrix and Kirchhoff's
Alternative Law and Ohm's Alternative Law. By establishing this connection, we
expect that the multidimensional electrical network could have more
applications beyond quantum walks.
- Abstract（参考訳）: 近年、Apers と Piddock [TQC '23] はKirchhoff の法則とOhm の法則を考慮し、量子ウォークと電気ネットワークの自然接続を強化した。
本稿では,Jeffery と Zur [STOC '23] による新しい多次元量子ウォークフレームワークに基づいて,Kirchhoff の代替法則とOhm の代替法則を定義することにより,多次元電気ネットワークを開発する。
この多次元電気ネットワークは,多次元量子ウォークアルゴリズムを用いて得られた電気の流れをサンプリングし,グラフ問題に対する指数的量子古典分離を実現する。
まずこの枠組みを用いて、バラシュラマン、Li、Harrow [arXiv '23] によって定義される一次元ランダム階層グラフのマーク頂点を求める。
本研究では,子ども, cleve, deotto, farhi, gutmann, spielman [stoc '03] による溶接木問題の指数関数的量子古典的分離をランダムな階層グラフに一般化した。
この結果は, より単純な解析によって部分的に回復する。
さらに,溶接木をベースとした3ドル規則グラフを構築することにより,パスフィンディング問題に対する指数的な高速化を示すことができる。
これはLi [arXiv '23] による開問題の1つを解決し、非正則グラフを構築し、次数情報を用いて同様のスピードアップを達成する。
グラフの(エッジ頂点)帰属行列と電気ネットワークにおけるキルヒホフの法則とオームの法則の接続に類似して、代替帰属行列とキルヒホフの代替法則とオームの代替法則との接続を再構築する。
この接続を確立することで、多次元電気ネットワークは量子ウォークを超えてより多くの応用が期待できる。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。