Despite the exponential overhead to describe general multiqubit quantum states and processes, efficient methods for certain state families and operations have been developed and utilized. The stabilizer formalism and the Gottesman-Knill theorem, where pure stabilizer or graph states are manipulated by Clifford operations and Pauli measurements, are prominent examples, and these states play a major role in many applications in quantum technologies. Here we develop a noisy stabilizer formalism, i.e., a method that allows one to efficiently describe and follow not only pure states under Clifford operations and Pauli measurements but also Pauli noise processes acting on such stabilizer states, including uncorrelated and correlated dephasing and single- or multiple-qubit depolarizing noise. The method scales linearly in the number of qubits of the initial state, but exponentially in the size of the target state. Thus, whenever a noisy stabilizer state is manipulated by means of local Pauli measurements such that a multipartite entangled state of a few qubits is generated, one can efficiently describe the resulting state.
The stabilizer formalism is a central framework in quantum computing and one of the key building blocks for fault-tolerant quantum computers. According to the Gottesman–Knill theorem, we can efficiently simulate any quantum system consisting of stabilizer states, Clifford gates, and Pauli measurements on a classical computer. A key challenge in developing robust quantum technologies is that physical quantum systems are unavoidably affected by noise, which degrades quantum information. Accurate noise modeling is therefore essential. For stabilizer states, the noisy stabilizer formalism has recently been introduced as a framework for efficiently describing the evolution of graph states subject to Pauli-diagonal noise under Clifford operations and Pauli measurements. In this thesis, we explore and extend this formalism in two directions. First, we generalize the method from graph states to arbitrary stabilizer states, thereby extending the Gottesman-Knill theorem to noisy scenarios. Second, we extend the formalism to handle noise models beyond Pauli-diagonal channels. Moreover, we study the applicability of the noisy stabilizer formalism to entanglement purification protocols.
We introduce the qudit noisy stabilizer formalism, a framework for efficiently describing the evolution of stabilizer states in prime-power dimensions subject to generalized Pauli-diagonal noise under Clifford operations and generalized Pauli measurements. For arbitrary dimensions, the formalism remains applicable, though restricted to a subset of stabilizer states and operations. The computational complexity scales linearly with the number of qudits in the initial state and exponentially with the number of qudits in the final state. This ensures that when noisy qudit stabilizer states evolve via generalized Pauli measurements and Clifford operations to generate multipartite entangled states of a few qudits, their description remains efficient. We demonstrate this by analyzing the generation of a generalized Bell pair from a noisy linear cluster state subject to two distinct noise sources acting on each of the qudits.
Characterizing large noisy multiparty quantum states using genuine multipartite entanglement is a challenging task. In this paper, we calculate lower bounds of genuine multipartite entanglement localized over a chosen multiparty subsystem of multiqubit stabilizer states in the noiseless and noisy scenarios. In the absence of noise, adopting a graph-based technique, we perform the calculation for arbitrary graph states as representatives of the stabilizer states and show that the graph operations required for the calculation have a polynomial scaling with the system size. As demonstrations, we compute the localized genuine multipartite entanglement over subsystems of large graphs having linear, ladder, and square structures. We also extend the calculation for graph states subjected to single-qubit Markovian or non-Markovian Pauli noise on all qubits and demonstrate, for a specific lower bound of the localizable genuine multipartite entanglement corresponding to a specific Pauli measurement setup, the existence of a critical noise strength beyond which all of the postmeasured states are biseparable. The calculation is also useful for arbitrary large stabilizer states under noise due to the local unitary connection between stabilizer states and graph states. We demonstrate this by considering a toric code defined on a square lattice and computing a lower bound of localizable genuine multipartite entanglement over a nontrivial loop of the code. Similar to the graph states, we show the existence of the critical noise strength in this case also and discuss its interesting features.
Abstract The standard stabilizer formalism provides a setting to show that quantum computations restricted to operations within the Clifford group are classically efficiently simulable: this is the content of the well-known Gottesman–Knill theorem. This work analyzes the mathematical structure behind this theorem to find possible generalizations and derivation of constraints required for constructing a non-trivial generalized Clifford group. We prove that if the closure of the stabilizing set is dense in the set of SU(d) transformations, then the associated Clifford group is trivial, consisting only of local gates and permutations of subsystems. This result demonstrates the close relationship between the density of the stabilizing set and the simplicity of the corresponding Clifford group. We apply the analysis to investigate stabilization with binary observables for qubits and find that the formalism is equivalent to the standard stabilization for a low number of qubits. Based on the observed patterns, we conjecture that a large class of generalized stabilizer states are equivalent to the standard ones. Our results provide better insights into the structure of Gottesman–Knill-type results, consequently allowing us to draw a sharper line between quantum and classical computation.
Despite the widespread belief that quantum computers cannot be efficiently simulated classically, efficient simulation is known to be possible in certain restricted regimes. In particular, the Gottesman-Knill theorem states that Clifford circuits can be efficiently simulated. We begin this thesis by reviewing and comparing several known techniques for efficient simulation of Clifford circuits: the stabilizer formalism, CH form, affine form, and the graph state formalism. We describe each simulation method and give four different proofs of the Gottesman-Knill theorem. \n \nNext we review a recent work [15], which shows that restricting the geometry of Clifford circuits can lead to a further speedup. We give an algorithm for simulating Pauli basis measurements on a planar graph state in time
widetildeO(nomega/2), where
omega<2.373 is the matrix multiplication exponent. This algorithm achieves a quadratic speedup over using Clifford simulation methods directly. As an application of this algorithm, we consider a depth-
d Clifford circuit whose two-qubit gates act along edges of a planar graph and describe how to sample from its output distribution or compute an output probability in time $\\widetilde{O}(n^{\\omega/2}d^\\omega)$. For
d=O(logn), both of these results are quadratic speedups over using Clifford simulation methods directly. \n \nFinally, we extend these simulation algorithms to universal circuits by using stabilizer rank methods. We follow a previously known gadgetization procedure [9] to show that given a depth-
d Clifford+
T circuit with
t T gates and whose two-qubit gates act along edges of a planar graph, we can sample from its output distribution in time
widetildeO(20.7926tn5/2t6d3) and can compute output probabilities in time
widetildeO(20.3963tn3/2t6d3). Previous work [9,6], applied to the case
d=O(logn), gives algorithms for sampling in time
O(20.3963tn6t6) and computation of output probabilities in time
O(20.3963tn3t3). Our sampling algorithm offers improved scaling in
n but poorer scaling in the exponential term, while our algorithm for computing output probabilities offers improved scaling in
n with identical scaling in the exponential term.
Stabilizer states, along with Clifford manipulations (unitary transformations and measurements) thereof—despite being efficiently simulable on a classical computer—are an important tool in quantum information processing, with applications to quantum computing, error correction, and networking. Graph states, defined on a graph, are a special class of stabilizer states that are central to measurement-based quantum computing, all-photonic quantum repeaters, distributed quantum computing, and entanglement distribution in a network. All stabilizer states are local-Clifford equivalent to graph states. In this paper, we review the stabilizer framework and extend it by incorporating general stabilizer measurements such as multi-qubit joint projections. We provide an explicit procedure—using Karnaugh maps from Boolean algebra—for converting arbitrary stabilizer gates into tableau operations of the CHP formalism for efficient stabilizer manipulations. We derive graphical rules for arbitrary stabilizer manipulations of graph states, including multi-qubit stabilizer projections and unitaries. We implement the graphical rulebook resulting from above into a MATLAB simulator with a GUI. A user of this tool, e.g., for research in quantum networks, will not require any background in quantum information or the stabilizer framework.