論文の概要: Accelerated quantum search using partial oracles and Grover's algorithm
- arxiv url: http://arxiv.org/abs/2403.13035v1
- Date: Tue, 19 Mar 2024 11:32:02 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-21 20:59:01.715761
- Title: Accelerated quantum search using partial oracles and Grover's algorithm
- Title(参考訳): 部分オラクルとグローバーアルゴリズムを用いた加速量子探索
- Authors: Fintan M. Bolton,
- Abstract要約: グロバーのアルゴリズム(英: Grover's algorithm)は、順序のないデータベースを探索する手段として考案されたアルゴリズムであり、量子計算によって生成された結果集合から解を抽出する手法としても用いられる。
本稿では,個別のオラクルをマッチング条件の各ビットに関連付け,独立にテスト可能な複数の部分的なオラクル関数を得るという考え方について検討する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Grover's algorithm, orginally conceived as a means of searching an unordered database, can also be used as a technique for extracting solutions from the result sets generated by quantum computations. The algorithm exploits the concept of an oracle function, which abstracts the process of matching a search item (returning 1 for a match and 0 otherwise). This black-box approach hides the details of a search problem and works with the assumption that the items in the search space are completely unordered. In this case, searching for 1 target item in a search space of size $N$ scales as $\mathcal{O}(\sqrt{N})$ oracle queries (or $\mathcal{O}(\sqrt{N/M})$ oracle queries for $M$ target items in a search space of size $N$). Hidden inside the typical black-box oracle, however, the process of matching an item usually involves matching multiple data bits. In this article, we explore the idea of associating a separate oracle with each bit of the matching condition, obtaining multiple partial oracle functions which can be tested independently. Exploring this idea leads to a multi-stage hybrid search algorithm, whose performance can fall within a wide range, anywhere between $\mathcal{O}(\sqrt{N})$ (same as Grover) or $\mathcal{O}(\log(N))$ (exponentially faster). Apparently, the search acceleration works by dynamically discovering order in the search space, where the order consists of correlations between the partial oracle functions and the search index. This new algorithm is validated against the simplest kind of search scenario.
- Abstract(参考訳): グロバーのアルゴリズム(英: Grover's algorithm)は、順序のないデータベースを探索する手段として考案されたアルゴリズムであり、量子計算によって生成された結果集合から解を抽出する手法としても用いられる。
このアルゴリズムはオラクル関数の概念を利用して、検索項目をマッチングするプロセスを抽象化する(マッチと0を返却する)。
このブラックボックスアプローチは、検索問題の詳細を隠蔽し、検索空間内のアイテムが完全に順序づけられていないという仮定で機能する。
この場合、サイズ$N$の検索空間で1つのターゲット項目を検索すると、$\mathcal{O}(\sqrt{N})$oracleクエリ(または$\mathcal{O}(\sqrt{N/M})$oracleクエリ)としてスケールする。
しかし、典型的なブラックボックスのオラクルの中に隠されているアイテムをマッチングするプロセスは、通常複数のデータビットをマッチングする。
本稿では,個別のオラクルをマッチング条件の各ビットに関連付け,独立にテスト可能な複数の部分的なオラクル関数を得るという考え方について検討する。
このアイデアを探索することで、(Groverのように)$\mathcal{O}(\sqrt{N})$ (Same as Grover) や$\mathcal{O}(\log(N))$ (exponentially faster) など、幅広い範囲でパフォーマンスが低下する多段階ハイブリッド検索アルゴリズムが実現される。
探索加速度は探索空間の順序を動的に発見し、その順序は部分オラクル関数と探索インデックスの相関関係から成り立っている。
このアルゴリズムは最も単純な検索シナリオに対して検証される。
関連論文リスト
- BQP, meet NP: Search-to-decision reductions and approximate counting [0.0]
本稿では,探索-決定還元と近似カウントという,ブール充足可能性(SAT)問題の研究の2つの基本的な課題に焦点をあてる。
まず、ポリ時間チューリングマシンがNPオラクルに対して$Theta(n)$クエリを必要とする古典的な設定とは対照的に、量子的には$Theta(log n)$クエリが十分であることを示す。
近似カウンティングに移行し、探索-決定還元と近似カウンティングの量子リンクを利用して、既存の古典的近似カウンティングアルゴリズムが最適であることを示す。
論文 参考訳(メタデータ) (2024-01-08T14:59:48Z) - Fast Interactive Search with a Scale-Free Comparison Oracle [17.38671584773247]
比較ベースの検索アルゴリズムにより、ユーザはフォームのクエリに応答してデータベース内のターゲットアイテム$t$を見つけることができる。
そのような類似性三重項に対して$(i,j;t)$に対して$gamma$-CKLと呼ばれるスケールフリー確率オラクルモデルを提案する。
我々は,バックトラッキング戦略により,$gamma$-CKL のオラクルの下で,指数関数的に収束率の高い探索アルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-06-02T09:33:19Z) - Quantum Algorithms for Identifying Hidden Strings with Applications to
Matroid Problems [8.347058637480506]
我々は、ペアの$s, s'$を特定するために、最大内部積のオラクルに$O(1)$クエリを消費する量子アルゴリズムを提案する。
また、サブセットのオラクルに$fracn2+O(sqrtn)$クエリを消費する量子アルゴリズムを提案し、任意の古典的アルゴリズムが少なくとも$n+Omega(1)$クエリを必要とすることを証明した。
論文 参考訳(メタデータ) (2022-11-19T11:14:19Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳(メタデータ) (2022-05-19T16:04:40Z) - Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
本稿では,長距離接続を伴う複雑な検索空間上に探索アルゴリズムを構築する。
我々はtextbfIF-NAS という単純なアルゴリズムを提案し、異なるサブネットワークを構築するために周期的なサンプリング戦略を実行する。
提案した探索空間において、IF-NASはランダムサンプリングと従来の重み付け検索のアルゴリズムを有意差で上回っている。
論文 参考訳(メタデータ) (2021-12-05T06:42:48Z) - How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。
本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。
さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
論文 参考訳(メタデータ) (2021-10-05T20:15:35Z) - Simplified Quantum Algorithm for the Oracle Identification Problem [0.0]
oracleは未知の文字列のビットに$x$ of length$n$をアクセスし、既知のセットである$Csubseteq0,1n$に属することを約束する。
目標は、できるだけ少数のオラクルへのクエリを使って$x$を識別することだ。
この問題に対して,クエリ複雑性を$Oleft(sqrtfracnlog M log(n/log M)+1right)$,$M$は$C$である。
論文 参考訳(メタデータ) (2021-09-08T19:48:27Z) - Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with
a Faulty Oracle [7.449644976563424]
本稿では,クラスタリングを不良オラクルで研究するためのエレガントな理論的モデルを提案する。
一般の場合の$k$クラスタに対して、クエリ最適で時間効率のアルゴリズムを得られるかどうかというオープンな疑問として残された。
情報理論の回復が可能であれば,全ての定数$k$に対して,ほぼ最適なクエリ複雑性(最大$O(log2 n)$)を持つ時間効率アルゴリズムを提供する。
論文 参考訳(メタデータ) (2021-06-18T22:20:12Z) - Determinantal Beam Search [75.84501052642361]
ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。
複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。
ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
論文 参考訳(メタデータ) (2021-06-14T13:01:46Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳(メタデータ) (2021-06-04T02:32:26Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。