論文の概要: Integer Programming Using A Single Atom

• arxiv url: http://arxiv.org/abs/2402.16541v1
• Date: Mon, 26 Feb 2024 12:59:20 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-27 13:36:05.638394
• Title: Integer Programming Using A Single Atom
• Title（参考訳）: 単一原子を用いた整数プログラミング
• Authors: Kapil Goswami, Peter Schmelcher, Rick Mukherjee
• Abstract要約: 我々は,IP問題を元の形で任意の量子システムにマップし,解くアルゴリズムを開発した。 最適解は、最大8変数と最大4つの制約を持ついくつかのプロトタイプIP問題に対して、2-40mus以内で見つかる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Integer programming (IP), as the name suggests is an integer-variable-based approach commonly used to formulate real-world optimization problems with constraints. Currently, quantum algorithms reformulate the IP into an unconstrained form through the use of binary variables, which is an indirect and resource-consuming way of solving it. We develop an algorithm that maps and solves an IP problem in its original form to any quantum system that possesses a large number of accessible internal degrees of freedom which can be controlled with sufficient accuracy. Using a single Rydberg atom as an example, we associate the integer values to electronic states belonging to different manifolds and implement a selective superposition of these different states to solve the full IP problem. The optimal solution is found within 2-40{\mu}s for a few prototypical IP problems with up to eight variables and up to four constraints including a non-linear IP problem, which is usually harder to solve with classical algorithms when compared with linear IP problems. Our algorithm for solving IP is benchmarked using the Branch & Bound approach and it outperforms the classical algorithm in terms of the number of steps needed to converge and carries the potential to improve the bounds provided by the classical algorithm for larger problems.
• Abstract（参考訳）: 整数型プログラミング(英: Integer Programming、IP)は、実世界の最適化問題を制約で定式化するために一般的に用いられる整数変数ベースの手法である。 現在、量子アルゴリズムは、間接的かつリソース消費の方法であるバイナリ変数を用いることで、IPを制約のない形式に再構成している。 我々は、IP問題を元の形式で、十分な精度で制御できる多数のアクセス可能な内部自由度を持つ任意の量子システムにマッピングし、解決するアルゴリズムを開発する。 1つのRydberg原子を例として、整数値を異なる多様体に属する電子状態に関連付け、これらの異なる状態の選択的重ね合わせを実装して完全なIP問題を解く。 最適解は、線形IP問題と比較して古典的なアルゴリズムで解くのが難しい非線形IP問題を含む最大4つの制約を含む、最大8変数のプロトタイプIP問題に対して、2-40{\mu}sで見つかる。 提案アルゴリズムは, 分岐境界法を用いてベンチマークを行い, 収束に必要なステップ数で古典的アルゴリズムを上回り, より大規模な問題に対して古典的アルゴリズムが提供するバウンドを改善する可能性を秘めている。

関連論文リスト

• The Differentiable Feasibility Pump [49.55771920271201]
  本稿では,従来の実現可能性ポンプとその追随点の多くを,特定のパラメータを持つ勾配差アルゴリズムとみなすことができることを示す。 この再解釈の中心的な側面は、伝統的なアルゴリズムがそのコストに関して線形緩和の解を区別することを観察することである。
  論文  参考訳（メタデータ） (2024-11-05T22:26:51Z)
• 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)
• Solving The Travelling Salesman Problem Using A Single Qubit [0.0]
  トラベルセールスマン問題(TSP)はNP-ハード組合せ最適化問題として人気がある。 本稿では,量子並列性(quantum parallelism)の原理を導出し,単一量子ビットを用いて任意のTSPを解くアルゴリズムを提案する。 我々のアルゴリズムの基盤となるフレームワークは、古典的ブラキストクロンのアプローチの量子バージョンである。
  論文  参考訳（メタデータ） (2024-07-24T12:06:37Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• Non-variational Quantum Combinatorial Optimisation [3.6538093004443155]
  本稿では,多種多様な最適化問題を解くために,非変分量子アルゴリズムを提案する。 アルゴリズムの汎用性は、様々な問題に適用することで実証される。 各問題インスタンスに対して、アルゴリズムは少数の反復で大域的に最適な解を求める。
  論文  参考訳（メタデータ） (2024-04-04T02:36:24Z)
• Efficient quantum linear solver algorithm with detailed running costs [0.0]
  量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。 我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
  論文  参考訳（メタデータ） (2023-05-19T00:07:32Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Ising formulation of integer optimization problems for utilizing quantum annealing in iterative improvement strategy [1.14219428942199]
  繰り返し改善戦略において量子アニーリングを利用するために,整数最適化問題のイジング定式化を提案する。 基底状態と候補解との重なりがしきい値を超えた場合, 完全に連結されたフェロポッツモデルに対して一階相転移を回避できることを解析的に示す。
  論文  参考訳（メタデータ） (2022-11-08T02:12:49Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。 私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。 実際の量子コンピュータを用いて得られた結果について述べる。
  論文  参考訳（メタデータ） (2022-01-25T05:59:24Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms [0.0]
  分割・対数手法を用いて、元の問題を小さな問題の集合に還元する。 この手法は任意のQUBOインスタンスに適用でき、全古典的またはハイブリッドな量子古典的アプローチにつながる。
  論文  参考訳（メタデータ） (2021-01-19T19:00:40Z)

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

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