論文の概要: Tight Quantum Lower Bound for k-Distinctness
- arxiv url: http://arxiv.org/abs/2604.05133v1
- Date: Mon, 06 Apr 2026 19:52:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-08 17:42:09.469266
- Title: Tight Quantum Lower Bound for k-Distinctness
- Title（参考訳）: k-distinctnessのためのタイト量子下界
- Authors: Aleksandrs Belovs,
- Abstract要約: 我々は新しい量子クエリローバウンドフレームワークを導入する。
このフレームワークが入力文字列の等しい要素を見つけるという問題に対してどのように振る舞うかを示す。
特に、k-distinctness問題に対する最初の厳密な量子クエリローバウンドを証明することによって、そのパワーを実証する。
- 参考スコア（独自算出の注目度）: 52.10197476419622
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we introduce a new quantum query lower bound framework. It is inspired by Zhandry's compressed oracle technique, but it also subsumes the polynomial method as a special case. Compared to Zhandry's technique, our approach has two key differences. First, we do not use any oracles (except for the standard input oracle), and define ``knowledge'' directly through the expansion of the state of the algorithm in the Fourier basis. Second, we allow arbitrary probability distributions of inputs. We show how this framework behaves on the problem of finding equal elements in the input string. In particular, we demonstrate its power by proving a first tight quantum query lower bound for the k-Distinctness problem.
- Abstract（参考訳）: 本稿では,新しい量子クエリローバウンドフレームワークを提案する。
これは Zhandry の圧縮オラクル法に着想を得たものであるが、多項式法を特別な場合と仮定する。
Zhandryの手法と比較して、我々のアプローチには2つの重要な違いがある。
まず、(標準的な入力オラクルを除いて)いかなるオラクルも使用せず、フーリエ基底におけるアルゴリズムの状態の展開を通して直接 ``knowledge'' を定義する。
第二に、入力の任意の確率分布を許容する。
このフレームワークが入力文字列の等しい要素を見つけるという問題に対してどのように振る舞うかを示す。
特に、k-distinctness問題に対する最初の厳密な量子クエリローバウンドを証明することによって、そのパワーを実証する。
関連論文リスト
- Compressed Permutation Oracles [0.6768558752130311]
我々は、圧縮された置換オラクルの音質を発達させ、証明する。
我々は、基本的にすべての既知の量子クエリの低い境界をランダムな置換モデルで再証明する。
論文 参考訳（メタデータ） (2025-09-23T03:13:48Z) - Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。
我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。
クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-25T15:32:37Z) - One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。
これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
論文 参考訳（メタデータ） (2023-01-05T11:05:22Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - The NISQ Complexity of Collision Finding [2.9405711598281536]
現代の暗号における基本的なプリミティブである衝突耐性ハッシュは、同じハッシュ値を生成する入力を効率的に見つける方法がないことを保証している。
現在、量子敵はNISQのパワーを備えたフルスケールのコンピュータを必要とする。
本稿では, NISQアルゴリズムの3つの異なるモデルについて検討する。
論文 参考訳（メタデータ） (2022-11-23T13:55:28Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs
of Sequential Work [10.43571631715192]
我々は、量子ランダムオラクルモデル(QROM)における量子アルゴリズムの分析のために、Zhandryによって導入されたいわゆる圧縮オラクル手法を再考する。
我々の主な技術的貢献は、クエリ複雑性の結果を証明するために圧縮されたオラクル技法の並列クエリの一般化を単純化するフレームワークである。
本手法の具体的な暗号的応用として,Cohen と Pietrzak が提唱した "Simple Proofs of Sequential Work" が量子攻撃に対して安全であることを示す。
論文 参考訳（メタデータ） (2020-10-22T12:44:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。