論文の概要: Procedurally Optimised ZX-Diagram Cutting for Efficient T-Decomposition in Classical Simulation

• arxiv url: http://arxiv.org/abs/2403.10964v2
• Date: Mon, 12 Aug 2024 11:20:40 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-13 23:48:12.726290
• Title: Procedurally Optimised ZX-Diagram Cutting for Efficient T-Decomposition in Classical Simulation
• Title（参考訳）: 古典シミュレーションにおける効率的なT分解のための手続き最適化ZX-Diagram切削
• Authors: Matthew Sutcliffe, Aleks Kissinger,
• Abstract要約: 本稿では,ZX-ダイアグラムにおけるカットの最適パターンを見つけ,T数削減を最大化するための一般的な手順を提案する。 検証可能な回路が小さい場合、この手法は71%の時間で可能な限り最適なカットを実現できることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A quantum circuit may be strongly classically simulated with the aid of ZX-calculus by decomposing its $t$ T-gates into a sum of $2^{\alpha t}$ classically computable stabiliser terms. In this paper, we introduce a general procedure to find an optimal pattern of vertex cuts in a ZX-diagram to maximise its T-count reduction at the cost of the fewest cuts. Rather than reducing a Clifford+T diagram based on a fixed routine of decomposing its T-gates directly (as is the conventional approach), we focus instead on taking advantage of certain patterns and structures common to such circuits to, in effect, design by automatic procedure an arrangement of spider decompositions that is optimised for the particular circuit. In short, this works by assigning weights to vertices based on how many T-like gates they are blocking from fusing/cancelling and then appropriately propagating these weights through any neighbours which are then blocking weighted vertices from fusing, and so on. Ultimately, this then provides a set of weightings on relevant nodes, which can then each be cut, starting from the highest weighted down. While this is a heuristic approach, we show that, for circuits small enough to verify, this method achieves the most optimal set of cuts possible $71\%$ of the time. Furthermore, there is no upper bound for the efficiency achieved by this method, allowing, in principle, an effective decomposition efficiency $\alpha\rightarrow0$ for highly structured circuits. Even applied to random pseudo-structured circuits (produced from CNOTs, phase gates, and Toffolis), we record the number of stabiliser terms required to reduce all T-gates, via our method as compared to that of the more conventional T-decomposition approaches (namely \cite{kissinger21}, with $\alpha\approx0.47$), and show consistent improvements of orders of magnitude, with an effective efficiency $0.1\lesssim\alpha\lesssim0.2$.
• Abstract（参考訳）: 量子回路は、古典的に計算可能な安定化項の和に$t$T-ゲートを分解することで、ZX-計算の助けを借りて古典的に強くシミュレートすることができる。 本稿では,ZX-ダイアグラムにおける頂点カットの最適パターンを見つけるための一般的な手順を紹介し,最も少ないカットのコストでTカウントの削減を最大化する。 Tゲートを直接分解する固定ルーチンに基づいてクリフォード+Tダイアグラムを縮小する代わりに、そのような回路に共通する特定のパターンや構造を利用して、実質的には特定の回路に最適化されたクモ分解の配列を自動的に設計する。 要するに、これはウェイトをバーチカンに割り当てて、ブロックしているT字型のゲートの数に基づいて、そのウェイトを近隣のあらゆる場所に適切に伝播させ、重み付きバーチカンをヒュージングからブロックするなどして機能する。 最終的に、これは関連するノードに一連の重み付けを提供し、各ノードをカットして、最上位の重み付けから始めることができる。 これはヒューリスティックなアプローチであるが、検証可能な回路が十分小さい場合、この手法は711\%の時間で可能な限り最適なカットを実現できることを示す。 さらに、この方法によって達成される効率の上限はなく、原理的には、高度に構造化された回路に対して有効分解効率$\alpha\rightarrow0$が可能である。 ランダムな擬構造回路(CNOT、位相ゲート、Toffolisから生成される)にも適用しても、従来のT-分解アプローチ(つまり$\alpha\approx0.47$)と比較して、T-ゲートを減らすのに必要な安定化項の数が記録され、有効効率は$0.1\lesssim\alpha\lesssim0.2$である。

関連論文リスト

• Finding Transformer Circuits with Edge Pruning [71.12127707678961]
  自動回路発見の効率的かつスケーラブルなソリューションとしてエッジプルーニングを提案する。 本手法は,従来の手法に比べてエッジ数の半分未満のGPT-2の回路を探索する。 その効率のおかげで、Edge PruningをCodeLlama-13Bにスケールしました。
  論文  参考訳（メタデータ） (2024-06-24T16:40:54Z)
• Causal flow preserving optimisation of quantum circuits in the ZX-calculus [0.0]
  本稿では,非クリフォードゲート数と2ビットゲート数の最小化を目的とした最適化アルゴリズムを提案する。 回路をZXダイアグラムに変換することで、回路に戻る前に単純化することができる。 QFT回路を最適化するための特に効果的な戦略も注目されており、非クリフォードゲートに対して正確に1つの2ビットゲートとなる。
  論文  参考訳（メタデータ） (2023-12-05T14:24:44Z)
• Reduced Contraction Costs of Corner-Transfer Methods for PEPS [0.0]
  無限に投影された絡み合ったペア状態の収縮を抑えるための最優先計算コストを削減できる近似法を提案する。 計算コストの改善により、大きな結合次元の計算が可能となり、そのポテンシャルを拡大して課題を解決することができる。
  論文  参考訳（メタデータ） (2023-06-14T02:54:12Z)
• Fast quantum circuit cutting with randomized measurements [0.0]
  本稿では,単一デバイス上で利用可能な物理量子ビット数を超えて,量子計算のサイズを拡大する手法を提案する。 これは、大きな回路の出力状態を異なるデバイス間で分離可能な状態として表すために、無作為に計測・準備チャネルを挿入することで達成される。
  論文  参考訳（メタデータ） (2022-07-29T15:13:04Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。 我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
  論文  参考訳（メタデータ） (2021-11-01T15:43:36Z)
• Depth Optimized Ansatz Circuit in QAOA for Max-Cut [0.9670182163018803]
  我々は$O(Delta cdot n2)$ greedyアルゴリズムを提案する。 このアルゴリズムは,Max-Cut に対する QAOA の各イテレーションにおける成功確率が 10 倍近いことを数値的に示す。
  論文  参考訳（メタデータ） (2021-10-09T19:45:12Z)
• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions [0.0]
  量子回路の古典的強大なシミュレーションのための拡張手法を提案する。 この手法は、ZX計算に基づく自動単純化戦略と、安定化器の和法を組み合わせたものである。
  論文  参考訳（メタデータ） (2021-09-02T16:42:52Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)

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

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