論文の概要: Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo
- arxiv url: http://arxiv.org/abs/2312.03768v1
- Date: Tue, 5 Dec 2023 21:15:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-08 17:38:49.235383
- Title: Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo
- Title（参考訳）: Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo
- Authors: Gustavo Alves Bezerra
- Abstract要約: Groverのアルゴリズムは、$O(sqrtN/k)$ stepsを使って$N$要素を持つ、順序のないデータベースで$k$要素を見つけることができる。
この研究は、他のグラフのマーク要素の値$k$を推定するために量子カウントアルゴリズムを使用する問題に取り組む。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Studies on Quantum Computing have been developed since the 1980s, motivating
researches on quantum algorithms better than any classical algorithm possible.
An example of such algorithms is Grover's algorithm, capable of finding $k$
(marked) elements in an unordered database with $N$ elements using
$O(\sqrt{N/k})$ steps. Grover's algorithm can be interpreted as a quantum walk
in a complete graph (with loops) containing $N$ vertices from which $k$ are
marked. This interpretation motivated search algorithms in other graphs --
complete bipartite graph, grid, and hypercube. Using Grover's algorithm's
linear operator, the quantum counting algorithm estimates the value of $k$ with
an error of $O(\sqrt{k})$ using $O(\sqrt{N})$ steps. This work tackles the
problem of using the quantum counting algorithm for estimating the value $k$ of
marked elements in other graphs; more specifically, the complete bipartite
graph. It is concluded that for a particular case, running the proposed
algorithm at most $t$ times wields an estimation of $k$ with an error of
$O(\sqrt{k})$ using $O(t\sqrt{N})$ steps and success probability of at least
$(1 - 2^{-t})8/\pi^2$.
- Abstract（参考訳）: 量子コンピューティングの研究は1980年代から発展し、量子アルゴリズムの研究はあらゆる古典的アルゴリズムよりも優れたものとなった。
そのようなアルゴリズムの例として、Groverのアルゴリズムがあり、$O(\sqrt{N/k})$ steps を用いて$N$要素を持つ無順序データベースで$k$(マーク付き)要素を見つけることができる。
グローバーのアルゴリズムは、$k$がマークされた$n$頂点を含む完全グラフ(ループ付き)の量子ウォークとして解釈できる。
この解釈は検索アルゴリズムを他のグラフ - 完全二部グラフ、グリッド、ハイパーキューブ - に動機づけた。
グロバーのアルゴリズムの線形作用素を用いて、量子カウントアルゴリズムは$O(\sqrt{k})$の誤差で$k$の値を推定し、$O(\sqrt{N})$のステップを使用する。
この研究は、量子カウントアルゴリズムを使って他のグラフのマークされた要素の値$k$を推定する問題に取り組んでいる。
特定の場合、提案されたアルゴリズムを少なくとも$t$ timesで実行すると、$O(\sqrt{k})$の誤差で$k$と推定され、$O(t\sqrt{N})$のステップと成功確率は少なくとも$(1 - 2^{-t})8/\pi^2$である。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - 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) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - 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) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳（メタデータ） (2021-06-10T16:28:23Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Leveraging Unknown Structure in Quantum Query Algorithms [0.0]
本研究では,事前の約束がなくても,これらのスピードアップが持続することを示すために,修正されたスパンプログラムアルゴリズムを示す。
我々のアルゴリズムは、$tildeO(sqrtkn)$クエリを使って、少なくとも$k$のエッジを持つパスがある場合、この問題を解決する。
論文 参考訳（メタデータ） (2020-12-02T15:32:52Z) - Quantum algorithms for graph problems with cut queries [17.149741568581096]
量子アルゴリズムは、$O(d log(n)2) の後に最大$d$のグラフを学習できることを示す。
また、量子アルゴリズムは、$O(sqrtm log(n)3/2)$多くのカットクエリで一般的なグラフを学習できることを示す。
論文 参考訳（メタデータ） (2020-07-16T12:21:01Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Resonant Quantum Search with Monitor Qubits [0.0]
連続的ハミルトニアンと共振を利用した一般化探索問題($N$項目中$k$マークされた項目を探索する)のアルゴリズムを提案する。
この共振アルゴリズムはGroverアルゴリズムと同じ時間複雑性$O(sqrtN/k)$を持つ。
論文 参考訳（メタデータ） (2020-02-21T19:31:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。