論文の概要: Highly Efficient Encoding for Job-Shop Scheduling Problems and its Application on Quantum Computers

• arxiv url: http://arxiv.org/abs/2401.16381v1
• Date: Mon, 29 Jan 2024 18:21:49 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-30 13:42:11.399465
• Title: Highly Efficient Encoding for Job-Shop Scheduling Problems and its Application on Quantum Computers
• Title（参考訳）: ジョブショップスケジューリング問題に対する高効率符号化と量子コンピュータへの応用
• Authors: Mathias Schmid, Sarah Braun, Rudolf Sollacher, Michael J. Hartmann
• Abstract要約: ジョブショップスケジューリング問題は、一連のジョブをマシン上で実行するための最適なスケジュールを見つけることを目的としている。 ジョブショップスケジューリング問題の効率的なエンコーディングを導入し、可能なすべてのスケジュールをカウントするためには、ビットストリングをはるかに少なくする必要がある。 提案手法を導入することで,従来検討されていた戦略よりも量子アルゴリズムの性能が大幅に向上することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial optimization problems are considered to be an application, where quantum computing can have transformative impact. In the industrial context, job shop scheduling problems that aim at finding the optimal schedule for a set of jobs to be run on a set of machines are of immense interest. Here we introduce an efficient encoding of job shop scheduling problems, which requires much fewer bit-strings for counting all possible schedules than previously employed encodings. For problems consisting of $N$ jobs with $N$ operations, the number of required bit-strings is at least reduced by a factor $N / \log_2(N)$ as compared to time indexed encodings. This is particularly beneficial for solving job shop scheduling problems on quantum computers, since much fewer qubits are needed to represent the problem. Our approach applies to the large class of flexible and usual job-shop scheduling problems, where operations can possibly be executed on multiple machines. Using variational quantum algorithms, we show that the encoding we introduce leads to significantly better performance of quantum algorithms than previously considered strategies. Importantly, the encoding we develop also enables significantly more compact classical representations and will therefore be highly useful even beyond applicability on quantum hardware.
• Abstract（参考訳）: 組合せ最適化問題は、量子コンピューティングが変換的影響を持つアプリケーションであると考えられている。 産業的な文脈では、一連のマシン上で実行される一連のジョブの最適なスケジュールを見つけることを目的としたジョブショップスケジューリングの問題は非常に興味深い。 ここでは,従来採用されていたジョブショップスケジューリング問題を効率的に符号化する手法を提案する。 $N$ジョブと$N$演算からなる問題に対して、必要なビットストリングの数は、時間インデックスエンコーディングと比較して少なくとも$N / \log_2(N)$で減少する。 これは量子コンピュータのジョブショップスケジューリング問題を解決するのに特に有用である。 我々のアプローチは、複数のマシンで操作を実行できる、フレキシブルで通常のジョブショップスケジューリング問題に適用される。 本稿では, 変分量子アルゴリズムを用いて, 従来検討されていた戦略よりも, 量子アルゴリズムの性能が著しく向上することを示す。 重要な点として、私たちが開発している符号化は、さらにコンパクトな古典表現を可能にし、量子ハードウェアへの適用性を超えても非常に有用である。

関連論文リスト

• Digitized Counterdiabatic Quantum Algorithms for Logistics Scheduling [33.04597339860113]
  本稿では,2つのスケジューリング問題に対して,ディジタル化された反断熱量子最適化(DCQO)アルゴリズムを提案する。 ジョブショップスケジューリング問題では,特定の制約下で複数のタスクを実行するロボットの最適なスケジュールを見つけることを目的としている。 旅行セールスパーソンの問題は、すべての都市をカバーし、最短の旅行距離と関連する経路を見つけることである。
  論文  参考訳（メタデータ） (2024-05-24T16:53:30Z)
• Efficient Encodings of the Travelling Salesperson Problem for Variational Quantum Algorithms [0.0]
  本研究では,トラベリングセールスマン問題に対する様々なエンコーディングについて検討する。 置換符号化は、実現可能性の問題に悩まされないため、良好な結果が得られるという証拠が得られます。
  論文  参考訳（メタデータ） (2024-04-08T12:30:07Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。 そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
  論文  参考訳（メタデータ） (2023-06-14T13:44:35Z)
• Solving various NP-Hard problems using exponentially fewer qubits on a Quantum Computer [0.0]
  NPハード問題は、一般時間アルゴリズムで正確に解けるとは考えられていない。 本稿では,問題のサイズに応じて対数的にスケールする独自手法を構築した。 これらのアルゴリズムは、100以上のノードのグラフサイズを持つ量子シミュレータと、256のグラフサイズまでの実際の量子コンピュータでテストされる。
  論文  参考訳（メタデータ） (2023-01-17T16:03:33Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCSは、量子古典ハイブリッドシステムにおけるインデックス検索とカウントを目的としている。 我々はQiskitでIQuCSを実装し、集中的な実験を行う。 その結果、量子ビットの消費を最大66.2%削減できることが示されている。
  論文  参考訳（メタデータ） (2022-09-22T21:54:28Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  本稿では,グラフニューラルネットワーク(GNN)と組み合わせた強化学習(RL)手法を提案する。 この問題は、巨大な検索スペース、重い尾の報酬分布、そして困難なクレジット割り当てのために非常に難しい。 GNNを基本方針として利用するRLエージェントが,これらの課題にどのように対処できるかを示す。
  論文  参考訳（メタデータ） (2022-04-18T21:45:13Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。 我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
  論文  参考訳（メタデータ） (2022-02-10T18:59:52Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• On connectivity-dependent resource requirements for digital quantum simulation of $d$-level particles [0.703901004178046]
  一般に使われている量子演算子をトロッタライズするのに必要なSWAPゲートの数について検討する。 結果は、ハードウェアの共同設計や、与えられた短期量子ハードウェアの集合に対する効率的なキューディット符号化の選択に適用できる。
  論文  参考訳（メタデータ） (2020-05-26T22:28:51Z)

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

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