論文の概要: Quantum Circuit Cutting: Complexity and Optimization
- arxiv url: http://arxiv.org/abs/2604.23700v1
- Date: Sun, 26 Apr 2026 13:30:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-28 17:12:07.506399
- Title: Quantum Circuit Cutting: Complexity and Optimization
- Title（参考訳）: 量子回路切断の複雑さと最適化
- Authors: Yuval Idan, Eitan Zahavi, Elad Mentovich, Eliahu Cohen, Shmuel Zaks,
- Abstract要約: 現在の雑音の中間スケール量子(NISQ)年代は、重大な誤差とノイズによって特徴づけられる。
量子回路切断は これらの制約に対処する 有望なツールとして現れました
この研究は、カット配置の複雑性理論的特徴付けと、境界サイズの分解の実用的な解法を提供する。
- 参考スコア（独自算出の注目度）: 0.2283561089098416
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The current noisy intermediate-scale quantum (NISQ) era is characterized by substantial errors and noise, which limit the practical feasibility of deep, many-qubit circuits. To address these constraints, quantum circuit cutting has emerged as a promising tool. Recently, there has been significant research on methods for performing such cutting effectively. In this work, the duality between quantum circuits and classical graphs - specifically, directed acyclic graphs (dags) - is leveraged to analyze the complexity of finding an optimal circuit-cutting configuration that minimizes the number of cuts. After developing a rigorous graph-theoretic framework, the complexity of identifying cut locations that partition a given quantum circuit into smaller fragments is characterized. The corresponding graph-combinatorial task is then defined, and the resulting partition problem is shown to be NP-complete. Furthermore, even a simplified version of the problem, restricted to circuits composed only of one- and two-qubit gates, is shown to be NP-complete. Finally, based on these constraints, an algorithm grounded in satisfiability modulo theories (SMT) is proposed to find optimal cuts when the number of qubits per partition is bounded. This work therefore provides a complexity-theoretic characterization of cut placement and a practical solver for bounded-size decompositions.
- Abstract（参考訳）: 現在のノイズの多い中間スケール量子(NISQ)時代は、深い多ビット回路の実用可能性を制限する重大な誤差とノイズによって特徴づけられる。
これらの制約に対処するため、量子回路切断は有望なツールとして登場した。
近年,このような切削を効果的に行う方法に関する研究が盛んに行われている。
本研究では、量子回路と古典グラフの双対性(特に有向非巡回グラフ(ダグ))を利用して、カット数を最小限に抑える最適な回路切断構成を見つける複雑さを分析する。
厳密なグラフ理論フレームワークを開発した後、与えられた量子回路をより小さな断片に分割する切断された位置を特定する複雑さが特徴づけられる。
対応するグラフ合成タスクが定義され、結果として生じる分割問題はNP完全であることが示される。
さらに,1ビットと2ビットのゲートのみで構成される回路に制限された簡易版でさえNP完全であることが示されている。
最後に、これらの制約に基づいて、分割当たりの量子ビット数が有界であるときに最適なカットを求めるために、SMT(Saturfiability modulo theory)に基づくアルゴリズムを提案する。
この研究は、切断された配置の複雑性理論的な特徴づけと、境界サイズの分解の実用的な解法を提供する。
関連論文リスト
- A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
分散量子最適化のための構造認識フレームワークを提案する。
検索スペースが$N$の場合、我々のフレームワークはプロセッサやセパレータに依存した要素に対して$O(sqrtN)$クエリ複雑性を達成する。
構造を考慮した分解は、量子ネットワーク上でのスケーラブルな分散量子最適化に実践的な道をもたらすことを示す。
論文 参考訳（メタデータ） (2026-03-08T15:15:52Z) - Algebraic Reduction to Improve an Optimally Bounded Quantum State Preparation Algorithm [0.6875312133832078]
n$-qubit量子状態の合成は、多くの量子アルゴリズムのための横断的なサブルーチンである。
より単純な代数的分解は、所望状態の実際の部分の準備を複素状態から分離するために提案される。
複雑性の低減は、元の分解で3つではなく、各一様に制御されたゲートに対して1つの演算子$$を使用するためである。
論文 参考訳（メタデータ） (2026-02-06T09:40:09Z) - Spatial and temporal circuit cutting with hypergraphic partitioning [0.0]
本稿では,空間的シナリオと時間的シナリオの両方に適したハイパーグラフに基づく回路切断手法を提案する。
量子回路を高レベルハイパーグラフとしてモデル化することにより、Stoer-Wagner、Fiduccia-Mattheyses、Kernighan-Linなどの分割を適用できる。
論文 参考訳（メタデータ） (2025-04-12T20:31:07Z) - Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
CNOT回路は一般的な量子回路の共通構成ブロックである。
本稿では,CNOTゲート数を最適化するための最先端アルゴリズムを提案する。
シミュレーション評価により、提案手法はほとんど常に有用であることが示され、CNOTゲートの数を最大10%削減する。
論文 参考訳（メタデータ） (2024-08-07T19:51:22Z) - Full Characterization of the Depth Overhead for Quantum Circuit Compilation with Arbitrary Qubit Connectivity Constraint [5.755460769073285]
量子コンピュータのいくつかの物理的実装では、2量子ビット演算は特定の量子ビットのペアにのみ適用できる。
本稿では、基礎となる制約グラフのルーティング数によって、深さオーバーヘッドを完全に特徴づける。
論文 参考訳（メタデータ） (2024-02-04T08:29:41Z) - A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method [39.671915199737846]
量子格子ボルツマン法(QLBM)における非圧縮性ナビエ-ストークス方程式の多重回路アルゴリズムを提案する。
提案法は2次元蓋駆動キャビティフローに対して検証および実証を行った。
論文 参考訳（メタデータ） (2024-01-20T15:32:01Z) - FragQC: An Efficient Quantum Error Reduction Technique using Quantum
Circuit Fragmentation [4.2754140179767415]
誤差確率が一定の閾値を超えると、量子回路をサブ回路に切断するソフトウェアツールであるFragQCを提示する。
回路を切断せずに直接実行した場合の忠実度は14.83%増加し、8.45%が最先端のICP法である。
論文 参考訳（メタデータ） (2023-09-30T17:38:31Z) - Investigating the effect of circuit cutting in QAOA for the MaxCut
problem on NISQ devices [36.32934805738396]
ノイズ中間スケール量子(NISQ)デバイスは、量子ビット数の制限と短いデコヒーレンス時間によって制限される。
量子回路切断は、大きな量子回路の実行を複数の小さな量子回路の実行に分解する。
論文 参考訳（メタデータ） (2023-02-03T15:02:28Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z) - Improving the Performance of Deep Quantum Optimization Algorithms with
Continuous Gate Sets [47.00474212574662]
変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。
本稿では,QAOAの回路深度依存性能について実験的に検討する。
この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
論文 参考訳（メタデータ） (2020-05-11T17:20:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。