論文の概要: Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy
- arxiv url: http://arxiv.org/abs/2607.08517v1
- Date: Thu, 09 Jul 2026 14:11:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-10 14:45:27.561213
- Title: Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy
- Title（参考訳）: 行列差分法による探索問題に対する量子通信下界
- Abstract要約: 探索問題に対する一方向量子通信の低境界について検討する。
衝突検出のためには、厳密な$(N1/4)$ワンウェイ量子通信を低い境界で証明する。
三角形を見つけるためには、$m$エッジを持つグラフに対して$left(sqrt_Vright)$、$(m)$トライアングル、定数$_E$の1パス量子ストリーミング空間を低い境界で証明する。
- 参考スコア（独自算出の注目度）: 4.843542453440025
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study one-way quantum communication lower bounds for search problems. Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to standard quantum lower-bound techniques. We overcome this by developing a novel method based on matrix discrepancy, which allows us to bound the output measurements of a quantum protocol jointly. As applications of our method, we establish the first tight quantum lower bounds for two fundamental search problems in some natural parameter regimes: collision finding and triangle finding. For collision finding, we prove a tight $Ω(N^{1/4})$ one-way quantum communication lower bound. Previously, the best-known quantum communication lower bound for collision finding was $Ω(N^{1/12})$ due to Göös and Jain (RANDOM 2022), and no stronger bound was known even under the one-way restriction. For triangle finding in graph streams, we prove a one-pass quantum streaming space lower bound of $Ω\left(\sqrt{Δ_V}\right)$ for graphs with $m$ edges, $Θ(m)$ triangles, and constant $Δ_E$, where $Δ_V$ and $Δ_E$ denote the maximum number of triangles sharing a common vertex and edge, respectively, under the condition that $1\le Δ_V\le m^{2/3}$. This constitutes the first nontrivial quantum space lower bound in this regime, matching the classical upper bound of Jayaram and Kallaugher (RANDOM 2021) up to logarithmic factors. Notably, our method also recovers the classical lower bound of Kallaugher and Price (SODA 2017) through an entirely different argument, avoiding their Boolean-Hidden-Matching reduction that breaks down for quantum protocols.
- Abstract（参考訳）: 探索問題に対する一方向量子通信の低境界について検討する。
決定問題とは異なり、探索問題は多くの有効な出力を持つことができ、これは標準的な量子下界技術の基本障壁となる。
この課題を克服するために,行列の差分に基づく新しい手法を開発し,量子プロトコルの出力測定を協調的に行なえるようにした。
提案手法の応用として, 衝突探索と三角形探索という2つの基本探索問題に対して, 最初の厳密な量子下界を確立する。
衝突発見のためには、厳密な$Ω(N^{1/4})$一方向量子通信の下界を証明する。
衝突発見のための最もよく知られた量子通信の下限はゲースとジャイン(RANDOM 2022)による$Ω(N^{1/12})であり、一方の制限の下でも強い境界は知られていない。
グラフストリームの三角形を見つけるためには、$m$辺を持つグラフに対して$Ω\left(\sqrt{Δ_V}\right)$の1パス量子ストリーミング空間を証明し、$Δ_V$と$Δ_E$はそれぞれ共通の頂点と辺を共有する三角形の最大数を表す。
これはこの状態において最初の非自明な量子空間の下界を構成し、古典的なJayaram と Kallaugher (RANDOM 2021) の上界を対数的因子に一致する。
特に,本手法は,量子プロトコルを分解するブール・ハイデン・マーチングの低減を回避し,カライヤー・アンド・プライス(SODA 2017)の古典的下界を全く異なる議論によって復元する。
関連論文リスト
- Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid [31.45779401617503]
クナスター・タルスキーの不動点定理(Knaster-Tarski fixed-point theorem)は、完備格子上のすべての単調函数が不動点を持つという定理である。
非負スペクトル逆法を用いて、$[n]k$上の単調関数の固定点を求めるために、$(klog n)$量子クエリローバウンドを証明した。
論文 参考訳（メタデータ） (2026-09-03T13:06:12Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Quartic quantum speedups for community detection [84.14713515477784]
我々は,準量子スピードアップを実現するハイパーグラフコミュニティ検出のための量子アルゴリズムを開発した。
提案アルゴリズムは,従来検討されていた PCA や $p$XORSAT といった問題を超えて拡張した Kikuchi 法に基づいている。
論文 参考訳（メタデータ） (2025-10-09T17:35:17Z) - Purest Quantum State Identification [14.22473588576799]
我々は、量子計算と通信の精度を向上させるために使用できる、最も純粋な量子状態同定を導入する。
非コヒーレントな戦略に対しては、エラー確率$expleft(-Omegaleft(fracN H_1log(K) 2nfracright)$を達成し、量子特性学習を根本的に改善する最初の適応アルゴリズムを導出する。
論文 参考訳（メタデータ） (2025-02-20T07:42:16Z) - Rank lower bounds on non-local quantum computation [0.0]
非局所量子計算(NLQC)は、2つの量子システム間の相互作用を1ラウンドの通信と共有絡みによって置き換える。
NLQCの2つのクラス、$f$-routingと$f$-BB84を研究し、これは古典的な情報理論の暗号と量子位置の検証に関係している。
論文 参考訳（メタデータ） (2024-02-28T19:00:09Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Quantum Lower Bounds by Sample-to-Query Lifting [33.82353457014144]
本稿では,量子サンプル対クエリリフト定理を用いて,量子クエリの下界を証明するための新しい手法を提案する。
位相/振幅推定やハミルトニアンシミュレーションなど,いくつかの既知の下界に対する統一的な証明を提供する。
論文 参考訳（メタデータ） (2023-08-03T14:41:49Z) - Approximate degree lower bounds for oracle identification problems [19.001036556917818]
本稿では,特定のオラクル識別問題に対する近似次数下界を証明するためのフレームワークを提案する。
我々の下界は、大域関数と等値関数に対するランダムな通信上界によって駆動される。
論文 参考訳（メタデータ） (2023-03-07T14:30:28Z) - 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) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。