SymPhase: Phase Symbolization for Fast Simulation of Stabilizer Circuits

• URL: http://arxiv.org/abs/2311.03906v2
• Date: Wed, 22 Nov 2023 04:26:08 GMT
• Title: SymPhase: Phase Symbolization for Fast Simulation of Stabilizer Circuits
• Authors: Wang Fang and Mingsheng Ying
• Abstract summary: This paper proposes an efficient stabilizer circuit simulation algorithm that only traverses the circuit forward once. We introduce phase symbolization into stabilizer generators, which allows possible Pauli faults in the circuit to be accumulated explicitly as symbolic expressions. We show how to integrate symbolic phases into the stabilizer tableau and maintain them efficiently using bit-vector encoding.
• Score: 3.5664433935013165
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper proposes an efficient stabilizer circuit simulation algorithm that only traverses the circuit forward once. We introduce phase symbolization into stabilizer generators, which allows possible Pauli faults in the circuit to be accumulated explicitly as symbolic expressions in the phases of stabilizer generators. This way, the measurement outcomes are also symbolic expressions, and we can sample them by substituting the symbolic variables with concrete values, without traversing the circuit repeatedly. We show how to integrate symbolic phases into the stabilizer tableau and maintain them efficiently using bit-vector encoding. A new data layout of the stabilizer tableau in memory is proposed, which improves the performance of our algorithm (and other stabilizer simulation algorithms based on the stabilizer tableau). We implement our algorithm and data layout in a Julia package named SymPhase.jl, and compare it with Stim, the state-of-the-art simulator, on several benchmarks. We show that SymPhase.jl has superior performance in terms of sampling time, which is crucial for generating a large number of samples for further analysis.

Related papers

• 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)
• Stabilizer circuit verification [0.0]
  We propose a set of efficient classical algorithms to fully characterize and exhaustively verify stabilizer circuits. We provide an algorithm for checking the equivalence of stabilizer circuits. All of our algorithms provide relations of measurement outcomes among corresponding circuit representations.
  arXiv  Detail & Related papers  (2023-09-15T18:06:17Z)
• Speedy Contraction of ZX Diagrams with Triangles via Stabiliser Decompositions [0.30938904602244344]
  We use the ZX calculus to iteratively decompose magic states into stabiliser terms. We show that this technique greatly speeds up the simulation of quantum circuits involving multi-controlled gates. We also use our software to contract diagrams representing the gradient variance of parametrised quantum circuits.
  arXiv  Detail & Related papers  (2023-07-04T16:13:53Z)
• Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For Hidden Markov Models [70.26374282390401]
  Decoding the original signal (i.e., hidden chain) from the noisy observations is one of the main goals in nearly all HMM based data analyses. We present Quick Adaptive Ternary (QATS), a divide-and-conquer procedure which decodes the hidden sequence in polylogarithmic computational complexity.
  arXiv  Detail & Related papers  (2023-05-29T19:37:48Z)
• Performance Embeddings: A Similarity-based Approach to Automatic Performance Optimization [71.69092462147292]
  Performance embeddings enable knowledge transfer of performance tuning between applications. We demonstrate this transfer tuning approach on case studies in deep neural networks, dense and sparse linear algebra compositions, and numerical weather prediction stencils.
  arXiv  Detail & Related papers  (2023-03-14T15:51:35Z)
• Sampled Transformer for Point Sets [80.66097006145999]
  sparse transformer can reduce the computational complexity of the self-attention layers to $O(n)$, whilst still being a universal approximator of continuous sequence-to-sequence functions. We propose an $O(n)$ complexity sampled transformer that can process point set elements directly without any additional inductive bias.
  arXiv  Detail & Related papers  (2023-02-28T06:38:05Z)
• Improved Graph Formalism for Quantum Circuit Simulation [77.34726150561087]
  We show how to efficiently simplify stabilizer states to canonical form. We characterize all linearly dependent triplets, revealing symmetries in the inner products. Using our novel controlled-Pauli $Z$ algorithm, we improve runtime for inner product computation from $O(n3)$ to $O(nd2)$ where $d$ is the maximum degree of the graph.
  arXiv  Detail & Related papers  (2021-09-20T05:56:25Z)
• Stim: a fast stabilizer circuit simulator [0.0]
  Stim is a fast simulator for quantum stabilizer circuits. It can analyze a distance 100 surface code circuit in 15 seconds and then begin sampling full circuit shots at a rate of 1 kHz.
  arXiv  Detail & Related papers  (2021-03-03T06:21:21Z)
• Feynman-path type simulation using stabilizer projector decomposition of unitaries [10.307548042529874]
  We propose a classical simulation method for quantum circuits based on decomposing unitary gates into a sum of stabilizer projectors. By only decomposing the non-Clifford gates, we take advantage of the Gottesman-Knill theorem and build a bridge between stabilizer-based simulation and Feynman-path-type simulation.
  arXiv  Detail & Related papers  (2020-09-10T19:25:19Z)
• Learning Stabilizing Controllers for Unstable Linear Quadratic Regulators from a Single Trajectory [85.29718245299341]
  We study linear controllers under quadratic costs model also known as linear quadratic regulators (LQR) We present two different semi-definite programs (SDP) which results in a controller that stabilizes all systems within an ellipsoid uncertainty set. We propose an efficient data dependent algorithm -- textsceXploration -- that with high probability quickly identifies a stabilizing controller.
  arXiv  Detail & Related papers  (2020-06-19T08:58:57Z)
• 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.