論文の概要: Quantum Query Complexity of Maximum Degree and its Generalizations
- arxiv url: http://arxiv.org/abs/2610.13906v1
- Date: Fri, 09 Oct 2026 17:47:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-13 04:06:29.704715
- Title: Quantum Query Complexity of Maximum Degree and its Generalizations
- Title（参考訳）: 最大Degreeの量子クエリ複雑性とその一般化
- Abstract要約: いくつかの基本グラフ問題の量子クエリ複雑性について検討する。
すべての定数$kgeq 1$に対して、$O(n2-1/(k+1))$-query量子アルゴリズムを与える。
我々は、$k$-Graph Collisionを含む最大$(k,n-k)$-Cutへの還元を確立する。
- 参考スコア（独自算出の注目度）: 0.26097841018267615
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the quantum query complexity of several basic graph problems. 1) We prove a tight $Θ(n^{3/2})$ bound for finding a maximum-out-degree vertex in an $n$-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an $n$-vertex undirected graph requires $Θ(n^{3/2})$ quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum $(k,n-k)$-Cut, which asks for the largest cut with one side of size $k$. For every constant $k\geq 1$, we give an $O(n^{2-1/(k+1)})$-query quantum algorithm. 4) We establish a reduction to Maximum $(k,n-k)$-Cut involving $k$-Graph Collision, which asks whether the marked vertices of a known graph contain a $k$-clique. For $k\geq 3$, this yields unconditional lower bounds with exponents strictly larger than $3/2$, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for $k$-Graph Collision, the reduction yields a lower bound matching our upper bound above.
- Abstract（参考訳）: いくつかの基本グラフ問題の量子クエリ複雑性について検討する。
1) マンデ、パラアシュタル、サウラブの予想(FSTTCS'23)を解き、$n$-頂点トーナメントにおける最大外度頂点を見つけるための厳密な$(n^{3/2})$バウンドを証明する。
2) 同じ証明のアイデアを用いて、$n$-vertex の無向グラフにおける最大度頂点を見つけるには、Apers と Lee [CCC'21] の業績における有界な有界な量子クェリ(英語版)$$$(n^{3/2}) が必要であるという直接的な証明を与える。
上述の2つの下界は、最大等級または最大外度しか計算できない。
3) Maximum $(k,n-k)$-Cut も検討する。
すべての定数$k\geq 1$に対して、$O(n^{2-1/(k+1)})$-query量子アルゴリズムを与える。
4) 既知のグラフのマークされた頂点が$k$-cliqueを含むかどうかを問う、$k$-Graph Collisionを含む最大$(k,n-k)$-Cutへの還元を確立する。
k\geq 3$ の場合、これは指数が 3/2$ より厳密に大きい無条件の下限となり、この問題は最大度を計算するよりも厳密に難しいことを示している。
さらに、$k$-グラフ衝突を予想すると、還元は上界に一致する下界が得られる。
関連論文リスト
- Quantum Query Lower Bounds for Triangle-Listing and Spanners [3.3186745403320326]
固定された$kge 7$に対して、乗法的な$k$-spannerを構成するには$(n1+frac12_k)$の量子クエリが必要である。
これは三角形リストのための最初の非自明な量子下界であり、ジアンとペン(ICML 2026)が提起した質問である。
論文 参考訳（メタデータ） (2026-09-29T09:18:33Z) - An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
単位球面上の最適化問題の総和緩和を解析するためのargmax原理を開発する。
私たちの指導原則は、最大値が丸みを帯びた候補であることです。
論文 参考訳（メタデータ） (2026-08-03T17:58:00Z) - Optimal Quantum de Finetti Theorems via Argmax Rounding [42.55259086694773]
ボゾン状態と任意の交換可能な状態に対する最適有限量子デ・フィネッティ上界を証明する。
我々の証明は、対称拡張半定プログラムの積分性ギャップとしてのFinetti近似を定式化したものである。
スペクトルの切り離しはヒルベルト-シュミット距離における最初の次元自由ボソニック・デ・フィネッティの定理を与える。
論文 参考訳（メタデータ） (2026-08-03T17:57:15Z) - A Spectral Proof of the Hypergraph Moore Bound [46.26532142699448]
ハイパーグラフムーア境界に関するファイゲの2008年の予想を証明する。
すべての$kge3$と$1leellle n$に対して、$n$ vertices 上の任意の $k$-uniform hypergraph は、$C,nk/2/ellk/2-1$ hyperedges は、最大$A,elllog(en/ell)$で偶数被覆を含む。
論文 参考訳（メタデータ） (2026-07-28T17:38:31Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Almost all graphs are vertex-minor universal [0.0]
均一にランダムなグラフ $Gsim Mathrmvm(k)$ が、高い確率で $(sqrt n)$-vertex-minor Universal であることを証明する。
これは量子通信ネットワークに直接的な意味を持つ。
論文 参考訳（メタデータ） (2026-02-06T20:59:33Z) - Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。
この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
論文 参考訳（メタデータ） (2025-08-28T17:04:18Z) - A note on quantum lower bounds for local search via congestion and expansion [4.68073705539907]
G$上の局所探索の量子クエリの複雑さは$Omegabigl( fracnfrac34sqrtg bigr)$であることを示す。
古典的な設定とは対照的に、そのようなグラフに対して、下界と最もよく知られた上界の$Obigl(nfrac13 bigr)$の間の量子ケースにギャップが残っている。
論文 参考訳（メタデータ） (2024-12-17T21:42:42Z) - A sublinear query quantum algorithm for s-t minimum cut on dense simple
graphs [1.0435741631709405]
グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。
この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
論文 参考訳（メタデータ） (2021-10-29T07:35:46Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。