論文の概要: 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) など、幅広い範囲でパフォーマンスが低下する多段階ハイブリッド検索アルゴリズムが実現される。
探索加速度は探索空間の順序を動的に発見し、その順序は部分オラクル関数と探索インデックスの相関関係から成り立っている。
このアルゴリズムは最も単純な検索シナリオに対して検証される。
関連論文リスト
- Near-deterministic quantum search algorithm without phase control [10.754825115553086]
グローバーのアルゴリズムは、4つのうち1つを検索した場合にのみ、ターゲット項目を確実に見つけることができる。
位相制御のないほぼ決定論的量子探索アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-15T14:20:47Z) - Auditable Algorithms for Approximate Model Counting [31.609554468870382]
我々は、$Sigma3P$ oracleを呼び出す新しい決定論的近似カウントアルゴリズムを開発したが、より少ない変数で$SigmaP$ oracleを使用して認証することができる。
これは、監査の複雑さが近似カウントの複雑さのためにどのように交換できるかを初めて示す。
論文 参考訳（メタデータ） (2023-12-19T17:47:18Z) - 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) - 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) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Deterministic Grover search with a restricted oracle [2.976027966501599]
グロバーの量子探索アルゴリズムは古典的アルゴリズムよりも二次的な量子的優位性を提供する。
量子探索オラクルをユーザが制御することなく、正しい結果を返すための修正版を提示する。
論文 参考訳（メタデータ） (2022-01-01T02:04:11Z) - 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) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Towards Meta-Algorithm Selection [78.13985819417974]
インスタンス固有のアルゴリズム選択(AS)は、固定された候補集合からのアルゴリズムの自動選択を扱う。
メタアルゴリズムの選択は、いくつかのケースで有益であることを示す。
論文 参考訳（メタデータ） (2020-11-17T17:27:33Z) - Grover's search algorithm for $n$ qubits with optimal number of
iterations [0.0]
グローバーの探索アルゴリズムは、グローバーの拡散操作に続くオラクルの合成操作の繰り返し数に依存する。
1leq M leq N$ターゲット状態を持つ$n$-qubit Groverの探索アルゴリズムを構築するための一般的なスキームを示す。
論文 参考訳（メタデータ） (2020-11-08T18:46:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。