論文の概要: 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つを解決し、非正則グラフを構築し、次数情報を用いて同様のスピードアップを達成する。
グラフの(エッジ頂点)帰属行列と電気ネットワークにおけるキルヒホフの法則とオームの法則の接続に類似して、代替帰属行列とキルヒホフの代替法則とオームの代替法則との接続を再構築する。
この接続を確立することで、多次元電気ネットワークは量子ウォークを超えてより多くの応用が期待できる。
関連論文リスト
- Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
本稿では、離散時間量子ウォークによる溶接木問題に対する最適線形打撃時間の簡単な証明を行う。
同じ手法は他の1次元階層グラフにも適用できる。
論文 参考訳(メタデータ) (2024-04-30T11:45:49Z) - Quantum information spreading in generalised dual-unitary circuits [49.1574468325115]
局所演算子は、二重単位回路のように光速で拡散することを示す。
これらの特性を用いて、回路内の絡み合い膜に対する閉形式表現を求める。
論文 参考訳(メタデータ) (2023-12-05T18:09:27Z) - Bell pair extraction using graph foliage techniques [0.0]
私たちは、複数のペアがネットワーク間で同時に通信できるかどうかに興味を持っています。
量子ネットワークはグラフ状態で表すことができ、グラフ状態上で特定の量子演算を実行するための通信リンクを生成することができる。
論文 参考訳(メタデータ) (2023-11-25T22:33:29Z) - Multipartite Entanglement in Quantum Networks using Subgraph
Complementations [10.483535574476477]
絡み合った状態は量子コンピューティングの構成要素である。
ノイズレス量子ネットワーク上でグラフ状態を分散する新しい手法を提案する。
本研究では,量子ビット数,古典的通信用ビット数,EPRペアの利用量の改善について述べる。
論文 参考訳(メタデータ) (2023-08-25T23:03:25Z) - Path convergence of Markov chains on large graphs [3.693375843298262]
グラフのサイズが無限大になるにつれて、プロセスのランダムな軌跡は測度値グラフの空間上の決定論的曲線に収束することを示す。
このアプローチの新たな特徴は、ある制限状態におけるメトロポリス連鎖に対して正確な指数収束速度を提供することである。
論文 参考訳(メタデータ) (2023-08-18T00:13:59Z) - Exponential speedups for quantum walks in random hierarchical graphs [6.896797484250303]
量子ウォークを階層グラフのクラスに一般化する方法を示す。
これらのグラフ上の量子ウォークのヒット時間は、特定の乱れた強結合ハミルトニアンにおけるゼロモードの局在特性に関係している。
論文 参考訳(メタデータ) (2023-07-27T17:59:58Z) - 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) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳(メタデータ) (2021-06-11T09:43:09Z) - Estimating the entropy of shallow circuit outputs is hard [77.34726150561087]
シャノンエントロピー推定の意思決定問題バージョンはエントロピー差分(ED)である
量子回路(QED)の類似の問題
オラクルと比較して、これらの問題は指数関数的に大きい回路と同等に難しいものではないことを示す。
論文 参考訳(メタデータ) (2020-02-27T15:32:08Z) - Generation and Robustness of Quantum Entanglement in Spin Graphs [0.0]
絡み合いは量子情報処理にとって重要な資源である。
グラフ構造を用いて高忠実な絡み合った状態を生成する方法を示す。
また,製造誤差が絡み合い発生プロトコルに与える影響についても検討する。
論文 参考訳(メタデータ) (2020-02-18T16:11:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。