論文の概要: 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独立ランダム文字列の効率的な構成に関する既存の結果に基づいて構築されている。
このアルゴリズムはラプラシアン系を解き、ミンカットやスパルセストカットのようなカット問題の範囲を近似する量子スピードアップを意味する。
関連論文リスト
- Comparison among Classical, Probabilistic and Quantum Algorithms for
Hamiltonian Cycle problem [0.0]
ハミルトニアンサイクル問題(HCP)は、n 個のノードと m 個のエッジを持つグラフ G を持ち、各ノードを正確に1度に接続する経路を見つけることである。
本稿では、計算の異なるモデル、特に確率的および量子的モデルを用いて、aHCPを解くアルゴリズムを比較する。
論文 参考訳(メタデータ) (2023-11-18T02:36:10Z) - Quantum speedups for linear programming via interior point methods [2.07180164747172]
本稿では,$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.22559617939136506]
我々は、我々の分割と形式主義の征服を通じて、大きな$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) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳(メタデータ) (2022-02-10T18:59:52Z) - 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 [79.28094304325116]
対称正定値行列(SPD)の最も一般的なスペクトル和を推定するための新しい量子アルゴリズムを提案し,解析する。
関数 $f$ と行列 $A に対して、スペクトル和は $S_f(A) :=textTr[f(A)] = sum_j f(lambda_j)$, ここで $lambda_j$ は固有値である。
論文 参考訳(メタデータ) (2020-11-12T16:29:45Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。