論文の概要: An in-principle super-polynomial quantum advantage for approximating
combinatorial optimization problems
- arxiv url: http://arxiv.org/abs/2212.08678v3
- Date: Wed, 13 Sep 2023 16:41:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-14 18:32:59.127300
- Title: An in-principle super-polynomial quantum advantage for approximating
combinatorial optimization problems
- Title（参考訳）: 組合せ最適化問題近似のための原理的超多項量子アドバンテージ
- Authors: Niklas Pirnay, Vincent Ulitzsch, Frederik Wilde, Jens Eisert,
Jean-Pierre Seifert
- Abstract要約: 量子コンピュータは、最適化問題に対する近似解法において、古典的コンピュータよりも高次超多項式的優位性を有することを証明している。
量子アドバンテージのコアは、究極的にはShorの量子アルゴリズムからファクタリングのために借用されている。
- 参考スコア（独自算出の注目度）: 5.907281242647458
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Combinatorial optimization - a field of research addressing problems that
feature strongly in a wealth of scientific and industrial contexts - has been
identified as one of the core potential fields of applicability of quantum
computers. It is still unclear, however, to what extent quantum algorithms can
actually outperform classical algorithms for this type of problems. In this
work, by resorting to computational learning theory and cryptographic notions,
we prove that quantum computers feature an in-principle super-polynomial
advantage over classical computers in approximating solutions to combinatorial
optimization problems. Specifically, building on seminal work by Kearns and
Valiant and introducing a new reduction, we identify special types of problems
that are hard for classical computers to approximate up to polynomial factors.
At the same time, we give a quantum algorithm that can efficiently approximate
the optimal solution within a polynomial factor. The core of the quantum
advantage discovered in this work is ultimately borrowed from Shor's quantum
algorithm for factoring. Concretely, we prove a super-polynomial advantage for
approximating special instances of the so-called integer programming problem.
In doing so, we provide an explicit end-to-end construction for advantage
bearing instances. This result shows that quantum devices have, in principle,
the power to approximate combinatorial optimization solutions beyond the reach
of classical efficient algorithms. Our results also give clear guidance on how
to construct such advantage-bearing problem instances.
- Abstract（参考訳）: 様々な科学的、産業的な文脈で大きく機能する問題に対処する研究分野である組合せ最適化は、量子コンピュータの応用可能性の中核的な分野の1つとして認識されている。
しかし、量子アルゴリズムがこのタイプの問題に対して、いかにして古典的アルゴリズムよりも優れているかはまだ不明である。
本研究では,計算学習理論と暗号概念を用いて,量子コンピュータが,コンビネート最適化問題に対する解近似において,古典的コンピュータよりも原理上超多項的優位性を有することを証明した。
具体的には、カーンズとヴァリアントによる基礎研究に基づいて新しい還元を導入し、古典的コンピュータが多項式因子を近似することが難しい問題の種類を特定する。
同時に、多項式係数内の最適解を効率的に近似できる量子アルゴリズムを与える。
この研究で発見された量子アドバンテージの核は、最終的にショアの量子アルゴリズムからファクタリングに借用されている。
具体的には、いわゆる整数プログラミング問題の特殊事例を近似する超多項式的優位性を示す。
そのために私たちは、ベアリングインスタンスを利用するための明示的なエンドツーエンドの構成を提供します。
この結果は、量子デバイスは、原理的に、古典的効率的なアルゴリズムの範囲を超えた組合せ最適化解を近似する力を持っていることを示している。
また,このような有利な問題インスタンスの構築方法について,明確なガイダンスも提供する。
関連論文リスト
- Maximizing the practical achievability of quantum annealing attacks on factorization-based cryptography [0.0]
本研究は、整数分解問題と離散対数問題に基づくスキームの暗号解析のための量子的手法に焦点を当てる。
本稿では、量子計算と古典計算を組み合わせたアプローチを改善することにより、分解問題の最大の事例を現実的に解く方法を示す。
論文 参考訳（メタデータ） (2024-10-07T11:55:23Z) - 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) - Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
変分アルゴリズム (VQA) は, NISQシステムの実用化に向けた最有力候補の1つである。
本稿では,VQAの現状と最近の発展を考察し,近似最適化への適用性を強調した。
10ノードと20ノードのグラフ上でMaxCut問題を解くために,深さの異なるQAOA回路を実装した。
論文 参考訳（メタデータ） (2024-07-08T22:02:39Z) - Towards Quantum Computational Mechanics [1.530480694206666]
本稿では、量子コンピューティングを用いて、計算ホモジェナイゼーションにおける代表要素体積(RVE)問題を解く方法について述べる。
我々の量子RVE解法は古典解法に対して指数加速度を得る。
論文 参考訳（メタデータ） (2023-12-06T12:53:02Z) - Challenges and Opportunities in Quantum Optimization [14.7608536260003]
量子コンピュータの最近の進歩は、ブラトフォース古典シミュレーションを超えるスケールで問題を解決する能力を示している。
計算機科学や物理学全般において、主要な最適化問題に対するアプローチは様々である。
論文 参考訳（メタデータ） (2023-12-04T19:00:44Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - 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) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - A quantum-inspired tensor network method for constrained combinatorial
optimization problems [5.904219009974901]
本稿では,一般に局所的に制約された最適化問題に対する量子インスパイアされたテンソルネットワークに基づくアルゴリズムを提案する。
我々のアルゴリズムは、興味のある問題に対してハミルトニアンを構築し、量子問題に効果的にマッピングする。
本研究は,本手法の有効性と応用の可能性を示すものである。
論文 参考訳（メタデータ） (2022-03-29T05:44:07Z) - Polynomial unconstrained binary optimisation inspired by optical
simulation [52.11703556419582]
制約のないバイナリ最適化の問題を解決するために,光コヒーレントIsingマシンにヒントを得たアルゴリズムを提案する。
提案アルゴリズムを既存のPUBOアルゴリズムに対してベンチマークし,その優れた性能を観察する。
タンパク質の折り畳み問題や量子化学問題へのアルゴリズムの適用は、PUBO問題による電子構造問題の近似の欠点に光を当てる。
論文 参考訳（メタデータ） (2021-06-24T16:39:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。