論文の概要: Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
- arxiv url: http://arxiv.org/abs/2609.10808v1
- Date: Wed, 09 Sep 2026 20:20:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-11 23:53:35.135442
- Title: Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
- Title（参考訳）: ラベロシンメトリーによる衝突検出と要素識別のための高次時間空間下界
- Abstract要約: 我々は、$S$ qubitsを使用するアルゴリズムが、$O(S/log N)$の衝突のないデータベースエントリのみを効果的に保持できることを示す。
この推定値を圧縮されたオラクル技法に置き換えると、記述されたトレードオフが得られる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function $f:[N]\to [N]$, the BHT algorithm finds a collision using $O(N^{1/3})$ queries and a quantumly accessible classical table containing $O(N^{1/3})$ input-output pairs, whereas a logarithmic-space Grover search uses $O(\sqrt N)$ queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem. We resolve this equation within the class of label-symmetric algorithms, which treat the function $f$'s output labels as interchangeable. We prove that such algorithm that makes $T$ queries, uses $S$ qubits, and finds a collision in a uniformly random function $f:[M]\to [N]$ with constant probability satisfies $$T=Ω(N^{1/3}) \qquad\text{and}\qquad T^2S=Ω(N\log N).$$ For the setting where $M=N$, these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on $f: [n] \to [n^2]$ must satisfy $$T=Ω(n^{2/3}) \qquad\text{and}\qquad T^2S=Ω(n^2\log n),$$ matching Ambainis's quantum walk. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms. To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using $S$ qubits can effectively retain information about only $O(S/\log N)$ collision-free database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.
- Abstract（参考訳）: 衝突発見の量子スピードアップを維持するには、どれくらいのメモリが必要か?
均一にランダムな関数 $f:[N]\to [N]$ に対して、BHT アルゴリズムは$O(N^{1/3})$クエリと$O(N^{1/3})$入力出力ペアを含む量子アクセス可能な古典テーブルとの衝突を見つけ、対数空間グロバー探索では$O(\sqrt N)$クエリを使用する。
これらの極端な間の最適なクエリ空間のトレードオフを決定することは、依然として大きなオープンな問題である。
我々はこの方程式を、関数$f$の出力ラベルを交換可能なものとして扱うラベル対称アルゴリズムのクラス内で解決する。
我々は、$T$クエリを作成し、$S$ qubitsを使用し、一定の確率を持つ一様ランダム関数$f:[M]\to [N]$の衝突が$T=Ω(N^{1/3}) \qquad\text{and}\qquad T^2S=Ω(N\log N)を満たすことを証明した。
$M=N$の場合、これらの境界はBHTアルゴリズムの空間効率のよい実装と一致する。
トレードオフの結果、[n] \to [n^2]$は$T=Ω(n^{2/3}) \qquad\text{and}\qquad T^2S=Ω(n^2\log n)で満たされなければならない。
したがって、両方のトレードオフはラベル対称アルゴリズムのクラス内で最適である。
これらの結果を証明するため,圧縮オラクル法の空間感応版を開発した。
圧縮されたオラクルは、アルゴリズムが学習した情報をデータベースの進化的な重ね合わせに記録する。
ラベル対称性と表現理論を用いて、$S$ qubits を用いたアルゴリズムは、$O(S/\log N)$の衝突のないデータベースエントリのみを効果的に保持できることを示す。
この推定値を圧縮されたオラクル技法に置き換えると、記述されたトレードオフが得られる。
関連論文リスト
- Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps [28.438129186461598]
コンパクト凸集合の一般ノルム $|cdot|$ と自己写像 $T$ に対して、小さな固定点残差 $|T(x)-x| leq $ を持つ点を計算するオラクル複雑性について検討する。
弱ラデマッハ型$q > 1$の任意のノルムに対して、高い確率でそのような問題を解くアルゴリズムを提供する。
論文 参考訳（メタデータ） (2026-09-08T23:09:39Z) - A Simple Algorithm for Best Separable State [5.5559749120901385]
本研究では,無絡状態上での量子測定の最大受容確率を求める最適分離状態問題 (BSS) について検討する。
古典的な意味での目標は、$langle(x otimes y), M (x otimes y)rangle$ over unit vectors $x,y$ where $0 preceq M preceq I$である。
論文 参考訳（メタデータ） (2026-08-10T19:04:15Z) - 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) - Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。
クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。
このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
論文 参考訳（メタデータ） (2026-01-07T22:07:44Z) - Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。
コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。
我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
論文 参考訳（メタデータ） (2025-09-25T07:39:25Z) - Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses [0.0]
平均ケース複雑性理論に基づいて,$m=Omega(n2+delta+epsilon)$のとき,max-k-SSAT が平均計算アルゴリズムであることを示す。
また、平均ケース複雑性理論に基づいて$m=Omega(n2+delta+epsilon)$のとき、max-k-SSATが平均であることが証明される。
論文 参考訳（メタデータ） (2024-03-05T15:03:47Z) - Exact Quantum Query Algorithms Outperforming Parity -- Beyond The
Symmetric functions [3.652509571098291]
まず、$Omega left(2fracsqrtn2 right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_algo(f)$)を得る。
Q_algo$のクエリ複雑性は$lceil frac3n4 rceil$であるのに対して、$D_oplus(f)$は$n-1$と$lceil frac3n4 rceの間で異なる。
論文 参考訳（メタデータ） (2020-08-14T12:17:48Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。