論文の概要: Quantum Query Complexity Beyond the Worst Case

• arxiv url: http://arxiv.org/abs/2609.35580v1
• Date: Mon, 28 Sep 2026 16:35:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 20:37:24.364416
• Title: Quantum Query Complexity Beyond the Worst Case
• Title（参考訳）: 最悪の場合を超えた量子クエリの複雑さ
• Abstract要約: 量子クエリの複雑さが古典的なクエリの複雑さよりも指数関数的に小さい全関数が存在することを示す。 また,スムース化により,最悪の解析結果よりも大きな量子スピードアップが期待できることを示す。
• 参考スコア（独自算出の注目度）: 3.3564219191591125
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in practice. We initiate a systematic study of its quantum counterpart and show the following results. $(1)$ We show that there is a total function whose smoothed quantum query complexity is exponentially smaller than its classical query complexity. $(2)$ We give near-tight characterizations of smoothed randomized and quantum query complexities for symmetric Boolean functions, unifying the worst-case complexity results of [Beals et al, FOCS'98] and average-case complexity results of [Ambainis and de Wolf, STACS'00]. $(3)$ We study string problems such as pattern matching and edit distance and, in various regimes, give polynomial to superpolynomial quantum speedups. Our main technical ingredients include a near-tight quantum algorithm for $\varepsilon$-approximating the number of collisions between two non-repetitive strings, improving the result of Le Gall and Ng [QIC'22]. Together, our results show that smoothing can reveal larger quantum speedups than worst-case analysis suggests, opening a path towards quantum advantage on more realistic inputs.
• Abstract（参考訳）: スムース解析は、アルゴリズムの性能を最悪の場合を超えて説明するための古典的なアルゴリズムの中心的なフレームワークであり、しばしばアルゴリズムが実際にうまく機能する理由を説明する。 量子対する量子の体系的な研究を開始し、以下の結果を示す。 ここでは、スムーズな量子クエリの複雑性が古典的なクエリの複雑さよりも指数関数的に小さい全関数が存在することを示す。 $(2)$ 対称ブール関数に対するスムーズなランダム化および量子クエリの複雑さのほぼ28の特徴づけを与え、[Beals et al, FOCS'98] の最悪の複雑性結果と[Ambainis and de Wolf, STACS'00] の平均複雑性結果を統一する。 $(3)$ パターンマッチングや編集距離などの文字列問題を研究し、様々なレシエーションにおいて、超多項式的な量子スピードアップに多項式を与える。 我々の主な技術要素は、2つの非反復弦間の衝突数を近似する$\varepsilon$-approximating $\varepsilonの量子アルゴリズムであり、Le Gall と Ng [QIC'22] の結果を改善している。 その結果、スムーシングは最悪のケース分析より大きな量子スピードアップを示し、より現実的な入力に対する量子優位性への道を開くことができた。

関連論文リスト

• Parameterized quantum algorithms for closest string problems [0.42970700836450487]
  CSP(Closest String Problem)とCSSP(Closest Substring Problem)の3つの量子アルゴリズムを提案する。 各アルゴリズムは、特定の設定で古典的なアルゴリズムよりも優れた性能を示す。 また、二進アルファベットを持つCSPの条件付き下界を導出し、最初のアルゴリズムがその支配的なスケーリング係数において厳密であることを示す。
  論文  参考訳（メタデータ） (2025-10-17T11:01:15Z)
• Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
  量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。 近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。 提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
  論文  参考訳（メタデータ） (2024-09-05T17:56:51Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  特に、状態準備および読み出しプロセスのような実装のいくつかのステップは、アルゴリズム自体の複雑さの側面を超越することができる。 本稿では、方程式の線形系と微分方程式の線形系を解くための量子アルゴリズムの完全な実装に関わる複雑性について述べる。
  論文  参考訳（メタデータ） (2021-06-23T16:33:33Z)

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

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