論文の概要: Accelerated quantum search using partial oracles and Grover's algorithm

• arxiv url: http://arxiv.org/abs/2403.13035v2
• Date: Mon, 18 Nov 2024 16:50:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-19 14:28:52.995851
• Title: Accelerated quantum search using partial oracles and Grover's algorithm
• Title（参考訳）: 部分オラクルとグローバーアルゴリズムを用いた加速量子探索
• Authors: Fintan M. Bolton,
• Abstract要約: グロバーのアルゴリズム(英: Grover's algorithm)は、順序のないデータベースを探索する手段として考案されたアルゴリズムであり、量子計算によって生成される結果集合から解を抽出するためにも用いられる。 マッチング条件の各ビットに個別のオラクルを関連付け、独立にテスト可能な複数の部分的なオラクル関数を得るという考え方を探求する。 アルゴリズムは最も単純な検索シナリオに対して検証され、入力されたインデックスビットは置換演算を用いてスクランブルされる。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Grover's algorithm, orginally conceived as a means of searching an unordered database, can also be used to extract solutions from the result sets generated by quantum computations. The Grover 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), where searching for 1 target item in a search space of size $N$ scales as $\mathcal{O}(\sqrt{N})$ oracle queries. 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))$. The algorithm is validated against the simplest kind of search scenario, where the incoming index bits are scrambled using a permutation operation.
• Abstract（参考訳）: グロバーのアルゴリズム(英: Grover's algorithm)は、順序のないデータベースを探索する手段として考案されたアルゴリズムであり、量子計算によって生成される結果集合から解を抽出するためにも用いられる。 Groverアルゴリズムは、探索項目をマッチングするプロセス(マッチと0を返します)を抽象化するオラクル関数の概念を利用しており、そこでは1つのターゲット項目を検索空間で$N$スケールして$\mathcal{O}(\sqrt{N})$ Oracleクエリとして検索する。 本稿では,個別のオラクルをマッチング条件の各ビットに関連付け,独立にテスト可能な複数の部分的なオラクル関数を得るという考え方について検討する。 このアイデアを探索することで、$\mathcal{O}(\sqrt{N})$ (Same as Grover) や$\mathcal{O}(\log(N))$ (same as Grover)$)$ (same as Grover)$ (same as $\mathcal{O}(\log(N))$)$ の任意の範囲でパフォーマンスが低下する多段階ハイブリッド検索アルゴリズムが実現される。 アルゴリズムは最も単純な検索シナリオに対して検証され、入力されたインデックスビットは置換演算を用いてスクランブルされる。

関連論文リスト

• Near-deterministic quantum search algorithm without phase design [10.754825115553086]
  グローバーのアルゴリズムは、4つのうち1つを探索した場合にのみ、確実にターゲット状態を見つけることができる。 決定論的探索アルゴリズムは8,16,32のうち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)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。