論文の概要: Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem

• arxiv url: http://arxiv.org/abs/2301.01589v1
• Date: Tue, 3 Jan 2023 02:22:00 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-08 22:27:10.375255
• Title: Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
• Title（参考訳）: NP完全頂点色問題に対する量子フェーシビリティラベリング
• Authors: Junpeng Zhan
• Abstract要約: 本稿では、カラーリング問題に対する全ての可能な解をラベル付けするための量子フィジビリティラベリング(QFL)アルゴリズムを提案する。 前回の研究で提案したVQSアルゴリズムは、26量子ビットまでで、非構造化データベースから良い要素を見つけるための指数的な高速化を実現している。 QFLとVQSは、VQSが任意の量子ビットに対して効率的であることが証明された場合、NP完全問題を時間内に解く最初のアルゴリズムとなる可能性がある。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many important science and engineering problems can be converted into NP-complete problems which are of significant importance in computer science and mathematics. Currently, neither existing classical nor quantum algorithms can solve these problems in polynomial time. To overcome this difficulty, this paper proposes a quantum feasibility labeling (QFL) algorithm to label all possible solutions to the vertex coloring problem, which is a well-known NP-complete problem. The variational quantum search (VQS) algorithm proposed in my previous work has been demonstrated, up to 26 qubits, to achieve an exponential speedup in finding good element(s) from an unstructured database. Using the labels and the associated possible solutions as input, the VQS can find all feasible solutions to the vertex coloring problem. The number of qubits and the circuit depth required by the QFL each is a polynomial function of the number of vertices, the number of edges, and the number of colors of a vertex coloring problem. The QFL together with the VQS could be the first algorithm to solve an NP-complete problem in polynomial time, provided that the VQS is proved to be efficient for any number of qubits.
• Abstract（参考訳）: 多くの重要な科学と工学の問題は、コンピュータ科学と数学において重要なNP完全問題に変換できる。 現在、既存の古典アルゴリズムや量子アルゴリズムではこれらの問題を多項式時間で解くことはできない。 そこで本研究では,np完全問題である頂点彩色問題に対して,可能な解すべてをラベル付けする量子化可能性ラベル付け(qfl)アルゴリズムを提案する。 前回の研究で提案した変分量子サーチ(VQS)アルゴリズムは、26キュービットまでで、非構造化データベースから良い要素を見つけるための指数的な高速化を実現している。 ラベルと関連する可能な解を入力として、VQSは頂点色問題に対するすべての実現可能な解を見つけることができる。 QFLが要求する量子ビット数と回路深さは、頂点の数、エッジの数、頂点色問題の色数の多項式関数である。 QFLとVQSは多項式時間でNP完全問題を解く最初のアルゴリズムであり、VQSが任意の量子ビットに対して効率的であることが証明される。

関連論文リスト

• Towards Less Greedy Quantum Coalition Structure Generation in Induced Subgraph Games [3.6021182997326022]
  100%再生可能エネルギーへの移行には、マイクログレードと呼ばれる有能なプロシューマーのサブセットに分割するなど、エネルギーネットワークを管理する新しい技術が必要である。 最適な方法で行うことは、誘導サブグラフゲームにおける結合構造生成問題に抽象化できるため、難しい最適化問題である。 本研究は,GCS-Qをソリューション品質の面で上回りうるかどうかを検証し,より控えめなQAベースのアプローチを提案する。
  論文  参考訳（メタデータ） (2024-08-08T10:54:56Z)
• Quantum Speedup for the Maximum Cut Problem [6.588073742048931]
  古典的なグラフに対して2次スピードアップを施した任意のグラフ$G$に対する最大カット問題を解く量子アルゴリズムを提案する。 NP完全問題に対するオラクル関連量子アルゴリズムについて,本アルゴリズムを最適とみなす。
  論文  参考訳（メタデータ） (2023-05-26T05:31:25Z)
• Solving Subset Sum Problems using Quantum Inspired Optimization Algorithms with Applications in Auditing and Financial Data Analysis [2.0981723008692392]
  Hopfield Networksの勾配勾配勾配が、人工データと実データの両方の解を確実に見つける方法を示す。 本稿では,このアルゴリズムを断熱量子コンピュータに応用する方法を概説する。
  論文  参考訳（メタデータ） (2022-10-28T12:22:15Z)
• From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
  まず、量子力学とグラフ理論の相関関係について、量子コンピュータが有用な解を生成できることを示す。 本稿では,その実践性と適用性について,一般的なグラフ学習手法について概説する。 今後の研究の触媒として期待される量子グラフ学習のスナップショットを提供する。
  論文  参考訳（メタデータ） (2022-02-19T02:56:47Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• ORQVIZ: Visualizing High-Dimensional Landscapes in Variational Quantum Algorithms [51.02972483763309]
  変分量子アルゴリズム(VQA)は、量子コンピュータの実用的な応用を見つけるための有望な候補である。 この作業には、オープンソースのPythonパッケージである$textitorqviz$のリリースが伴っている。
  論文  参考訳（メタデータ） (2021-11-08T18:17:59Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• 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)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding [0.0]
  グラフ彩色問題に対する空間効率のよい量子最適化アルゴリズムを提案する。 我々の回路は標準的アプローチよりも深い。 現在利用可能な代替品を探索するために、量子アニール上でランダムなグラフ色付けの研究を行う。
  論文  参考訳（メタデータ） (2020-09-15T18:34:17Z)
• Decomposition algorithms for solving NP-hard problems on a quantum annealer [0.0]
  NPハード問題は、計算化学、生化学、コンピュータネットワークセキュリティに応用されている。 Adaabatic quantum annealers can search the optimum value of such NP-hard optimization problem, because the problem can be embedded on their hardware。 本稿ではNP-hardグラフ問題に対する分解アルゴリズムの一般的な枠組みについて検討する。
  論文  参考訳（メタデータ） (2020-09-10T15:59:06Z)

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

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