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
• Authors: Matthew Sutcliffe, Aleks Kissinger,
• 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

• 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)
• 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)
• 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.