論文の概要: A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds
- arxiv url: http://arxiv.org/abs/2609.40334v2
- Date: Thu, 01 Oct 2026 17:58:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-03 01:19:23.573861
- Title: A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds
- Title（参考訳）: 量子クエリ複雑度と時間空間トレードオフ境界に対する雑音演算子アプローチ
- Abstract要約: 我々は、ソートのための最初の完全な量子時空間トレードオフを証明した。
ノイズ演算子引数を適用するには、純粋に古典的な推論が必要です。
また、強い普遍的なハッシュ関数ファミリである$H$を$n$bitsから$m$bitsにすると、ほぼすべてのハッシュ関数が$H$で、少なくとも$S$qubitsのメモリを持つアルゴリズムを必要とすることを証明するためにも使用しています。
- 参考スコア（独自算出の注目度）: 1.3254304182988286
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeoffs between time and space are surprisingly limited. The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time-space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an $Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))$ lower bound on the number of queries that a fully general quantum algorithm with at most $S$ qubits of memory requires to sort $n$ numbers from $[n^2]$. Applying our noise operator argument involves purely classical reasoning, which makes it particularly simple to use. We also use it to prove that, for any strongly universal (pairwise independent) hash function family $H$ from $n$ bits to $m$ bits, almost all hash functions in $H$ require any algorithm with at most $S$ qubits of memory to make $Ω(nm/S)$ quantum queries to input $x$ in order to compute $h(x)$, even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing $h(x)$ with both $h$ and $x$ as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our quantum lower bounds.
- Abstract（参考訳）: 時間と空間(メモリ)は計算における最も重要なコストの尺度の1つである。
しかし、時間と空間の間の無条件の量子トレードオフを証明するツールが驚くほど限られています。
最初の量子時間空間のトレードオフの下界は、クラック、シュパレク、デ・ウルフによってソートされた。
残念なことに、それらの手法は出力に富んだ下限(つまり、下限は非適応的な出力スケジュールを持つアルゴリズムにのみ適用される)の証明に限られており、他の手法はソートのために出力に満ちた下限以上のものを与えていない。
ここでは、ソートのための最初の完全な量子時空間トレードオフを証明している。
そこで我々は,雑音演算子に基づく新しい手法を導入し,量子クエリと時間空間のトレードオフを下限とする解析ツールキットを提案する。
得られた量子ノイズ安定性と量子記録クエリー法を組み合わせることで、最大で$S$ qubitsのメモリを持つ完全一般量子アルゴリズムが$[n^2]$から$n$の数値をソートする必要があるクエリ数に対する$Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))$の低いバウンドを証明できる。
ノイズ演算子引数を適用するには、純粋に古典的な推論が必要です。
また、強い普遍性を持つハッシュ関数ファミリに対して、$n$bitsから$m$bitsまで、ほぼすべてのハッシュ関数が$H$の任意のアルゴリズムを必要とすることを証明するためにも、$Ω(nm/S)$量子方程式が$h(x)$を計算するために$x$を入力するために$S$のメモリを持つ必要がある。
以前は、マンスール、ニサン、ティワリは、ハッシュミキシング補題を用いて入力として$h$と$x$の計算で一致する古典的な下界を示していた。
我々のノイズ演算子は、ハッシュ関数の関連する特性を使って量子的下界を証明できる。
関連論文リスト
- Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
ハミルトニアン$H = sum_j h_j$ の場合、ゲート上の下界と量子コンピュータ上の時間発展をシミュレートするクエリの複雑さを証明できる。
任意の項ノルムのホールドは$|h_j|$, time $t$, trace-distance error $$である。
論文 参考訳（メタデータ） (2026-07-22T07:41:32Z) - Tight Success Probabilities for Quantum Period Finding and Phase Estimation [2.2329417756084093]
我々は、測定された$hatell$ が正の整数倍の 2n / r$ の許容値$M$ 内にあるときに必ず成功する一般的な後処理アルゴリズムを考える。
1 に収束する成功確率について、新しい(八つの)下限と上限を与える。
我々の分析は、量子回路の複雑さと成功確率を最適化する際の古典的な処理に費やした労力との間のトレードオフを慎重に活用することを可能にする。
論文 参考訳（メタデータ） (2025-06-25T15:14:59Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - A simple lower bound for the complexity of estimating partition functions on a quantum computer [0.20718016474717196]
分割関数 $mathsfZ(beta)=sum_xinchi e-beta H(x)$ をハミルトニアン$H(x)$ で特徴づけられるギブス分布に対して推定する複雑性について検討する。
我々は、ギブス状態のコヒーレントな符号化を通して反射に依存することにより、この問題を解く量子アルゴリズムの単純で自然な下界を提供する。
論文 参考訳（メタデータ） (2024-04-03T02:38:49Z) - Efficient Pauli channel estimation with logarithmic quantum memory [17.16536262746742]
a protocol can estimated the eigen values of a Pauli channel to error $epsilon$ using only $O(log n/epsilon2)$ ancilla and $tildeO(n2/epsilon2)$ measured。
我々の知識によれば、量子メモリの対数的に多くの量子ビットが指数統計上の優位性のために十分である最初の量子学習タスクである。
論文 参考訳（メタデータ） (2023-09-25T17:53:12Z) - Efficient Quantum State Synthesis with One Query [0.0]
本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。
我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
論文 参考訳（メタデータ） (2023-06-02T17:49:35Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z) - Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs [0.0]
ランダム関数 $f : [N] rightarrow [N]$ の衝突対を量子コンピュータを用いて探索する。
利用可能なメモリのサイズが制限された場合、関数に対するクエリの数は大幅に増加しなければなりません。
論文 参考訳（メタデータ） (2020-02-20T18:48:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。