論文の概要: Breaking the Treewidth Barrier in Quantum Circuit Simulation with Decision Diagrams

• arxiv url: http://arxiv.org/abs/2510.06775v1
• Date: Wed, 08 Oct 2025 08:58:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.374969
• Title: Breaking the Treewidth Barrier in Quantum Circuit Simulation with Decision Diagrams
• Title（参考訳）: 決定図を用いた量子回路シミュレーションにおける木幅バリアの破壊
• Authors: Bin Cheng, Ziyuan Wang, Ruixuan Deng, Jianxin Chen, Zhengfeng Ji,
• Abstract要約: この研究は、著者のサブセットによってCAV 2025で提案された決定図に基づくシミュレーション手法であるFeynmanDDを厳密に分析する。 任意の単一ビットゲートをアダマールゲートとTゲートの列に拡張するためにSolovay-Kitaevアルゴリズムを用いる場合、この手法は効率的であることを示す。
• 参考スコア（独自算出の注目度）: 8.586836962892443
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Classical simulation of quantum circuits is a critical tool for validating quantum hardware and probing the boundary between classical and quantum computational power. Existing state-of-the-art methods, notably tensor network approaches, have computational costs governed by the treewidth of the underlying circuit graph, making circuits with large treewidth intractable. This work rigorously analyzes FeynmanDD, a decision diagram-based simulation method proposed in CAV 2025 by a subset of the authors, and shows that the size of the multi-terminal decision diagram used in FeynmanDD is exponential in the linear rank-width of the circuit graph. As linear rank-width can be substantially smaller than treewidth and is at most larger than the treewidth by a logarithmic factor, our analysis demonstrates that FeynmanDD outperforms all tensor network-based methods for certain circuit families. We also show that the method remains efficient if we use the Solovay-Kitaev algorithm to expand arbitrary single-qubit gates to sequences of Hadamard and T gates, essentially removing the gate-set restriction posed by the method.
• Abstract（参考訳）: 量子回路の古典的シミュレーションは、量子ハードウェアを検証し、古典的および量子的計算パワーの境界を探索するための重要なツールである。 既存の最先端の手法、特にテンソルネットワークアプローチは、基礎となる回路グラフのツリー幅に支配される計算コストを持ち、大きなツリー幅の回路を抽出することができる。 この研究は、著者のサブセットによってCAV 2025で提案された決定図に基づくシミュレーション手法であるFeynmanDDを厳密に分析し、FeynmanDDで使用される多項決定図のサイズが回路グラフの線形ランク幅で指数関数的であることを示す。 線形階数幅は木幅よりもかなり小さく、対数係数により木幅よりもかなり大きいため、FeynmanDDは特定の回路系に対してテンソルネットワークに基づく手法よりも優れていることを示す。 また,Solovay-Kitaev アルゴリズムを用いて任意の単一ビットゲートを Hadamard および T ゲートの列に拡張し,本手法が提案するゲートセット制限を本質的に除去した場合,この手法は効率的であることを示す。

関連論文リスト

• Practical Application of the Quantum Carleman Lattice Boltzmann Method in Industrial CFD Simulations [44.99833362998488]
  この研究は、格子ボルツマン法(LBM)に基づくCFDへのハイブリッド量子古典的アプローチの実用的な数値評価を提示する。 本手法は, 異なる境界条件, 周期性, バウンスバック, 移動壁を有する3つのベンチマークケースで評価した。 提案手法の有効性を検証し,10～3ドル程度の誤差忠実度と,実際の量子状態サンプリングに十分な確率を達成できた。
  論文  参考訳（メタデータ） (2025-04-17T15:41:48Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。 完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。 ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
  論文  参考訳（メタデータ） (2025-01-02T05:06:16Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  量子学習理論の最近の進歩は、様々な古典的な入力によって生成された測定データから、大きな量子ビット回路の線形特性を効率的に学習できるのか? 我々は、小さな予測誤差を達成するためには、$d$で線形にスケーリングするサンプルの複雑さが必要であることを証明し、それに対応する計算複雑性は、dで指数関数的にスケールする可能性がある。 そこで本研究では,古典的影と三角展開を利用したカーネルベースの手法を提案し,予測精度と計算オーバーヘッドとのトレードオフを制御可能とした。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Efficient Quantum Circuits for Non-Unitary and Unitary Diagonal Operators with Space-Time-Accuracy trade-offs [1.0749601922718608]
  ユニタリおよび非ユニタリ対角作用素は量子アルゴリズムの基本的な構成要素である。 本稿では,一元対角演算子と非単元対角演算子を効率よく調整可能な量子回路で実装する一般手法を提案する。
  論文  参考訳（メタデータ） (2024-04-03T15:42:25Z)
• 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)
• Simulation Paths for Quantum Circuit Simulation with Decision Diagrams [72.03286471602073]
  決定図を用いて量子回路をシミュレートする際に選択される経路の重要性について検討する。 我々は、専用のシミュレーションパスを調査できるオープンソースのフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-03-01T19:00:11Z)
• Simulation of Quantum Computing on Classical Supercomputers [23.350853237013578]
  本研究では,非方向グラフの切断エッジに基づくスキームを提案する。 このスキームは、木幅の大きな無向グラフのエッジをカットし、多くの無向グラフを得る。 4096コアのスーパーコンピュータ上で120量子3規則QAOAアルゴリズムをシミュレートできる。
  論文  参考訳（メタデータ） (2020-10-28T13:26:41Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。 線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。 実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
  論文  参考訳（メタデータ） (2020-06-16T21:56:22Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。