論文の概要: Approximate Solutions of Combinatorial Problems via Quantum Relaxations
- arxiv url: http://arxiv.org/abs/2111.03167v2
- Date: Mon, 8 Nov 2021 18:52:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-09 04:14:30.590239
- Title: Approximate Solutions of Combinatorial Problems via Quantum Relaxations
- Title（参考訳）: 量子緩和による組合せ問題の近似解
- Authors: Bryce Fuller, Charles Hadfield, Jennifer R. Glick, Takashi Imamichi,
Toshinari Itoko, Richard J. Thompson, Yang Jiao, Marna M. Kagele, Adriana W.
Blom-Schieber, Rudy Raymond, Antonio Mezzacapo
- Abstract要約: 本稿では,最大カット問題とその重み付きバージョンに対する近似解の生成法を提案する。
これらの緩和は可換写像によって定義され、量子ランダムアクセス符号からアイデアを借りて構築される。
緩和されたハミルトニアンのスペクトルと元の問題の最適切断との間には、2つの量子丸めプロトコルを通して関係を定めている。
- 参考スコア（独自算出の注目度）: 5.9971331744096394
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Combinatorial problems are formulated to find optimal designs within a fixed
set of constraints. They are commonly found across diverse engineering and
scientific domains. Understanding how to best use quantum computers for
combinatorial optimization is to date an open problem. Here we propose new
methods for producing approximate solutions for the maximum cut problem and its
weighted version, which are based on relaxations to local quantum Hamiltonians.
These relaxations are defined through commutative maps, which in turn are
constructed borrowing ideas from quantum random access codes. We establish
relations between the spectra of the relaxed Hamiltonians and optimal cuts of
the original problems, via two quantum rounding protocols. The first one is
based on projections to random magic states. It produces average cuts that
approximate the optimal one by a factor of least 0.555 or 0.625, depending on
the relaxation chosen, if given access to a quantum state with energy between
the optimal classical cut and the maximal relaxed energy. The second rounding
protocol is deterministic and it is based on estimation of Pauli observables.
The proposed quantum relaxations inherit memory compression from quantum random
access codes, which allowed us to test the performances of the methods
presented for 3-regular random graphs and a design problem motivated by
industry for sizes up to 40 nodes, on superconducting quantum processors.
- Abstract（参考訳）: 組合せ問題は、一定の制約セット内で最適な設計を見つけるために定式化される。
様々な工学分野や科学分野にまたがっている。
組合せ最適化のために量子コンピュータを最もよく使う方法を理解することは、オープンな問題である。
本稿では,局所量子ハミルトニアンに対する緩和に基づく最大カット問題とその重み付きバージョンに対する近似解を生成する新しい手法を提案する。
これらの緩和は可換写像を通じて定義され、量子ランダムアクセス符号からアイデアを借りて構築される。
緩和されたハミルトニアンのスペクトルと元の問題の最適切断との関係を、2つの量子丸めプロトコルによって確立する。
1つ目はランダムマジック状態への射影に基づいている。
最適カットと最大緩和エネルギーの間のエネルギーを持つ量子状態へのアクセスが与えられた場合、選択された緩和度に応じて、最小0.555または0.625で最適カットを近似する平均カットを生成する。
第2のラウンドプロトコルは決定論的であり、パウリ観測可能性の推定に基づいている。
提案した量子緩和法は、量子ランダムアクセス符号からメモリ圧縮を継承し、3つの規則ランダムグラフに提示された手法の性能と、超伝導量子プロセッサ上の最大40ノードの産業によって動機付けられた設計問題をテストする。
関連論文リスト
- Quantum Relaxation for Solving Multiple Knapsack Problems [7.003282322403712]
組合せ問題はビジネスにおいて共通の課題であり、特定の制約の下で最適なソリューションを見つける必要がある。
本研究では,制約付き最適化問題に対するハイブリッド量子古典法について検討する。
提案手法は、可換写像によって定義される局所量子ハミルトニアンの緩和に依存する。
論文 参考訳（メタデータ） (2024-04-30T11:40:07Z) - 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) - Recursive Quantum Relaxation for Combinatorial Optimization Problems [3.3053321430025258]
既存の量子最適化手法のいくつかは、最適量子状態から最も高い確率で測定される二項解を求める解法に統一可能であることを示す。
テンソルネットワーク技術を用いたMAX-CUT問題における数百ノードの標準ベンチマークグラフの実験は、RQRAOがゴーマン-ウィリアムソン法より優れ、最先端の古典的解法に匹敵することを示した。
論文 参考訳（メタデータ） (2024-03-04T13:48:21Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - A Universal Quantum Algorithm for Weighted Maximum Cut and Ising
Problems [0.0]
本稿では,二項問題の近似解を計算するためのハイブリッド量子古典アルゴリズムを提案する。
我々は、重み付き最大カットまたはイジング・ハミルトン演算子をブロック符号化するユニタリおよびエルミート演算子を実装するために浅深さ量子回路を用いる。
この作用素の変動量子状態への期待を測定すると、量子系の変動エネルギーが得られる。
論文 参考訳（メタデータ） (2023-06-10T23:28:13Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Efficiently Solve the Max-cut Problem via a Quantum Qubit Rotation
Algorithm [7.581898299650999]
我々はQQRA(Quantum Qubit Rotation Algorithm)という単純なアルゴリズムを導入する。
最大カット問題の近似解は 1 に近い確率で得られる。
我々は、よく知られた量子近似最適化アルゴリズムと古典的なゲーマン・ウィリアムソンアルゴリズムと比較する。
論文 参考訳（メタデータ） (2021-10-15T11:19:48Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。