論文の概要: Breaking the quantum barriers for Graph Collision

• arxiv url: http://arxiv.org/abs/2611.05356v1
• Date: Tue, 03 Nov 2026 18:53:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-07 05:19:36.672055
• Title: Breaking the quantum barriers for Graph Collision
• Title（参考訳）: グラフ衝突の量子障壁を破る
• Abstract要約: まず、予測された$(n2/3)$のクエリを、有界誤差量子アルゴリズムで下界に反証する。 次に、このアプローチを改良し、$widetilde O(n11/17)$クエリアルゴリズムを得る。 我々はこれらのアルゴリズムを$(sqrtnlog n)$の量子クエリローバウンドで補う。
• 参考スコア（独自算出の注目度）: 5.098250749223323
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the graph collision problem, the task is to decide whether a known graph on $n$ vertices contains an edge with both endpoints marked, given query access to the input bits specifying the marked vertices. We first refute the conjectured $Ω(n^{2/3})$ query lower bound with a bounded error quantum algorithm using $\widetilde O(n^{92/139})$ queries. We then refine this approach to obtain a $\widetilde O(n^{11/17})$ query algorithm. We also obtain a $\widetilde O((nq)^{11/17})$ query bound for all (partial) Boolean output functions with positive certificate complexity at most 2 and alphabet size $q$, contrasting a known $Ω(n^{2/3})$ lower bound for such problems with large alphabet sizes. We complement these algorithms with an $Ω(\sqrt{n\log n})$ quantum query lower bound for graph collision, exceeding the $O(\sqrt n)$ certificate complexity barrier for the positive adversary method.
• Abstract（参考訳）: グラフ衝突問題では、既知の$n$頂点上のグラフが、マークされた両方のエンドポイントを持つエッジを含むか否かを判断し、マークされた頂点を指定する入力ビットへのクエリアクセスを与える。 我々はまず、$\widetilde O(n^{92/139})$クエリを使って、有界な誤り量子アルゴリズムで下界の$Ω(n^{2/3})$クエリを解いた。 次に、このアプローチを改良して$\widetilde O(n^{11/17})$クエリアルゴリズムを得る。 また、全ての(部分的な)ブール出力関数に対する$\widetilde O((nq)^{11/17})$クエリバウンドを最大2で正の証明複雑性を持ち、既知の$Ω(n^{2/3})$ローバウンドに対して$q$とする。 我々は、これらのアルゴリズムを、グラフ衝突に対する量子クエリローバウンド$Ω(\sqrt{n\log n})$$O(\sqrt n)$証明複雑性障壁を超える$Ω(\sqrt{n\log n})$量子クエリローバウンドで補完する。

関連論文リスト

• Superlinear Quantum Query Lower Bounds for Subgraph Detection [5.69782807899183]
  サブグラフ検出は、その隣接行列にクエリを通してアクセスされる$n$-vertexグラフが、固定グラフ$H$のコピーを含むかどうかを問う。 本研究では、この問題の有界エラー量子クエリの複雑性について、非条件超線形下界を初めて証明する。
  論文  参考訳（メタデータ） (2026-09-30T17:42:46Z)
• An Optimal Quantum Linear Systems Algorithm [1.4903245304585715]
  量子線形システム問題(QLSP)では、条件番号$$$の$d$スパース$Ntimes N$Matrix$A$へのクエリアクセスが与えられる。 目標は、$vec x$ of $Avecx=vecb$に比例する量子状態に$$-approximationを出力することである。 行列エントリに対して$O(sqrt N)$クエリを使用して,任意の$Ntimes N$ユニタリを境界誤差で実装可能であることを示す。
  論文  参考訳（メタデータ） (2026-09-28T17:22:14Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• Quantum speedups for dynamic programming on $n$-dimensional lattice graphs [0.11470070927586015]
  複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。 最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
  論文  参考訳（メタデータ） (2021-04-29T14:50:03Z)
• Leveraging Unknown Structure in Quantum Query Algorithms [0.0]
  本研究では,事前の約束がなくても,これらのスピードアップが持続することを示すために,修正されたスパンプログラムアルゴリズムを示す。 我々のアルゴリズムは、$tildeO(sqrtkn)$クエリを使って、少なくとも$k$のエッジを持つパスがある場合、この問題を解決する。
  論文  参考訳（メタデータ） (2020-12-02T15:32:52Z)
• Quantum algorithms for graph problems with cut queries [17.149741568581096]
  量子アルゴリズムは、$O(d log(n)2) の後に最大$d$のグラフを学習できることを示す。 また、量子アルゴリズムは、$O(sqrtm log(n)3/2)$多くのカットクエリで一般的なグラフを学習できることを示す。
  論文  参考訳（メタデータ） (2020-07-16T12:21:01Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

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

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