論文の概要: Quantum-Assisted Recursive Algorithm for Solving the Exact Cover Problem

• arxiv url: http://arxiv.org/abs/2509.10811v1
• Date: Sat, 13 Sep 2025 13:03:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-16 17:26:22.788659
• Title: Quantum-Assisted Recursive Algorithm for Solving the Exact Cover Problem
• Title（参考訳）: 厳密な被覆問題の解法のための量子支援再帰アルゴリズム
• Authors: Xiao-Hui Ni, Jia-Cheng Fan, Ling-Xiao Li, Zi-Wen Huang, Su-Juan Qin, Bing-Jie Xu, Wei-Huang, Fei Gao,
• Abstract要約: 本稿では,正確な被覆問題を解くための量子支援再帰アルゴリズムを提案する。 QARAは古典的および量子的プルーニングを交互に適用することでこの問題に対処する。 その結果, 正確な解を求める際のQARAの確率は, QAOAと再帰QAOAのどちらよりも約60%高いことがわかった。
• 参考スコア（独自算出の注目度）: 11.97361336620397
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The exact cover problem is an NP-complete problem with broad applications. Studies show that although applying the Quantum Approximate Optimization Algorithm (QAOA) to this problem can yield improved solution quality with deeper circuit depth, it can limit the algorithm's applicability on noisy intermediate-scale quantum devices. To improve solution quality at shallow depth, we propose a Quantum-Assisted Recursive Algorithm (QARA) for solving the exact cover problem. QARA addresses the problem by alternately applying classical and quantum pruning. Classical pruning is a repeatable pre-processing step to simplify the problem. When the classical pruning cannot promote the problem simplification, quantum pruning is invoked. During quantum pruning, QARA extracts information from the QAOA's output state to identify the subset with the strongest selection bias. This subset is then used to prune the problem based on our problem-tailored reduction rules. Furthermore, QARA incorporates a local verification and rollback mechanism to assistively judge the effectiveness of the quantum simplification. After quantum pruning, classical pruning is applied again to the reduced problem if the remaining subsets and element set are not null. This alternating process repeats until the original problem is fully resolved. In our numerical simulations, we evaluate the performance of QARA at one-layer depth on 140 instances with subset sizes ranging from 8 to 20. Numerical results show that the probability of QARA in finding an exact solution is approximately 60\% higher than that of both QAOA and Recursive QAOA, highlighting its efficiency.
• Abstract（参考訳）: 厳密な被覆問題は広く応用されたNP完全問題である。 この問題に量子近似最適化アルゴリズム(QAOA)を適用することで、より深い回路深度で解の質を向上させることができるが、ノイズの多い中間規模量子デバイスに対するアルゴリズムの適用性を制限することができる。 そこで本研究では,量子支援再帰アルゴリズム(QARA)を提案する。 QARAは古典的および量子的プルーニングを交互に適用することでこの問題に対処する。 古典的なプルーニングは、問題を単純化するための繰り返し可能な前処理ステップである。 古典的なプルーニングが問題の単純化を促進することができない場合、量子プルーニングが起動される。 量子プルーニング中、QARAはQAOAの出力状態から情報を抽出し、最も強い選択バイアスを持つサブセットを特定する。 このサブセットは、問題の調整されたリダクションルールに基づいて問題を解明するために使用されます。 さらに、QARAには、量子単純化の有効性を補助的に判断するローカル検証とロールバック機構が組み込まれている。 量子プルーニングの後、残りの部分集合と要素集合がヌルでない場合、古典的なプルーニングは還元問題に再び適用される。 この交互プロセスは、元の問題が完全に解決されるまで繰り返される。 数値シミュレーションでは, サブセットサイズが8～20の140インスタンスに対して, 1層深さでのQARAの性能を評価した。 その結果, 正確な解を求める際のQARAの確率は, QAOAと再帰QAOAのどちらよりも約60倍高く, その効率性を強調した。

関連論文リスト

• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  我々はQCBOの制約を満たす量子状態の同値重ね合わせを生成する変動的アプローチを開発する。 結果として生じる同値な重ね合わせは、QUBO/QCBOを解く量子アルゴリズムの初期状態として使用できる。
  論文  参考訳（メタデータ） (2025-08-04T16:44:53Z)
• Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
  本稿では,VarQITEが従来の手法に比べて平均最適性ギャップを著しく小さくすることを示す。 ハミルトニアンのスケーリングにより、最適化コストをさらに削減し、収束を加速できることを実証する。
  論文  参考訳（メタデータ） (2025-04-17T03:09:37Z)
• Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach [36.05085942729295]
  本稿では、古典的なNPG推定器で使用されるランダムサンプリングを決定論的勾配推定手法で置き換える量子自然ポリシー勾配(QNPG)アルゴリズムを提案する。 提案したQNPGアルゴリズムは、量子オラクルへのクエリに対する$tildemathcalO(epsilon-1.5)$のサンプル複雑性を達成し、マルコフ決定プロセス(MDP)へのクエリに対する$tildemathcalO(epsilon-2)$の古典的な下界を大幅に改善する。
  論文  参考訳（メタデータ） (2025-01-27T17:38:30Z)
• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。 そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。 我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
  論文  参考訳（メタデータ） (2024-03-22T18:00:03Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Efficient Classical Computation of Quantum Mean Values for Shallow QAOA Circuits [15.279642278652654]
  浅いQAOA回路の量子ビット数と線形にスケールするグラフ分解に基づく古典的アルゴリズムを提案する。 我々の結果は、QAOAによる量子アドバンテージの探索だけでなく、NISQプロセッサのベンチマークにも有用である。
  論文  参考訳（メタデータ） (2021-12-21T12:41:31Z)
• Quantum Error Mitigation Relying on Permutation Filtering [84.66087478797475]
  本稿では,既存の置換に基づく手法を特殊なケースとして含む,置換フィルタ(permutation filters)と呼ばれる一般的なフレームワークを提案する。 提案するフィルタ設計アルゴリズムは, 常に大域的最適度に収束し, フィルタが既存の置換法よりも大幅に改善できることを示す。
  論文  参考訳（メタデータ） (2021-07-03T16:07:30Z)
• 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)
• Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
  入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。 我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。 我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
  論文  参考訳（メタデータ） (2020-12-03T07:12:08Z)

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

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