論文の概要: Advanced unembedding techniques for quantum annealers
- arxiv url: http://arxiv.org/abs/2009.05028v3
- Date: Wed, 28 Dec 2022 00:56:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-03 00:37:54.482852
- Title: Advanced unembedding techniques for quantum annealers
- Title（参考訳）: 量子アニーラーのための先進的アンエンベディング技術
- Authors: Elijah Pelofske, Georg Hahn, Hristo Djidjev
- Abstract要約: 本研究は4つの重要なNPハード問題に対するアンエンベディング手法について述べる。
我々の手法は単純であり、解決される問題の構造的特性を生かしている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The D-Wave quantum annealers make it possible to obtain high quality
solutions of NP-hard problems by mapping a problem in a QUBO (quadratic
unconstrained binary optimization) or Ising form to the physical qubit
connectivity structure on the D-Wave chip. However, the latter is restricted in
that only a fraction of all pairwise couplers between physical qubits exists.
Modeling the connectivity structure of a given problem instance thus
necessitates the computation of a minor embedding of the variables in the
problem specification onto the logical qubits, which consist of several
physical qubits "chained" together to act as a logical one. After annealing, it
is however not guaranteed that all chained qubits get the same value (-1 or +1
for an Ising model, and 0 or 1 for a QUBO), and several approaches exist to
assign a final value to each logical qubit (a process called "unembedding"). In
this work, we present tailored unembedding techniques for four important
NP-hard problems: the Maximum Clique, Maximum Cut, Minimum Vertex Cover, and
Graph Partitioning problems. Our techniques are simple and yet make use of
structural properties of the problem being solved. Using Erd\H{o}s-R\'enyi
random graphs as inputs, we compare our unembedding techniques to three popular
ones (majority vote, random weighting, and minimize energy). We demonstrate
that our proposed algorithms outperform the currently available ones in that
they yield solutions of better quality, while being computationally equally
efficient.
- Abstract（参考訳）: D-Wave量子異方体は、QUBOやIsing形式の問題をD-Waveチップ上の物理量子ビット接続構造にマッピングすることで、NP-hard問題の高品質な解を得ることができる。
しかし、後者は、物理キュービット間の全てのペアワイズカプラの分数しか存在しないという点で制限されている。
したがって、与えられた問題インスタンスの接続構造をモデル化するには、問題仕様の変数の小さな埋め込みを論理キュービットに計算する必要がある。
しかし、アニーリングの後、すべての鎖の量子ビットが同じ値(イジングモデルでは-1または+1、QUBOでは0または1)であることは保証されず、各論理キュービットに最終的な値を割り当てるためにいくつかのアプローチが存在する。
本研究では,最大傾き,最大カット,最小頂点被覆,グラフ分割の4つの重要なNPハード問題に対して,非埋め込み手法を提案する。
我々の手法は単純であり、解決される問題の構造的特性を利用する。
erd\h{o}s-r\'enyiランダムグラフを入力として使用し,提案手法を3つの人気グラフ(多数投票,ランダム重み付け,エネルギー最小化)と比較した。
提案アルゴリズムが現在利用可能なアルゴリズムより優れており、計算効率が等しく、より良い品質の解が得られることを実証する。
関連論文リスト
- An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Quantum Annealers Chain Strengths: A Simple Heuristic to Set Them All [0.0]
チップトポロジを直接マップしない問題の解決は、量子コンピュータでは依然として困難である。
相互接続された物理量子ビットの集合としての論理量子ビットの生成は、チップの間隔によって課される制限を克服する。
強磁性結合を維持するために、密結合された論理量子ビットはより低い鎖強度を必要とすることを示す。
論文 参考訳（メタデータ） (2024-04-08T12:24:03Z) - Logical qubit implementation for quantum annealing: augmented Lagrangian
approach [0.0]
量子アニール上の最適化問題の解法は、通常、各問題の変数を接続された量子ビットの集合で表わす必要がある。
連鎖重みを小さくする適切な論理量子ビット表現を生成するための最適化に基づく手法を提案する。
論文 参考訳（メタデータ） (2023-01-29T08:45:36Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Solving Larger Optimization Problems Using Parallel Quantum Annealing [0.0]
並列量子アニールとグラフ分解を組み合わせたハイブリッドアプローチにより、より大規模な最適化問題を正確に解けることを示す。
最大傾き問題を最大120ノードと6395エッジのグラフに適用する。
論文 参考訳（メタデータ） (2022-05-24T15:56:15Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - Parallel Quantum Annealing [0.0]
D-Wave Systems, Inc. の量子アニールは、NPハード問題の高品質な解を計算する効率的な方法を提供する。
本稿では,利用可能な量子ビットをよりよく活用するための並列量子アニール法を提案する。
本手法は,最大傾き問題の解法として,TTS(Time-to-Solution)を用いて劇的な高速化を実現することができることを示す。
論文 参考訳（メタデータ） (2021-11-11T00:10:44Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Decomposition algorithms for solving NP-hard problems on a quantum
annealer [0.0]
NPハード問題は、計算化学、生化学、コンピュータネットワークセキュリティに応用されている。
Adaabatic quantum annealers can search the optimum value of such NP-hard optimization problem, because the problem can be embedded on their hardware。
本稿ではNP-hardグラフ問題に対する分解アルゴリズムの一般的な枠組みについて検討する。
論文 参考訳（メタデータ） (2020-09-10T15:59:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。