論文の概要: Few Quantum Algorithms on Amplitude Distribution
- arxiv url: http://arxiv.org/abs/2208.00162v2
- Date: Fri, 20 Jan 2023 18:53:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-02 23:54:38.176090
- Title: Few Quantum Algorithms on Amplitude Distribution
- Title（参考訳）: 振幅分布に関する量子アルゴリズム
- Authors: Debajyoti Bera and Tharrmashastha Sapv
- Abstract要約: 振幅フィルタリングは、振幅が指定されたしきい値より大きい重ね合わせにおける基底状態の同定に関係している。
量子ビットの不足を考えると、この研究の焦点はログ空間のアルゴリズムを設計することである。
- 参考スコア（独自算出の注目度）: 0.5584060970507505
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Amplitude filtering is concerned with identifying basis-states in a
superposition whose amplitudes are greater than a specified threshold;
probability filtering is defined analogously for probabilities. Given the
scarcity of qubits, the focus of this work is to design log-space algorithms
for them. Both algorithms follow a similar pattern of estimating the amplitude
(or, probability for the latter problem) of each state, in superposition, then
comparing each estimate against the threshold for setting up a flag qubit upon
success, finally followed by amplitude amplification of states in which the
flag is set. We show how to implement each step using very few qubits by
designing three subroutines. Our first algorithm performs amplitude
amplification even when the "good state'' operator has a small probability of
being incorrect -- here we improve upon the space complexity of the previously
known algorithms. Our second algorithm performs "true amplitude estimation'' in
roughly the same complexity as that of "amplitude estimation'', which actually
estimates a probability instead of an amplitude. Our third algorithm is for
performing amplitude estimation in parallel (superposition) which is difficult
when each estimation branch involves different oracles. As an immediate reward,
we observed that the above algorithms for the filtering problems directly
improved the upper bounds on the space-bounded query complexity of problems
such as non-linearity estimation of Boolean functions and $k$-distinctness.
- Abstract（参考訳）: 振幅フィルタリングは、振幅が特定のしきい値より大きい重ね合わせにおける基底状態の同定に関係しており、確率フィルタリングは確率に対して類似して定義される。
qubitsの不足を考えると、この取り組みの焦点はログスペースアルゴリズムを設計することである。
どちらのアルゴリズムも、重ね合わせで各状態の振幅(あるいは後者の問題の確率)を推定し、各推定値と成功時のフラグキュービットを設定するしきい値を比較し、最後にフラグが設定された状態の振幅増幅を行うという類似のパターンに従う。
3つのサブルーチンを設計することで,ごくわずかなキュービットで各ステップを実装する方法を示す。
第1のアルゴリズムは,「よい状態」演算子が誤り確率が小さい場合であっても振幅増幅を行う。ここでは,既知のアルゴリズムの空間複雑性を改善する。第2のアルゴリズムは,振幅ではなく実際に確率を推定する「振幅推定」とほぼ同じ複雑さで「真の振幅推定」を行う。
第3のアルゴリズムは並列(重畳)で振幅推定を行うためであり、各推定分岐が異なるオラクルを含む場合、その計算は困難である。
その報奨として,上記のフィルタリング問題に対するアルゴリズムは,ブール関数の非線形性推定や$k$-distinctnessといった問題に対する空間境界付きクエリの複雑性の上限を直接改善した。
関連論文リスト
- Quantum amplitude estimation from classical signal processing [0.0]
本稿では, 振幅推定の問題は, 到着方向推定と呼ばれる信号処理における問題に直接対応できることを示す。
位相推定自由な並列量子振幅推定(QAE)アルゴリズムを作成し、全クエリの複雑さは$sim 4.9/varepsilon$で、並列クエリの複雑さは$sim 0.40/varepsilon$で95%の信頼性を持つ。
論文 参考訳（メタデータ） (2024-05-23T15:31:46Z) - Optimal Coherent Quantum Phase Estimation via Tapering [0.0]
量子位相推定は、多くの量子アルゴリズムを支える基本的なプリミティブの1つである。
我々は,テープ型量子位相推定アルゴリズムと呼ばれる標準アルゴリズムの改良版を提案する。
提案アルゴリズムは,高コストなコヒーレント中央値手法を必要とせず,最適なクエリ複雑性を実現する。
論文 参考訳（メタデータ） (2024-03-27T18:17:23Z) - On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。
A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
論文 参考訳（メタデータ） (2023-08-23T08:38:53Z) - Amplitude amplification-inspired QAOA: Improving the success probability
for solving 3SAT [55.78588835407174]
振幅増幅アルゴリズムは、可変代入を満たすために非構造化探索に適用することができる。
Quantum Approximate Optimization Algorithm (QAOA)は、ノイズのある中間量子デバイスのための3SATを解くための有望な候補である。
振幅増幅によるQAOAの変種を導入し、3SATの成功確率を改善する。
論文 参考訳（メタデータ） (2023-03-02T11:52:39Z) - The Adversary Bound Revisited: From Optimal Query Algorithms to Optimal
Control [0.0]
このノートは"One-Way Ticket to Las Vegas and the Quantum Adversary"という論文を補完している。
私は、Barnum-Saks-Szegedyと同じ視点で、逆境界-普遍アルゴリズムの双対性を異なる形で開発する。
論文 参考訳（メタデータ） (2022-11-29T15:25:45Z) - Amplitude Estimation from Quantum Signal Processing [0.30458514384586405]
振幅推定アルゴリズムはGroverのアルゴリズムに基づいており、入力状態と所望の結果に関する反射を交互に行う。
量子信号処理により、より柔軟な方法で振幅を推定できることがわかった。
論文 参考訳（メタデータ） (2022-07-18T14:22:10Z) - Adaptive Algorithm for Quantum Amplitude Estimation [13.82667502131475]
振幅の間隔推定のための適応アルゴリズムを提案する。
提案アルゴリズムは、同じレベルの精度を達成するために、同じ数の量子クエリを使用する。
我々は,古典モンテカルロサンプリングに対する2次高速化として,オラクルクエリの数が$O(1/epsilon)$に達することを厳密に証明する。
論文 参考訳（メタデータ） (2022-06-16T21:11:15Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - A Systematic Characterization of Sampling Algorithms for Open-ended
Language Generation [71.31905141672529]
本稿では,自己回帰型言語モデルに広く採用されている祖先サンプリングアルゴリズムについて検討する。
エントロピー低減, 秩序保存, 斜面保全の3つの重要な特性を同定した。
これらの特性を満たすサンプリングアルゴリズムのセットが,既存のサンプリングアルゴリズムと同等に動作することがわかった。
論文 参考訳（メタデータ） (2020-09-15T17:28:42Z) - Beyond Worst-Case Analysis in Stochastic Approximation: Moment
Estimation Improves Instance Complexity [58.70807593332932]
近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。
最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。
提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
論文 参考訳（メタデータ） (2020-06-08T09:25:47Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。