論文の概要: Solving various NP-Hard problems using exponentially fewer qubits on a Quantum Computer

• arxiv url: http://arxiv.org/abs/2301.06978v2
• Date: Fri, 12 Jan 2024 13:36:13 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-16 00:30:31.026529
• Title: Solving various NP-Hard problems using exponentially fewer qubits on a Quantum Computer
• Title（参考訳）: 量子コンピュータにおける指数的に少ない量子ビットを用いたNP-Hard問題の解法
• Authors: Yagnik Chatterjee, Eric Bourreau, Marko J. Ran\v{c}i\'c
• Abstract要約: NPハード問題は、一般時間アルゴリズムで正確に解けるとは考えられていない。 本稿では,問題のサイズに応じて対数的にスケールする独自手法を構築した。 これらのアルゴリズムは、100以上のノードのグラフサイズを持つ量子シミュレータと、256のグラフサイズまでの実際の量子コンピュータでテストされる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: NP-hard problems are not believed to be exactly solvable through general polynomial time algorithms. Hybrid quantum-classical algorithms to address such combinatorial problems have been of great interest in the past few years. Such algorithms are heuristic in nature and aim to obtain an approximate solution. Significant improvements in computational time and/or the ability to treat large problems are some of the principal promises of quantum computing in this regard. The hardware, however, is still in its infancy and the current Noisy Intermediate Scale Quantum (NISQ) computers are not able to optimize industrially relevant problems. Moreover, the storage of qubits and introduction of entanglement require extreme physical conditions. An issue with quantum optimization algorithms such as QAOA is that they scale linearly with problem size. In this paper, we build upon a proprietary methodology which scales logarithmically with problem size - opening an avenue for treating optimization problems of unprecedented scale on gate-based quantum computers. In order to test the performance of the algorithm, we first find a way to apply it to a handful of NP-hard problems: Maximum Cut, Minimum Partition, Maximum Clique, Maximum Weighted Independent Set. Subsequently, these algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256. To our knowledge, these constitute the largest realistic combinatorial optimization problems ever run on a NISQ device, overcoming previous problem sizes by almost tenfold.
• Abstract（参考訳）: NPハード問題は一般多項式時間アルゴリズムによって正確に解けるとは考えられていない。 このような組合せ問題に対処するハイブリッド量子古典アルゴリズムは、ここ数年で大きな関心を集めている。 このようなアルゴリズムは本質的にヒューリスティックであり、近似解を得ることを目指している。 計算時間および/または大きな問題を扱う能力の重要な改善は、この点において量子コンピューティングの主要な約束である。 しかし、ハードウェアはまだ初期段階であり、現在のNISQ(Noisy Intermediate Scale Quantum)コンピュータは産業的に関係のある問題を最適化できない。 さらに、量子ビットの保存と絡み合いの導入は極端な物理的条件を必要とする。 QAOAのような量子最適化アルゴリズムの問題は、問題のサイズに応じて線形にスケールすることである。 本稿では,ゲート型量子コンピュータにおける前例のないスケールの最適化問題を処理するために,対数的に問題サイズにスケールする独自の手法を構築した。 アルゴリズムの性能をテストするために、まず、最大カット、最小分割、最大傾き、最大重み付き独立セットというNPハード問題に適用する方法を見つけます。 その後、これらのアルゴリズムは、100以上のノードのグラフサイズを持つ量子シミュレータと、256のグラフサイズまでの実際の量子コンピュータでテストされる。 我々の知る限り、これらはNISQデバイス上で実行された史上最大の現実的な組合せ最適化問題であり、以前の問題サイズを10倍近く上回っている。

関連論文リスト

• 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)
• Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
  現在利用可能な量子デバイスは、限られた量子ビットと高いレベルのノイズしか持たず、それらのデバイスで正確に解決できる問題のサイズを制限している。 我々は、変分量子アルゴリズム -- 離散化量子排他探索 -- を改善する新しい方法を提案する。
  論文  参考訳（メタデータ） (2024-07-24T22:06:05Z)
• A quantum annealing approach to the minimum distance problem of quantum codes [0.0]
  本稿では,量子安定化器符号の最小距離を準拘束的二項最適化問題として再定式化することで計算する手法を提案する。 D-Wave Advantage 4.1quantum annealerと比較することにより,本手法の実用性を示す。
  論文  参考訳（メタデータ） (2024-04-26T21:29:42Z)
• Quantum Optimization for the Maximum Cut Problem on a Superconducting Quantum Computer [0.3518016233072556]
  半定値アプローチに着想を得たハイブリッド量子古典アルゴリズムの性能について検討した。 何千もの問題インスタンスのランダムアンサンブルに対して平均99%のパフォーマンスを達成した。 実行時解析により、大規模問題における量子解法は、グロビと競合するが、他の問題には劣ることを示した。
  論文  参考訳（メタデータ） (2024-04-26T17:59:22Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• 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)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Noisy intermediate-scale quantum computing algorithm for solving an $n$-vertex MaxCut problem with log($n$) qubits [0.0]
  本稿ではQAOAと比較して指数的に少ない量子ビットを用いる新しい量子最適化アルゴリズムを提案する。 これらの結果は、ゲートベースの量子コンピュータにおける最先端の実験と比較して、グラフサイズが40%増加することを示している。
  論文  参考訳（メタデータ） (2021-10-20T21:33:41Z)
• Multiple Query Optimization using a Hybrid Approach of Classical and Quantum Computing [1.7077661158850292]
  データ集約的な問題領域において重要なNPハード問題である多重クエリ最適化問題(MQO)に取り組む。 ゲート型量子コンピュータ上でMQOを解くために,新しい古典量子アルゴリズムを提案する。 提案アルゴリズムでは, クビット効率が99%に近づき, ほぼ2倍に向上した。
  論文  参考訳（メタデータ） (2021-07-22T08:12:49Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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