論文の概要: Quantum Query Complexity for List Search

• arxiv url: http://arxiv.org/abs/2609.38736v1
• Date: Wed, 30 Sep 2026 01:20:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:26.952182
• Title: Quantum Query Complexity for List Search
• Title（参考訳）: リスト検索における量子クエリの複雑さ
• Abstract要約: リスト頂点が描画される周辺アドレス空間は、クエリの複雑さに影響を与えうることを示す。 すべての$N ge ell ge 1$に対して、この問題の決定版と探索版の両方が量子クエリ複雑性を持つことを証明します。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Searching in a linked list is one of the most basic problems in classical algorithms. Although the nodes of the list come with memory addresses, classically those addresses play no role in the cost of search: one simply starts at the head and follows successor pointers to search for an element. In this paper, we show that the quantum setting is different. Here, the ambient address space from which the list vertices are drawn can itself affect the query complexity. We study the following problem analogous to search in a linked list in the query complexity model: the input consists of an address universe $[N]$, a public start symbol $s$, a successor oracle $f$ whose non-$\perp$ values trace a hidden simple path $s \to a_1 \to a_2 \to \cdots \to a_\ell \to \perp$, and a marking oracle $g$ that marks at most one list vertex. The task is to decide whether the list contains a marked vertex. We prove that both the decision and search versions of this problem for all $N \ge \ell \ge 1$ have quantum query complexity $Θ\!\bigl(\min\{\ell,(N\ell)^{1/4}\}\bigr)$. Thus, quite surprisingly, when $N < \ell^3$ the optimal quantum complexity is $(N\ell)^{1/4}$, which is strictly smaller than the $Θ(\ell)$ cost of ordinary linked-list traversal. This gives a precise characterization of when the ambient address space yields a genuine quantum advantage for linked-list search. We extend our results and give the same tight asymptotic bounds for the natural double linked-list version as well.
• Abstract（参考訳）: リンクリストで検索することは、古典的アルゴリズムにおける最も基本的な問題の1つである。 リストのノードはメモリアドレスを伴っているが、古典的にはこれらのアドレスは検索コストにおいて何の役割も果たさない。 本稿では,量子設定が異なることを示す。 ここでは、リスト頂点が描画される周辺アドレス空間自体がクエリの複雑さに影響を与える可能性がある。 入力はアドレス空間$[N]$,パブリックスタートシンボル$s$,非$\perp$値が隠れた単純なパス$s \to a_1 \to a_2 \to \cdots \to a_\ell \to \perp$,マーキングオラクル$g$から成り立つ。 タスクは、リストがマークされた頂点を含むかどうかを決定することである。 すべての$N \ge \ell \ge 1$に対して、この問題の決定版と探索版の両方が、量子クエリの複雑さを$ ! \bigl(\min\{\ell,(N\ell)^{1/4}\bigr)$ したがって、$N < \ell^3$ のとき、最適量子複雑性は$(N\ell)^{1/4}$であり、通常のリンクリストのトラバーサルのコストより厳密に小さい。 これにより、周辺アドレス空間がリンクリスト探索に真の量子優位性をもたらすときの正確な特徴づけが得られる。 結果を拡張して、自然二重リンクリスト版についても、同様の厳密な漸近的境界を与える。

関連論文リスト

• Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
  メモリが$m$ の単位球上の$d$ 次元 1$-Lipschitz 凸関数を最小化する。 まず、そのようなアルゴリズムは、$tilde(fracd2sqrtm)$ Oracle queryを作らなければならないことを示す。 決定論的最適化アルゴリズムでは$tilde(mind1.6,fracd8/3m2/3)$クエリが必要である。
  論文  参考訳（メタデータ） (2026-07-21T00:40:59Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• 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)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
  論文  参考訳（メタデータ） (2023-02-20T19:11:44Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

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

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