論文の概要: Quantum algorithms for graph problems with cut queries
- arxiv url: http://arxiv.org/abs/2007.08285v2
- Date: Tue, 4 Aug 2020 12:04:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-09 07:12:46.484980
- Title: Quantum algorithms for graph problems with cut queries
- Title（参考訳）: カットクエリを用いたグラフ問題に対する量子アルゴリズム
- Authors: Troy Lee and Miklos Santha and Shengyu Zhang
- Abstract要約: 量子アルゴリズムは、$O(d log(n)2) の後に最大$d$のグラフを学習できることを示す。
また、量子アルゴリズムは、$O(sqrtm log(n)3/2)$多くのカットクエリで一般的なグラフを学習できることを示す。
- 参考スコア（独自算出の注目度）: 17.149741568581096
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Let $G$ be an $n$-vertex graph with $m$ edges. When asked a subset $S$ of
vertices, a cut query on $G$ returns the number of edges of $G$ that have
exactly one endpoint in $S$. We show that there is a bounded-error quantum
algorithm that determines all connected components of $G$ after making
$O(\log(n)^6)$ many cut queries. In contrast, it follows from results in
communication complexity that any randomized algorithm even just to decide
whether the graph is connected or not must make at least $\Omega(n/\log(n))$
many cut queries. We further show that with $O(\log(n)^8)$ many cut queries a
quantum algorithm can with high probability output a spanning forest for $G$.
En route to proving these results, we design quantum algorithms for learning
a graph using cut queries. We show that a quantum algorithm can learn a graph
with maximum degree $d$ after $O(d \log(n)^2)$ many cut queries, and can learn
a general graph with $O(\sqrt{m} \log(n)^{3/2})$ many cut queries. These two
upper bounds are tight up to the poly-logarithmic factors, and compare to
$\Omega(dn)$ and $\Omega(m/\log(n))$ lower bounds on the number of cut queries
needed by a randomized algorithm for the same problems, respectively.
The key ingredients in our results are the Bernstein-Vazirani algorithm,
approximate counting with "OR queries", and learning sparse vectors from inner
products as in compressed sensing.
- Abstract（参考訳）: g$を$m$のエッジを持つ$n$-vertexグラフにしましょう。
頂点のサブセット$s$を尋ねると、$g$のカットクエリは$s$のちょうど1つのエンドポイントを持つ$g$のエッジ数を返す。
我々は,$O(\log(n)^6)$ 多くのカットクエリを作成した後に,$G$のすべての連結成分を決定する有界エラー量子アルゴリズムが存在することを示す。
対照的に、グラフが接続されているかどうかを判断するだけのランダム化アルゴリズムであっても、通信複雑性の結果、少なくとも$\Omega(n/\log(n))$多くのカットクエリをしなければならない。
さらに、$O(\log(n)^8)$の多くのカットクエリでは、量子アルゴリズムが高確率出力のスパンジングを$G$で得ることを示す。
これらの結果を証明するために,カットクエリを用いたグラフ学習のための量子アルゴリズムを設計する。
量子アルゴリズムは、$O(d \log(n)^2)$多くのカットクエリの後、最大$d$のグラフを学習でき、$O(\sqrt{m} \log(n)^{3/2})$多くのカットクエリを学習できる。
これら2つの上界は多対数因子に密接であり、同じ問題に対してランダム化アルゴリズムが必要とするカットクエリの数に対して、$\Omega(dn)$と$\Omega(m/\log(n))$の下位境界と比較する。
結果の鍵となる要素はbernstein-vaziraniアルゴリズムであり,"or query"で近似カウントし,圧縮センシングのように内積からスパースベクトルを学習する。
関連論文リスト
- A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
本稿では,最大$tildeO(d2m3/4)$量子クエリにおいて,$G$のエッジを学習するアルゴリズムを提案する。
特に、確率の高い確率で$tildeO(sqrtm)$量子クエリでサイクルとマッチングを学習するランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-28T21:23:40Z) - Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo [0.0]
Groverのアルゴリズムは、$O(sqrtN/k)$ stepsを使って$N$要素を持つ、順序のないデータベースで$k$要素を見つけることができる。
この研究は、他のグラフのマーク要素の値$k$を推定するために量子カウントアルゴリズムを使用する問題に取り組む。
論文 参考訳（メタデータ） (2023-12-05T21:15:09Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - A sublinear query quantum algorithm for s-t minimum cut on dense simple
graphs [1.0435741631709405]
グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。
この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
論文 参考訳（メタデータ） (2021-10-29T07:35:46Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Quantum complexity of minimum cut [0.2538209532048867]
隣接行列モデルにおける最小カット問題の量子クエリと時間複雑性を特徴付ける。
我々のアルゴリズムは、Apers and de Wolf (FOCS 2020) によるグラフスカラー化のための量子アルゴリズムを用いており、Kawarabayashi and Thorup (STOC 2015) と Rubinstein, Schramm and Weinberg (ITCS 2018) による準最小カットの構造に関する結果である。
論文 参考訳（メタデータ） (2020-11-19T13:51:49Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。