論文の概要: Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model

• arxiv url: http://arxiv.org/abs/2610.01752v1
• Date: Thu, 01 Oct 2026 14:18:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.183917
• Title: Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model
• Title（参考訳）: 有界グラフモデルにおける二分数性および拡張テストの準最適量子クエリ下界
• Abstract要約: 有界度モデルにおけるグラフ特性試験における2つの正準問題である二分性および拡張試験について検討する。 古典的な設定では、これらのテスト問題の両方に$widetilde(sqrtN)クエリが必要である。 多大な努力にもかかわらず、この10年半の間にこれらの結果は改善されていない。
• 参考スコア（独自算出の注目度）: 1.6379393441314491
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexity. In the classical setting, it is known that $\widetildeΘ(\sqrt{N})$ queries are necessary and sufficient for both these testing problems (Goldreich and Ron, 1999, 2000 & 2002), where $N$ denotes the number of vertices of the input graph. Due to their significance, (Ambainis, Childs, and Liu, 2011) initiated the study of these problems in the quantum setting and designed quantum algorithms for bipartiteness and expansion testing that perform $\widetilde{O}(N^{1/3})$ queries, showing a polynomial speedup. They also proved that $\widetildeΩ(N^{1/4})$ queries are necessary for expansion testing, but the possibility of an exponential quantum advantage for bipartiteness testing remained open. Despite significant effort, there has been no improvement in these results in the last decade and a half. In this work, we prove essentially tight $\widetildeΩ(N^{1/3})$ quantum query lower bounds for both bipartiteness and expansion testing, thereby completely characterizing the quantum query complexity of these problems up to polylogarithmic factors. While our proofs use the polynomial method similarly to Ambainis, Childs, and Liu, we use intermediate problems that we relate to the main problems via reductions, and perform a more precise analysis of the resulting polynomials, leading to the near-optimal lower bounds.
• Abstract（参考訳）: 本研究では、量子クエリ複雑性のレンズを用いて、有界度モデルにおけるグラフ特性試験における2つの正準問題である二分性テストと拡張テストについて検討する。 古典的な設定では、$\widetilde'(\sqrt{N})$クエリはこれらのテスト問題(Goldreich and Ron, 1999, 2000 & 2002)に十分必要であり、$N$は入力グラフの頂点数を表す。 それらの重要性から (Ambainis, Childs, and Liu, 2011) は、これらの問題の量子設定における研究を開始し、二分法と拡張テストのための量子アルゴリズムを設計し、$\widetilde{O}(N^{1/3})$クエリを実行し、多項式のスピードアップを示した。 また、拡張テストには$\widetildeΩ(N^{1/4})$クエリが必要であることも証明したが、双分数テストの指数的量子優位性の可能性は未解決のままであった。 多大な努力にもかかわらず、この10年半の間にこれらの結果は改善されていない。 本研究では、二分性および拡張テストの両方の量子クエリローバウンドに対して、本質的に$\widetildeΩ(N^{1/3})$の量子クエリローバウンドを証明し、これらの問題の量子クエリ複雑性を多変数因子まで完全に特徴づける。 証明は、アムバイニス、チャイルドズ、リューと同様の多項式法を用いるが、還元による主問題と関係する中間問題を使用し、結果の多項式をより正確に解析し、最適に近い下界へと導く。

関連論文リスト

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。 浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
  論文  参考訳（メタデータ） (2026-09-01T15:54:34Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Quantum property testing in sparse directed graphs [0.9624643581968987]
  古典的な一方向モデルでは、$k$-star-freeness、より一般に$k$-source-subgraph-freenessをテストするという問題は、大きめの$k$にとってほとんど極端に難しい。 この問題は量子環境においてほとんど有利であることを示す。
  論文  参考訳（メタデータ） (2024-10-07T13:00:43Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Lower Bounds for Unitary Property Testing with Proofs and Advice [0.0]
  ユニタリプロパティのテストでは、テスタとしても知られる量子アルゴリズムは、ブラックボックスのユニタリへのクエリアクセスが与えられる。 本稿では,一元性検定の量子クエリの下位境界を証明するための新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-01-15T19:00:36Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)

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

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