Dynamic T-decomposition for classical simulation of quantum circuits

• URL: http://arxiv.org/abs/2412.17182v1
• Date: Sun, 22 Dec 2024 22:51:23 GMT
• Title: Dynamic T-decomposition for classical simulation of quantum circuits
• Authors: Wira Azmoon Ahmad, Matthew Sutcliffe,
• Abstract summary: 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.
• Score: 0.0
• License:
• Abstract: It is known that a quantum circuit may be simulated with classical hardware via stabilizer state (T-)decomposition in $O(2^{\alpha t})$ time, given $t$ non-Clifford gates and a decomposition efficiency $\alpha$. The past years have seen a number of papers presenting new decompositions of lower $\alpha$ to reduce this runtime and enable simulation of ever larger circuits. More recently, it has been demonstrated that well placed applications of apparently weaker (higher $\alpha$) decompositions can in fact result in better overall efficiency when paired with the circuit simplification strategies of ZX-calculus. In this work, we take the most generalized T-decomposition (namely vertex cutting), 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 $\alpha_{\text{eff}}\ll1$. By taking into account this broader scope of the ZX-diagram and incorporating the simplification facilitated by the well-motivated cuts, we derive a handful of efficient T-decompositions whose applicabilities are relatively frequent. In benchmarking these new 'dynamic' decompositions against the existing alternatives, we observe a significant reduction in overall $\alpha$ and hence overall runtime for classical simulation, particularly for certain common circuit classes.

Related papers

• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose arbitrary exponentials into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions. We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums [0.9208007322096532]
  We show that a family of quantum circuits can in fact be simulated in time via symbolic path integrals. We hence resolve an open conjecture about the efficient simulability of this class of circuits-time.
  arXiv  Detail & Related papers  (2024-08-05T18:56:20Z)
• Procedurally Optimised ZX-Diagram Cutting for Efficient T-Decomposition in Classical Simulation [0.0]
  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.
  arXiv  Detail & Related papers  (2024-03-16T16:18:43Z)
• Fast classical simulation of quantum circuits via parametric rewriting in the ZX-calculus [0.0]
  ZX-calculus is an algebraic formalism that allows quantum computations to be simplified via a small number of simple rewrite rules. We show that it is possible to perform the final stage of classical simulation quickly utilising a high degree of GPU parallelism.
  arXiv  Detail & Related papers  (2024-03-11T14:44:59Z)
• A Circuit Domain Generalization Framework for Efficient Logic Synthesis in Chip Design [92.63517027087933]
  A key task in Logic Synthesis (LS) is to transform circuits into simplified circuits with equivalent functionalities. To tackle this task, many LS operators apply transformations to subgraphs -- rooted at each node on an input DAG -- sequentially. We propose a novel data-driven LS operator paradigm, namely PruneX, to reduce ineffective transformations.
  arXiv  Detail & Related papers  (2023-08-22T16:18:48Z)
• Model based Multi-agent Reinforcement Learning with Tensor Decompositions [52.575433758866936]
  This paper investigates generalisation in state-action space over unexplored state-action pairs by modelling the transition and reward functions as tensors of low CP-rank. Experiments on synthetic MDPs show that using tensor decompositions in a model-based reinforcement learning algorithm can lead to much faster convergence if the true transition and reward functions are indeed of low rank.
  arXiv  Detail & Related papers  (2021-10-27T15:36:25Z)
• 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)
• Investigating the Scalability and Biological Plausibility of the Activation Relaxation Algorithm [62.997667081978825]
  Activation Relaxation (AR) algorithm provides a simple and robust approach for approximating the backpropagation of error algorithm. We show that the algorithm can be further simplified and made more biologically plausible by introducing a learnable set of backwards weights. We also investigate whether another biologically implausible assumption of the original AR algorithm -- the frozen feedforward pass -- can be relaxed without damaging performance.
  arXiv  Detail & Related papers  (2020-10-13T08:02:38Z)
• Concurrent Alternating Least Squares for multiple simultaneous Canonical Polyadic Decompositions [2.3513645401551333]
  We introduce the Concurrent ALS algorithm and library, which offers an interface to Matlab. We show how multiple decompositions of the same tensor can be fused together at the algorithmic level to increase the arithmetic intensity. Experimental results on artificial and real datasets demonstrate a shorter time to completion due to increased arithmetic intensity.
  arXiv  Detail & Related papers  (2020-10-09T16:55:46Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19:00:00Z)

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.