論文の概要: Quantum Speedup for Graph Sparsification, Cut Approximation and
Laplacian Solving
- arxiv url: http://arxiv.org/abs/1911.07306v4
- Date: Mon, 8 May 2023 11:00:04 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-10 02:28:02.446270
- Title: Quantum Speedup for Graph Sparsification, Cut Approximation and
Laplacian Solving
- Title（参考訳）: グラフスパーシフィケーション、カット近似、ラプラシアン解のための量子スピードアップ
- Authors: Simon Apers and Ronald de Wolf
- Abstract要約: スペクトルスペーシフィケーション」は、ノード数でエッジの数をほぼ直線に減らす。
スペクトルスカラー化のための量子スピードアップとその多くの応用について述べる。
我々のアルゴリズムはラプラシア系を解くための量子スピードアップを意味する。
- 参考スコア（独自算出の注目度）: 1.0660480034605238
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph sparsification underlies a large number of algorithms, ranging from
approximation algorithms for cut problems to solvers for linear systems in the
graph Laplacian. In its strongest form, "spectral sparsification" reduces the
number of edges to near-linear in the number of nodes, while approximately
preserving the cut and spectral structure of the graph. In this work we
demonstrate a polynomial quantum speedup for spectral sparsification and many
of its applications. In particular, we give a quantum algorithm that, given a
weighted graph with $n$ nodes and $m$ edges, outputs a classical description of
an $\epsilon$-spectral sparsifier in sublinear time
$\tilde{O}(\sqrt{mn}/\epsilon)$. This contrasts with the optimal classical
complexity $\tilde{O}(m)$. We also prove that our quantum algorithm is optimal
up to polylog-factors. The algorithm builds on a string of existing results on
sparsification, graph spanners, quantum algorithms for shortest paths, and
efficient constructions for $k$-wise independent random strings. Our algorithm
implies a quantum speedup for solving Laplacian systems and for approximating a
range of cut problems such as min cut and sparsest cut.
- Abstract（参考訳）: グラフスパーシフィケーションは、カット問題の近似アルゴリズムからグラフラプラシアンにおける線形系の解法まで、多くのアルゴリズムの基礎となっている。
最も強い形では、"spectral sparsification"(スペクトルスパーシフィケーション)は、グラフのカットとスペクトル構造をほぼ保存しながら、ノード数において辺の数をニアリニアに減少させる。
本研究では、スペクトルスペーシフィケーションのための多項式量子スピードアップとその多くの応用を実証する。
特に、$n$ノードと$m$エッジを持つ重み付きグラフを与えられた量子アルゴリズムは、サブ線形時間$\tilde{O}(\sqrt{mn}/\epsilon)$における$\epsilon$-spectral sparsifierの古典的な記述を出力する。
これは最適古典複雑性 $\tilde{O}(m)$ と対照的である。
また、我々の量子アルゴリズムはポリログ因子に最適であることを示す。
このアルゴリズムは、スパーシフィケーション、グラフスパンナー、最短経路の量子アルゴリズム、および$k$-wise独立ランダム文字列の効率的な構成に関する既存の結果に基づいて構築されている。
このアルゴリズムはラプラシアン系を解き、ミンカットやスパルセストカットのようなカット問題の範囲を近似する量子スピードアップを意味する。
関連論文リスト
- Promise of Graph Sparsification and Decomposition for Noise Reduction in QAOA: Analysis for Trapped-Ion Compilations [5.451583832235867]
我々は Max-Cut 問題を解くための近似コンパイル手法を開発した。
結果はグラフスカラー化と分解の原則に基づいている。
新たなコンパイル手法では,ノイズの顕著な低減が示される。
論文 参考訳（メタデータ） (2024-06-20T14:00:09Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Quantum speedups for linear programming via interior point methods [1.8434042562191815]
本稿では,$d$変数上の不等式制約で線形プログラムを解く量子アルゴリズムについて述べる。
我々のアルゴリズムは、リーとシドフォードの最先端インテリアポイント法におけるニュートンステップを高速化する。
論文 参考訳（メタデータ） (2023-11-06T16:00:07Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian [0.5097809301149342]
我々は、我々の分割と形式主義の征服を通じて、大きな$Lambda$の量子化よりも優れたスケーリングと量子化を得られることを示す。
また,マルチコントロールされたXゲート群を実装する新しい方法を含む,ゲート最適化のための新しいアルゴリズムおよび回路レベル技術も提供する。
論文 参考訳（メタデータ） (2023-06-19T23:20:30Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - Generating Target Graph Couplings for QAOA from Native Quantum Hardware
Couplings [3.2622301272834524]
本稿では,Ising型量子スピン系における限定大域制御を用いた任意の対象結合グラフの構築手法を提案する。
本手法は、量子近似最適化アルゴリズム(QAOA)をトラップされたイオン量子ハードウェア上に実装することによるものである。
Max-Cut QAOAのノイズシミュレーションにより、我々の実装は標準ゲートベースのコンパイルよりもノイズの影響を受けにくいことが示された。
論文 参考訳（メタデータ） (2020-11-16T18:43:09Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。