論文の概要: Quadratic Sums-of-Powers for Fixed-Parameter Tractable Quantum-Circuit Simulation

• arxiv url: http://arxiv.org/abs/2605.29944v1
• Date: Thu, 28 May 2026 13:54:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-30 02:45:56.367936
• Title: Quadratic Sums-of-Powers for Fixed-Parameter Tractable Quantum-Circuit Simulation
• Title（参考訳）: 固定パラメータトラクタブル量子回路シミュレーションのための2次出力推定法
• Authors: Alexis de Colnet, Floris Geerts, Rihan Hai, Alfons Laarman, Joon Hyung Lee, Guillermo A. Pérez,
• Abstract要約: 難易度を最も正確に管理する構造量は、経路可変グラフのランク幅であることを示す。 このランク幅と回路サイズでのみ指数関数となる時間における振幅を評価するアルゴリズムを提案する。 新しい方法は、アダマールと対角ゲートから作られた全ての回路、特にクリフォード+T上の回路に適用される。
• 参考スコア（独自算出の注目度）: 17.91644278251664
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Strongly simulating a quantum circuit, that is, computing an output amplitude, amounts to summing the circuit's Feynman paths, a weighted count over assignments to the Boolean ``path'' variables. The circuit's gates induce correlations among these variables, forming a graph whose structure determines the hardness of the simulation task. This sum-of-powers viewpoint underlies recent simulators built on knowledge-representation tools from artificial intelligence, namely binary decision diagrams and weighted model counting. We show that the structural quantity most accurately governing the difficulty is the rank-width of the path-variable graph, and we give an algorithm that evaluates the amplitude in time that is exponential only in this rank-width and polynomial in the circuit size. Rank-width can be far smaller than the widths that control competing methods: as corollaries, our algorithm reproduces a recent decision-diagram simulation breakthrough as a special case and matches the Markov--Shi tensor-network contraction bound. To complement this, we exhibit circuit families on which our algorithm provably beats both competing methods. The new method applies to every circuit built from Hadamard and diagonal gates, in particular to circuits over Clifford+T. In practical terms, general-purpose decision-diagram and model-counting tools can serve as the workhorse, with our specialized algorithm dispatched to exploit a small rank-width of the associated graph when it is present.
• Abstract（参考訳）: 量子回路、すなわち出力振幅の計算を強くシミュレートすると、回路のファインマンパス(Boolean ``path''変数への割り当てに対する重み付きカウント)を和らげることになる。 回路のゲートはこれらの変数間の相関を誘導し、その構造がシミュレーションタスクの硬さを決定するグラフを形成する。 この総和の観点は、人工知能の知識表現ツール、すなわち二分決定図と重み付きモデル計数に基づいて構築された最近のシミュレータに基づいている。 この困難さを最も正確に管理する構造量はパス変数グラフのランク幅であり、回路サイズにおいてこのランク幅と多項式のみ指数関数である時間における振幅を評価するアルゴリズムを提供する。 ランク幅は競合する手法を制御する幅よりも遥かに小さく、このアルゴリズムは最近の決定ダイアグラムシミュレーションのブレークスルーを特別なケースとして再現し、マルコフ-シーテンソル-ネットワークの収縮境界と一致する。 これを補完するために、我々は、アルゴリズムが競合する手法を確実に打ち負かす回路ファミリを示す。 この新しい手法は、アダマールと対角ゲートから作られた全ての回路、特にクリフォード+T上の回路に適用される。 実用面では、汎用的な意思決定図とモデルカウントツールがワークホースとして機能し、我々の専門アルゴリズムは、関連するグラフの小さなランク幅を利用するために派遣される。

関連論文リスト

• Breaking the Treewidth Barrier in Quantum Circuit Simulation with Decision Diagrams [8.586836962892443]
  この研究は、著者のサブセットによってCAV 2025で提案された決定図に基づくシミュレーション手法であるFeynmanDDを厳密に分析する。 任意の単一ビットゲートをアダマールゲートとTゲートの列に拡張するためにSolovay-Kitaevアルゴリズムを用いる場合、この手法は効率的であることを示す。
  論文  参考訳（メタデータ） (2025-10-08T08:58:58Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  量子学習理論の最近の進歩は、様々な古典的な入力によって生成された測定データから、大きな量子ビット回路の線形特性を効率的に学習できるのか? 我々は、小さな予測誤差を達成するためには、$d$で線形にスケーリングするサンプルの複雑さが必要であることを証明し、それに対応する計算複雑性は、dで指数関数的にスケールする可能性がある。 そこで本研究では,古典的影と三角展開を利用したカーネルベースの手法を提案し,予測精度と計算オーバーヘッドとのトレードオフを制御可能とした。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Automatically Identifying Local and Global Circuits with Linear Computation Graphs [45.760716193942685]
  Sparse Autoencoders (SAEs) と Transcoders と呼ばれる変種を用いた回路発見パイプラインを導入する。 本手法は各ノードの因果効果を計算するために線形近似を必要としない。 GPT-2 Small: Bracket, induction, Indirect Object Identification circuits の3種類の回路を解析する。
  論文  参考訳（メタデータ） (2024-05-22T17:50:04Z)
• Simulation of Graph Algorithms with Looped Transformers [6.0465914748433915]
  理論的観点から, グラフ上のアルゴリズムをシミュレートするトランスフォーマーネットワークの能力について検討する。 このアーキテクチャは、Dijkstraの最も短い経路のような個々のアルゴリズムをシミュレートできることを示す。 付加的なアテンションヘッドを利用する場合のチューリング完全度を一定幅で示す。
  論文  参考訳（メタデータ） (2024-02-02T02:48:03Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  量子コンピューティングは、カーネルマシンが量子カーネルを利用してデータ間の類似度を表現できるようにすることで、機械学習モデルを強化することができる。 本稿では,ニューラルアーキテクチャ検索やAutoMLと同じような最適化手法を用いて,この問題に対するアプローチを提案する。 その結果、高エネルギー物理問題に対する我々のアプローチを検証した結果、最良のシナリオでは、手動設計のアプローチに関して、テストの精度を一致または改善できることが示された。
  論文  参考訳（メタデータ） (2022-09-22T16:42:14Z)
• Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation [1.2704529528199062]
  量子回路シミュレーションにおける重要な問題の1つは、縮退木の構築である。 本稿では,最適な縮尺木を構築するための新しい時間アルゴリズムを提案する。 提案手法は、試験された量子回路の大部分において、優れた結果が得られることを示す。
  論文  参考訳（メタデータ） (2022-09-07T02:50:30Z)
• Simulation Paths for Quantum Circuit Simulation with Decision Diagrams [72.03286471602073]
  決定図を用いて量子回路をシミュレートする際に選択される経路の重要性について検討する。 我々は、専用のシミュレーションパスを調査できるオープンソースのフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-03-01T19:00:11Z)
• Machine Learning Optimization of Quantum Circuit Layouts [63.55764634492974]
  本稿では量子回路マッピングQXXとその機械学習バージョンQXX-MLPを紹介する。 後者は、レイアウトされた回路の深さが小さくなるように最適なQXXパラメータ値を自動的に推論する。 近似を用いてレイアウト法を学習可能な経験的証拠を提示する。
  論文  参考訳（メタデータ） (2020-07-29T05:26:19Z)

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

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