論文の概要: Noisy Quantum Query Complexity via Fractional Block Sensitivity

• arxiv url: http://arxiv.org/abs/2610.00506v2
• Date: Fri, 02 Oct 2026 22:31:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-07 04:43:28.497831
• Title: Noisy Quantum Query Complexity via Fractional Block Sensitivity
• Title（参考訳）: 分数ブロック感度によるノイズ量子クエリ複雑性
• Abstract要約: 我々は、不完全オラクルアクセスのいくつかのモデルの下で、量子クエリの複雑さについて研究する。 我々は、分数ブロック感度(operatornamefbs$)に基づく共通フレームワークを通して下位境界を開発する。
• 参考スコア（独自算出の注目度）: 0.34410212782758043
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study quantum query complexity under several models of imperfect oracle access, and develop lower bounds through a common framework based on fractional block sensitivity ($\operatorname{fbs}$). For a negligent oracle that applies the correct query with probability $1-p$, we prove a lower bound in terms of $\operatorname{fbs}(f,0^n)$. We also show, perhaps surprisingly, that negligence need not destroy quantum speedups: any function $f$ can be transformed into a partial function $f'$ whose negligent query complexity essentially preserves the quantum query complexity of $f$. This gives partial functions with exponential quantum speedups even under negligent queries, and in particular rules out a general lower bound in terms of $\operatorname{fbs}(f)$ for partial functions in this model. For two other models, we obtain general lower bounds in terms of $\operatorname{fbs}(f)$ for all Boolean functions. For hybrid algorithms using $Q$ coherent and $C$ classical queries, we prove the tradeoff $C+Q^2=Ω(\operatorname{fbs}(f))$. For an IID dephasing noisy model where each query dephases the query-index register at rate $p$ independently, we prove $Ω\!\left(p\,\operatorname{fbs}(f)\right)$ queries are necessary. Finally, we introduce a broader family of time-varying dephasing models and identify a variational resource that is always lower bounded by $\operatorname{fbs}(f)$. Computing this resource reduces to a convex optimization problem, providing a simple way to derive lower bounds for new noise schedules. As applications, we recover the hybrid and IID dephasing bounds and determine the query complexity of unstructured search when the dephasing rate grows over time.
• Abstract（参考訳）: 本研究では,不完全オラクルアクセスの複数のモデルの下で量子クエリの複雑性について検討し,分数ブロック感度(\operatorname{fbs}$)に基づく共通フレームワークを用いて下位境界を開発する。 確率 1-p$ で正しいクエリを適用できる負のオラクルに対して、$\operatorname{fbs}(f,0^n)$ という条件で下界を証明する。 任意の関数$f$は、ネグリジェントクエリの複雑さが本質的に$f$の量子クエリの複雑さを保存する部分関数$f'$に変換することができる。 これにより、指数的な量子スピードアップを持つ部分関数は、ネグリジェントなクエリの下でも得られ、特にこのモデルにおける部分関数に対して$\operatorname{fbs}(f)$という一般的な下界を規定する。 他の2つのモデルに対して、すべてのブール関数に対して $\operatorname{fbs}(f)$ の一般下界を得る。 Q$コヒーレントおよび$C$古典的クエリを用いたハイブリッドアルゴリズムに対しては、$C+Q^2=Ω(\operatorname{fbs}(f))$のトレードオフを証明する。 各クエリがクエリインデックスレジスタを独立して$p$で分解するIDD dephasing noisyモデルに対して、$Ω\! p\,\operatorname{fbs}(f)\right)$クエリが必要です。 最後に、時間変化のデファス化モデルのより広範なファミリを導入し、常に$\operatorname{fbs}(f)$で区切られている変動資源を識別する。 このリソースの計算は凸最適化の問題に還元され、新しいノイズスケジュールの低い境界を導出する簡単な方法が提供される。 アプリケーションとして、ハイブリッドおよびIIDのデフォーカス境界を回復し、デフォーカスレートが時間とともに大きくなると、非構造化検索のクエリ複雑性を判定する。

関連論文リスト

• The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem [18.167418729752068]
  本研究では、未知の量子状態の対称性を特定することを目的とする状態隠蔽部分群問題(State hidden subgroup problem, StateHSP)について検討する。 我々は、$O(log(|G/H|)/sqrt)$forward and inverse query を用いて時間効率の量子アルゴリズムを与え、一致する $(log(|G/H|)/sqrt)$ lower bound を証明する。 応用として、安定化群を学習し、絡み合いを突き止め、隠れた翻訳対称性を同定するための高速なアルゴリズムを得る。
  論文  参考訳（メタデータ） (2026-09-28T17:21:41Z)
• Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach [19.400202883397537]
  定量化ブール式(QBF)の妥当性を検討する。 抽出可能なクラスに到達する前に削除しなければならない節の変数数という新しいパラメータを提案する。 CCバックドアが$k$であるなら、FPT時間でQBFを解くことに興味があります。
  論文  参考訳（メタデータ） (2026-05-12T13:00:55Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations [0.0]
  本稿では,量子特異値変換の枠組みにおいて,$alpha$-QPEのスケーリングが自然かつ簡潔に導出可能であることを示す。 符号関数の近似が良くなるほど、符号を正確に決定する必要があるサンプルは少なくなる。
  論文  参考訳（メタデータ） (2022-07-29T17:57:03Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。 CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。 その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-01-23T16:47:52Z)

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

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