論文の概要: Tight Quantum Query Bounds for Collision Finding over Arbitrary Bounded Types
- arxiv url: http://arxiv.org/abs/2611.17804v1
- Date: Fri, 13 Nov 2026 06:35:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-16 18:43:16.317353
- Title: Tight Quantum Query Bounds for Collision Finding over Arbitrary Bounded Types
- Title(参考訳): 任意境界型上での衝突検出のための高次量子クエリ境界
- Abstract要約: 所定の型の$N$-入出力関数で1$r$-collisionを求める場合の有界エラー量子クエリの複雑性が分かる。
すべての固定された最大クラスサイズと衝突順序に対して、少なくとも2,ldots,r$のクラスの数によって決定されるスケールの最大値として厳密な境界を与える。
中間クラスサイズは発生せず、すべての実行可能な出力アルファベットが許可される。
- 参考スコア(独自算出の注目度): 1.5939757296986599
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We determine the bounded-error quantum query complexity of finding one $r$-collision in an $N$-input function of prescribed type, which specifies all equality-class sizes. For every fixed maximum class size and collision order, we give a tight bound as the maximum of scales determined by the numbers of classes of size at least $2,\ldots,r$. The lower bound holds for a uniformly random function of that type, and a matching algorithm succeeds on every such function. No intermediate class size is required to occur, and every feasible output alphabet is allowed. The characterization connects the abundant-collision regime associated with set equality to the sparse-target regime of $k$-distinctness. In particular, finding the unique $(k+1)$-collision in type $(k^n,k+1)$ has complexity $Θ_k(N^{3/4-1/[4(2^{k+1}-1)]})$, where $N=kn+k+1$, resolving an open problem of Belovs. For the lower bound, we introduce a filtered compressed permutation oracle that projects onto a harmonic database subspace after each complete function query. Its $O(T/N)$ comparison error over $T$ queries overcomes the square-root limitation of the unfiltered process. Hidden capacity extensions and moment estimates retain the populations at each intermediate collision order. Matching upper bounds use sampled collision lists and colored adaptive learning graphs, with a coherent decision-to-search conversion that avoids logarithmic overhead. We also give an alternative nested quantum-walk algorithm for three-collision search, matching the bound up to polylogarithmic factors.
- Abstract(参考訳): 所定の型の$N$-入出力関数で1$r$-collisionを求める場合の有界エラー量子クエリの複雑性を判定する。
すべての固定された最大クラスサイズと衝突順序に対して、少なくとも2,\ldots,r$のクラスの数によって決定されるスケールの最大値として厳密な境界を与える。
下界はその型の一様ランダムな関数を持ち、マッチングアルゴリズムはそのようなすべての関数で成功する。
中間クラスサイズは発生せず、すべての実行可能な出力アルファベットが許可される。
キャラクタリゼーションは、集合同値と$k$-distinctnessのスパースターゲットレギュレーションを結び付ける。
特に、$(k+1)$-collision in type $(k^n,k+1)$ の複雑性は、$n=kn+k+1$ の開問題を解くため、$n(N^{3/4-1/[4(2^{k+1}-1)])$ となる。
下限については、各完全関数クエリの後にハーモニックデータベースサブスペースに投影されるフィルタ圧縮置換オラクルを導入する。
その$O(T/N)$比較誤差$T$クエリは、未フィルタリングプロセスの平方根制限を克服する。
隠れた容量拡張とモーメント推定は、各中間衝突順に個体群を保持する。
一致した上位境界は、対数的オーバーヘッドを回避するコヒーレントな決定-探索変換を備えたサンプル衝突リストと適応学習グラフを使用する。
また,3コリジョン探索のためのネスト付き量子ウォークアルゴリズムを提案する。
関連論文リスト
- Quantum Lower Bounds for Collision Problems [5.501204611528696]
Promised $k$-to-one Finding の適応的および非適応的量子クエリ複素量に対して、厳密な下界を確立する。
下限は非制限適応アルゴリズムの$_k(n1/2-1/(2(2k-1))$と1ラウンド非適応アルゴリズムの$_k(n1-1/k)$である。
論文 参考訳(メタデータ) (2026-11-01T10:14:01Z) - Tight bounds for hybrid quantum-classical query algorithms [0.45880283710344066]
クエリモデルにおけるハイブリッド量子古典アルゴリズムについて検討する。
状態準備単位によって指定された2つの分布を区別するハイブリッドな下界を導出する。
論文 参考訳(メタデータ) (2026-10-05T17:53:05Z) - 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) - Collision Resistance of Single-Layer Neural Nets [3.2522957478427283]
単層二層ニューラルネットワークにおける衝突のアルゴリズム的複雑性について検討する。
本研究は, 衝突抵抗の厳密な基準として, オーバーラップギャップ特性を用いた最初の研究である。
論文 参考訳(メタデータ) (2026-06-02T15:52:45Z) - A Tight Quantum Algorithm for Multiple Collision Search [4.913876853745498]
ランダム関数における衝突の探索は、基本的な計算問題である。
残りの最適範囲に対処するアルゴリズムを新たに提供し,問題を解消する。
我々のアルゴリズムはクエリーにおいて(最大1要素まで)厳密であり、また量子RAMの仮定の下でも間に合う。
論文 参考訳(メタデータ) (2025-09-17T11:15:02Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳(メタデータ) (2022-12-03T02:45:23Z) - Finding many Collisions via Reusable Quantum Walks [1.376408511310322]
衝突発見は暗号解析におけるユビキタスな問題である。
本稿では,この問題に対するアルゴリズムを改良し,特に許容可能なパラメータの範囲を広げる。
応用として、最短ベクトル問題に対する量子シービングアルゴリズムを改善する。
論文 参考訳(メタデータ) (2022-05-27T14:50:45Z) - 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) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳(メタデータ) (2021-06-04T02:32:26Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。