論文の概要: Recursive Quantum Relaxation for Combinatorial Optimization Problems

• arxiv url: http://arxiv.org/abs/2403.02045v3
• Date: Thu, 09 Jan 2025 23:25:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-13 15:24:45.993305
• Title: Recursive Quantum Relaxation for Combinatorial Optimization Problems
• Title（参考訳）: 組合せ最適化問題に対する再帰的量子緩和
• Authors: Ruho Kondo, Yuki Sato, Rudy Raymond, Naoki Yamamoto,
• Abstract要約: 本稿では,既存の量子最適化手法を解法に統一して二項解を求める方法を示す。 MAX-CUT問題における数百ノードの標準ベンチマークグラフの実験は、完全に古典的な方法で行われた。
• 参考スコア（独自算出の注目度）: 3.3053321430025258
• License:
• Abstract: Quantum optimization methods use a continuous degree-of-freedom of quantum states to heuristically solve combinatorial problems, such as the MAX-CUT problem, which can be attributed to various NP-hard combinatorial problems. This paper shows that some existing quantum optimization methods can be unified into a solver to find the binary solution which is most likely measured from the optimal quantum state. Combining this finding with the concept of quantum random access codes (QRACs) for encoding bits into quantum states on fewer qubits, we propose an efficient recursive quantum relaxation method called recursive quantum random access optimization (RQRAO) for MAX-CUT. Experiments on standard benchmark graphs with several hundred nodes in the MAX-CUT problem, conducted in a fully classical manner using a tensor network technique, show that RQRAO not only outperforms the Goemans-Williamson and recursive QAOA methods, but also is comparable to state-of-the-art classical solvers. The code is available at \url{https://github.com/ToyotaCRDL/rqrao}.
• Abstract（参考訳）: 量子最適化法は、量子状態の自由度を連続的に使い、MAX-CUT問題などの組合せ問題をヒューリスティックに解く。 本稿では,既存の量子最適化手法を解法に統一して,最適量子状態から最も高い確率で測定される二項解を求めることができることを示す。 この発見と、より少ない量子ビット上の量子状態にビットを符号化する量子ランダムアクセス符号(QRAC)の概念を組み合わせることで、MAX-CUTのための再帰的量子ランダムアクセス最適化(RQRAO)と呼ばれる効率的な再帰的量子緩和法を提案する。 テンソルネットワーク技術を用いたMAX-CUT問題における数百ノードの標準ベンチマークグラフの実験は、RQRAOがゴーマン・ウィリアムソン法や再帰的QAOA法よりも優れているだけでなく、最先端の古典的解法に匹敵することを示した。 コードは \url{https://github.com/ToyotaCRDL/rqrao} で公開されている。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• A quantum annealing approach to the minimum distance problem of quantum codes [0.0]
  本稿では,量子安定化器符号の最小距離を準拘束的二項最適化問題として再定式化することで計算する手法を提案する。 D-Wave Advantage 4.1quantum annealerと比較することにより,本手法の実用性を示す。
  論文  参考訳（メタデータ） (2024-04-26T21:29:42Z)
• Solving non-native combinatorial optimization problems using hybrid quantum-classical algorithms [0.0]
  組合せ最適化は、物流から金融まで幅広い分野に適用可能な、困難な問題である。 量子コンピューティングは、様々なアルゴリズムを用いてこれらの問題を解決するために使われてきた。 この研究は、量子と古典のリソースをハイブリッドなアプローチで統合することで、これらの課題を克服する枠組みを提示している。
  論文  参考訳（メタデータ） (2024-03-05T17:46:04Z)
• A Universal Quantum Algorithm for Weighted Maximum Cut and Ising Problems [0.0]
  本稿では,二項問題の近似解を計算するためのハイブリッド量子古典アルゴリズムを提案する。 我々は、重み付き最大カットまたはイジング・ハミルトン演算子をブロック符号化するユニタリおよびエルミート演算子を実装するために浅深さ量子回路を用いる。 この作用素の変動量子状態への期待を測定すると、量子系の変動エネルギーが得られる。
  論文  参考訳（メタデータ） (2023-06-10T23:28:13Z)
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization [0.0]
  本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。 目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
  論文  参考訳（メタデータ） (2023-05-23T16:17:57Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Efficiently Solve the Max-cut Problem via a Quantum Qubit Rotation Algorithm [7.581898299650999]
  我々はQQRA(Quantum Qubit Rotation Algorithm)という単純なアルゴリズムを導入する。 最大カット問題の近似解は 1 に近い確率で得られる。 我々は、よく知られた量子近似最適化アルゴリズムと古典的なゲーマン・ウィリアムソンアルゴリズムと比較する。
  論文  参考訳（メタデータ） (2021-10-15T11:19:48Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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