論文の概要: Grover's search algorithm for $n$ qubits with optimal number of
iterations
- arxiv url: http://arxiv.org/abs/2011.04051v2
- Date: Sun, 22 Nov 2020 07:59:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-24 23:19:22.625154
- Title: Grover's search algorithm for $n$ qubits with optimal number of
iterations
- Title（参考訳）: 最適反復数をもつ$n$量子ビットに対するGroverの探索アルゴリズム
- Authors: Simanraj Sadana
- Abstract要約: グローバーの探索アルゴリズムは、グローバーの拡散操作に続くオラクルの合成操作の繰り返し数に依存する。
1leq M leq N$ターゲット状態を持つ$n$-qubit Groverの探索アルゴリズムを構築するための一般的なスキームを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The success probability of a search of $M$ targets from a database of size
$N$, using Grover's search algorithm depends critically on the number of
iterations of the composite operation of the oracle followed by Grover's
diffusion operation. Although the required number of iterations scales as
$\mathcal{O}(\sqrt{N})$ for large $N$, the asymptote is not a good indicator of
the optimal number of iterations when $\sqrt{M/N}$ is not small. A scheme for
the determination of the exact number of iterations, subject to a threshold set
for the success probability of the search (probability of detecting the target
state(s)), is crucial for the efficacy of the algorithm. In this work, a
general scheme for the construction of $n$-qubit Grover's search algorithm with
$1 \leq M \leq N$ target states is presented, along with the procedure to find
the optimal number of iterations for a successful search. It is also shown that
for given $N$ and $M$, there is an upper-bound on the success probability of
the algorithm.
- Abstract（参考訳）: グローバーの探索アルゴリズムを用いて、$M$のターゲットを$N$のデータベースから検索する成功確率は、オラクルの合成操作の繰り返し回数とグローバーの拡散操作に大きく依存する。
必要なイテレーション数は、大きな$n$に対して$\mathcal{o}(\sqrt{n})$となるが、$\sqrt{m/n}$が小さくない場合、アsymptoteは最適なイテレーション数を示す良い指標ではない。
探索の成功確率(目標状態を検出する可能性)のしきい値が設定された反復の正確な数を決定するためのスキームがアルゴリズムの有効性に不可欠である。
本研究は, 1 ドル= 1 のleq m \leq n$ を対象とする,n$-qubit grover の探索アルゴリズムを構成するための一般的なスキームと,検索成功のための最適なイテレーション数を求める手順について述べる。
また、与えられた$n$ と $m$ に対して、アルゴリズムの成功確率に上限があることも示されている。
関連論文リスト
- A Bi-directional Quantum Search Algorithm [30.62704006898929]
本稿では、パーシャルグローバーの探索アルゴリズムと双方向探索を組み合わせて、高速グローバーの量子探索アルゴリズムを作成する。
両方向探索手法をGrover部分探索に組み込み,初期状態と1つのマーク付き状態を並列に比較した。
提案したBDGSアルゴリズムは、最先端のDepth-First Grover's Search (DFGS) とジェネリックGrover's Search (GS) の実装を2〜20ドルでベンチマークする。
論文 参考訳（メタデータ） (2024-04-24T03:11:10Z) - Accelerated quantum search using partial oracles and Grover's algorithm [0.0]
グロバーのアルゴリズム(英: Grover's algorithm)は、順序のないデータベースを探索する手段として考案されたアルゴリズムであり、量子計算によって生成される結果集合から解を抽出するためにも用いられる。
マッチング条件の各ビットに個別のオラクルを関連付け、独立にテスト可能な複数の部分的なオラクル関数を得るという考え方を探求する。
アルゴリズムは最も単純な検索シナリオに対して検証され、入力されたインデックスビットは置換演算を用いてスクランブルされる。
論文 参考訳（メタデータ） (2024-03-19T11:32:02Z) - 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) - 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) - 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) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳（メタデータ） (2022-11-28T08:40:12Z) - Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer [2.487445341407889]
Depth-First SearchとGroverのアルゴリズムを組み合わせてDepth-First Grover Search(DFGS)を生成する
DFGSは未知の解数で非構造化データベース上の複数解探索問題を処理する。
新しいアルゴリズムは$mathcalO(msqrtN)$の平均複雑さを達成し、通常のGrover Searchと同じくらい効率的に機能する。
論文 参考訳（メタデータ） (2022-10-10T13:10:28Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Quantum Approximate Counting with Nonadaptive Grover Iterations [1.14219428942199]
量子設定では、近似カウントは$Oleft(sqrtN/epsilon, sqrtN/K/epsilonright)$クエリで行うことができる。
我々は,非適応的なGrover反復のみを用いるアルゴリズムが$Oleft(sqrtN/epsilonright)$クエリ複雑性を達成可能であることを示す。
論文 参考訳（メタデータ） (2020-10-09T04:48:14Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。