論文の概要: Atom Cavity Encoding for NP-Complete Problems

• arxiv url: http://arxiv.org/abs/2407.11851v1
• Date: Tue, 16 Jul 2024 15:32:42 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-17 14:13:22.131562
• Title: Atom Cavity Encoding for NP-Complete Problems
• Title（参考訳）: NP-Complete問題に対するAtomキャビティ符号化
• Authors: Meng Ye, Xiaopeng Li,
• Abstract要約: 我々は、カープの21個のNP完全問題の大部分を含む、多数のNP完全問題に対する符号化スキームを提案する。 このような計算問題を, 原子数の線形コストで, 原子キャビティ・システムによって符号化できることが判明した。 本研究は,NP完全問題の解法において,原子空洞系の実用的な量子的優位性を求めるための重要なガイダンスを提供することを期待している。
• 参考スコア（独自算出の注目度）: 5.482856804346147
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider an atom-cavity system having long-range atomic interactions mediated by cavity modes. It has been shown that quantum simulations of spin models with this system can naturally be used to solve number partition problems. Here, we present encoding schemes for numerous NP-complete problems, encompassing the majority of Karp's 21 NP-complete problems. We find a number of such computation problems can be encoded by the atom-cavity system at a linear cost of atom number. There are still certain problems that cannot be encoded by the atom-cavity as efficiently, such as quadratic unconstrained binary optimization (QUBO), and the Hamiltonian cycle. For these problems, we provide encoding schemes with a quadratic or quartic cost in the atom number. We expect this work to provide important guidance to search for the practical quantum advantage of the atom-cavity system in solving NP-complete problems. Moreover, the encoding schemes we develop here may also be adopted in other optical systems for solving NP-complete problems, where a similar form of Mattis-type spin glass Hamiltonian as in the atom-cavity system can be implemented.
• Abstract（参考訳）: キャビティモードを介する長距離原子間相互作用を有する原子空洞系を考える。 このシステムを用いたスピンモデルの量子シミュレーションは、数分割問題の解法として自然に利用できることが示されている。 ここでは、カープの21個のNP完全問題の大部分を含む、多数のNP完全問題に対する符号化スキームを提案する。 このような計算問題を,原子番号の線形コストで,原子キャビティシステムによって符号化できることが判明した。 原子キャビティによって効率的にエンコードできない問題として、二次的非制約二元最適化(QUBO)やハミルトンサイクルがある。 これらの問題に対して、原子番号の2次的あるいは4次的なコストで符号化スキームを提供する。 本研究は,NP完全問題の解法において,原子空洞系の実用的な量子的優位性を求めるための重要なガイダンスを提供することを期待している。 さらに、ここで開発された符号化スキームは、他の光学系でもNP完全問題の解法として採用され、原子キャビティ系と同様にマティス型スピングラスハミルトニアンが実装される。

関連論文リスト

• Universal Quantum Optimization with Cold Atoms in an Optical Cavity [14.568979066292918]
  原子空洞系は任意の接続性を持つ量子最適化に普遍的であることを示す。 単一モードキャビティを考慮し、原子に対する工学的量子ハミルトニアンが直接数分割問題を符号化するラマンカップリング方式を開発する。
  論文  参考訳（メタデータ） (2023-06-29T13:42:19Z)
• Quantum Programming of the Satisfiability Problem with Rydberg Atom Graphs [1.2179548969182574]
  実験では、リドベルク原子を用いて(すなわち、満足度(3-SAT)の問題をプログラムし、解を求める)。
  論文  参考訳（メタデータ） (2023-02-28T07:49:10Z)
• Solving various NP-Hard problems using exponentially fewer qubits on a Quantum Computer [0.0]
  NPハード問題は、一般時間アルゴリズムで正確に解けるとは考えられていない。 本稿では,問題のサイズに応じて対数的にスケールする独自手法を構築した。 これらのアルゴリズムは、100以上のノードのグラフサイズを持つ量子シミュレータと、256のグラフサイズまでの実際の量子コンピュータでテストされる。
  論文  参考訳（メタデータ） (2023-01-17T16:03:33Z)
• Towards Neural Variational Monte Carlo That Scales Linearly with System Size [67.09349921751341]
  量子多体問題(Quantum many-body problem)は、例えば高温超伝導体のようなエキゾチックな量子現象をデミストする中心である。 量子状態を表すニューラルネットワーク(NN)と変分モンテカルロ(VMC)アルゴリズムの組み合わせは、そのような問題を解決する上で有望な方法であることが示されている。 ベクトル量子化技術を用いて,VMCアルゴリズムの局所エネルギー計算における冗長性を利用するNNアーキテクチャVector-Quantized Neural Quantum States (VQ-NQS)を提案する。
  論文  参考訳（メタデータ） (2022-12-21T19:00:04Z)
• 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)
• Variance minimisation on a quantum computer for nuclear structure [0.0]
  本稿では,量子コンピュータを用いた小型核系の励起状態スペクトルの分散に基づく検出法を提案する。 我々の目標は、核構造を再現し予測できる量子コンピューティングアルゴリズムを開発することである。
  論文  参考訳（メタデータ） (2022-09-16T09:38:07Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Hardware-Efficient, Fault-Tolerant Quantum Computation with Rydberg Atoms [55.41644538483948]
  我々は中性原子量子コンピュータにおいてエラー源の完全な特徴付けを行う。 計算部分空間外の状態への原子量子ビットの崩壊に伴う最も重要なエラーに対処する,新しい,明らかに効率的な手法を開発した。 我々のプロトコルは、アルカリ原子とアルカリ原子の両方にエンコードされた量子ビットを持つ最先端の中性原子プラットフォームを用いて、近い将来に実装できる。
  論文  参考訳（メタデータ） (2021-05-27T23:29:53Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• Number Partitioning with Grover's Algorithm in Central Spin Systems [0.0]
  本稿では,部分和問題として知られるNP完全決定問題のクラスに対する解を求めるGrover探索を提案する。 各問題インスタンスは、一組の量子ビットの中央スピンやボソンへのカップリングに符号化され、溶液を知らずにオラクルの実現を可能にする。
  論文  参考訳（メタデータ） (2020-09-11T17:31:39Z)

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

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