論文の概要: Solving various NP-Hard problems using exponentially fewer qubits on a
Quantum Computer
- arxiv url: http://arxiv.org/abs/2301.06978v1
- Date: Tue, 17 Jan 2023 16:03:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-18 13:42:48.607468
- 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倍近く上回っている。
関連論文リスト
- Evidence of Scaling Advantage for the Quantum Approximate Optimization
Algorithm on a Classically Intractable Problem [16.821121709738957]
量子近似最適化アルゴリズム(QAOA)は、量子コンピュータにおける最適化問題を解くための主要な候補アルゴリズムである。
本稿では,Low Autocorrelation Binary Sequences (LABS) 問題に対するQAOAの広範な数値解析を行う。
このシステムサイズ、固定パラメータと一定の数のレイヤを持つQAOAのランタイムは、ブランチ・アンド・バウンド・ソルバよりも優れたスケールである。
論文 参考訳(メタデータ) (2023-08-04T14:17:21Z) - NISQ-compatible approximate quantum algorithm for unconstrained and
constrained discrete optimization [0.0]
本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。
目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
論文 参考訳(メタデータ) (2023-05-23T16:17:57Z) - 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) - Demonstrating robust simulation of driven-dissipative problems on
near-term quantum computers [53.20999552522241]
量子コンピュータは物理学と化学における量子力学系のシミュレーションに革命をもたらす。
現在の量子コンピュータは、訂正されていないノイズ、ゲートエラー、デコヒーレンスのためにアルゴリズムを不完全に実行している。
ここでは、量子力学における最も難しい問題の1つとして、駆動散逸多体問題の解法が本質的にエラーに対して堅牢であることを示す。
論文 参考訳(メタデータ) (2021-08-02T21:36:37Z) - Multiple Query Optimization using a Hybrid Approach of Classical and
Quantum Computing [1.7077661158850292]
データ集約的な問題領域において重要なNPハード問題である多重クエリ最適化問題(MQO)に取り組む。
ゲート型量子コンピュータ上でMQOを解くために,新しい古典量子アルゴリズムを提案する。
提案アルゴリズムでは, クビット効率が99%に近づき, ほぼ2倍に向上した。
論文 参考訳(メタデータ) (2021-07-22T08:12:49Z) - Training variational quantum algorithms is NP-hard [0.7614628596146599]
古典最適化の問題はNPハードであることが示される。
対数的に多くの量子ビットや自由フェルミオンからなる古典的トラクタブルシステムであっても、最適化はNPハードであることが示される。
論文 参考訳(メタデータ) (2021-01-18T19:00:01Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳(メタデータ) (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。