論文の概要: Compilation for Surface Code Quantum Computers
- arxiv url: http://arxiv.org/abs/2311.18042v1
- Date: Wed, 29 Nov 2023 19:36:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-01 19:02:26.609586
- Title: Compilation for Surface Code Quantum Computers
- Title(参考訳): 表面コード量子コンピュータのためのコンパイル
- Authors: Abtin Molavi, Amanda Xu, Swamit Tannu, Aws Albarghouthi
- Abstract要約: 表面符号を実装した量子コンピュータにおける量子回路のコンパイル問題について検討する。
問題となるのは、(1)回路キュービットをデバイスキュービットにマッピングし、(2)相互作用するキュービットのペア間で実行経路をルーティングすることである。
例えば,ノード不連続経路の問題を解くために,グリーディアルゴリズムを利用してSCMRを効率的に緩和する手法を提案する。
- 参考スコア(独自算出の注目度): 8.093450284837559
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Practical applications of quantum computing depend on fault-tolerant devices
with error correction. Today, the most promising approach is a class of
error-correcting codes called surface codes. In this paper, we study the
problem of compiling quantum circuits for quantum computers implementing
surface codes. The problem involves (1) mapping circuit qubits to the device
qubits and (2) routing execution paths between pairs of interacting qubits. We
call this the surface code mapping and routing problem (SCMR).
Solving SCMR near-optimally is critical for both efficiency and correctness.
An optimal solution limits the cost of a computation in terms of precious
quantum resources and also minimizes the probability of incurring an undetected
logical error, which increases with each additional time step.
We study SCMR from a theoretical and practical perspective. First, we prove
that SCMR, as well as a constrained version of the problem, is NP-complete.
Second, we present a optimal algorithm for solving SCMR that is based on a SAT
encoding. Third, we present a spectrum of efficient relaxations of SCMR, for
example, by exploiting greedy algorithms for solving the problem of
node-disjoint paths. Finally, we implement and evaluate our algorithms on a
large suite of real and synthetic circuits. Our results suggest that our
relaxations are a powerful tool for compiling realistic workloads. The
relaxation-based algorithms are orders of magnitude faster than the optimal
algorithm (solving instances with tens of thousands of gates in minutes), while
still finding high-quality solutions, achieving the theoretical lower bound on
up to 55 out of 168 circuits from a diverse benchmark suite.
- Abstract(参考訳): 量子コンピューティングの実践的応用は、誤り訂正を伴う耐故障性デバイスに依存する。
今日、最も有望なアプローチは、surface codesと呼ばれるエラー訂正符号のクラスである。
本稿では,曲面符号を実装した量子コンピュータにおける量子回路のコンパイル問題について検討する。
問題は(1)デバイスキュービットへの回路キュービットのマッピング、(2)相互作用するキュービットのペア間の実行パスのルーティングである。
これを表面コードマッピングとルーティング問題(SCMR)と呼ぶ。
SCMRをほぼ最適に解くことは効率と正確性の両方に重要である。
最適な解法は、貴重な量子資源の観点から計算のコストを制限し、また、追加の時間ステップごとに増加する未検出論理誤差を発生させる確率を最小化する。
我々はscmrを理論的かつ実用的な観点から研究する。
まず、scmrは問題の制約付きバージョンと同様にnp完全であることが証明される。
次に,SAT符号化に基づくSCMRの最適解法を提案する。
第3に,ノード分割経路の問題を解くために,グリージーアルゴリズムを利用してSCMRを効率的に緩和する手法を提案する。
最後に,本アルゴリズムを実回路と合成回路の大規模な集合上で実装し,評価する。
結果は、リラクゼーションが現実的なワークロードをコンパイルするための強力なツールであることを示唆している。
緩和に基づくアルゴリズムは、最適なアルゴリズム(数分で数万のゲートを持つインスタンスを解決)よりも桁違いに高速であるが、高品質な解を見つけ、様々なベンチマークスイートから168個の回路のうち55個まで理論的に低い値が得られる。
関連論文リスト
- Exploring the Potential of Qutrits for Quantum Optimization of Graph
Coloring [0.0]
Qutritsは、短期デバイス上のいくつかの問題を解決するのに役立つかもしれない。
我々はPennyLaneを用いてノイズレスシミュレーションを行い、量子ビットベースのQAOAに対する定式化を比較する。
この研究は、クォートリットが近距離デバイス上のいくつかの問題を解決するのに有用であることを示しているが、ノイズの多い環境におけるその可能性を評価するにはさらなる作業が必要であることを示唆している。
論文 参考訳(メタデータ) (2023-08-15T21:31:37Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳(メタデータ) (2023-06-14T13:44:35Z) - Qubit Mapping and Routing via MaxSAT [6.711547274386115]
短期量子コンピューティングにおける重要な問題は、量子ビット間の接続が限られている物理デバイスに論理回路を配置することである。
QMRを可能な限り最適に解いて追加ノイズの量を減らすことが重要であり、量子的に無駄になる可能性がある。
本稿では,最大満足度(MAXSAT)の低減によるQMR問題の最適解法を提案する。
論文 参考訳(メタデータ) (2022-08-29T15:39:04Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳(メタデータ) (2022-06-30T03:15:23Z) - Improving Quantum Computation by Optimized Qubit Routing [0.0]
スワップ挿入による量子ビットルーティングのための高品質な分解手法を提案する。
この最適化問題は、特定の量子ハードウェアに量子アルゴリズムをコンパイルする文脈で発生する。
本稿では,統合割当問題とトークンスワップ問題に対する数値計算結果について述べる。
論文 参考訳(メタデータ) (2022-06-02T20:32:18Z) - Near-Optimal Fidelity in Quantum Circuits through Incorporating
Efficient Real-time Error Based Heuristics in Compiler Mappings [0.0]
本稿では,リアルタイムのエラーフィードバックとデバイス接続情報を組み込む効率的な手法の発見に焦点をあてる。
我々のベストアプローチは、1つのベースラインとtextbf1.934x(平均)よりも、ランダムベンチマークの他のベースラインよりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-04-18T20:06:44Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳(メタデータ) (2022-01-06T21:02:30Z) - OMPQ: Orthogonal Mixed Precision Quantization [64.59700856607017]
混合精度量子化は、ハードウェアの多重ビット幅演算を利用して、ネットワーク量子化の全ポテンシャルを解き放つ。
本稿では、整数プログラミングの損失と高い相関関係にあるネットワーク性の概念であるプロキシメトリックを最適化することを提案する。
このアプローチは、量子化精度にほとんど妥協することなく、検索時間と必要なデータ量を桁違いに削減する。
論文 参考訳(メタデータ) (2021-09-16T10:59:33Z) - Optimal qubit assignment and routing via integer programming [0.22940141855172028]
論理量子回路を2ビット接続に制限のあるハードウェアにマッピングする問題を考察する。
我々はこの問題を2変数のネットワークフロー定式化を用いて整数線形プログラムとしてモデル化する。
本稿では,回路の忠実度,全深度,クロストークの尺度などのコスト関数について考察する。
論文 参考訳(メタデータ) (2021-06-11T15:02:26Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳(メタデータ) (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。