論文の概要: 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}$パラメータが必要である。

関連論文リスト

• 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)
• Imposing Constraints on Driver Hamiltonians and Mixing Operators: From Theory to Practical Implementation [0.0]
  制約部分集合を満たすハミルトン項を見つけるための一般表現を与え、これらを用いて関連する問題の複雑さを特徴づける。 次に、これらのプリミティブをハミルトンドライバとユニタリミキサーに変換して、制約付き量子アニール演算子Ansatz (CQA) と量子交換演算子Ansatz (QAOA) に使用できるアルゴリズム的な手順を与える。 実験により,12～22のインスタンスに対してこれらのアプローチを実証的にベンチマークし,最適相対性能を示すとともに,指数曲線が2次速度アップと一致することを示す。
  論文  参考訳（メタデータ） (2024-07-02T06:23:02Z)
• Equivariant QAOA and the Duel of the Mixers [1.1985053703926616]
  本稿ではQAOA調整ミキサーHamiltonianを構築するための体系的方法論を提案する。 このアプローチの鍵となるのは、ヒルベルト空間の根底にあるQAOA上の対称性群の作用と通勤する作用素を特定することである。
  論文  参考訳（メタデータ） (2024-05-12T08:22:41Z)
• Graph-controlled Permutation Mixers in QAOA for the Flexible Job-Shop Problem [0.0]
  Quantum Alternating Operator Ansatzは制約付き最適化ソリューションのためのアルゴリズムフレームワークを提供する。 既知の標準QAOAプロトコルとは対照的に、最適化問題の制約はアンザッツ回路の混合層に組み込まれている。 フレキシブルなジョブショップ問題を含む幅広いスケジューリング問題に対する混合演算子を開発した。
  論文  参考訳（メタデータ） (2023-11-07T16:16:52Z)
• 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)
• 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)
• 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)

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

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