Fugu-MT 論文翻訳(概要): Faster Quantum Concentration via Grover's Search

論文の概要: Faster Quantum Concentration via Grover's Search

arxiv url: http://arxiv.org/abs/2103.09818v1
Date: Tue, 16 Mar 2021 21:12:28 GMT
ステータス: 処理完了
システム内更新日: 2023-04-07 23:13:46.847456
Title: Faster Quantum Concentration via Grover's Search
Title（参考訳）: グローバー探索による量子集中の高速化
Authors: Cem M. Unsal and A. Yavuz Oruc
Abstract要約: 脂肪およびスリム濃縮器におけるルーティング集中割当のための量子アルゴリズムを提案する。我々のアルゴリズムは、$O(sqrtnclnc)$時間を取る。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We present quantum algorithms for routing concentration assignments on full capacity fat-and-slim concentrators, bounded fat-and-slim concentrators, and regular fat-and-slim concentrators. Classically, the concentration assignment takes $O(n)$ time on all these concentrators, where $n$ is the number of inputs. Powered by Grover's quantum search algorithm, our algorithms take $O(\sqrt{nc}\ln{c})$ time, where $c$ is the capacity of the concentrator. Thus, our quantum algorithms are asymptotically faster than their classical counterparts, when $c\ln^2{c}=o(n)$.In general, $c = n^\mu,$ satisfies $c\ln^2{c}=o(n),$ implying a time complexity of $O(n^{0.5(1+ \mu )} \ln n),$ for any $\mu, 0 < \mu < 1.$
Abstract（参考訳）: 本稿では,フル容量脂肪・スリム濃縮器,境界脂肪・スリム濃縮器,正規脂肪・スリム濃縮器の濃度割り当てをルーティングする量子アルゴリズムを提案する。古典的には、濃度割当は、すべての集中子に$O(n)$時間を要するが、ここでは$n$は入力の数である。グローバーの量子探索アルゴリズムにより、我々のアルゴリズムはo(\sqrt{nc}\ln{c})$時間を取る。したがって、量子アルゴリズムは古典的アルゴリズムよりも漸近的に高速であり、$c\ln^2{c}=o(n)$である。一般に、$c = n^\mu,$ satisfies $c\ln^2{c}=o(n),$ は任意の$\mu, 0 < \mu < 1.$ に対して$o(n^{0.5(1+ \mu )} \ln n)の時間の複雑さを意味する。

関連論文リスト

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)
A Quantum Approximation Scheme for k-Means [0.16317061277457]
QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
論文参考訳（メタデータ） (2023-08-16T06:46:37Z)
Near-Optimal Quantum Coreset Construction Algorithms for Clustering [15.513270929560088]
我々は、$tildeO(sqrtnkd3/2)$クエリ複雑性を持つ$mathbbRd$で$k$-clusteringのコアセットを見つける量子アルゴリズムを与える。私たちのコアセットは入力サイズを$n$から$mathrmpoly(kepsilon-1d)$に減らします。
論文参考訳（メタデータ） (2023-06-05T12:22:46Z)
Quantum Speedups for Bayesian Network Structure Learning [0.0]
ノードが$n$のネットワークの場合、最も高速な既知のアルゴリズムは、最悪の場合は$O(cn)$で実行され、20年で改善はない。近年の量子コンピューティングの発展に触発されて、BNSLが量子スピードアップを認めているかどうかを問う。我々は、$c leq 1.817$と$c leq 1.982$の2つのアルゴリズムを与える。
論文参考訳（メタデータ） (2023-05-31T09:15:28Z)
On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文参考訳（メタデータ） (2023-03-20T08:17:32Z)
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)
Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文参考訳（メタデータ） (2022-06-07T18:00:01Z)
Quantum Algorithm for Fidelity Estimation [8.270684567157987]
2つの未知の混合量子状態 $rho$ と $sigma$ に対して、それらの忠実度 $F(rho,sigma)$ は基本的な問題である。我々は、この問題を$namepoly(log (N), r, 1/varepsilon)$ timeで解く量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2021-03-16T13:57:01Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文参考訳（メタデータ） (2020-02-18T16:14:55Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。