論文の概要: Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication

• arxiv url: http://arxiv.org/abs/2510.15721v1
• Date: Fri, 17 Oct 2025 15:11:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-20 20:17:34.669482
• Title: Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication
• Title（参考訳）: 行列ベクトル乗算における平均値削減のための量子最悪のケース
• Authors: Divesh Aggarwal, Dexter Kwan,
• Abstract要約: 最悪のケース対平均ケースの削減は、最悪のケースの硬さと平均ケースの計算困難の間の橋渡しとなる。 本研究では,量子設定に焦点をあて,行列の粒度乗算問題に対する新たな還元法を提案する。 我々は、成功確率に依存した平均ケース低減のための量子最悪のケースを得る。
• 参考スコア（独自算出の注目度）: 5.743750345138881
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Worst-case to average-case reductions are a cornerstone of complexity theory, providing a bridge between worst-case hardness and average-case computational difficulty. While recent works have demonstrated such reductions for fundamental problems using deep tools from ad- ditive combinatorics, these approaches often suffer from substantial complexity and suboptimal overheads. In this work, we focus on the quantum setting, and provide a new reduction for the Matrix-Vector Multiplication problem that is more efficient, and conceptually simpler than previous constructions. By adapting hardness self-amplification techniques to the quantum do- main, we obtain a quantum worst-case to average-case reduction with improved dependence on the success probability, laying the groundwork for broader applications in quantum fine-grained complexity.
• Abstract（参考訳）: 最悪のケースから平均ケースへの削減は複雑性理論の基盤であり、最悪のケースの硬さと平均ケースの計算困難の間の橋渡しとなる。 近年の研究では、ディープツールを用いたアドディティブなコンビネータからの基本的問題を減らすことが実証されているが、これらのアプローチは多くの場合、相当な複雑さと準最適オーバーヘッドに悩まされている。 本研究では,従来の構成よりも効率的で概念的にシンプルである行列ベクトル乗算問題に対して,量子設定に焦点をあてる。 量子do-mainにハードネス自己増幅技術を適用することで、成功確率への依存性を改善した平均ケース削減に量子最悪のケースが得られ、量子微細化複雑性における幅広い応用の基礎となる。

関連論文リスト

• Towards Quantum Accelerated Large-scale Topology Optimization [0.0]
  本稿では,TO問題を効率的に解き,量子コンピューティングを利用して潜在的な量子優位性を利用するための実践的な方法を提案する。 本研究は,3次元連続体構造における大規模・多材料TO課題を対象としている。
  論文  参考訳（メタデータ） (2025-07-19T04:30:14Z)
• Maximizing the practical achievability of quantum annealing attacks on factorization-based cryptography [0.0]
  本研究は、整数分解問題と離散対数問題に基づくスキームの暗号解析のための量子的手法に焦点を当てる。 本稿では、量子計算と古典計算を組み合わせたアプローチを改善することにより、分解問題の最大の事例を現実的に解く方法を示す。
  論文  参考訳（メタデータ） (2024-10-07T11:55:23Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Divide-and-conquer embedding for QUBO quantum annealing [0.0]
  組込み問題に焦点をあてたアプローチは、桁違いに性能を向上できることを示す。 以上の結果から,組込み問題に焦点をあてたアプローチにより,桁違いの性能向上が期待できることがわかった。
  論文  参考訳（メタデータ） (2022-11-03T23:22:06Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  本稿では,グラフニューラルネットワーク(GNN)と組み合わせた強化学習(RL)手法を提案する。 この問題は、巨大な検索スペース、重い尾の報酬分布、そして困難なクレジット割り当てのために非常に難しい。 GNNを基本方針として利用するRLエージェントが,これらの課題にどのように対処できるかを示す。
  論文  参考訳（メタデータ） (2022-04-18T21:45:13Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。 私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。 実際の量子コンピュータを用いて得られた結果について述べる。
  論文  参考訳（メタデータ） (2022-01-25T05:59:24Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• Robust and Fast Holonomic Quantum Gates with Encoding on Superconducting Circuits [4.354697470999286]
  超伝導回路上での普遍ホロノミック量子ゲートの簡易実装を提案する。 提案手法は従来よりも堅牢であり,スケーラブルなフォールトトレラント量子計算のための代替戦略として有望なものである。
  論文  参考訳（メタデータ） (2020-04-23T13:26:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。