論文の概要: Explicit Quantum Search Algorithm for the Densest k-Subgraph Problem

• arxiv url: http://arxiv.org/abs/2604.27782v1
• Date: Thu, 30 Apr 2026 12:21:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-01 16:31:54.083196
• Title: Explicit Quantum Search Algorithm for the Densest k-Subgraph Problem
• Title（参考訳）: 密度k-サブグラフ問題に対する明示的量子探索アルゴリズム
• Authors: Yu. A. Biriukov, R. D. Morozov, I. V. Dyakonov, S. S. Straupe,
• Abstract要約: 本稿では,任意のグラフに最も高密度な$k$-vertex部分グラフを求める問題に対処する。 ソーシャルネットワークの分析、不正検出、レコメンデーションシステム、バイオインフォマティクスに重要な応用がある。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper addresses the problem of finding the densest $k$-vertex subgraph in an arbitrary graph. This problem is NP-hard and has important applications in social network analysis, fraud detection, recommendation systems, and bioinformatics. We propose two quantum approaches to solve this problem: reduction to Quadratic Unconstrained Binary Optimization (QUBO) and using Grover's quantum search algorithm. For the latter approach, we present an explicit gate-based oracle circuit utilizing Dicke states and Quantum Fourier Transform for edge counting. Numerical simulations demonstrate a quadratic speedup over classical Brute-force search.
• Abstract（参考訳）: 本稿では,任意のグラフに最も高密度な$k$-vertex部分グラフを求める問題に対処する。 この問題はNPハードであり、ソーシャルネットワーク分析、不正検出、レコメンデーションシステム、バイオインフォマティクスに重要な応用がある。 本稿では,この問題を解決するための量子的アプローチとして,二次的非制約バイナリ最適化(QUBO)の削減と,Groverの量子探索アルゴリズムを用いた2つの方法を提案する。 後者のアプローチでは、Dicke状態とQuantum Fourier変換を利用した明示的なゲートベースオラクル回路をエッジカウントのために提案する。 数値シミュレーションは、古典的なブリュート力探索の2次高速化を実証する。

関連論文リスト

• Graph theory-based automated quantum algorithm for efficient querying of acyclic and multiloop causal configurations [0.0]
  ループ・トレー・デュナリティ内の因果構造を効率的に問合せする自動量子アルゴリズムである最小斜め最適化量子アルゴリズム(MCA)を提案する。 MCA量子アルゴリズムは、グラフ理論の手法、特に最小の傾き分割問題と類似して最適化される。
  論文  参考訳（メタデータ） (2025-08-06T02:18:08Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• Quantum querying based on multicontrolled Toffoli gates for causal Feynman loop configurations and directed acyclic graphs [0.0]
  両種類のアプリケーションでクエリを行う量子アルゴリズムを提案する。 アルゴリズムの効率は、二項節に基づく量子アルゴリズムとの比較により評価される。 これまでに検討されていない3ループ,4ループ,5ループのトポロジーを明示的に分析する。
  論文  参考訳（メタデータ） (2024-04-04T15:51:43Z)
• Addressing Quantum's "Fine Print": State Preparation and Information Extraction for Quantum Algorithms and Geologic Fracture Networks [0.0]
  この研究は、量子アルゴリズムを用いて地質的なフラクチャーフローシステムを解くための2つの要件に対処する。 この問題に対する我々のアプローチは、全体的な指数的なスピードアップと一致している。
  論文  参考訳（メタデータ） (2023-10-03T23:02:54Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• Quantum Speedup for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection [2.5272389610447856]
  実数値の高次非制約二項最適化問題をサポートする量子アルゴリズムを提案する。 提案アルゴリズムは,古典的領域におけるクエリの複雑さを低減し,量子領域における2次高速化を実現する。
  論文  参考訳（メタデータ） (2022-05-31T00:14:49Z)
• 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 algorithm for Feynman loop integrals [0.0]
  量子アルゴリズムのFeynmanループ積分への新しいベンチマーク適用を提案する。 ファインマンプロパゲーターの2つのオンシェル状態は、キュービットの2つの状態と同一視される。 量子アルゴリズムは、マルチループファインマン図形の因果特異構成を展開するために用いられる。
  論文  参考訳（メタデータ） (2021-05-18T17:41:56Z)

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

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