A streamlined demonstration that stabilizer circuits simulation reduces to Boolean linear algebra

• URL: http://arxiv.org/abs/2504.14101v1
• Date: Fri, 18 Apr 2025 22:57:24 GMT
• Title: A streamlined demonstration that stabilizer circuits simulation reduces to Boolean linear algebra
• Authors: Vsevolod I. Yashin,
• Abstract summary: Gottesman-Knill theorem states that computations on stabilizer circuits can be simulated on a classical computer.<n>This note aims to make the connection between stabilizer circuits and Boolean linear algebra even more explicit.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Gottesman-Knill theorem states that computations on stabilizer circuits can be simulated on a classical computer, conventional simulation algorithms extensively use linear algebra over bit strings. For instance, given a non-adaptive stabilizer circuit, the problem of computing the probability of a given outcome (strong simulation) is known to be log-space reducible to solving the system of linear equations over Boolean variables, which is commonly done by Gaussian elimination. This note aims to make the connection between stabilizer circuits and Boolean linear algebra even more explicit. To do this, we extend the stabilizer tableau formalism to include stabilizer tableau descriptions of arbitrary stabilizer operations (Clifford channels). Finding the tableau corresponding to the composition of two channels becomes a linear algebra problem. Any stabilizer circuit rewrites to a diagram with stabilizer tableaux on vertices, contracting an edge means to take the composition of channels, to compute the result of the circuit means to fully contract the diagram. Thus, simulating stabilizer circuits reduces to a sequence of Gaussian eliminations. This approach gives a new perspective on explaining the work of stabilizer tableau methods (reproducing the asymptotics) and creates opportunity for exploring various tensor-contraction techniques in stabilizer simulation.

Related papers

• Faster computation of nonstabilizerness [3.8061090528695543]
  The stabilizer extent is a useful tool to estimate the simulation cost using rank-based simulators. We propose faster numerical algorithms to compute the stabilizer extent.
  arXiv  Detail & Related papers  (2024-06-24T14:28:15Z)
• SymPhase: Phase Symbolization for Fast Simulation of Stabilizer Circuits [3.5664433935013165]
  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.
  arXiv  Detail & Related papers  (2023-11-07T11:45:36Z)
• 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)
• The Algebra for Stabilizer Codes [0.0]
  In the language of the stabilizer formalism, full rank stabilizer tableaux are exactly the bases for affine Lagrangian subspaces. We show that by splitting the projector for a stabilizer code we recover the error detection protocol and the error correction protocol with affine classical processing power.
  arXiv  Detail & Related papers  (2023-04-20T18:16:17Z)
• Numerically Stable Sparse Gaussian Processes via Minimum Separation using Cover Trees [57.67528738886731]
  We study the numerical stability of scalable sparse approximations based on inducing points. For low-dimensional tasks such as geospatial modeling, we propose an automated method for computing inducing points satisfying these conditions.
  arXiv  Detail & Related papers  (2022-10-14T15:20:17Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  We consider online statistical inference of constrained nonlinear optimization problems. We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
  arXiv  Detail & Related papers  (2022-05-27T00:34:03Z)
• 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)
• Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
  We propose a new formulation for the bundle adjustment problem which relies on nullspace marginalization of landmark variables by QR decomposition. Our approach, which we call square root bundle adjustment, is algebraically equivalent to the commonly used Schur complement trick. We show in real-world experiments with the BAL datasets that even in single precision the proposed solver achieves on average equally accurate solutions.
  arXiv  Detail & Related papers  (2021-03-02T16:26:20Z)
• Gaussian Process-based Min-norm Stabilizing Controller for Control-Affine Systems with Uncertain Input Effects and Dynamics [90.81186513537777]
  We propose a novel compound kernel that captures the control-affine nature of the problem. We show that this resulting optimization problem is convex, and we call it Gaussian Process-based Control Lyapunov Function Second-Order Cone Program (GP-CLF-SOCP)
  arXiv  Detail & Related papers  (2020-11-14T01:27:32Z)
• 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)

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.