論文の概要: Quantum Lower Bounds for Collision Problems

• arxiv url: http://arxiv.org/abs/2611.01767v1
• Date: Sun, 01 Nov 2026 10:14:01 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-03 20:05:42.94987
• Title: Quantum Lower Bounds for Collision Problems
• Title（参考訳）: 衝突問題に対する量子下界
• Abstract要約: Promised $k$-to-one Finding の適応的および非適応的量子クエリ複素量に対して、厳密な下界を確立する。 下限は非制限適応アルゴリズムの$_k(n1/2-1/(2(2k-1))$と1ラウンド非適応アルゴリズムの$_k(n1-1/k)$である。
• 参考スコア（独自算出の注目度）: 5.501204611528696
• License:
• Abstract: We establish tight lower bounds on the adaptive and non-adaptive quantum query complexities of Promised $k$-to-one Finding on an exactly $k$-to-one input string $x\in\mathbb Z_q^n$, for every fixed $k\ge2$ and every feasible alphabet size $q\ge n/k$. The lower bounds are $Ω_k(n^{1/2-1/(2(2^k-1))})$ for unrestricted adaptive algorithms and $Ω_k(n^{1-1/k})$ for one-round non-adaptive algorithms. The former matches the adaptive quantum algorithm of Liu and Zhandry [LZ19], whereas the latter matches classical birthday sampling even when the parallel queries are arbitrarily entangled. We also establish the non-adaptive lower bound $Ω_k(\sqrt{n/k})$ for $k$-to-one Testing when $q\ge n$, resolving an open question posed by Koiran, Landes, Portier, and Yao [KLPY10]. Our proofs generate the balanced input from a uniformly random permutation and use compressed permutation oracles to describe the information learned by the algorithm. The adaptive proof bounds the growth of partial collisions through successive queries. The one-round proof instead analyzes the state after the parallel queries directly, bounding the probability that the compressed database contains a full collision. In both proofs, a short verification step accounts for correct outputs that include unrecorded positions. For the decision problem, we also compare one-round states with independent and distinct output labels.
• Abstract（参考訳）: 我々は Promised $k$-to-one の適応的および非適応的量子クエリの複素量に対して、厳密な下限を確立した。 正確に$k$-to-one 入力文字列 $x\in\mathbb Z_q^n$, for every fixed $k\ge2$ およびすべての実現可能なアルファベットサイズ $q\ge n/k$。 下界は、非制限適応アルゴリズムの$Ω_k(n^{1/2-1/(2(2^k-1))} と、1ラウンド非適応アルゴリズムの$Ω_k(n^{1-1/k})$である。 前者はLiuとZhandry[LZ19]の適応量子アルゴリズムと一致し,後者は並列クエリが任意に絡み合った場合でも古典的誕生日サンプリングと一致する。 また、非適応的下界$Ω_k(\sqrt{n/k})$ for $k$-to-one Testing if $q\ge n$, resolving a open questionsposed by Koiran, Landes, Portier, and Yao [KLPY10]. 我々の証明は、一様ランダムな置換からバランスの取れた入力を生成し、圧縮された置換託を用いてアルゴリズムが学習した情報を記述する。 適応的な証明は、連続したクエリを通して部分衝突の成長を束縛する。 1ラウンドの証明は、直接並列クエリ後の状態を解析し、圧縮されたデータベースが完全な衝突を含む確率を限定する。 両方の証明において、短い検証ステップは、記録されていない位置を含む正しい出力について説明します。 決定問題に対しては、一周状態と独立した出力ラベルを比較する。

関連論文リスト

• Tight bounds for hybrid quantum-classical query algorithms [0.45880283710344066]
  クエリモデルにおけるハイブリッド量子古典アルゴリズムについて検討する。 状態準備単位によって指定された2つの分布を区別するハイブリッドな下界を導出する。
  論文  参考訳（メタデータ） (2026-10-05T17:53:05Z)
• Efficient Quantum State Identity Testing [0.7639235704257864]
  回路深度とサンプル複雑度を相補的に保証する2つの量子アルゴリズムを提案する。 1つは、並列スワップテストを使用して一定の深さで実行し、各入力状態のコピーを$O(log(n/)log(2/))で、少なくとも1-$の確率で成功する。 第二に、サンプルの複雑さを$O(log(n/))$に減らし、Jucys--Murphy 要素と Schur サンプリングに関する分析を行う。
  論文  参考訳（メタデータ） (2026-10-03T15:33:21Z)
• Optimal Quantum Junta Testing without Inverse Queries [10.042684323264202]
  未知の$n$-qubitユニタリまたは量子チャネルが与えられた場合、その目標は、それが少なくとも$k$ qubitsで非自明に作用するか、またはそのような操作の全てから$varepsilon$-farであるかを判断することである。 ユニタリおよびチャネルユンタテストの両方に厳密な境界を与える。
  論文  参考訳（メタデータ） (2026-09-29T16:16:54Z)
• Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure [50.58119214447535]
  マスク付き生成モデルは並列トークン予測を提供するが、正確な並列サンプリングはトークンを考慮しなければならない。 本研究は,発見を含む全評価がシーケンス長$N$のサブ線形であるかどうかを考察する。 本研究では, 森林構造を隠蔽した離散分布を, 固定された近似条件オラクルを通してアクセスする。
  論文  参考訳（メタデータ） (2026-09-29T15:39:50Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Quantum Advantage in Tolerant Junta Testing [0.5442955439283729]
  適応設定において、許容値$k$-juntaテスト問題に対する最初の超多項式量子優位性を確立する。 特定のパラメータ体系内では、高い精度で寛容な$k$-juntaテストが$mathrmpoly(k)$quantumquantumquantum(k)$で解けることを示す。
  論文  参考訳（メタデータ） (2026-06-22T11:42:39Z)
• 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)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。 我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
  論文  参考訳（メタデータ） (2023-06-02T17:49:35Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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