論文の概要: Auxiliary-Qubit-Free Quantum Approximate Optimization Algorithm for the Minimum Dominating Set Problem

• arxiv url: http://arxiv.org/abs/2509.16653v1
• Date: Sat, 20 Sep 2025 12:01:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-23 18:58:15.907466
• Title: Auxiliary-Qubit-Free Quantum Approximate Optimization Algorithm for the Minimum Dominating Set Problem
• Title（参考訳）: 最小支配集合問題に対する補助量子自由量子近似最適化アルゴリズム
• Authors: Guanghui Li, Xiaohui Ni, Junjian Su, Sujuan Qin, Fenzhuo Guo, Bingjie Xu, Wei Huang, Fei Gao,
• Abstract要約: 最小支配集合(MDS)問題に対する補助量子ビットフリー量子近似最適化アルゴリズム(QAOA)を提案する。 提案アルゴリズムは,従来のQAOAに匹敵する性能を達成し,量子ビットの削減を実現している。 マルチ角QAOAに基づくアブレーション研究では、共有回路パラメータを独立回路に置き換えることで、アルゴリズムの解の質をさらに改善できることが示されている。
• 参考スコア（独自算出の注目度）: 6.467872637658972
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum Approximate Optimization Algorithm (QAOA) is a promising framework for solving combinatorial optimization problems on near-term quantum devices. One such problem is the Minimum Dominating Set (MDS), which is NP-hard in graph theory. Existing QAOA studies for the MDS problem typically require a large number of auxiliary qubits, which increases hardware demands and hinders scalability on Noisy Intermediate-Scale Quantum (NISQ) devices. In this paper, we propose an auxiliary-qubit-free QAOA for the MDS problem. Unlike previous studies that introduce auxiliary variables to convert inequality constraints into equalities, our algorithm utilizes Boolean algebra to perform this transformation, eliminating the need for auxiliary qubits. Numerical experiments demonstrate that our algorithm achieves comparable performance to the existing best QAOA for this problem while using fewer qubits. Additionally, an ablation study based on multi-angle QAOA reveals that the solution quality of the algorithm can be further improved by replacing shared circuit parameters with independent ones.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、短期量子デバイスにおける組合せ最適化問題を解決するための有望なフレームワークである。 そのような問題の1つは最小支配集合(MDS)であり、これはグラフ理論においてNPハードである。 MDS問題に対する既存のQAOA研究は、通常、多数の補助量子ビットを必要とし、ハードウェアの要求を増大させ、ノイズのある中間量子(NISQ)デバイスにおけるスケーラビリティを阻害する。 本稿では,MDS問題に対する補助量子自由QAOAを提案する。 不等式制約を等式に変換するために補助変数を導入した以前の研究とは異なり、我々のアルゴリズムはブール代数を用いてこの変換を行い、補助量子ビットは不要である。 数値実験により,本アルゴリズムは従来のQAOAに匹敵する性能を示した。 さらに、マルチ角QAOAに基づくアブレーション研究により、共有回路パラメータを独立回路に置き換えることで、アルゴリズムの解の質をさらに改善できることが明らかになった。

関連論文リスト

• On the role of overparametrization in Quantum Approximate Optimization [0.0]
  変分量子アルゴリズムは、現代の量子アルゴリズム研究の基盤として登場した。 本研究は,量子近似最適化アルゴリズム (QAOA) に焦点をあてる。 MAX-CUT と MAX-2-SAT の2つの代表的な問題を考慮し、QAOA においてそのような問題を解くのに回路オーバーパラメトリゼーションが必要かどうかを検討する。
  論文  参考訳（メタデータ） (2025-08-13T18:00:00Z)
• Variational quantum algorithm-preserving feasible space for solving the uncapacitated facility location problem [3.3682090109106446]
  本稿では,変分量子アルゴリズムで実現可能な空間(VQA-PFS)アンサッツを提案する。 このアンザッツは制約変数に混合演算子を適用し、非制約変数にハードウェア効率アンザッツ(HEA)を用いる。 その結果, VQA-PFSは成功確率を著しく向上し, より高速な収束を示すことがわかった。
  論文  参考訳（メタデータ） (2023-12-12T01:36:49Z)
• Multi-sequence alignment using the Quantum Approximate Optimization Algorithm [0.0]
  本稿では、変分量子近似最適化アルゴリズム(QAOA)を用いた多重系列アライメント問題のハミルトニアン定式化と実装について述べる。 我々は、量子シミュレーターと実際の量子コンピュータ上での性能の両方において、我々のQAOA-MSAアルゴリズムの小さな例を考える。 調査されたMSAのインスタンスに対する理想的な解決策は、浅いp5量子回路でサンプリングされた最も可能性の高い状態であることが示されているが、現在のデバイスにおけるノイズのレベルは依然として深刻な課題である。
  論文  参考訳（メタデータ） (2023-08-23T12:46:24Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  余分なスラック変数を必要としない代替手法を提案する。 我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。 この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
  論文  参考訳（メタデータ） (2022-11-25T06:05:18Z)
• General Hamiltonian Representation of ML Detection Relying on the Quantum Approximate Optimization Algorithm [74.6114458993128]
  最適化問題を解くために考案された量子近似最適化アルゴリズム(QAOA)は、既存のノイズのある中間スケール量子(NISQ)デバイス上で実行することができる。 我々は、QAOAを適切に適応させることにより、一般星座の最大可能性(ML)検出問題を解く。 特に、M-ary Gray-mapped Quarature amplitude modulation (MQAM) 星座では、同相成分をコードする特定の量子ビットと二次成分をコードする量子ビットが、興味のある量子系において独立であることを示す。
  論文  参考訳（メタデータ） (2022-04-11T14:11:24Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• Quantum constraint learning for quantum approximate optimization algorithm [0.0]
  本稿では,探索部分空間を厳しく制約するミキサーハミルトンを学習するための量子機械学習手法を提案する。 学習したユニタリを直接適応可能なアンサッツを使用してQAOAフレームワークにプラグインすることができる。 また,Wasserstein距離を用いた近似最適化アルゴリズムの性能を,制約なしで評価する直感的計量法を開発した。
  論文  参考訳（メタデータ） (2021-05-14T11:31:14Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer [0.0]
  量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くハイブリッド変分量子古典アルゴリズムである。 我々は,QAOAの反復バージョンを開発し,特定のハードウェア制約に適応することができる。 アルゴリズムをMax-Cutグラフのクラス上でシミュレートし、標準QAOAよりもはるかに高速に収束することを示す。
  論文  参考訳（メタデータ） (2020-05-20T18:00:01Z)

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

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