論文の概要: Quantum algorithms for hypergraph simplex finding

• arxiv url: http://arxiv.org/abs/2409.00239v1
• Date: Fri, 30 Aug 2024 20:12:45 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-06 16:18:33.950243
• Title: Quantum algorithms for hypergraph simplex finding
• Title（参考訳）: ハイパーグラフ簡易探索のための量子アルゴリズム
• Authors: Zhiying Yu, Shalev Ben-David,
• Abstract要約: ハイパーグラフへの三角形探索の一般化である, 単純度探索のための量子クエリアルゴリズムについて検討する。 この問題は階数還元性を満たす:ランク-r$ハイパーグラフの単純さを見つける量子クエリアルゴリズムは、ランク-(r-1)$ハイパーグラフの単純さを見つけるためのより高速なアルゴリズムに変換できる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the quantum query algorithms for simplex finding, a generalization of triangle finding to hypergraphs. This problem satisfies a rank-reduction property: a quantum query algorithm for finding simplices in rank-$r$ hypergraphs can be turned into a faster algorithm for finding simplices in rank-$(r-1)$ hypergraphs. We then show that every nested Johnson graph quantum walk (with any constant number of nested levels) can be converted into an adaptive learning graph. Then, we introduce the concept of $\alpha$-symmetric learning graphs, which is a useful framework for designing and analyzing complex quantum search algorithms. Inspired by the work of Le Gall, Nishimura, and Tani (2016) on $3$-simplex finding, we use our new technique to obtain an algorithm for $4$-simplex finding in rank-$4$ hypergraphs with $O(n^{2.46})$ quantum query cost, improving the trivial $O(n^{2.5})$ algorithm.
• Abstract（参考訳）: ハイパーグラフへの三角形探索の一般化である, 単純度探索のための量子クエリアルゴリズムについて検討する。 この問題は階数還元性を満たす:ランク-r$ハイパーグラフの単純さを見つける量子クエリアルゴリズムは、ランク-(r-1)$ハイパーグラフの単純さを見つけるためのより高速なアルゴリズムに変換できる。 すると、ネストされたジョンソングラフの量子ウォーク(ネストされたレベルが一定数ある)が適応的な学習グラフに変換できることが示される。 次に、複雑な量子探索アルゴリズムを設計・解析するのに有用なフレームワークである$\alpha$-symmetric learning graphという概念を紹介した。 Le Gall, Nishimura, Tani (2016) の3$-simplex find に触発されて、我々は新しい手法を用いて、$O(n^{2.46})$量子クエリコストで4$-simplex find の 4$-simplex find のアルゴリズムを取得し、自明な$O(n^{2.5})$アルゴリズムを改善した。

関連論文リスト

• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo [0.0]
  Groverのアルゴリズムは、$O(sqrtN/k)$ stepsを使って$N$要素を持つ、順序のないデータベースで$k$要素を見つけることができる。 この研究は、他のグラフのマーク要素の値$k$を推定するために量子カウントアルゴリズムを使用する問題に取り組む。
  論文  参考訳（メタデータ） (2023-12-05T21:15:09Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。 3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。 数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
  論文  参考訳（メタデータ） (2023-11-19T00:06:11Z)
• Universal approach to deterministic spatial search via alternating quantum walks [2.940962519388297]
  本稿では,量子ウォークを交互に組み合わせることで,様々なグラフ上で決定論的量子探索アルゴリズムを設計するための新しいアプローチを提案する。 我々のアプローチは、異なるグラフに対してインスタンス固有の分析を必要としないため、普遍的である。
  論文  参考訳（メタデータ） (2023-07-30T05:14:19Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。 関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
  論文  参考訳（メタデータ） (2022-07-04T19:33:06Z)
• Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
  既存の量子ウォークに基づく探索アルゴリズムは、サッフル問題に悩まされている。 量子スピードアップを犠牲にすることなくロバスト性を実現する新しい量子ウォークベースの探索フレームワークを提案する。
  論文  参考訳（メタデータ） (2021-11-17T10:04:44Z)
• 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 algorithms for learning a hidden graph and beyond [0.05076419064097732]
  本稿では、量子アルゴリズムを用いて、託宣によって提供された未知のグラフを学習する問題について研究する。 ORおよびパリティクエリモデルにおいて、最も優れた古典的アルゴリズムの高速化を実現する量子アルゴリズムを提供する。 さらに、グループテスト問題の"ガッペ"バージョンに対して、Ambainisらのアルゴリズムに基づいて、この問題に対する時間効率の量子アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-11-17T13:12:43Z)
• A Query-Efficient Quantum Algorithm for Maximum Matching on General Graphs [0.0]
  最大マッチングのための量子アルゴリズムを設計する。 特に、$n$ノードと$m$エッジを持つグラフの場合、我々のアルゴリズムは行列モデルで$O(n7/4)クエリを生成する。
  論文  参考訳（メタデータ） (2020-10-05T20:34:39Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

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

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