論文の概要: Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs
- arxiv url: http://arxiv.org/abs/2407.14398v1
- Date: Fri, 19 Jul 2024 15:21:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-22 17:05:24.143305
- Title: Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs
- Title（参考訳）: 通常のサンフラワーグラフにおけるパスフィニングの指数量子アドバンテージ
- Authors: Jianqiang Li, Yu Tong,
- Abstract要約: 隣接リストのオラクルによるパスフィンディング問題に対して指数的量子古典的分離を可能にするグラフのクラスを見つける。
通常のヒマワリグラフに$s$-$t$の経路を求めるのに有効な量子アルゴリズムを提供するが、古典的アルゴリズムは指数関数的な時間を要する。
- 参考スコア（独自算出の注目度）: 5.173438526554426
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Finding problems that allow for superpolynomial quantum speedup is one of the most important tasks in quantum computation. A key challenge is identifying problem structures that can only be exploited by quantum mechanics. In this paper, we find a class of graphs that allows for exponential quantum-classical separation for the pathfinding problem with the adjacency list oracle, and this class of graphs is named regular sunflower graphs. We prove that, with high probability, a regular sunflower graph of degree at least $7$ is a mild expander graph, that is, the spectral gap of the graph Laplacian is at least inverse polylogarithmic in the graph size. We provide an efficient quantum algorithm to find an $s$-$t$ path in the regular sunflower graph while any classical algorithm takes exponential time. This quantum advantage is achieved by efficiently preparing a $0$-eigenstate of the adjacency matrix of the regular sunflower graph as a quantum superposition state over the vertices, and this quantum state contains enough information to help us efficiently find an $s$-$t$ path in the regular sunflower graph. Because the security of an isogeny-based cryptosystem depends on the hardness of finding an $s$-$t$ path in an expander graph \cite{Charles2009}, a quantum speedup of the pathfinding problem on an expander graph is of significance. Our result represents a step towards this goal as the first provable exponential speedup for pathfinding in a mild expander graph.
- Abstract（参考訳）: スーパーポリノミカル量子スピードアップを可能にする問題を見つけることは、量子計算において最も重要なタスクの1つである。
鍵となる課題は、量子力学でしか利用できない問題構造を特定することである。
本稿では,隣接度リストのオラクルによるパスフィニング問題に対する指数的量子-古典的分離を可能にするグラフのクラスを見つけ,このグラフのクラスを正日花グラフと呼ぶ。
高い確率で、次数7$以上の正日花グラフは、緩やかな拡大グラフであり、ラプラシアンのスペクトルギャップは、グラフサイズにおいて少なくとも逆多元数であることを示す。
通常のヒマワリグラフに$s$-$t$の経路を求めるのに有効な量子アルゴリズムを提供するが、古典的アルゴリズムは指数関数的な時間を要する。
この量子優位性は、正日花グラフの隣接行列の0$-eigenstateを頂点上の量子重ね合わせ状態として効率的に準備することで達成され、この量子状態は正日花グラフの$s$-$t$パスを効率的に見つけるのに十分な情報を含む。
等質性に基づく暗号システムのセキュリティは、拡張器グラフ \cite{Charles2009} における$s$-$t$パスを見つけることの難しさに依存するため、拡張器グラフ上のパスフィンディング問題の量子スピードアップは重要である。
我々の結果は、軽度の拡大グラフにおけるパスフィンディングのための最初の証明可能な指数的高速化として、この目標に向けての一歩である。
関連論文リスト
- Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
本稿では、離散時間量子ウォークによる溶接木問題に対する最適線形打撃時間の簡単な証明を行う。
同じ手法は他の1次元階層グラフにも適用できる。
論文 参考訳（メタデータ） (2024-04-30T11:45:49Z) - Exponential speedups for quantum walks in random hierarchical graphs [8.984888893275713]
量子ウォークを階層グラフのクラスに一般化する方法を示す。
これらのグラフ上の量子ウォークのヒット時間は、特定の乱れた強結合ハミルトニアンにおけるゼロモードの局在特性に関係している。
論文 参考訳（メタデータ） (2023-07-27T17:59:58Z) - Exponential speedup of quantum algorithms for the pathfinding problem [5.260626311429307]
非重みのないグラフで$s, t$が与えられたとき、パスフィンディング問題の目標は、$s$-$t$パスを見つけることである。
溶接木に基づいてグラフ$G$を構築し、隣接リスト oracle $O$ でパスフィニング問題を定義する。
古典的なアルゴリズムが確率の高い指数時間で$s$-$t$パスを見つけることはできないことを証明している。
論文 参考訳（メタデータ） (2023-07-24T02:50:34Z) - Graph Neural Network Bandits [89.31889875864599]
グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。
この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。
グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
論文 参考訳（メタデータ） (2022-07-13T18:12:36Z) - Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。
関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
論文 参考訳（メタデータ） (2022-07-04T19:33:06Z) - From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
まず、量子力学とグラフ理論の相関関係について、量子コンピュータが有用な解を生成できることを示す。
本稿では,その実践性と適用性について,一般的なグラフ学習手法について概説する。
今後の研究の触媒として期待される量子グラフ学習のスナップショットを提供する。
論文 参考訳（メタデータ） (2022-02-19T02:56:47Z) - Application of graph theory in quantum computer science [0.0]
連続時間量子ウォークモデルが非自明なグラフ構造に対して強力であることを示す。
CTQWで定義された量子空間探索は、様々な無向グラフでうまく機能することが証明されている。
この側面のスコープでは、複雑なグラフ構造に対しても量子スピードアップが観測されるかどうかを分析する。
論文 参考訳（メタデータ） (2021-09-27T12:07:25Z) - Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk [0.0]
連続時間量子ウォークによるジョンソングラフ上の空間探索は、固定径毎に1ドル程度の成功確率を持つ下界の$pisqrtN/2$を達成することを示す。
この証明は数学的に厳密であり、他のグラフクラスにも利用できる。
論文 参考訳（メタデータ） (2021-08-04T12:16:24Z) - 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) - (Sub)Exponential advantage of adiabatic quantum computation with no sign
problem [0.0]
符号問題のないギャップ付きハミルトニアンの断熱経路に従う量子アルゴリズムによる(部分)指数量子スピードアップの可能性を示す。
このスピードアップを示すハミルトニアンは、無向グラフの隣接行列に由来する。
論文 参考訳（メタデータ） (2020-11-18T19:04:51Z) - Continuous-time quantum walks in the presence of a quadratic
perturbation [55.41644538483948]
連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。
低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
論文 参考訳（メタデータ） (2020-05-13T14:53:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。