論文の概要: Quantum Query Advantage Requires Space

• arxiv url: http://arxiv.org/abs/2609.29497v1
• Date: Fri, 04 Sep 2026 13:04:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-28 05:09:56.047466
• Title: Quantum Query Advantage Requires Space
• Title（参考訳）: 量子クエリのアドバンテージは空間を必要とする
• Abstract要約: 古典的な計算よりも量子クエリの優位性は、それ自体が空間を必要とする。 固定されたすべての$01/100$と$Sle O(M1/100-)$に対して、その$S$空間量子クエリ複雑性は$Q_S=(M21/20)$を満たす。
• 参考スコア（独自算出の注目度）: 4.348431333880389
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hao, Huang, and Liu (STOC'26) recently showed that optimal quantum query complexity may require large workspace even for short-output problems, and asked whether a quantum query advantage over classical computation can itself require space. We resolve this question by exhibiting an explicit total Boolean function with quantum query complexity $Q=\widetildeΘ(M)$, and randomized query complexity $R=Θ(M^{21/20})$, whereas, for every fixed $0<η<1/100$ and $S\le O(M^{1/100-η})$, its $S$-space quantum query complexity satisfies $Q_S=ω(M^{21/20})$. Consequently, $$ Q<R<Q_S, $$ so the unrestricted quantum query advantage disappears under sufficiently small workspace. The separation is obtained through a one-bit filtered-parity construction and a space-sensitive quantum lower bound based on compressed-oracle capacity and a new parity-to-capacity inequality, which may be of independent interest.
• Abstract（参考訳）: Hao, Huang, and Liu (STOC'26) は最近、量子クエリの最適な複雑性は、短期出力問題においても大きなワークスペースを必要とすることを示した。 一方、0<η<1/100$ と $S\le O(M^{1/100-η})$ に対して、その$S$量子量子量子計算複雑性は $Q_S=ω(M^{21/20})$ を満たす。 その結果、$ Q<R<Q_S, $$ となると、制限なしの量子クエリの利点は十分に小さなワークスペースの下で消失する。 この分離は、1ビットのフィルタパリティ構造と、圧縮オーラル容量に基づく空間感受性量子下界と、独立性のある新しいパリティ・ツー・キャパシティの不等式によって得られる。

関連論文リスト

• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。 我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
  論文  参考訳（メタデータ） (2023-03-20T08:17:32Z)

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

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