論文の概要: 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)を強化し,一般化する。
我々は量子特異値変換に頼り、重ね合わせにおける線形検証とボゴリューボフ部分空間のノイズ量子オラクルからの学習のための量子アルゴリズムを構築する。
我々はこれらのツールを用いて、ボゴリューボフの補題の雑音ロバスト確率的一般化に基づく減算の中心にある量子局所補正補題の証明を行う。
関連論文リスト
- Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
現在利用可能な量子デバイスは、限られた量子ビットと高いレベルのノイズしか持たず、それらのデバイスで正確に解決できる問題のサイズを制限している。
我々は、変分量子アルゴリズム -- 離散化量子排他探索 -- を改善する新しい方法を提案する。
論文 参考訳（メタデータ） (2024-07-24T22:06:05Z) - Qubit-efficient quantum combinatorial optimization solver [0.0]
そこで我々は,候補ビット解をより少ない量子ビットの絡み合った波動関数にマッピングすることで,制限を克服する量子ビット効率のアルゴリズムを開発した。
このアプローチは、短期的な中間スケールと将来のフォールトトレラントな小規模量子デバイスに有効である。
論文 参考訳（メタデータ） (2024-07-22T11:02:13Z) - A quantum annealing approach to the minimum distance problem of quantum codes [0.0]
本稿では,量子安定化器符号の最小距離を準拘束的二項最適化問題として再定式化することで計算する手法を提案する。
D-Wave Advantage 4.1quantum annealerと比較することにより,本手法の実用性を示す。
論文 参考訳（メタデータ） (2024-04-26T21:29:42Z) - Lower bounds for quantum-inspired classical algorithms via communication complexity [0.5461938536945723]
線形回帰の解法,クラスタリングの監督,主成分分析,レコメンデーションシステム,ハミルトニアンシミュレーションに焦点をあてる。
基底行列のフロベニウスノルムの観点で二次下界を証明する。
これらの問題に対する量子アルゴリズムはフロベニウスノルムにおいて線型であるため、この結果は量子古典的分離が少なくとも二次的であることを意味する。
論文 参考訳（メタデータ） (2024-02-24T02:15:00Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。