Optimal algorithms for materializing stabilizer states and Clifford gates from compact descriptions

• URL: http://arxiv.org/abs/2604.15405v1
• Date: Thu, 16 Apr 2026 15:34:54 GMT
• Title: Optimal algorithms for materializing stabilizer states and Clifford gates from compact descriptions
• Abstract summary: We give an algorithm that runs in $O(2n)$ time and $O(2n)$ space.<n>As consequences, we obtain an optimal procedure for materializing a stabilizer state vector from a standard check-matrix description.<n>These results close the gap for dense stabilizer and Clifford materialization.
• Score: 5.706918315850497
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Stabilizer states admit compact classical descriptions, but many downstream tasks still require their full amplitude vectors. Since the output itself has size $2^n$, the main algorithmic question is whether one can materialize an $n$-qubit stabilizer state vector in optimal $O(2^n)$ time, rather than paying an additional polynomial overhead. We answer this question in the affirmative. Starting from the standard quadratic-form representation of stabilizer states, we give an algorithm that runs in $O(2^n)$ time and $O(2^n)$ space. The idea is to maintain a cached parity word that records all future off-diagonal quadratic phase increments simultaneously. As consequences, we obtain an optimal procedure for materializing a stabilizer state vector from a standard check-matrix description, and an optimal algorithm for expanding a Clifford tableau into its full dense matrix. These results close the asymptotic gap for dense stabilizer and Clifford materialization.

Related papers

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Faster computation of nonstabilizerness [3.8061090528695543]
  The stabilizer extent is a useful tool to estimate the simulation cost using rank-based simulators.<n>We propose faster numerical algorithms to compute the stabilizer extent.
  arXiv  Detail & Related papers  (2024-06-24T14:28:15Z)
• Fast algorithms for classical specifications of stabiliser states and Clifford gates [14.947570152519281]
  Conversions between and verifications of different specifications of stabiliser states and Clifford gates are important components of classical algorithms in quantum information.<n>We develop novel mathematical insights concerning stabiliser states and Clifford gates that significantly clarify their descriptions.<n>We then utilise these to provide ten new fast algorithms which offer advantages over any existing implementations.
  arXiv  Detail & Related papers  (2023-11-17T07:09:10Z)
• Do you know what q-means? [42.96240569413475]
  We present a classical $varepsilon$-$k$-means algorithm that performs an approximate version of one iteration of Lloyd's algorithm with time complexity.<n>We also propose an improved $q$-means quantum algorithm with time complexity.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  We show that our algorithms converge without any prior knowledge on the parameters of the problem.<n>All three algorithms work without prior knowledge of the diameter of the feasible set, the Lipschitz constant or smoothness of the objective function.<n>We extend our framework to relative scale and demonstrate the efficiency and robustness of our methods on large-scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates [0.9332987715848714]
  We give a pair of algorithms that efficiently learn a quantum state prepared by Clifford gates and $O(log n)$ non-Clifford gates.<n>Specifically, for an $n$-qubit state $|psirangle$ prepared with at most $t$ non-Clifford gates, our algorithms use $mathsfpoly(n,2t,1/varepsilon)$ time and copies of $|psirangle$ to learn $|psirangle$ to trace distance at most gates.
  arXiv  Detail & Related papers  (2023-05-22T18:49:52Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• 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)
• Improved upper bounds on the stabilizer rank of magic states [0.0]
  improvement is obtained by establishing a new upper bound on the stabilizer rank of $m$ copies of the magic state $|Trangle=sqrt2-1(|0rangle+eipi/4|1rangle)$ in the limit of large $m$. We obtain a strong simulation algorithm for circuits consisting of Clifford gates and $m$ instances of any (fixed) single-qubit $Z$-rotation gate with runtime $textpoly(n,m) 2m/2$.
  arXiv  Detail & Related papers  (2021-06-14T20:20:51Z)
• Lower Bounds on Stabilizer Rank [3.265773263570237]
  We prove that for a sufficiently small constant $delta, the stabilizer rank of any state which is $$-close to those states is $Omega(sqrtn/log n)$. This is the first non-trivial lower bound for approximate stabilizer rank.
  arXiv  Detail & Related papers  (2021-06-06T19:27:51Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  We propose a new algorithm -- the Momentum- Single-timescale Approximation (MSTSA) -- for tackling problems. MSTSA allows us to control the error in iterations due to inaccurate solution to the lower level subproblem.
  arXiv  Detail & Related papers  (2021-02-15T07:10:33Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10: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.