論文の概要: TIGER: Topology-aware Assignment using Ising machines Application to
Classical Algorithm Tasks and Quantum Circuit Gates
- arxiv url: http://arxiv.org/abs/2009.10151v1
- Date: Mon, 21 Sep 2020 19:46:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-01 09:03:43.928094
- Title: TIGER: Topology-aware Assignment using Ising machines Application to
Classical Algorithm Tasks and Quantum Circuit Gates
- Title（参考訳）: TIGER:Ising Machineを用いた古典的アルゴリズムタスクと量子回路ゲートへの応用
- Authors: Anastasiia Butko, Ilyas Turimbetov, George Michelogiannakis, David
Donofrio, Didem Unat, John Shalf
- Abstract要約: ゲートベースの量子コンピューティングでは、トポロジー的な方法でタスクをゲートにマップすることを目的とするマッピング問題が存在する。
既存のタスクアプローチは、物理最適化アルゴリズムのいずれかに基づいており、異なるスピードとソリューション品質のトレードオフを提供する。
本稿では,Ising マシンを用いてトポロジ対応の代入問題を解くアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 2.4047296366832307
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Optimally mapping a parallel application to compute and communication
resources is increasingly important as both system size and heterogeneity
increase. A similar mapping problem exists in gate-based quantum computing
where the objective is to map tasks to gates in a topology-aware fashion. This
is an NP-complete graph isomorphism problem, and existing task assignment
approaches are either heuristic or based on physical optimization algorithms,
providing different speed and solution quality trade-offs. Ising machines such
as quantum and digital annealers have recently become available and offer an
alternative hardware solution to solve this type of optimization problems. In
this paper, we propose an algorithm that allows solving the topology-aware
assignment problem using Ising machines. We demonstrate the algorithm on two
use cases, i.e. classical task scheduling and quantum circuit gate scheduling.
TIGER---topology-aware task/gate assignment mapper tool---implements our
proposed algorithms and automatically integrates them into the quantum software
environment. To address the limitations of physical solver, we propose and
implement a domain-specific partition strategy that allows solving larger-scale
problems and a weight optimization algorithm that allows tuning Ising model
parameters to achieve better restuls. We use D-Wave's quantum annealer to
demonstrate our algorithm and evaluate the proposed tool flow in terms of
performance, partition efficiency, and solution quality. Results show
significant speed-up compared to classical solutions, better scalability, and
higher solution quality when using TIGER together with the proposed partition
method. It reduces the data movement cost by 68\% in average for quantum
circuit assignment compared to the IBM QX optimizer.
- Abstract（参考訳）: 並列アプリケーションを計算および通信リソースに最適にマッピングすることは、システムサイズと不均一性の両方が増加するにつれてますます重要になる。
同様のマッピング問題はゲートベースの量子コンピューティングにも存在し、トポロジーを意識した方法でタスクをゲートにマッピングすることを目的としている。
これはNP完全グラフ同型問題であり、既存のタスク割り当てアプローチはヒューリスティックまたは物理最適化アルゴリズムに基づいており、異なる速度と解品質のトレードオフを提供する。
量子アニールやデジタルアニールなどのイズマシンが最近利用可能になり、このタイプの最適化問題を解決するための代替ハードウェアソリューションを提供する。
本論文では,Ising マシンを用いてトポロジ対応の代入問題を解くアルゴリズムを提案する。
このアルゴリズムを古典的タスクスケジューリングと量子回路ゲートスケジューリングという2つのユースケースで実証する。
TIGER(topology-aware task/gate assignment mapper tool)-提案したアルゴリズムを実装し、量子ソフトウェア環境に自動的に統合する。
物理ソルバの限界に対処するために,より大規模な問題を解決するためのドメイン特化分割戦略と,イジングモデルのパラメータをチューニングしてより適切な回復を可能にする重み最適化アルゴリズムを提案し,実装する。
我々はD-Waveの量子アニールを用いてアルゴリズムを実証し,提案するツールフローを性能,パーティション効率,ソリューション品質の観点から評価する。
その結果,提案手法と組み合わせてTIGERを用いた場合,従来のソリューションに比べて大幅な高速化,スケーラビリティの向上,ソリューション品質の向上が得られた。
これは、ibm qxオプティマイザと比較して、量子回路割り当ての平均データ移動コストを68\%削減する。
関連論文リスト
- Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem [2.4968861883180447]
対角ハミルトニアンの基底状態解を見つけることは、金融、物理学、計算機科学など多くの分野に関心を持つ理論的および実践的な問題の両方に関係している。
ここでは、新しいブロック符号化方式を用いて、これらの問題の基底状態を取得し、この手法をMaxCutに例証として応用する。
論文 参考訳（メタデータ） (2024-11-16T08:17:36Z) - Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
変分アルゴリズム (VQA) は, NISQシステムの実用化に向けた最有力候補の1つである。
本稿では,VQAの現状と最近の発展を考察し,近似最適化への適用性を強調した。
10ノードと20ノードのグラフ上でMaxCut問題を解くために,深さの異なるQAOA回路を実装した。
論文 参考訳（メタデータ） (2024-07-08T22:02:39Z) - Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
変分量子アルゴリズム(VQA)は、最適化と機械学習問題を解決するための有望な量子代替手段として登場した。
本稿では,回路設計が2つの分類問題に対して得られる性能に与える影響を実験的に示す。
また、実量子コンピュータのシミュレーションにおいて、ノイズの存在下で得られた回路の劣化について検討する。
論文 参考訳（メタデータ） (2024-04-17T11:00:12Z) - Algorithm-Oriented Qubit Mapping for Variational Quantum Algorithms [3.990724104767043]
短期デバイスに実装された量子アルゴリズムは、ノイズと限定的な量子ビット接続による量子ビットマッピングを必要とする。
本稿では,アルゴリズム指向キュービットマッピング(AOQMAP)と呼ばれる手法を提案する。
論文 参考訳（メタデータ） (2023-10-15T13:18:06Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳（メタデータ） (2023-06-14T13:44:35Z) - Quantum-Inspired Optimization over Permutation Groups [0.2294014185517203]
量子インスパイアされた最適化 (QIO) アルゴリズムは、量子力学的効果を古典的なハードウェアにエミュレートする計算手法である。
我々は、任意の最適化問題を解決するためにQIOツールをカスタマイズするアルゴリズムフレームワークPerm-QIOを開発した。
論文 参考訳（メタデータ） (2022-12-06T00:02:39Z) - Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs [0.0]
現在の量子最適化アルゴリズムでは、元の問題を二進最適化問題として表現し、量子デバイスに適した等価イジングモデルに変換する必要がある。
目的関数を計算し、制約を認証するための古典的プログラムを設計し、後に量子回路にコンパイルする。
その結果,量子近似最適化アルゴリズム (QAOA) が新たに導入された。
論文 参考訳（メタデータ） (2022-09-07T18:01:01Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳（メタデータ） (2020-10-01T18:14:11Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。