論文の概要: Quantum Speedup for the Quadratic Assignment Problem

• arxiv url: http://arxiv.org/abs/2410.12181v1
• Date: Wed, 16 Oct 2024 03:00:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-17 13:41:58.167810
• Title: Quantum Speedup for the Quadratic Assignment Problem
• Title（参考訳）: 二次割当問題に対する量子スピードアップ
• Authors: Taku Mikuriya, Kein Yukiyoshi, Shintaro Fujiwara, Giuseppe Thadeu Freitas de Abreu, Naoki Ishikawa,
• Abstract要約: そこで我々は,Dicke状態演算子を用いたGrover Adaptive Search (GAS)を用いて,二次代入問題の探索空間を小さくすることができることを示す。 また、GASの位相ゲートをZ軸の回転ゲートに置き換えることで、ペナルティを伴わずに量子回路を簡素化できることを示す。
• 参考スコア（独自算出の注目度）: 6.106029308649016
• License:
• 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 Dicke state operators. To that end, we first revise the traditional quadratic formulation of the QAP into a higher-order formulation, introducing a binary encoding method ordered by a descending Hamming weight, such that the number of terms in the objective function is reduced. We also show that the phase gate in the GAS can be replaced by a rotation gate about the Z axis, simplifying the quantum circuit without any penalty. Algebraic analyses in terms of the number of qubits, quantum gates, 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. Interestingly, it is suggested that the higher-order formulation is effective for problems whose size are powers of two, while the quadratic formulation is more effective for other sizes, indicating that switching between the two formulations can enhance the feasibility of the GAS-solved QAP.
• Abstract（参考訳）: NPハード組合せ最適化問題(NP-hard combinatorial optimization problem)として知られる2次代入問題(QAP)の探索空間は、Dicke状態演算子を用いたGrover Adaptive Search(GAS)を用いて削減可能であることを示す。 そこで我々はまず,QAPの従来の二次的定式化を高階の定式化に改定し,下降ハミング重みによって順序付けられた二進符号化法を導入し,目的関数の項数が減少するようにした。 また、GASの位相ゲートをZ軸の回転ゲートに置き換えることで、ペナルティのない量子回路を簡素化できることを示す。 量子ビット数, 量子ゲート数, クエリ複雑度の観点から代数的解析を行い, 提案手法は探索空間を著しく削減し, 従来の手法に比べて収束性能を向上することを示す。 興味深いことに、高次定式化は2の力を持つ問題に対して有効であり、2次定式化は他の大きさに対してより効果的であり、2つの定式化の切り替えがGAS解決QAPの実現可能性を高めることを示唆している。

関連論文リスト

• 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)
• 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)

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

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