Procedurally Optimised ZX-Diagram Cutting for Efficient T-Decomposition in Classical Simulation

• URL: http://arxiv.org/abs/2403.10964v2
• Date: Mon, 12 Aug 2024 11:20:40 GMT
• Title: Procedurally Optimised ZX-Diagram Cutting for Efficient T-Decomposition in Classical Simulation
• Abstract summary: We introduce a general procedure to find an optimal pattern of cuts in a ZX-diagram to maximise its T-count reduction. We show that, for circuits small enough to verify, this method achieves the most optimal set of cuts possible $71%$ of the time.
• Score: 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$.

Related papers

• Penalty-free quantum optimization applied to lattice protein folding [0.6999740786886536]
  We introduce an analog iterative local-search scheme, with which we successfully fold lattice proteins with lengths up to $N=14$ using local subgraphs with at most 26 qubits.<n>We validate this approach through classical simulations of the quantum circuits for lattice proteins of lengths $N=4$ and $N=6$.<n>To explore larger systems, we further introduce an iterative local-search scheme, with which we successfully fold lattice proteins with lengths up to $N=14$ using local subgraphs with at most 26 qubits.
  arXiv  Detail & Related papers  (2026-06-01T11:34:07Z)
• Optimal Approximation of Single Qubit Rotations within a Quantum Circuit [0.12599533416395764]
  Fault-tolerant quantum computing typically requires the transpilation of arbitrary quantum circuits into a finite, universal gate set, such as Clifford+T.<n>As a baseline, Diagonal approximation can be used for single-qubit Pauli rotations.<n>In this work, we present a linear-time algorithm that guarantees an optimal solution to this problem.
  arXiv  Detail & Related papers  (2026-05-10T17:38:53Z)
• Quantum Circuit Pre-Synthesis: Learning Local Edits to Reduce $T$-count [1.6195650245658724]
  Local synthesis approaches are commonly used to compile large circuits by decomposing them into substructures.<n>We propose textscQ-PreSyn, a strategy that, given a set of local edits preserving circuit equivalence, uses a RL agent to identify effective sequences.<n> Experimental results show up to a $20%$ reduction in $T$-count on circuits with up to 25 qubits.
  arXiv  Detail & Related papers  (2026-01-27T15:58:05Z)
• Scaling Bidirectional Spans and Span Violations in Attention Mechanism [5.755498052202004]
  canonical $O(N2)$ Transformer remains the empirical performance frontier in sequence modeling.<n>We propose an optimization framework that leverages an asymmetric projection to decompose the backward-pass gradients into parallel spans.<n>We demonstrate that selectively scaling these components, focusing primarily on $0th$ order bidirectional parallel spans, yields the most effective learning signal.
  arXiv  Detail & Related papers  (2025-12-15T07:03:24Z)
• PT$^2$-LLM: Post-Training Ternarization for Large Language Models [52.4629647715623]
  Large Language Models (LLMs) have shown impressive capabilities across diverse tasks, but their large memory and compute demands hinder deployment.<n>We propose PT$2$-LLM, a post-training ternarization framework tailored for LLMs.<n>At its core is an Asymmetric Ternary Quantizer equipped with a two-stage refinement pipeline.
  arXiv  Detail & Related papers  (2025-09-27T03:01:48Z)
• Generalized Gradient Norm Clipping & Non-Euclidean $(L_0,L_1)$-Smoothness [51.302674884611335]
  This work introduces a hybrid non-Euclidean optimization method which generalizes norm clipping by combining steepest descent and conditional gradient approaches.<n>We discuss how to instantiate the algorithms for deep learning and demonstrate their properties on image classification and language modeling.
  arXiv  Detail & Related papers  (2025-06-02T17:34:29Z)
• Optimal T depth quantum circuits for implementing arbitrary Boolean functions [4.730360540444164]
  We present a generic construction to obtain an optimal T depth quantum circuit for any arbitrary $n$-input $m$-output Boolean function $f.<n>We achieve this by inspecting the Algebraic Normal Form (ANF) of a Boolean function.<n>The implications of our results are highlighted explaining the provable lower bounds on S-box and block cipher implementations.
  arXiv  Detail & Related papers  (2025-06-02T11:07:54Z)
• Optimal Haar random fermionic linear optics circuits [0.0]
  We introduce optimal algorithms to sample over the non-particle-preserving (active) and particle-preserving (passive) FLO Haar measures.<n>We also provide quantum circuits to sample Clifford FLO with an optimal $Theta(n2)$ gate count.
  arXiv  Detail & Related papers  (2025-05-30T04:52:40Z)
• Survival of the Optimized: An Evolutionary Approach to T-depth Reduction [2.089191490381739]
  We propose a Genetic Algorithm (GA)-based approach to discover near-optimal T-gate merge patterns across circuit layers. Our framework yields an average improvement of 1.2x across varying circuit sizes and T-gate densities.
  arXiv  Detail & Related papers  (2025-04-13T00:55:18Z)
• Dynamic T-decomposition for classical simulation of quantum circuits [0.0]
  It is known that a quantum circuit may be simulated with classical hardware via stabilizer state (T-)decomposition in $O (2alpha t)$ time. In this work, we take the most generalized T-decomposition, which achieves a poor efficiency of $alpha=1$, and identify common structures to which applying this can, after simplification via ZX-calculus rewriting, yield very strong effective efficiencies. We observe a significant reduction in overall $alpha$ and hence overall runtime for classical simulation, particularly for certain common circuit classes.
  arXiv  Detail & Related papers  (2024-12-22T22:51:23Z)
• High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization [0.8341988468339112]
  Resource-efficient and high-precision approximate synthesis of quantum circuits expressed in the Clifford+T gate set is vital for Fault-Tolerant quantum computing. We leverage search-based methods to first approximately diagonalize a unitary, then perform the inversion analytically. Our approach improves both the implementation precision and run time of synthesis algorithms by orders of magnitude when evaluated on unitaries from real quantum algorithms.
  arXiv  Detail & Related papers  (2024-08-31T12:10:32Z)
• Finding Transformer Circuits with Edge Pruning [71.12127707678961]
  We propose Edge Pruning as an effective and scalable solution to automated circuit discovery. Our method finds circuits in GPT-2 that use less than half the number of edges compared to circuits found by previous methods. Thanks to its efficiency, we scale Edge Pruning to CodeLlama-13B, a model over 100x the scale that prior methods operate on.
  arXiv  Detail & Related papers  (2024-06-24T16:40:54Z)
• Causal flow preserving optimisation of quantum circuits in the ZX-calculus [0.0]
  This paper introduces an optimisation algorithm aiming to minimise non-Clifford gate count and two-qubit gate count. By translating a circuit into a ZX-diagram it can be simplified before being extracted back into a circuit. A particularly effective strategy for optimising QFT circuits is also noted, resulting in exactly one two-qubit gate per non-Clifford gate.
  arXiv  Detail & Related papers  (2023-12-05T14:24:44Z)
• Reduced Contraction Costs of Corner-Transfer Methods for PEPS [0.0]
  We propose a pair of approximations that allows the leading order computational cost of contracting an infinite projected entangled-pair state to be reduced. The improvement in computational cost enables us to perform large bond dimension calculations, extending its potential to solve challenging problems.
  arXiv  Detail & Related papers  (2023-06-14T02:54:12Z)
• Fast quantum circuit cutting with randomized measurements [0.0]
  We propose a new method to extend the size of a quantum computation beyond the number of physical qubits available on a single device. This is accomplished by randomly inserting measure-and-prepare channels to express the output state of a large circuit as a separable state across distinct devices.
  arXiv  Detail & Related papers  (2022-07-29T15:13:04Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  We investigate non-batch optimization problems where the objective is an expectation over smooth loss functions. Our work builds on the STORM algorithm, in conjunction with a novel approach to adaptively set the learning rate and momentum parameters.
  arXiv  Detail & Related papers  (2021-11-01T15:43:36Z)
• Depth Optimized Ansatz Circuit in QAOA for Max-Cut [0.9670182163018803]
  We propose an $O(Delta cdot n2)$ greedy algorithm, where $Delta$ is the maximum degree of the graph, that finds a spanning tree of lower height. We numerically show that this algorithm achieves nearly 10 times increase in the probability of success for each iteration of QAOA for Max-Cut.
  arXiv  Detail & Related papers  (2021-10-09T19:45:12Z)
• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions [0.0]
  We introduce an enhanced technique for strong classical simulation of quantum circuits. This technique combines the sum-of-stabilisers' method with an automated simplification strategy based on the ZX-calculus.
  arXiv  Detail & Related papers  (2021-09-02T16:42:52Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. We show that the Gaussian sketching matrix can be drastically sparsified, significantly reducing the computational cost of sketching. We prove that Newton-LESS enjoys nearly the same problem-independent local convergence rate as Gaussian embeddings.
  arXiv  Detail & Related papers  (2021-07-15T17:33:05Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  In this work, we seek to balance the fact that attenuating step-size is required for exact convergence with the fact that constant step-size learns faster in time up to an error. Rather than fixing the minibatch the step-size at the outset, we propose to allow parameters to evolve adaptively.
  arXiv  Detail & Related papers  (2020-07-02T16:02:02Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  This paper analyzes the trajectories of gradient descent (SGD) We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
  arXiv  Detail & Related papers  (2020-06-19T14:11:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.