論文の概要: Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits
- arxiv url: http://arxiv.org/abs/2405.12838v1
- Date: Tue, 21 May 2024 14:42:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-22 17:33:24.782727
- Title: Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits
- Title（参考訳）: 量子非同一平均推定:効率的なアルゴリズムと基本限界
- Authors: Jiachen Hu, Tongyang Li, Xinzhao Wang, Yecheng Xue, Chenyi Zhang, Han Zhong,
- Abstract要約: 非同一分散サンプルに対するクエリアクセスの平均推定のための量子アルゴリズムと低境界について検討する。
一方、有界または準ガウス確率変数の2次量子スピードアップを持つ量子平均推定器を与える。
一方、一般に、量子アルゴリズムが古典的なサンプルの数に対して二次的なスピードアップを達成することは不可能であることを示す。
- 参考スコア（独自算出の注目度）: 15.89518426969296
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We systematically investigate quantum algorithms and lower bounds for mean estimation given query access to non-identically distributed samples. On the one hand, we give quantum mean estimators with quadratic quantum speed-up given samples from different bounded or sub-Gaussian random variables. On the other hand, we prove that, in general, it is impossible for any quantum algorithm to achieve quadratic speed-up over the number of classical samples needed to estimate the mean $\mu$, where the samples come from different random variables with mean close to $\mu$. Technically, our quantum algorithms reduce bounded and sub-Gaussian random variables to the Bernoulli case, and use an uncomputation trick to overcome the challenge that direct amplitude estimation does not work with non-identical query access. Our quantum query lower bounds are established by simulating non-identical oracles by parallel oracles, and also by an adversarial method with non-identical oracles. Both results pave the way for proving quantum query lower bounds with non-identical oracles in general, which may be of independent interest.
- Abstract（参考訳）: 非同一分散サンプルに対するクエリアクセスの平均推定のための量子アルゴリズムと下位境界を体系的に検討する。
一方、有界または準ガウス確率変数の2次量子スピードアップを持つ量子平均推定器を与える。
一方、一般に量子アルゴリズムは、平均$\mu$を推定するために必要な古典的なサンプルの数に対して二次的なスピードアップを達成することは不可能であり、そこではサンプルは平均$\mu$に近い確率変数から来る。
技術的には、我々の量子アルゴリズムは有界および準ガウス確率変数をベルヌーイの場合に還元し、直接振幅推定が非同一クエリアクセスでは機能しないという課題を克服するために計算不能なトリックを使用する。
我々の量子クエリローバウンドは、非同一のオークルを並列のオークルでシミュレートし、また非同一のオークルを用いた逆法によっても確立される。
どちらの結果も、量子クエリの低い境界を、一般には独立な関心を持つ非同一のオラクルで証明する方法を舗装している。
関連論文リスト
- Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions [13.16814860487575]
非対数確率分布からサンプリングする量子アルゴリズムを提案する。
f$ は有限和 $f(x):= frac1Nsum_k=1N f_k(x)$ と書くことができる。
論文 参考訳（メタデータ） (2023-10-17T17:55:32Z) - Robust Dequantization of the Quantum Singular value Transformation and
Quantum Machine Learning Algorithms [0.0]
この弱い仮定の下では、ランダム化線形代数の技法がどれだけ多く適用できるかを示す。
また、これらの結果を用いて、多くの量子機械学習アルゴリズムの頑健な復号化を行う。
論文 参考訳（メタデータ） (2023-04-11T02:09:13Z) - One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。
これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
論文 参考訳（メタデータ） (2023-01-05T11:05:22Z) - 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) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Dual-Frequency Quantum Phase Estimation Mitigates the Spectral Leakage
of Quantum Algorithms [76.15799379604898]
量子位相推定は、レコード長の逆数が未知の位相の整数倍でない場合にスペクトルリークに悩まされる。
複数のサンプルが利用できるとき,クレーマー・ラオ境界に近づいた二重周波数推定器を提案する。
論文 参考訳（メタデータ） (2022-01-23T17:20:34Z) - Sampling and the complexity of nature [0.0]
量子サンプリングアルゴリズムの複雑性理論と物理基礎について検討する。
量子サンプリングデバイスをテストしたり、検証したりできる状況と状況について、光を当てています。
テーゼの包括的なテーマは、経路間の破壊的な干渉によって生じる量子サイン問題である。
論文 参考訳（メタデータ） (2020-12-14T19:35:27Z) - Simpler Proofs of Quantumness [16.12500804569801]
量子性の証明は、量子デバイスが古典的なデバイスでは不可能な計算タスクを実行できることを示す方法である。
現在、量子性の証明を示すための3つのアプローチがある。
トラップドアの爪のない関数をベースとした量子性の2次元証明(Challenge-Response)を与える。
論文 参考訳（メタデータ） (2020-05-11T01:31:18Z) - Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
Googleの最近の量子超越性実験は、量子コンピューティングがランダムな回路サンプリングという計算タスクを実行する遷移点を示している。
観測された量子ランタイムの利点の制約を、より多くの量子ビットとゲートで検討する。
論文 参考訳（メタデータ） (2020-05-05T20:11:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。