論文の概要: 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はより効果的であると結論付けることができる。
関連論文リスト
- 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) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - 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) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。