論文の概要: Solving non-native combinatorial optimization problems using hybrid
quantum-classical algorithms
- arxiv url: http://arxiv.org/abs/2403.03153v1
- Date: Tue, 5 Mar 2024 17:46:04 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-06 14:01:36.173496
- Title: Solving non-native combinatorial optimization problems using hybrid
quantum-classical algorithms
- Title（参考訳）: ハイブリッド量子古典アルゴリズムによる非ネイティブ組合せ最適化問題の解法
- Authors: Jonathan Wurtz, Stefan Sack, Sheng-Tao Wang
- Abstract要約: 組合せ最適化は、物流から金融まで幅広い分野に適用可能な、困難な問題である。
量子コンピューティングは、様々なアルゴリズムを用いてこれらの問題を解決するために使われてきた。
この研究は、量子と古典のリソースをハイブリッドなアプローチで統合することで、これらの課題を克服する枠組みを提示している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Combinatorial optimization is a challenging problem applicable in a wide
range of fields from logistics to finance. Recently, quantum computing has been
used to attempt to solve these problems using a range of algorithms, including
parameterized quantum circuits, adiabatic protocols, and quantum annealing.
These solutions typically have several challenges: 1) there is little to no
performance gain over classical methods, 2) not all constraints and objectives
may be efficiently encoded in the quantum ansatz, and 3) the solution domain of
the objective function may not be the same as the bit strings of measurement
outcomes. This work presents "non-native hybrid algorithms" (NNHA): a framework
to overcome these challenges by integrating quantum and classical resources
with a hybrid approach. By designing non-native quantum variational ansatzes
that inherit some but not all problem structure, measurement outcomes from the
quantum computer can act as a resource to be used by classical routines to
indirectly compute optimal solutions, partially overcoming the challenges of
contemporary quantum optimization approaches. These methods are demonstrated
using a publicly available neutral-atom quantum computer on two simple problems
of Max $k$-Cut and maximum independent set. We find improvements in solution
quality when comparing the hybrid algorithm to its ``no quantum" version, a
demonstration of a "comparative advantage".
- Abstract（参考訳）: 組合せ最適化は、物流から金融まで幅広い分野に適用可能な、困難な問題である。
近年、量子コンピューティングは、パラメータ化量子回路、断熱プロトコル、量子アニールなど、様々なアルゴリズムを用いてこれらの問題を解決しようとしている。
これらのソリューションにはいくつかの課題があります。
1) 古典的手法よりも性能が向上することがほとんどない。
2)全ての制約や目的を量子アンサッツに効率的に符号化できる訳ではなく、
3) 対象関数の解領域は測定結果のビット列と同一ではないかもしれない。
この研究は、量子リソースと古典リソースをハイブリッドアプローチに統合することでこれらの課題を克服するフレームワーク「非ネイティブハイブリッドアルゴリズム」(NNHA)を提示する。
問題構造を継承する非ネイティブな量子変分アンサーゼを設計することにより、量子コンピュータの測定結果は、古典的なルーチンによって間接的に最適解を計算するために使用されるリソースとして機能し、現代の量子最適化アプローチの課題を部分的に克服することができる。
これらの方法は、最大$k$-cut と最大独立集合の2つの単純な問題に対して、公開可能な中性原子量子コンピュータを用いて実証される。
ハイブリッドアルゴリズムと ` `no quantum" バージョンを比較すると,ソリューションの品質が向上し,"比較優位性" の実証が得られた。
関連論文リスト
- Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice [0.0]
変分量子アルゴリズム、特に変分量子固有解器の変種は最適化(CO)問題に対処するために提案されている。
ベンチマークとしてMax-Cutを用いてCO問題を解く上で,このスケーリング結果がどのような意味を持つのかを数値的に検討する。
論文 参考訳（メタデータ） (2024-08-06T09:57:34Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Iterative Quantum Algorithms for Maximum Independent Set: A Tale of
Low-Depth Quantum Algorithms [0.0]
我々は、反復最大量子アルゴリズム(Iterative Maximum Quantum Algorithms)と呼ばれる、量子最適化のための新しいハイブリッドアプローチのクラスについて研究する。
深度$p=1$のQAOAの場合、このアルゴリズムはMISの古典的欲求アルゴリズムと全く同じ操作と選択を行う。
論文 参考訳（メタデータ） (2023-09-22T18:00:03Z) - Quantum-Informed Recursive Optimization Algorithms [0.0]
最適化問題に対する量子インフォームド再帰最適化(QIRO)アルゴリズムのファミリを提案し,実装する。
提案手法は、量子資源を利用して、問題固有の古典的還元ステップで使用される情報を得る。
バックトラック技術を用いて、量子ハードウェアの要求を増大させることなく、アルゴリズムの性能をさらに向上させる。
論文 参考訳（メタデータ） (2023-08-25T18:02:06Z) - 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) - Classically-Boosted Quantum Optimization Algorithm [0.0]
我々は、量子最適化を強化するために既存の古典的手法を活用する自然なアプローチを探求する。
具体的には、近似解を見つけるために古典的なアルゴリズムを実行し、量子回路を用いて高品質な解の「近傍」を探索する。
CBQOA の Max 3SAT および Max Bisection への応用を実証し,これらの問題に対する従来のアプローチよりも優れていることを示す実証的証拠を提供する。
論文 参考訳（メタデータ） (2022-03-25T23:36:14Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z) - Solving Quadratic Unconstrained Binary Optimization with
divide-and-conquer and quantum algorithms [0.0]
分割・対数手法を用いて、元の問題を小さな問題の集合に還元する。
この手法は任意のQUBOインスタンスに適用でき、全古典的またはハイブリッドな量子古典的アプローチにつながる。
論文 参考訳（メタデータ） (2021-01-19T19:00:40Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。