論文の概要: Integer Programming Using A Single Atom
- arxiv url: http://arxiv.org/abs/2402.16541v2
- Date: Wed, 28 Feb 2024 10:18:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-29 11:59:52.364896
- Title: Integer Programming Using A Single Atom
- Title(参考訳): 単一原子を用いた整数プログラミング
- 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 that possesses
a large number of accessible internal degrees of freedom that 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 a few
microseconds for prototypical IP problems with up to eight variables and a
maximum number of 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 outperforms a
well-known classical algorithm (branch and bound) in terms of the number of
steps needed for convergence to the solution. Our approach carries the
potential to improve bounds on the solution for larger problems when compared
to the classical algorithms.
- Abstract(参考訳): 整数型プログラミング(英: Integer Programming、IP)は、実世界の最適化問題を制約で定式化するために一般的に用いられる整数変数ベースの手法である。
現在、量子アルゴリズムは、間接的かつリソース消費の方法であるバイナリ変数を用いることで、IPを制約のない形式に再構成している。
我々は,十分な精度で制御可能な多数の内部自由度を持つ量子システムに対して,ip問題を元の形式でマップし,解決するアルゴリズムを開発した。
1つのRydberg原子を例として、整数値を異なる多様体に属する電子状態に関連付け、これらの異なる状態の選択的重ね合わせを実装して完全なIP問題を解く。
最適解は、最大8変数と最大4つの制約を持つプロトタイプIP問題に対して数マイクロ秒以内に見つかる。
これはまた、線形ip問題を含み、線形ip問題と比較して古典アルゴリズムでは解くのが通常困難である。
IP を解くアルゴリズムは、解の収束に必要なステップの数の観点から、よく知られた古典的アルゴリズム(ブランチとバウンド)より優れている。
提案手法は,古典的アルゴリズムと比較して,より大きな問題に対する解のバウンダリを改善する可能性を秘めている。
関連論文リスト
- Quantum Variational Algorithms for the Allocation of Resources in a
Cloud/Edge Architecture [1.1715858161748576]
クラウド/エッジアーキテクチャは、異種コンピューティングノードの複数のレイヤを編成する必要がある。
異なるノード上での計算の最適割り当てとスケジューリングは非常に難しい問題であり、NP困難である。
近い将来,変分量子アルゴリズムが古典的アルゴリズムの代替となる可能性が示唆された。
論文 参考訳(メタデータ) (2024-01-25T17:37:40Z) - Fast, Scalable, Warm-Start Semidefinite Programming with Spectral
Bundling and Sketching [53.91395791840179]
我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。
USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
論文 参考訳(メタデータ) (2023-12-19T02:27:22Z) - 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) - Quantum Sparse Coding [5.130440339897477]
我々はスパース符号化のための量子インスピレーション付きアルゴリズムを開発した。
量子コンピュータとイジングマシンの出現は、より正確な推定につながる可能性がある。
我々はLightrの量子インスパイアされたデジタルプラットフォーム上でシミュレーションデータを用いて数値実験を行う。
論文 参考訳(メタデータ) (2022-09-08T13:00:30Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳(メタデータ) (2022-06-30T03:15:23Z) - 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) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。