論文の概要: Quantum Worst-Case to Average-Case Reductions for All Linear Problems
- arxiv url: http://arxiv.org/abs/2212.03348v1
- Date: Tue, 6 Dec 2022 22:01:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-09 18:43:03.772531
- Title: Quantum Worst-Case to Average-Case Reductions for All Linear Problems
- Title(参考訳): 全線形問題に対する平均値削減のための量子最悪のケース
- Authors: Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar,
Sathyawageeswar Subramanian
- Abstract要約: 量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
- 参考スコア(独自算出の注目度): 66.65497337069792
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of designing worst-case to average-case reductions for
quantum algorithms. For all linear problems, we provide an explicit and
efficient transformation of quantum algorithms that are only correct on a small
(even sub-constant) fraction of their inputs into ones that are correct on all
inputs. This stands in contrast to the classical setting, where such results
are only known for a small number of specific problems or restricted
computational models. En route, we obtain a tight $\Omega(n^2)$ lower bound on
the average-case quantum query complexity of the Matrix-Vector Multiplication
problem.
Our techniques strengthen and generalise the recently introduced additive
combinatorics framework for classical worst-case to average-case reductions
(STOC 2022) to the quantum setting. We rely on quantum singular value
transformations to construct quantum algorithms for linear verification in
superposition and learning Bogolyubov subspaces from noisy quantum oracles. We
use these tools to prove a quantum local correction lemma, which lies at the
heart of our reductions, based on a noise-robust probabilistic generalisation
of Bogolyubov's lemma from additive combinatorics.
- Abstract(参考訳): 量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
すべての線形問題に対して、我々は量子アルゴリズムの明示的かつ効率的な変換を提供し、それらは入力の小さな(定数以下の)分数のみを全ての入力で正しい分数に変換する。
これは古典的な設定とは対照的であり、そのような結果は少数の特定の問題や制限された計算モデルでのみ知られている。
その過程で,行列-ベクトル乗算問題の平均ケース量子クエリの複雑性に対して,厳密な$\Omega(n^2)$ローバウンドを求める。
提案手法は,最近導入された古典的最悪ケースから平均ケース還元までの加算コンビネータの枠組み(stoc 2022)を強化し,一般化する。
我々は量子特異値変換に頼り、重ね合わせにおける線形検証とボゴリューボフ部分空間のノイズ量子オラクルからの学習のための量子アルゴリズムを構築する。
我々はこれらのツールを用いて、ボゴリューボフの補題の雑音ロバスト確率的一般化に基づく減算の中心にある量子局所補正補題の証明を行う。
関連論文リスト
- Solving non-native combinatorial optimization problems using hybrid
quantum-classical algorithms [0.0]
組合せ最適化は、物流から金融まで幅広い分野に適用可能な、困難な問題である。
量子コンピューティングは、様々なアルゴリズムを用いてこれらの問題を解決するために使われてきた。
この研究は、量子と古典のリソースをハイブリッドなアプローチで統合することで、これらの課題を克服する枠組みを提示している。
論文 参考訳(メタデータ) (2024-03-05T17:46:04Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳(メタデータ) (2023-10-04T17:53:55Z) - Practical limitations of quantum data propagation on noisy quantum
processors [1.2891210250935146]
行列を高い条件数で反転させるのに古典的な計算を必要とする量子アルゴリズムは、誤り確率が非常に低い単一および2量子ゲートを必要とすることを示す。
我々の研究は、ノイズの多い環境下で実行できるハイブリッド量子古典アルゴリズムの主流概念に挑戦する。
論文 参考訳(メタデータ) (2023-06-22T17:12:52Z) - Formulation of the Electric Vehicle Charging and Routing Problem for a
Hybrid Quantum-Classical Search Space Reduction Heuristic [0.0]
制約付き量子最適化アルゴリズムの構築において、量子情報の多レベルキャリア -- 量子ビット -- をどのように活用するかを示す。
本稿では,制約付き解をサンプリングし,探索空間を大幅に削減するハイブリッド古典量子戦略を提案する。
論文 参考訳(メタデータ) (2023-06-07T13:16:15Z) - 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 communication complexity of linear regression [0.05076419064097732]
量子コンピュータは、いくつかの基本的な線形代数問題に対する通信の観点から、証明可能かつ指数関数的なスピードアップを持つことを示す。
本稿では,量子特異値変換のための効率的な量子プロトコルを提案する。
論文 参考訳(メタデータ) (2022-10-04T13:27:01Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳(メタデータ) (2022-09-28T17:53:25Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - Quantum Error Mitigation Relying on Permutation Filtering [84.66087478797475]
本稿では,既存の置換に基づく手法を特殊なケースとして含む,置換フィルタ(permutation filters)と呼ばれる一般的なフレームワークを提案する。
提案するフィルタ設計アルゴリズムは, 常に大域的最適度に収束し, フィルタが既存の置換法よりも大幅に改善できることを示す。
論文 参考訳(メタデータ) (2021-07-03T16:07:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。