論文の概要: Optimization of probabilistic quantum search algorithm with a priori
information
- arxiv url: http://arxiv.org/abs/2304.02856v1
- Date: Thu, 6 Apr 2023 04:33:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-07 15:13:42.796045
- Title: Optimization of probabilistic quantum search algorithm with a priori
information
- Title（参考訳）: 事前情報を用いた確率的量子探索アルゴリズムの最適化
- Authors: Yutong Huang, Shengshi Pang
- Abstract要約: グロバーの量子探索アルゴリズムは古典計算よりも量子コンピューティングの優位性を証明する典型的な量子アルゴリズムである。
確率的なGroverの探索アルゴリズムにより、データベースの故障確率がゼロでないことを考察する。
オラクル要素の非均一な事前分布では、オラクル呼び出しの数が大幅に削減できることが示される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A quantum computer encodes information in quantum states and runs quantum
algorithms to surpass the classical counterparts by exploiting quantum
superposition and quantum correlation. Grover's quantum search algorithm is a
typical quantum algorithm that proves the superiority of quantum computing over
classical computing. It has a quadratic reduction in the query complexity of
database search, and is known to be optimal when no a priori information about
the elements of the database is provided. In this work, we consider a
probabilistic Grover's search algorithm allowing nonzero probability of failure
for a database with general a priori probability distribution of the elements,
and minimize the number of oracle calls by optimizing the initial state of the
quantum system and the reflection axis of the diffusion operator. The initial
state and the reflection axis are allowed not to coincide, and thus the quantum
search algorithm rotates the quantum system in a three-dimensional subspace
spanned by the initial state, the reflection axis and the search target state.
The number of oracle calls is minimized by a variational method, and formal
analytical results are obtained with the assumption of low failure probability.
The results show that for nonuniform a priori distribution of the oracle
elements, the number of oracle calls can be significantly reduced given a small
decrease in the success probability of the quantum search algorithm, leading to
a lower average number of oracle calls to find the solution of the search
problem. The result is applied to a simple but nontrivial database model which
has $N$ elements with nonuniform two-valued a priori probabilities to show the
effect of the optimized search algorithm. The paper is concluded with a
discussion about the generalization to higher-order results that allows a
larger failure probability for the quantum search algorithm.
- Abstract（参考訳）: 量子コンピュータは量子状態の情報を符号化し、量子重ね合わせと量子相関を利用して量子アルゴリズムを実行する。
グロバーの量子探索アルゴリズムは古典計算よりも量子コンピューティングの優位性を証明する典型的な量子アルゴリズムである。
データベース検索のクエリの複雑さを2次に減らし、データベースの要素に関する事前情報が提供されていない場合に最適であることが知られている。
本研究では,要素の事前確率分布が一般的であるデータベースに対して,非ゼロ故障確率を許容する確率的グローバー探索アルゴリズムを検討し,量子系の初期状態と拡散作用素の反射軸を最適化することにより,oracle呼び出し数を最小化する。
初期状態と反射軸は一致しないので、量子探索アルゴリズムは、初期状態、反射軸および探索対象状態によって広がる3次元部分空間で量子システムを回転させる。
oracleの呼び出し数は変分法によって最小化され、形式的な分析結果は低い失敗確率の仮定で得られる。
その結果, 量子探索アルゴリズムの成功確率が小さくなると, オラクル要素の事前分布が一様でない場合には, オラクル呼び出しの数が大幅に減少し, オラクル呼び出しの平均数が減少し, 探索問題の解が見つかることがわかった。
この結果は、最適化された探索アルゴリズムの効果を示すために、非一様二値の事前確率を持つ$N$要素を持つ単純だが非自明なデータベースモデルに適用される。
この論文は、量子探索アルゴリズムのより大きな故障確率を可能にする高次結果への一般化に関する議論で締めくくられている。
関連論文リスト
- Quantum Architecture Search with Unsupervised Representation Learning [24.698519892763283]
教師なし表現学習は量子アーキテクチャ探索(QAS)を前進させる新しい機会を提供する
QASは変分量子アルゴリズム(VQA)のための量子回路を最適化するように設計されている
論文 参考訳（メタデータ） (2024-01-21T19:53:17Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - Quantum Search Approaches to Sampling-Based Motion Planning [0.0]
本稿では,従来のサンプリング型モーションプランナを,量子探索アルゴリズムを用いて解くことのできるデータベース・オーラル構造として,新しい定式化を提案する。
より単純なスパース環境では、量子完全経路探索アルゴリズム (Quantum Full Path Search Algorithm, Q-FPS) を定式化し、完全なランダムパス解の重ね合わせを生成する。
密集した非構造環境において、親子接続の量子重ね合わせを生成する量子高速探索ランダムツリーアルゴリズム q-RRT を定式化する。
論文 参考訳（メタデータ） (2023-04-10T19:12:25Z) - Quantum algorithm for finding minimum values in a Quantum Random Access
Memory [0.0]
最適古典的決定論的アルゴリズムは、データベース内の要素数と線形に増加する時間複雑性で最小値を見つけることができる。
本稿では,データベースの最小値を求める量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-12T16:22:17Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Speedup for Higher-Order Unconstrained Binary Optimization and
MIMO Maximum Likelihood Detection [2.5272389610447856]
実数値の高次非制約二項最適化問題をサポートする量子アルゴリズムを提案する。
提案アルゴリズムは,古典的領域におけるクエリの複雑さを低減し,量子領域における2次高速化を実現する。
論文 参考訳（メタデータ） (2022-05-31T00:14:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Hardware Efficient Quantum Search Algorithm [17.74233101199813]
本稿では,この課題を克服するために,ハードウェアの効率的な量子探索アルゴリズムを提案する。
我々の鍵となる考え方は、グローバル拡散操作を低コストな局所拡散に置き換えることである。
回路コストの削減は、システムの成功率を著しく向上させる。
論文 参考訳（メタデータ） (2021-03-26T01:08:50Z) - Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。
我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。
我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
論文 参考訳（メタデータ） (2020-12-03T07:12:08Z) - Transition Probabilities in Generalized Quantum Search Hamiltonian
Evolutions [0.0]
本研究では、連続時間量子探索問題において、ソース状態からターゲット状態への遷移確率を計算するために必要な計算面について検討する。
最小探索時間の観点からは、よく知られたFarhi-Gutmannアナログ量子探索アルゴリズムよりも優れていることが分かる。
論文 参考訳（メタデータ） (2020-02-06T13:16:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。