論文の概要: qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem

• arxiv url: http://arxiv.org/abs/2503.12551v1
• Date: Sun, 16 Mar 2025 15:41:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-18 15:58:53.616465
• Title: qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem
• Title（参考訳）: qReduMIS:最大独立集合問題に対する量子インフォームド還元アルゴリズム
• Authors: Martin J. A. Schuetz, Romina Yalovetzky, Ruben S. Andrist, Grant Salton, Yue Sun, Rudy Raymond, Shouvanik Chakrabarti, Atithi Acharya, Ruslan Shaydulin, Marco Pistoia, Helmut G. Katzgraber,
• Abstract要約: 本稿では,最大独立集合問題に対する量子インフォームド還元アルゴリズムの提案と実装を行う。 我々は、qReduMISが、Rydberg量子デバイスを含む幅広い問題解決者の直面する基本的な性能制限に対処するのに役立つことを示す。 超伝導量子ビットやトラップイオンなどの代替プラットフォームを用いたqReduMISの実装について概説する。
• 参考スコア（独自算出の注目度）: 10.162280421416208
• License:
• Abstract: We propose and implement a quantum-informed reduction algorithm for the maximum independent set problem that integrates classical kernelization techniques with information extracted from quantum devices. Our larger framework consists of dedicated application, algorithm, and hardware layers, and easily generalizes to the maximum weight independent set problem. In this hybrid quantum-classical framework, which we call qReduMIS, the quantum computer is used as a co-processor to inform classical reduction logic about frozen vertices that are likely (or unlikely) to be in large independent sets, thereby opening up the reduction space after removal of targeted subgraphs. We systematically assess the performance of qReduMIS based on experiments with up to 231 qubits run on Rydberg quantum hardware available through Amazon Braket. Our experiments show that qReduMIS can help address fundamental performance limitations faced by a broad set of (quantum) solvers including Rydberg quantum devices. We outline implementations of qReduMIS with alternative platforms, such as superconducting qubits or trapped ions, and we discuss potential future extensions.
• Abstract（参考訳）: 本稿では,量子デバイスから抽出した情報と古典的カーネル化技術を統合した最大独立集合問題に対する量子インフォームド還元アルゴリズムの提案と実装を行う。 我々のより大きなフレームワークは専用アプリケーション層、アルゴリズム層、ハードウェア層から構成されており、最大重量独立集合問題に容易に一般化できる。 我々はqReduMISと呼ぶこのハイブリッド量子古典的フレームワークにおいて、量子コンピュータをコプロセッサとして使用し、大きな独立した集合にある(あるいはありそうもない)凍った頂点について古典的な還元論理を知らせ、標的部分グラフの削除後に縮小空間を開放する。 我々は、Amazon Braketで利用可能なRydberg量子ハードウェア上で最大231量子ビットで動作する実験に基づいて、qReduMISの性能を体系的に評価する。 我々の実験により、qReduMISは、Rydberg量子デバイスを含む幅広い(量子)ソルバが直面する基本的な性能制限に対処できることが示された。 超伝導量子ビットやトラップイオンなどの代替プラットフォームを用いたqReduMISの実装について概説し、今後の拡張の可能性について論じる。

関連論文リスト

• Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization [0.8121127831316319]
  本稿では,デバイス間通信コストを大幅に削減する量子回路の構築手法を提案する。 そこで本研究では,従来のQDCA手法の約3倍の大きさのトラクタブル回路を構築できることを示す。
  論文  参考訳（メタデータ） (2024-05-01T20:49:50Z)
• Formulation of the Electric Vehicle Charging and Routing Problem for a Hybrid Quantum-Classical Search Space Reduction Heuristic [0.0]
  制約付き量子最適化アルゴリズムの構築において、量子情報の多レベルキャリア -- 量子ビット -- をどのように活用するかを示す。 本稿では,制約付き解をサンプリングし,探索空間を大幅に削減するハイブリッド古典量子戦略を提案する。
  論文  参考訳（メタデータ） (2023-06-07T13:16:15Z)
• Bootstrap Embedding on a Quantum Computer [4.138095344167023]
  分子ブートストラップの埋め込みを拡張し、量子コンピュータの実装に適したものにする。 古典的アルゴリズムを原理として、二次的なスピードアップがどのように得られるかを示す。
  論文  参考訳（メタデータ） (2023-01-04T05:49:15Z)
• Towards Neural Variational Monte Carlo That Scales Linearly with System Size [67.09349921751341]
  量子多体問題(Quantum many-body problem)は、例えば高温超伝導体のようなエキゾチックな量子現象をデミストする中心である。 量子状態を表すニューラルネットワーク(NN)と変分モンテカルロ(VMC)アルゴリズムの組み合わせは、そのような問題を解決する上で有望な方法であることが示されている。 ベクトル量子化技術を用いて,VMCアルゴリズムの局所エネルギー計算における冗長性を利用するNNアーキテクチャVector-Quantized Neural Quantum States (VQ-NQS)を提案する。
  論文  参考訳（メタデータ） (2022-12-21T19:00:04Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCSは、量子古典ハイブリッドシステムにおけるインデックス検索とカウントを目的としている。 我々はQiskitでIQuCSを実装し、集中的な実験を行う。 その結果、量子ビットの消費を最大66.2%削減できることが示されている。
  論文  参考訳（メタデータ） (2022-09-22T21:54:28Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  最大独立集合問題の解法として量子アルゴリズムを実験的に検討する。 問題の難易度は解の縮退と局所ミニマの数によって制御される。 最も難しいグラフでは、正確な解を見つける際に超線形量子スピードアップを観測する。
  論文  参考訳（メタデータ） (2022-02-18T19:00:01Z)
• Hardware-Efficient, Fault-Tolerant Quantum Computation with Rydberg Atoms [55.41644538483948]
  我々は中性原子量子コンピュータにおいてエラー源の完全な特徴付けを行う。 計算部分空間外の状態への原子量子ビットの崩壊に伴う最も重要なエラーに対処する,新しい,明らかに効率的な手法を開発した。 我々のプロトコルは、アルカリ原子とアルカリ原子の両方にエンコードされた量子ビットを持つ最先端の中性原子プラットフォームを用いて、近い将来に実装できる。
  論文  参考訳（メタデータ） (2021-05-27T23:29:53Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  量子コンピューティングの標準的なアプローチは、古典的にシミュレート可能なフォールトトレラントな演算セットを促進するという考え方に基づいている。 量子回路の古典的準確率シミュレーションをどのように促進するかを示す。
  論文  参考訳（メタデータ） (2021-03-12T20:58:41Z)
• Small quantum computers and large classical data sets [2.8174125805742416]
  本稿では,大規模古典データセット X とモデル Y の空間に関する問題に対して,ハイブリッド古典量子アルゴリズムを提案する。 これらのアルゴリズムは、X の重み付き部分集合を構成するためにデータ還元技術を使用し、各モデルにほぼ同じ損失をもたらすコアセットである。 具体的な応用としては、k平均クラスタリング、論理回帰、ゼロサムゲーム、ブースティングなどがある。
  論文  参考訳（メタデータ） (2020-03-31T18:00:16Z)

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

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