論文の概要: Divide and Conquer for Combinatorial Optimization and Distributed
Quantum Computation
- arxiv url: http://arxiv.org/abs/2107.07532v3
- Date: Thu, 12 Oct 2023 16:41:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-15 15:35:36.605116
- Title: Divide and Conquer for Combinatorial Optimization and Distributed
Quantum Computation
- Title(参考訳): 組合せ最適化と分散量子計算のための分割と克服
- Authors: Teague Tomesh, Zain H. Saleem, Michael A. Perlin, Pranav Gokhale,
Martin Suchara, Margaret Martonosi
- Abstract要約: 本稿では、大規模最適化問題を分散量子アーキテクチャにマッピングするハイブリッド変分法である量子除算法(QDCA)を紹介する。
これはグラフ分割と量子回路切断の組み合わせによって達成される。
我々は、最大独立集合問題のインスタンス上でQDCAをシミュレートし、類似の古典的アルゴリズムよりも優れた性能が得られることを確かめる。
- 参考スコア(独自算出の注目度): 3.8221353389253676
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Scaling the size of monolithic quantum computer systems is a difficult task.
As the number of qubits within a device increases, a number of factors
contribute to decreases in yield and performance. To meet this challenge,
distributed architectures composed of many networked quantum computers have
been proposed as a viable path to scalability. Such systems will need
algorithms and compilers that are tailored to their distributed architectures.
In this work we introduce the Quantum Divide and Conquer Algorithm (QDCA), a
hybrid variational approach to mapping large combinatorial optimization
problems onto distributed quantum architectures. This is achieved through the
combined use of graph partitioning and quantum circuit cutting. The QDCA, an
example of application-compiler co-design, alters the structure of the
variational ansatz to tame the exponential compilation overhead incurred by
quantum circuit cutting.
The result of this cross-layer co-design is a highly flexible algorithm which
can be tuned to the amount of classical or quantum computational resources that
are available, and can be applied to both near- and long-term distributed
quantum architectures. We simulate the QDCA on instances of the Maximum
Independent Set problem and find that it is able to outperform similar
classical algorithms. We also evaluate an 8-qubit QDCA ansatz on a
superconducting quantum computer and show that circuit cutting can help to
mitigate the effects of noise. Our work demonstrates how many small-scale
quantum computers can work together to solve problems $85\%$ larger than their
own qubit count, motivating the development and potential of large-scale
distributed quantum computing.
- Abstract(参考訳): モノリシックな量子コンピュータシステムのサイズをスケールするのは難しい作業です。
デバイス内の量子ビット数が増加するにつれて、多くの要因が収量と性能の低下に寄与する。
この課題に対処するため、ネットワーク化された多くの量子コンピュータからなる分散アーキテクチャが拡張性への有効な経路として提案されている。
このようなシステムには、分散アーキテクチャに適したアルゴリズムとコンパイラが必要です。
本稿では,大規模組合せ最適化問題を分散量子アーキテクチャにマッピングするハイブリッド変分法であるquantum divide and conquer algorithm (qdca)を提案する。
これはグラフ分割と量子回路切断の組み合わせによって達成される。
アプリケーションコンパイラ共設計の例であるqdcaは、変分アンサッツの構造を変更し、量子回路切断によって生じる指数的コンパイルオーバーヘッドを和らげる。
このクロスレイヤー共設計の結果は、利用可能な古典的あるいは量子的な計算資源の量に合わせて調整できる非常に柔軟なアルゴリズムであり、近距離および長期の分散量子アーキテクチャにも適用できる。
我々は、最大独立集合問題のインスタンス上でQDCAをシミュレートし、類似の古典的アルゴリズムよりも優れた性能が得られることを確かめる。
また、超伝導量子コンピュータ上での8量子QDCAアンサッツの評価を行い、回路切断がノイズの影響を緩和することを示す。
我々の研究は、大規模な分散量子コンピューティングの発展とポテンシャルを動機付け、量子ビット数よりも85 %$の問題を解くために、いかに小さな量子コンピュータが協力できるかを実証している。
関連論文リスト
- Quantum Compiling with Reinforcement Learning on a Superconducting Processor [55.135709564322624]
超伝導プロセッサのための強化学習型量子コンパイラを開発した。
短絡の新規・ハードウェア対応回路の発見能力を示す。
本研究は,効率的な量子コンパイルのためのハードウェアによるソフトウェア設計を実証する。
論文 参考訳(メタデータ) (2024-06-18T01:49:48Z) - Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization [0.8121127831316319]
本稿では,デバイス間通信コストを大幅に削減する量子回路の構築手法を提案する。
そこで本研究では,従来のQDCA手法の約3倍の大きさのトラクタブル回路を構築できることを示す。
論文 参考訳(メタデータ) (2024-05-01T20:49:50Z) - Revisiting the Mapping of Quantum Circuits: Entering the Multi-Core Era [2.465579331213113]
本稿では,コア間通信の削減を目的として,コアへのキュービット割り当てを最適化するために設計されたマルチコアマッピングアルゴリズムである,ハンガリークビット割り当て(HQA)アルゴリズムを紹介する。
モジュラーアーキテクチャの最先端回路マッピングアルゴリズムに対するHQAの評価では、実行時間と非ローカル通信の点で4.9times$と1.6times$の改善が示されている。
論文 参考訳(メタデータ) (2024-03-25T21:31:39Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳(メタデータ) (2024-02-26T09:32:07Z) - Applying an Evolutionary Algorithm to Minimize Teleportation Costs in Distributed Quantum Computing [3.0846297887400977]
量子通信ネットワークは、古典的および量子チャネルを介して複数の量子コンピュータ(QC)を接続することによって形成することができる。
分散量子コンピューティングでは、QCは集合的に量子計算を行う。
本稿では,この問題に対する進化的アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-11-30T13:10:28Z) - Hungarian Qubit Assignment for Optimized Mapping of Quantum Circuits on
Multi-Core Architectures [1.1288814203214292]
量子コンピュータは、これらのクラスタ間のスペーサー接続を備えた密結合量子ビットのクラスタを特徴とするモジュラーアプローチを採用することが期待されている。
複数の処理コアにキュービットを効率よく分散させることは、量子コンピューティングシステムの性能とスケーラビリティを向上させる上で重要である。
ハンガリーのQubit Assignment(HQA)アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-21T15:48:45Z) - Iterative Qubits Management for Quantum Index Searching in a Hybrid
System [56.39703478198019]
IQuCSは、量子古典ハイブリッドシステムにおけるインデックス検索とカウントを目的としている。
我々はQiskitでIQuCSを実装し、集中的な実験を行う。
その結果、量子ビットの消費を最大66.2%削減できることが示されている。
論文 参考訳(メタデータ) (2022-09-22T21:54:28Z) - Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
本稿では,グラフニューラルネットワーク(GNN)と組み合わせた強化学習(RL)手法を提案する。
この問題は、巨大な検索スペース、重い尾の報酬分布、そして困難なクレジット割り当てのために非常に難しい。
GNNを基本方針として利用するRLエージェントが,これらの課題にどのように対処できるかを示す。
論文 参考訳(メタデータ) (2022-04-18T21:45:13Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳(メタデータ) (2022-01-06T21:02:30Z) - Quantum Algorithms and Simulation for Parallel and Distributed Quantum
Computing [0.0]
大規模量子コンピュータを構築するための実行可能なアプローチは、小規模量子コンピュータと量子ネットワークを相互接続することである。
並列および分散量子アルゴリズムの設計と検証を簡単にすることを目的としたシミュレーションプラットフォームであるInterlin-qを提案する。
論文 参考訳(メタデータ) (2021-06-12T19:41:48Z) - Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
本稿では、QAS(Quantum Architecture Search)と呼ばれるリソースと実行時の効率的なスキームを提案する。
QASは、よりノイズの多い量子ゲートを追加することで得られる利点と副作用のバランスをとるために、自動的にほぼ最適アンサッツを求める。
数値シミュレータと実量子ハードウェアの両方に、IBMクラウドを介してQASを実装し、データ分類と量子化学タスクを実現する。
論文 参考訳(メタデータ) (2020-10-20T12:06:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。