論文の概要: Quantum algorithm for approximating the expected value of a random-exist quantified oracle
- arxiv url: http://arxiv.org/abs/2412.00567v1
- Date: Sat, 30 Nov 2024 19:42:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-04 15:42:13.941253
- Title: Quantum algorithm for approximating the expected value of a random-exist quantified oracle
- Title（参考訳）: ランダム存在量化オラクルの期待値を近似するための量子アルゴリズム
- Authors: Caleb Rotello,
- Abstract要約: 量子振幅増幅と推定は、非構造化探索と推定タスクに二次的なスピードアップを示す。
これらの量子アルゴリズムのコヒーレントな組み合わせは、ランダムに存在する量子化されたオラクルの期待値を計算するための二次的なスピードアップも提供することを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Quantum amplitude amplification and estimation have shown quadratic speedups to unstructured search and estimation tasks. We show that a coherent combination of these quantum algorithms also provides a quadratic speedup to calculating the expectation value of a random-exist quantified oracle. In this problem, Nature makes a decision randomly, i.e. chooses a bitstring according to some probability distribution, and a player has a chance to react by finding a complementary bitstring such that an black-box oracle evaluates to $1$ (or True). Our task is to approximate the probability that the player has a valid reaction to Nature's initial decision. We compare the quantum algorithm to the average-case performance of Monte-Carlo integration over brute-force search, which is, under reasonable assumptions, the best performing classical algorithm. We find the performance separation depends on some problem parameters, and show a regime where the canonical quadratic speedup exists.
- Abstract（参考訳）: 量子振幅増幅と推定は、非構造化探索と推定タスクに二次的なスピードアップを示す。
これらの量子アルゴリズムのコヒーレントな組み合わせは、ランダムに存在する量子化されたオラクルの期待値を計算するための二次的なスピードアップも提供することを示す。
この問題において、Natureはランダムに決定する、すなわち確率分布に応じてビットストリングを選択し、プレイヤーはブラックボックスのオラクルが1ドル(またはTrue)と評価されるような補完的なビットストリングを見つけることで反応する。
我々の課題は、プレイヤーがネイチャーの最初の決定に対して有効な反応をする確率を近似することである。
量子アルゴリズムとモンテカルロ積分の平均ケース性能を比較した。
性能分離はいくつかの問題パラメータに依存しており、正準二次的スピードアップが存在する状態を示す。
関連論文リスト
- Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Recovering the original simplicity: succinct and deterministic quantum
algorithm for the welded tree problem [0.0]
この研究は、よく知られた溶接木問題に対する量子アルゴリズムを再考する。
最も単純な量子ウォークに基づく非常に簡潔な量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-17T16:03:50Z) - Quantum Search Approaches to Sampling-Based Motion Planning [0.0]
本稿では,従来のサンプリング型モーションプランナを,量子探索アルゴリズムを用いて解くことのできるデータベース・オーラル構造として,新しい定式化を提案する。
より単純なスパース環境では、量子完全経路探索アルゴリズム (Quantum Full Path Search Algorithm, Q-FPS) を定式化し、完全なランダムパス解の重ね合わせを生成する。
密集した非構造環境において、親子接続の量子重ね合わせを生成する量子高速探索ランダムツリーアルゴリズム q-RRT を定式化する。
論文 参考訳（メタデータ） (2023-04-10T19:12:25Z) - Opening the Black Box Inside Grover's Algorithm [0.0]
グロバーのアルゴリズムは、量子コンピュータが古典的コンピュータよりも有利であることを示す主要なアルゴリズムである。
我々は,古典的コンピュータ上で動作可能な量子インスパイアされたアルゴリズムを構築し,Groverのタスクを,オラクルへの(シミュレーションの)呼び出し数で線形に実行する。
論文 参考訳（メタデータ） (2023-03-20T17:56:20Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
論文 参考訳（メタデータ） (2023-03-02T05:08:15Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Deterministic Grover search with a restricted oracle [2.976027966501599]
グロバーの量子探索アルゴリズムは古典的アルゴリズムよりも二次的な量子的優位性を提供する。
量子探索オラクルをユーザが制御することなく、正しい結果を返すための修正版を提示する。
論文 参考訳（メタデータ） (2022-01-01T02:04:11Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。