論文の概要: Free Job-Shop Scheduling With Hardcoded Constraints
- arxiv url: http://arxiv.org/abs/2211.05822v1
- Date: Thu, 10 Nov 2022 19:25:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-19 19:06:14.298387
- Title: Free Job-Shop Scheduling With Hardcoded Constraints
- Title(参考訳): ハードコード制約付き自由ジョブショップスケジューリング
- Authors: Gereon Ko{\ss}mann and Lennart Binkowski and Ren\'e Schwonnek
- Abstract要約: 同様に構築されたミキサーの所望の特性は、純粋に古典的な対象に直接リンク可能であることを示す。
より自然にグループ構造を組み込む新しい変分量子アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Hardcoding constrained optimization problems into a variational quantum
algorithm often turns out to be a challenging task. In this work we provide a
solution for the class of free job-shop problems (FJSP), which we achieve by
rigorously employing the symmetries of the classical problem. An established
approach for hardcoding the constraints of the closely related traveling
salesman problem (TSP) into mixer Hamiltonians was recently given by Hadfield
et al.'s Quantum Alternating Operator Ansatz (QAOA). For FJSP, which contains
TSP as a subclass, we show that desired properties of similarly constructed
mixers can be directly linked to a purely classical object: the group of
feasibility-preserving bit value permutations. We also outline a generic way to
construct QAOA-like-mixers for these problems. We further propose a new
variational quantum algorithm that incorporates the underlying group structure
more naturally, and provide a concrete numerical example. Unlike the QAOA, our
algorithm allows bounding the amount of parameters necessary to reach every
feasible solution from above: If $J$ jobs are to be distributed, we need at
most $J {(J - 1)}^{2} / {2}$ parameters.
- Abstract(参考訳): 制約付き最適化問題を変分量子アルゴリズムにハードコーディングすることは、しばしば難しい課題である。
本研究では,古典問題の対称性を厳格に活用することにより達成される自由ジョブショップ問題(fjsp)のクラスに対する解法を提案する。
密接な関係を持つ旅行セールスマン問題(TSP)の制約をミキサーハミルトンにハードコーディングするための確立されたアプローチは、HadfieldらのQuantum Alternating Operator Ansatz (QAOA)によって最近与えられた。
サブクラスとして TSP を含む FJSP に対して、同様に構築されたミキサーの所望の特性は、純粋に古典的なオブジェクトに直接リンク可能であることを示す。
また、これらの問題に対してQAOAライクなミキサーを構築するための一般的な方法についても概説する。
さらに,基礎となる群構造をより自然に組み込む新しい変分量子アルゴリズムを提案し,具体的な数値例を示す。
我々のアルゴリズムはQAOAと異なり、上記の全ての実現可能なソリューションに到達するのに必要なパラメータの量を制限している:$J$ジョブが分散されている場合、少なくとも$J {(J - 1)}^{2} / {2}$パラメータが必要である。
関連論文リスト
- Graph-controlled Permutation Mixers in QAOA for the Flexible Job-Shop
Problem [0.0]
Quantum Alternating Operator Ansatzは制約付き最適化ソリューションのためのアルゴリズムフレームワークを提供する。
既知の標準QAOAプロトコルとは対照的に、最適化問題の制約はアンザッツ回路の混合層に組み込まれている。
フレキシブルなジョブショップ問題を含む幅広いスケジューリング問題に対する混合演算子を開発した。
論文 参考訳(メタデータ) (2023-11-07T16:16:52Z) - Efficient application of the factorized form of the unitary
coupled-cluster ansatz for the variational quantum eigensolver algorithm by
using linear combination of unitaries [0.0]
変分量子固有解法は、短期量子コンピュータにとって最も有望なアルゴリズムの1つである。
強い相関電子を含む量子化学問題を解くことができる。
論文 参考訳(メタデータ) (2023-02-17T04:03:06Z) - Variational Amplitude Amplification for Solving QUBO Problems [0.0]
本研究は、キュービット重畳状態に適したQUBO問題に焦点をあてる。
我々は、QUBOをコストオラクルの演算として符号化する回路設計を、標準Grover拡散演算子$U_textrms$と組み合わせると、最適および近似最適解に対応する状態の測定確率が高くなることを示す。
論文 参考訳(メタデータ) (2023-01-31T14:33:40Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Unbalanced penalization: A new approach to encode inequality constraints
of combinatorial problems for quantum optimization algorithms [58.720142291102135]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳(メタデータ) (2022-11-25T06:05:18Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳(メタデータ) (2022-11-16T18:59:54Z) - Quantum-classical tradeoffs and multi-controlled quantum gate
decompositions in variational algorithms [0.5109395231379227]
短期量子コンピュータの計算能力は、ゲート演算のノイズの多い実行と物理量子ビットの限られた数によって制限される。
ハイブリッド変分アルゴリズムは、問題の解決に使用される量子資源と古典的リソースの間の幅広いトレードオフを可能にするため、短期量子デバイスに適している。
論文 参考訳(メタデータ) (2022-10-10T00:25:18Z) - 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) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳(メタデータ) (2022-03-11T17:19:26Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳(メタデータ) (2022-03-01T19:47:16Z) - Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State
Preparation [0.0]
本稿では,Grover 様選択位相シフト混合演算子を用いた量子交互演算子 Ansatz (QAOA) の変種を提案する。
GM-QAOA は任意のNP最適化問題に取り組み、全ての実現可能な解の同値な重ね合わせを効率的に作成することができる。
論文 参考訳(メタデータ) (2020-05-30T20:24:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。