論文の概要: Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding

• arxiv url: http://arxiv.org/abs/2009.07314v1
• Date: Tue, 15 Sep 2020 18:34:17 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-02 04:17:50.508367
• Title: Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
• Title（参考訳）: 空間効率な埋め込みによるグラフ色問題に対する量子最適化
• Authors: Zsolt Tabi and Kareem H. El-Safty and Zs\'ofia Kallus and P\'eter H\'aga and Tam\'as Kozsik and Adam Glos and Zolt\'an Zimbor\'as
• Abstract要約: グラフ彩色問題に対する空間効率のよい量子最適化アルゴリズムを提案する。 我々の回路は標準的アプローチよりも深い。 現在利用可能な代替品を探索するために、量子アニール上でランダムなグラフ色付けの研究を行う。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Current quantum computing devices have different strengths and weaknesses depending on their architectures. This means that flexible approaches to circuit design are necessary. We address this task by introducing a novel space-efficient quantum optimization algorithm for the graph coloring problem. Our circuits are deeper than the ones of the standard approach. However, the number of required qubits is exponentially reduced in the number of colors. We present extensive numerical simulations demonstrating the performance of our approach. Furthermore, to explore currently available alternatives, we perform a study of random graph coloring on a quantum annealer to test the limiting factors of that approach, too.
• Abstract（参考訳）: 現在の量子コンピューティングデバイスは、アーキテクチャによって長所と短所が異なる。 これは、回路設計への柔軟なアプローチが必要であることを意味する。 グラフカラー化問題に対して,空間効率のよい量子最適化アルゴリズムを導入することで,この問題に対処する。 私たちの回路は標準的なアプローチよりも深いです。 しかし、必要な量子ビットの数は、色数で指数関数的に減少する。 提案手法の性能を示す数値シミュレーションを広範囲に実施する。 さらに、現在利用可能な代替案を検討するために、量子アニーラのランダムグラフ色付けの研究を行い、そのアプローチの制限因子についても検証する。

関連論文リスト

• Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization [0.8121127831316319]
  本稿では,デバイス間通信コストを大幅に削減する量子回路の構築手法を提案する。 そこで本研究では,従来のQDCA手法の約3倍の大きさのトラクタブル回路を構築できることを示す。
  論文  参考訳（メタデータ） (2024-05-01T20:49:50Z)
• ATOM: An Efficient Topology Adaptive Algorithm for Minor Embedding in Quantum Computing [18.594343052664335]
  ハードウェアグラフの拡張可能な部分グラフである適応トポロジーの新たな概念を導入する。 ATOMは論理グラフからノードを反復的に選択し、ハードウェアグラフの適応トポロジーに埋め込む。 実験の結果、ATOMは最先端技術よりもはるかに少ない実行時間で実現可能な埋め込みを実現することができることがわかった。
  論文  参考訳（メタデータ） (2023-07-04T17:45:07Z)
• Parallelization techniques for quantum simulation of fermionic systems [0.0]
  フェルミオン作用素を量子ビット作用素にマッピングすることは、量子コンピュータ上でフェルミオン系をシミュレートするための重要なステップである。 このような写像の選択が量子プロセッサの量子ビット接続とどのように相互作用するかを検討する。
  論文  参考訳（メタデータ） (2022-07-25T18:41:59Z)
• From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
  まず、量子力学とグラフ理論の相関関係について、量子コンピュータが有用な解を生成できることを示す。 本稿では,その実践性と適用性について,一般的なグラフ学習手法について概説する。 今後の研究の触媒として期待される量子グラフ学習のスナップショットを提供する。
  論文  参考訳（メタデータ） (2022-02-19T02:56:47Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。 我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
  論文  参考訳（メタデータ） (2021-08-18T09:26:17Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)
• Quantum walk processes in quantum devices [55.41644538483948]
  グラフ上の量子ウォークを量子回路として表現する方法を研究する。 提案手法は,量子ウォークアルゴリズムを量子コンピュータ上で効率的に実装する方法である。
  論文  参考訳（メタデータ） (2020-12-28T18:04:16Z)
• Graph Coloring with Quantum Annealing [0.0]
  そこで我々は,D-Wave 2X を独立セットサンプリングとして用いたグラフカラー化近似アルゴリズムを開発した。 ランダムに生成された小さなグラフインスタンスのセットは、テストセットとして役立ちます。 我々の性能分析は、ハイブリッド量子古典アルゴリズムにおける量子優位性に限界があることを示唆している。
  論文  参考訳（メタデータ） (2020-12-08T15:08:22Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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