論文の概要: A Hybrid Quantum-Classical Approach to the Electric Mobility Problem
- arxiv url: http://arxiv.org/abs/2310.02760v1
- Date: Wed, 4 Oct 2023 12:14:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-05 15:21:19.837644
- Title: A Hybrid Quantum-Classical Approach to the Electric Mobility Problem
- Title(参考訳): 電力移動問題に対するハイブリッド量子-古典的アプローチ
- Authors: Margarita Veshchezerova, Mikhail Somov, David Bertsche, Steffen
Limmer, Sebastian Schmitt, Michael Perelshtein, Ayush Joshi Tripathi
- Abstract要約: NP-hard Electric Vehicle Fleet Charging and Allocation Problemのためのハイブリッド量子古典ルーチンを提案する。
分解法の性能を古典的・量子的メタヒューリスティックスで評価する。
提案手法の主な利点は、多くの不等式制約のある現実的な問題に対して量子ベースの方法を可能にすることである。
- 参考スコア(独自算出の注目度): 0.8796261172196743
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We suggest a hybrid quantum-classical routine for the NP-hard Electric
Vehicle Fleet Charging and Allocation Problem. The original formulation is a
Mixed Integer Linear Program with continuous variables and inequality
constraints. To separate inequality constraints that are difficult for quantum
routines we use a decomposition in master and pricing problems: the former
targets the assignment of vehicles to reservations and the latter suggests
vehicle exploitation plans that respect the battery state-of-charge
constraints. The master problem is equivalent to the search for an optimal set
partition. In our hybrid scheme, the master problem is reformulated in a
quadratic unconstrained binary optimization problem which can be solved with
quantum annealing on the DWave Advantage system. On large instances, we
benchmark the performance of the decomposition technique with classical and
quantum-inspired metaheuristics: simulated annealing, tabu search, and vector
annealing by NEC. The numerical results with purely classical solvers are
comparable to the solutions from the traditional mixed integer linear
programming approaches in terms of solution quality while being faster. In
addition, it scales better to larger instances. The major advantage of the
proposed approach is that it enables quantum-based methods for this realistic
problem with many inequality constraints. We show this by initial studies on
DWave hardware where optimal solutions can be found for small instances.
- Abstract(参考訳): NP-hard Electric Vehicle Fleet Charging and Allocation Problemのためのハイブリッド量子古典ルーチンを提案する。
元の定式化は連続変数と不等式制約を持つ混合整数線形プログラムである。
量子ルーチンで難しい不等式制約を分離するために、我々はマスターと価格の問題の分解を使用する: 前者は予約への車両の割り当てを目標とし、後者はバッテリーの充電状態の制約を尊重する車両利用計画を提案する。
マスター問題は最適な集合分割の探索と等価である。
本手法では、DWaveアドバンテージシステム上での量子アニーリングで解くことができる2次非制約二元最適化問題において、マスター問題を再構成する。
NECによる模擬アニール,タブ探索,ベクトルアニールなど,古典的および量子的メタヒューリスティックスによる分解手法の性能評価を行った。
純粋に古典的な解法を用いた数値計算結果は、解品質の点で従来の混合整数線形計画法による解に匹敵する。
さらに、大きなインスタンスに対してスケール性も向上している。
提案手法の主な利点は、多くの不等式制約のある現実的な問題に対して量子ベースの方法を可能にすることである。
これをDWaveハードウェアの初期研究で示しており、小さなインスタンスに対して最適な解を見つけることができる。
関連論文リスト
- Quadratic versus Polynomial Unconstrained Binary Models for Quantum Optimization illustrated on Railway Timetabling [0.0]
本稿では,任意の問題をpolynomial Unconstrained Binary Optimization (PUBO)問題に再構成する汎用手法を提案する。
また、擬似非拘束バイナリ最適化(QUBO)問題への総合的な再構成も提供する。
この結果から,PUBOの改定がQUBOよりも優れていることが示唆された。
論文 参考訳(メタデータ) (2024-11-15T09:23:52Z) - Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection [3.6021182997326022]
量子計算カラーブルーを用いて解くのに適した二次非拘束バイナリ最適化(QUBO)問題を定式化する。
この定式化は、最大自己充足力とそれらの間を流れる最小限のパワーを持つコミュニティを見つけることを目的としている。
D-Waveのハイブリッド量子古典解法、古典解法、分枝結合解法などである。
論文 参考訳(メタデータ) (2024-07-09T11:44:58Z) - Quantum Relaxation for Solving Multiple Knapsack Problems [7.003282322403712]
組合せ問題はビジネスにおいて共通の課題であり、特定の制約の下で最適なソリューションを見つける必要がある。
本研究では,制約付き最適化問題に対するハイブリッド量子古典法について検討する。
提案手法は、可換写像によって定義される局所量子ハミルトニアンの緩和に依存する。
論文 参考訳(メタデータ) (2024-04-30T11:40:07Z) - Hybrid Quantum-Classical Multilevel Approach for Maximum Cuts on Graphs [1.7720089167719628]
我々は、Max-Cutの大規模インスタンスを解決するために、スケーラブルなハイブリッドマルチレベルアプローチを導入する。
フレームワークでのQAOAの使用は、古典的なアプローチに匹敵するものであることを示す。
論文 参考訳(メタデータ) (2023-09-15T23:54:46Z) - NISQ-compatible approximate quantum algorithm for unconstrained and
constrained discrete optimization [0.0]
本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。
目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
論文 参考訳(メタデータ) (2023-05-23T16:17:57Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳(メタデータ) (2022-11-16T18:59:54Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳(メタデータ) (2022-05-24T03:49:10Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - Quantum-optimal-control-inspired ansatz for variational quantum
algorithms [105.54048699217668]
変分量子アルゴリズム (VQA) の中心成分は状態準備回路(英語版)であり、アンザッツ(英語版)または変分形式(英語版)とも呼ばれる。
ここでは、対称性を破るユニタリを組み込んだ「解」を導入することで、このアプローチが必ずしも有利であるとは限らないことを示す。
この研究は、より一般的な対称性を破るアンスの開発に向けた第一歩となり、物理学や化学問題への応用に繋がる。
論文 参考訳(メタデータ) (2020-08-03T18:00:05Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳(メタデータ) (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。