論文の概要: State-space reduction techniques exploiting specific constraints for quantum search Application to a specific job scheduling problem

• arxiv url: http://arxiv.org/abs/2501.07174v1
• Date: Mon, 13 Jan 2025 10:06:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-14 14:22:07.373483
• Title: State-space reduction techniques exploiting specific constraints for quantum search Application to a specific job scheduling problem
• Title（参考訳）: 量子探索のための特定の制約を利用した状態空間削減手法 : 特定のジョブスケジューリング問題への応用
• Authors: Rodolphe Griset, Ioannis Lavdas, Jiri Guth Jarkovsky,
• Abstract要約: 最先端の量子探索アルゴリズムは、高密度に到達するまでこれらの元素の密度を単調に増加させることで、分布内の特定の元素の探索を可能にする。 本研究は、スケジューリング問題の特定の制約を利用して、問題サイズの関数としてほぼ2次的に増加する状態の初期重ね合わせを構築することを提案する。 量子エミュレータに関する数値的な結果は、状態空間削減アプローチの可能性を強調し、より小さく、より関連性の高い解空間に焦点をあてることで、より効率的な量子探索プロセスをもたらす可能性がある。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Quantum search has emerged as one of the most promising fields in quantum computing. State-of-the-art quantum search algorithms enable the search for specific elements in a distribution by monotonically increasing the density of these elements until reaching a high density. This kind of algorithms demonstrate a theoretical quadratic speed-up on the number of queries compared to classical search algorithms in unstructured spaces. Unfortunately, the major part of the existing literature applies quantum search to problems which size grows exponnentialy with the input size without exploiting any specific problem structure, rendering this kind of approach not exploitable in real industrial problems. In contrast, this work proposes exploiting specific constraints of scheduling problems to build an initial superposition of states with size almost quadraticaly increasing as a function of the problem size. This state space reduction, inspired by the quantum walk algorithm, constructs a state superposition corresponding to all paths in a state-graph embedding spacing constraints between jobs. Our numerical results on quantum emulators highlights the potential of state space reduction approach, which could lead to more efficient quantum search processes by focusing on a smaller, more relevant, solution space.
• Abstract（参考訳）: 量子検索は、量子コンピューティングの最も有望な分野の1つとして登場した。 最先端の量子探索アルゴリズムは、高密度に到達するまでこれらの元素の密度を単調に増加させることで、分布内の特定の元素の探索を可能にする。 この種のアルゴリズムは、非構造空間における古典的な探索アルゴリズムと比較して、クエリ数に関する理論的2次的なスピードアップを示す。 残念なことに、既存の文献の大部分は、特定の問題構造を使わずに、入力サイズに比例して大きさが増大する問題に量子探索を適用しており、このようなアプローチは実際の産業問題では利用できない。 対照的に、本研究では、スケジューリング問題の特定の制約を利用して、問題サイズの関数としてほぼ2次的に増加する状態の初期重ね合わせを構築することを提案する。 この状態空間削減は、量子ウォークアルゴリズムにインスパイアされ、ジョブ間の間隔の制約を埋め込んだ状態グラフにおいて、すべてのパスに対応する状態重ね合わせを構築する。 量子エミュレータに関する数値的な結果は、状態空間削減アプローチの可能性を強調し、より小さく、より関連性の高い解空間に焦点をあてることで、より効率的な量子探索プロセスをもたらす可能性がある。

関連論文リスト

• Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
  現在利用可能な量子デバイスは、限られた量子ビットと高いレベルのノイズしか持たず、それらのデバイスで正確に解決できる問題のサイズを制限している。 我々は、変分量子アルゴリズム -- 離散化量子排他探索 -- を改善する新しい方法を提案する。
  論文  参考訳（メタデータ） (2024-07-24T22:06:05Z)
• Quantum Computing and Tensor Networks for Laminate Design: A Novel Approach to Stacking Sequence Retrieval [1.6421520075844793]
  主な例として、積層複合材料の重量最適化がある。 量子計算の急速に発展する分野は、これらの複雑な問題に対処するための新しいアプローチを提供するかもしれない。
  論文  参考訳（メタデータ） (2024-02-09T15:01:56Z)
• Optimized General Uniform Quantum State Preparation [0.0]
  我々は,任意のN状態の均一な重ね合わせを調製し,奥行きを最小化し,アシラリー量子ビットを使わずに最適化された回路の一般解法を開発した。 このアルゴリズムは、特に2つのワイヤゲートの使用において効率的であり、IonQ量子コンピュータ上で検証され、量子非構造探索アルゴリズムに応用されていることを示す。
  論文  参考訳（メタデータ） (2023-11-30T22:40:33Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  期待されている量子コンピュータの応用は、科学と産業にまたがる。 本稿では,量子アルゴリズムの応用分野について検討する。 私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
  論文  参考訳（メタデータ） (2023-10-04T17:53:55Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Quantum amplitude damping for solving homogeneous linear differential equations: A noninterferometric algorithm [0.0]
  本研究は,同種LDEを解くための効率的な量子アルゴリズムを構築するために,量子振幅減衰演算を資源として利用する新しい手法を提案する。 このようなオープンな量子系にインスパイアされた回路は、非干渉法で解の実際の指数項を構成することができることを示す。
  論文  参考訳（メタデータ） (2021-11-10T11:25:32Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。 本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
  論文  参考訳（メタデータ） (2021-06-11T09:43:09Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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