論文の概要: Qubit-efficient quantum local search for combinatorial optimization

• arxiv url: http://arxiv.org/abs/2502.02245v1
• Date: Tue, 04 Feb 2025 11:44:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-05 14:58:27.857154
• Title: Qubit-efficient quantum local search for combinatorial optimization
• Title（参考訳）: 組合せ最適化のための量子効率量子局所探索
• Authors: M. Podobrii, V. Kuzmin, V. Voloshinov, M. Veshchezerova, M. R. Perelshtein,
• Abstract要約: 本稿では,lceil log l rceil$ qubitsのみを用いた局所探索の量子バージョンを実装した量子ビット効率変動量子アルゴリズムを提案する。 この成果は、短期量子デバイスにおける大規模最適化問題を解決するアルゴリズムの可能性を強調している。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: An essential component of many sophisticated metaheuristics for solving combinatorial optimization problems is some variation of a local search routine that iteratively searches for a better solution within a chosen set of immediate neighbors. The size $l$ of this set is limited due to the computational costs required to run the method on classical processing units. We present a qubit-efficient variational quantum algorithm that implements a quantum version of local search with only $\lceil \log_2 l \rceil$ qubits and, therefore, can potentially work with classically intractable neighborhood sizes when realized on near-term quantum computers. Increasing the amount of quantum resources employed in the algorithm allows for a larger neighborhood size, improving the quality of obtained solutions. This trade-off is crucial for present and near-term quantum devices characterized by a limited number of logical qubits. Numerically simulating our algorithm, we successfully solved the largest graph coloring instance that was tackled by a quantum method. This achievement highlights the algorithm's potential for solving large-scale combinatorial optimization problems on near-term quantum devices.
• Abstract（参考訳）: 組合せ最適化問題を解決するための多くの洗練されたメタヒューリスティクスの重要な要素は、選択した近傍の集合の中でより優れた解を反復的に探索する局所探索ルーチンのバリエーションである。 このセットの$l$は、古典的な処理ユニットでメソッドを実行するのに必要な計算コストのために制限されている。 本稿では,局所探索の量子バージョンを$\lceil \log_2 l \rceil$ qubitsで実装した量子ビット効率変動量子アルゴリズムを提案する。 アルゴリズムで使用される量子リソースの量を増やすことで、より大きな近傍サイズが実現され、得られるソリューションの品質が向上する。 このトレードオフは、論理量子ビットの限られた数で特徴づけられる、現在および短期量子デバイスにとって不可欠である。 このアルゴリズムを数値シミュレーションし,量子的手法により取り組んだ最大グラフカラー化の解法を成功させた。 この成果は、短期量子デバイス上での大規模な組合せ最適化問題を解決するアルゴリズムの可能性を強調している。

関連論文リスト

• Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice [0.0]
  変分量子アルゴリズム、特に変分量子固有解器の変種は最適化(CO)問題に対処するために提案されている。 ベンチマークとしてMax-Cutを用いてCO問題を解く上で,このスケーリング結果がどのような意味を持つのかを数値的に検討する。
  論文  参考訳（メタデータ） (2024-08-06T09:57:34Z)
• Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
  現在利用可能な量子デバイスは、限られた量子ビットと高いレベルのノイズしか持たず、それらのデバイスで正確に解決できる問題のサイズを制限している。 我々は、変分量子アルゴリズム -- 離散化量子排他探索 -- を改善する新しい方法を提案する。
  論文  参考訳（メタデータ） (2024-07-24T22:06:05Z)
• Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization [0.8121127831316319]
  本稿では,デバイス間通信コストを大幅に削減する量子回路の構築手法を提案する。 そこで本研究では,従来のQDCA手法の約3倍の大きさのトラクタブル回路を構築できることを示す。
  論文  参考訳（メタデータ） (2024-05-01T20:49:50Z)
• Solving non-native combinatorial optimization problems using hybrid quantum-classical algorithms [0.0]
  組合せ最適化は、物流から金融まで幅広い分野に適用可能な、困難な問題である。 量子コンピューティングは、様々なアルゴリズムを用いてこれらの問題を解決するために使われてきた。 この研究は、量子と古典のリソースをハイブリッドなアプローチで統合することで、これらの課題を克服する枠組みを提示している。
  論文  参考訳（メタデータ） (2024-03-05T17:46:04Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  期待されている量子コンピュータの応用は、科学と産業にまたがる。 本稿では,量子アルゴリズムの応用分野について検討する。 私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
  論文  参考訳（メタデータ） (2023-10-04T17:53:55Z)
• Near-Term Distributed Quantum Computation using Mean-Field Corrections and Auxiliary Qubits [77.04894470683776]
  本稿では,限られた情報伝達と保守的絡み合い生成を含む短期分散量子コンピューティングを提案する。 我々はこれらの概念に基づいて、変分量子アルゴリズムの断片化事前学習のための近似回路切断手法を作成する。
  論文  参考訳（メタデータ） (2023-09-11T18:00:00Z)
• Parallel circuit implementation of variational quantum algorithms [0.0]
  本稿では,変分量子アルゴリズム(VQA)の量子回路を分割し,並列トレーニングと実行を可能にする手法を提案する。 本稿では,この問題からの固有構造を同定可能な最適化問題に適用する。 我々は,本手法がより大きな問題に対処できるだけでなく,1つのスライスのみを用いてパラメータをトレーニングしながら,完全なVQAモデルを実行することもできることを示した。
  論文  参考訳（メタデータ） (2023-04-06T12:52:29Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。 我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
  論文  参考訳（メタデータ） (2021-08-18T09:26:17Z)
• 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)

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

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