論文の概要: Integer Programming Using A Single Atom
- arxiv url: http://arxiv.org/abs/2402.16541v3
- Date: Tue, 23 Jul 2024 10:27:14 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-24 22:53:21.598835
- Title: Integer Programming Using A Single Atom
- Title（参考訳）: 単一のAtomを使った整数プログラミング
- Authors: Kapil Goswami, Peter Schmelcher, Rick Mukherjee,
- Abstract要約: 我々は,IP問題を元の形で任意の量子システムにマップし,解くアルゴリズムを開発した。
最適解は、最大8つの変数と4つの制約を持つIP問題に対して数マイクロ秒以内に見つかる。
- 参考スコア（独自算出の注目度）: 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 possessing a large number of accessible internal degrees of freedom that are controlled with sufficient accuracy. This work leverages the principle of superposition to solve the optimization problem. 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 different states to solve the full IP problem. The optimal solution is found within a few microseconds for prototypical IP problems with up to eight variables and four constraints. This also includes non-linear IP problems, which are usually harder to solve with classical algorithms when compared to their linear counterparts. Our algorithm for solving IP is benchmarked by a well-known classical algorithm (branch and bound) in terms of the number of steps needed for convergence to the solution. This approach carries the potential to improve the solutions obtained for larger-size problems using hybrid quantum-classical algorithms.
- Abstract（参考訳）: 整数型プログラミング(英: Integer Programming、IP)は、実世界の最適化問題を制約で定式化するために一般的に用いられる整数変数ベースの手法である。
現在、量子アルゴリズムは、間接的かつリソース消費の方法であるバイナリ変数を用いることで、IPを制約のない形式に再構成している。
我々は、IP問題を元の形式で、適切な精度で制御される多数のアクセス可能な内部自由度を持つ任意の量子システムにマップし、解決するアルゴリズムを開発する。
この研究は、最適化問題を解決するために重ね合わせの原理を活用する。
1つのRydberg原子を例として、整数値を異なる多様体に属する電子状態に関連付け、異なる状態の選択的重ね合わせを実装して完全なIP問題を解決する。
最適解は、最大8変数と4つの制約を持つプロトタイプIP問題に対して数マイクロ秒以内に見つかる。
これには非線形IP問題も含まれており、通常、線形IP問題と比較して古典的なアルゴリズムでは解くのが困難である。
IP を解くアルゴリズムは、解の収束に必要なステップの数の観点から、よく知られた古典的アルゴリズム(ブランチとバウンド)によってベンチマークされる。
このアプローチは、ハイブリッド量子古典アルゴリズムを用いて、より大きな問題に対して得られる解を改善する可能性をもたらす。
関連論文リスト
- 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) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳（メタデータ） (2023-12-18T18:29:01Z) - 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) - Alternatives to a nonhomogeneous partial differential equation quantum
algorithm [52.77024349608834]
Apsi(textbfr)=f(textbfr)$ という形の非等質線型偏微分方程式を解くための量子アルゴリズムを提案する。
これらの成果により、現代の技術に基づく量子アルゴリズムの実験的実装が容易になった。
論文 参考訳（メタデータ） (2022-05-11T14:29:39Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。