論文の概要: Grover Adaptive Search for the Higher-Order Formulation of Quadratic Assignment Problems

• arxiv url: http://arxiv.org/abs/2410.12181v2
• Date: Thu, 09 Oct 2025 10:38:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-10 15:34:28.297729
• Title: Grover Adaptive Search for the Higher-Order Formulation of Quadratic Assignment Problems
• Title（参考訳）: 二次割当問題の高次定式化のためのグロバー適応探索
• Authors: Taku Mikuriya, Shintaro Fujiwara, Kein Yukiyoshi, Giuseppe Thadeu Freitas de Abreu, Naoki Ishikawa,
• Abstract要約: 我々は、置換準備演算子(PPO)を用いたグロバー適応探索(GAS)を用いて二次代入問題の探索空間を縮小できることを実証した。 まず,従来の2次非拘束バイナリ最適化(QUBO)を高次非拘束バイナリ最適化(HUBO)に変換する。 量子ビット数, 量子ゲート数, 回路深さ, クエリの複雑さの代数的解析を行い, 提案手法が探索空間を著しく減少させることを示す。
• 参考スコア（独自算出の注目度）: 9.018512859020992
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We demonstrate that the search space of the quadratic assignment problem (QAP), known as an NP-hard combinatorial optimization problem, can be reduced using Grover adaptive search (GAS) with permutation preparation operator (PPO). To that end, we first revise the traditional quadratic unconstrained binary optimization (QUBO) formulation of the QAP into a higher-order unconstrained binary optimization (HUBO) formulation, introducing a binary encoding method. Algebraic analyses in terms of the number of qubits, quantum gates, circuit depth, and query complexity are performed, which indicate that our proposed approach significantly reduces the search space size, improving convergence performance to the optimal solution compared to the conventional one. Furthermore, although the PPO for HUBO has a greater circuit depth than the PPO for QUBO, when the analysis is extended to the entire state preparation operator, both HUBO and QUBO exhibit comparable depths. Therefore, owing to its smaller number of variables, HUBO can be concluded to be more effective.
• Abstract（参考訳）: NPハード組合せ最適化問題(NP-hard combinatorial optimization problem)として知られる2次代入問題(QAP)の探索空間は、置換準備演算子(PPO)を用いたGrover Adaptive Search(GAS)を用いて削減可能であることを示す。 そこで我々はまず,従来の2次非制約バイナリ最適化(QUBO)の定式化を高階非制約バイナリ最適化(HUBO)の定式化に修正し,バイナリ符号化手法を導入した。 量子ビット数, 量子ゲート数, 回路深度, クエリの複雑度の観点から代数的解析を行い, 提案手法は探索空間のサイズを大幅に削減し, 従来の手法に比べて収束性能を向上することを示す。 さらに、HUBO用PPOは、QUBO用PPOよりも回路深度が大きいが、解析が状態準備演算子全体に拡張されると、HUBOとQUBOの両者は同等の深さを示す。 したがって、変数の数が少ないため、HUBOはより効果的であると結論付けることができる。

関連論文リスト

• Encoding Matters: Benchmarking Binary and D-ary Representations for Quantum Combinatorial Optimization [1.3824488054100907]
  本研究では,D-ary Optimization (QUDO) を,高次元ヒルベルト空間において決定変数を直接符号化する代替の定式化として検討する。 本研究では,QUDOがトラベリングセールスマン問題,グラフカラー化,ジョブスケジューリング,Max-K-Cutなど,広範なペナルティ構築を必要とせずに,様々な問題クラスにおいて構造的制約を自然に捉えていることを示す。 本研究は、量子最適化のためのスケーラブルで表現力のある表現としてQUDOを強調し、近似比を一貫して改善し、等価回路深さでの計算オーバーヘッドを大幅に削減することを示した。
  論文  参考訳（メタデータ） (2026-02-07T04:37:32Z)
• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  チュートリアルは変分量子回路とQUBO問題の概要から始まる。 次に、ハミルトンの定式化、ゲート分解、サンプル応用など、QAOAの詳細を探索する。 このチュートリアルはこれらの概念を高階ハミルトニアンに拡張し、関連する対称性と回路構成について議論する。
  論文  参考訳（メタデータ） (2025-11-23T09:54:20Z)
• Adam assisted Fully informed Particle Swarm Optimization ( Adam-FIPSO ) based Parameter Prediction for the Quantum Approximate Optimization Algorithm (QAOA) [1.024113475677323]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、マックス・カット問題などの最適化問題の解法として用いられる顕著な変分アルゴリズムである。 QAOAの重要な課題は、高品質なソリューションにつながる適切なパラメータを効率的に特定することである。
  論文  参考訳（メタデータ） (2025-06-07T13:14:41Z)
• Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
  本稿では,VarQITEが従来の手法に比べて平均最適性ギャップを著しく小さくすることを示す。 ハミルトニアンのスケーリングにより、最適化コストをさらに削減し、収束を加速できることを実証する。
  論文  参考訳（メタデータ） (2025-04-17T03:09:37Z)
• Grover Adaptive Search with Spin Variables [3.190355298836875]
  このスピンベースアルゴリズムのために設計された新しい量子辞書サブルーチンを導入する。 このアプローチの重要な利点は、量子回路を構成するのに必要なCNOTゲートの数を大幅に削減することである。
  論文  参考訳（メタデータ） (2024-10-15T14:24:27Z)
• Quantum Speedup of the Dispersion and Codebook Design Problems [6.735173690339397]
  分散問題はNPハードに分類される最適化問題である。 本稿では,Grover Adaptive Search(GAS)量子アルゴリズムによる解を実現するために,最大値と最大値の分散問題の新しい定式化を提案する。
  論文  参考訳（メタデータ） (2024-06-11T12:00:50Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• 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)
• Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations [2.9564164925541503]
  グロバー適応探索(Grover Adaptive Search、GAS)は、二項最適化問題の解法として設計された量子抜粋探索アルゴリズムである。 キュービット数と必要ゲート数を同時に削減できる高階二項式を提案する。
  論文  参考訳（メタデータ） (2023-08-03T07:20:24Z)
• DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean Optimization [10.513103815142731]
  PBO(Pseudo-Boolean Optimization)の解法における局所探索アルゴリズムの改良法について検討する。 我々のアルゴリズムであるDeciLS-PBOは最先端のアルゴリズムと比較して有望な性能を持つ。
  論文  参考訳（メタデータ） (2023-01-28T17:03:56Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
  統計的決定論の研究からシャノンエントロピーの一般化を考える。 まず,このエントロピーの特殊なケースがBO手順でよく用いられる獲得関数に繋がることを示す。 次に、損失に対する選択肢の選択が、どのようにして柔軟な獲得関数の族をもたらすかを示す。
  論文  参考訳（メタデータ） (2022-10-04T04:43:58Z)
• Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem [2.840363325289377]
  NPハード無線チャネル割り当て問題を高階非制約バイナリ最適化(HUBO)として定式化する方法を提案する。 我々は、チャネルインデックスの昇降二進符号化を考案し、特定の量子回路を構築し、Grover Adaptive Search(GAS)に必要なキュービットとゲートの正確な数を導出する。 解析により,提案するHUBOの定式化により,従来の2次定式化と比較して,キュービット数やクエリの複雑さが著しく減少することが明らかとなった。
  論文  参考訳（メタデータ） (2022-08-10T06:59:43Z)
• 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)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。 我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
  論文  参考訳（メタデータ） (2021-08-18T09:26:17Z)
• 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)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。 また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。 我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。 すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
  論文  参考訳（メタデータ） (2020-10-01T18:14:11Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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