Fugu-MT 論文翻訳(概要): Elementary proofs of quantum lower bounds for element distinctness and k-sum

論文の概要: Elementary proofs of quantum lower bounds for element distinctness and k-sum

arxiv url: http://arxiv.org/abs/2610.32693v1
Date: Fri, 23 Oct 2026 14:20:47 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-27 01:38:06.546233
Title: Elementary proofs of quantum lower bounds for element distinctness and k-sum
Title（参考訳）: 元素の特異性とk-sumに対する量子下界の初等証明
Abstract要約: 我々は、元差分性に対する$(n2/3)$量子クエリローバウンドと、$k$-sum問題に対する$(nk/(k+1))$ローバウンドの基本的な証明を与える。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We give elementary proofs of the $Ω(n^{2/3})$ quantum query lower bound for element distinctness and the $Ω(n^{k/(k+1)})$ lower bound for the $k$-sum problem, for fixed $k$ and sufficiently large groups. The proofs use only basic properties of quantum states and linear algebra, analyzing the differences of algorithm states on different inputs.
Abstract（参考訳）: 固定された$k$および十分に大きな群に対して、$Ω(n^{2/3})$量子クエリローバウンドと$Ω(n^{k/(k+1)})$ $Ω(n^{k/(k+1)})$ローバウンドの基本的な証明を与える。証明は量子状態と線形代数の基本的な性質のみを使用し、異なる入力に対するアルゴリズム状態の違いを分析する。

関連論文リスト

Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points [31.45779401617503]
タルスキの不動点問題は、幅$n$の$k$次元格子上の単調写像の固定点を求め、ゲーム理論、経済学、検証に応用できる。量子下界に対する2つのブートストラッピング定理を証明する。
論文参考訳（メタデータ） (2026-10-12T05:39:35Z)
Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model [1.6379393441314491]
有界度モデルにおけるグラフ特性試験における2つの正準問題である二分性および拡張試験について検討する。古典的な設定では、これらのテスト問題の両方に$widetilde(sqrtN)クエリが必要である。多大な努力にもかかわらず、この10年半の間にこれらの結果は改善されていない。
論文参考訳（メタデータ） (2026-10-01T14:18:02Z)
Quantum state isomorphism problems for groups [41.49556721904551]
群作用下での量子状態同型問題の計算複雑性について検討する。純粋状態バージョンの場合、問題はすべての非自明な群に対して BQP-hard であることが示される。混合状態バージョンの場合、非自明で有限で効率的な表現可能な群に対して、問題はQSZK完全である。
論文参考訳（メタデータ） (2026-05-12T18:05:27Z)
Tight Quantum Lower Bound for k-Distinctness [52.10197476419622]
我々は新しい量子クエリローバウンドフレームワークを導入する。このフレームワークが入力文字列の等しい要素を見つけるという問題に対してどのように振る舞うかを示す。特に、k-distinctness問題に対する最初の厳密な量子クエリローバウンドを証明することによって、そのパワーを実証する。
論文参考訳（メタデータ） (2026-04-06T19:52:58Z)
Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文参考訳（メタデータ） (2026-03-19T15:53:41Z)
Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
実測値の最初の2Omega(n)$モーメントと無作為位相によるS(N)$置換の指数和が一致することを示す。我々の証明の核心は、ランダム行列理論における大次元(大きな=N$)展開と方法の間の概念的接続である。
論文参考訳（メタデータ） (2024-04-25T17:08:34Z)
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文参考訳（メタデータ） (2024-02-29T01:35:46Z)
Lower Bounds for Unitary Property Testing with Proofs and Advice [0.0]
ユニタリプロパティのテストでは、テスタとしても知られる量子アルゴリズムは、ブラックボックスのユニタリへのクエリアクセスが与えられる。本稿では,一元性検定の量子クエリの下位境界を証明するための新しい手法を提案する。
論文参考訳（メタデータ） (2024-01-15T19:00:36Z)

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