[Feature]: Stabilizer Tensor Networks

[Fe-r-oz]

Is your feature request related to a problem? Please describe.

To efficiently simulate systems beyond a few dozen qubits, alternative methods are necessary due to the exponential increase in complexity associated with brute force techniques. Identifying and understanding which quantum states can be simulated easily and the reasons behind it leads us to Resource theories [1] that prove to be a valuable tool as they characterize the operations that are straightforward to perform (free operations) within a specific framework (Cheap resources vs expensive resources). This paper Stabilizer Tensor Networks: universal quantum simulator on a basis of stabilizer states [2] particularly focuses on entanglement[1] and stabilizer rank[1](resource linked to non-stabilizerness), owing to their relevance to tensor networks (TN) and the stabilizer formalism, respectively.

Recently, The properties of magic in Matrix Product States (MPS), a specific type of tensor network (TN), is discussed by Nonstabilizerness via matrix product states in the Pauli basis [3] and Learning the stabilizer group of a Matrix Product State[4]. The authors note that separable states possessing significant magic are complex within the stabilizer formalism, despite being straightforward to simulate using resource theories of entanglement. This indicates that these resources are, in a sense, orthogonal (Figure 1a). Their paper aims to unify simulation strategies for entanglement and magic by employing a special basis, which was originally introduced by Ted B(S, D) in conjunction with tensor networks (see Figure 1b) thereby proposing method which can be utilized to simulate arbitrary quantum circuits.

CREDITS: !(Figure is taken from Sergi and Artur's paper on Stabilizer TN [2])

Their work focuses on 1D MPS structure to encode the amplitudes of a quantum state:

$$\mathcal{T}^{i_1 i_2 \ldots i_n} = \sum_{k_1 k_2 \ldots k_{n-1}} (T_1)^{i_1}_{k_1} (T_2)^{i_2}_{k_2} (T_3)^{i_3}_{k_3} \cdots (T_N)^{i_n}_{k_{n-1}} \tag{1}$$

Here, the bond dimension χ of bond k in a tensor network corresponds to the Schmidt rank, encoding the entropy between subsystems: χ = 1 for separable states, χ = 2 for states with local entanglement, and up to χ = 2^(n/2) for maximally entangled states.

Since they are using special basis: B(S,D) the following representation is exactly same as Ted's special basis used for generalized stabilizer. In fact, they explicitly make this connection. Filler details: B(T) = B(S, D) = {d|ψₛ⟩ d ∈ D} ; stabilizer basis corresponding to T where S is full stabilizer and D is corresponding destabilizer.

$$|\psi\rangle = \sum_{i=0}^{2^n} \nu_i d_i |\psi_S\rangle. \tag{2}$$

These amplitudes on an $MPS$ using $|\nu\rangle = \sum_i \nu_i |i\rangle$, and it is shown how they change when applying any unitary gate or measurement with the following update rules: $1)$ Clifford gate G. $2)$ Non-Clifford gate U. $3)$ Measurement of observable $O$. These update rules are the same as mentioned in the algorithm 1, algorithm2, and algorithm 3 of Ted's paper for generalized stabilizer.

Describe the solution you’d like
The first interesting point to note the special basis B(S, D) utilize in this paper is from the Ted's paper! Incorporating the ITensor backend simulator would be highly pertinent for realizing the concepts discussed in the paper. According to the authors, stabilizer tensor networks can serve as a practical means to estimate the simulation complexity of a circuit based on its $T$ gate count, a task typically confined to theoretical methods. Their method is available as Python source code capable of simulating any circuit, suggesting potential improvements in efficiency. A notable enhancement could be integrating it with tableau handling as implemented by QuantumClifford.

I will thoroughly provide details action steps soon after rereading complete paper.

Describe alternatives you’ve considered

Alternative approach namely, Hybrid Stabilizer Matrix Product Operator (MPO) formalism:

Motivation: Generic unitary evolution creates correlations throughout a system that spread linearly over time, leading to a linear increase in entanglement. (Refer to Entanglement in Many-Body Systems). This results in an exponential growth of the $MPS$ bond dimension, ultimately causing [classical simulations to fail . (Refer to Spreading of correlations and entanglement after a quench in the one-dimensional Bose-Hubbard model). However, the primary focus is often not on the full evolution of the many-body wave function but rather on the expectation values of local observables. This is one of the most challenging problems in many-body physics, particularly the evaluation of $⟨ψ| Û† Ô Û |ψ⟩$, where $Û$ is a generic unitary evolution and $Ô$ is a local observable, starting from a state $|ψ⟩$ with short-range correlations, like an $MPS$.

The stabilizer formalism comes to the rescue: When the unitary evolution is driven by a Clifford operator, it is known that the computational complexity of this many-body physics task reduces from exponential to polynomial in the number of qubits $N$. This paper titled Hybrid Stabilizer Matrix Product Operator propose a new strategy that integrates the stabilizer formalism into the tensor network framework, combining the strengths of both approaches to improve the simulation of many-body quantum system dynamics. Their work introduces a hybrid approach that merges tensor network methods with the stabilizer formalism, enhancing the ability to accurately model unitary dynamics while alleviating the exponential increase in entanglement that challenges classical simulations.

Goal: They create a hybrid stabilizer and $TN$ method to "disentangle time-evolved $MPS$", enabling precise computation of expectation values over longer times at a fixed resource amount (χ)by decomposing evolution into $TN$ evolution and a Clifford operator, applying the stabilizer formalism, and then calculating the expectation value.

Their approach as shown in the figure can be described by this set of equations shown below:

CREDITS: Antonio, Alessandr, and Mario from their paper: Hybrid Stabilizer Matrix Product Operator

$$\begin{align} Generic \space Pauli\space String: \hat{\Sigma}^{\mu} = \hat{\sigma}_1^{\mu_1} \hat{\sigma}_2^{\mu_2} \cdots \hat{\sigma}_N^{\mu_N} \in \mathcal{P}_N = \mathcal{P}^{\otimes N} \tag{3}\\\ Operator \space acting \space on \space many-body \space Hilbert \space space:O = \hat{\Sigma}_{\mu} O_{\mu} \hat{\Sigma}^{\mu} \tag{4}\\\ MPO \space representation: O_{\mu_1, \mu_2, \ldots, \mu_N} = O_1^{\mu_1} O_2^{\mu_2} \cdots O_N^{\mu_N} \tag{5}\\\ evaluate \space this \space for \space short\space range \space correlated \space| \psi \rangle : \langle \psi | \hat{U}^\dagger \hat{\Sigma}^{\mu} \hat{U} | \psi \rangle \tag{6}\\\ decompose \space U \space => \\\ \space local \space Magic \space R \space and \space Clifford \space \space circuit \space C: \hat{U} = \hat{R}_{j_M} \hat{C}_M \cdots \hat{R}_{j_2} \hat{C}_2 \hat{R}_{j_1} \hat{C}_1\tag{7} \\\ Stabilizer \space MPO \space representation: \hat{U} = \hat{C} \hat{T}_M \cdots \hat{T}_2 \hat{T}_1 \tag{8}\\\ \hat{T}_m = \hat{C}_1^\dagger \cdots \hat{C}_m^\dagger \hat{R}_{j_m} \hat{C}_m \cdots \hat{C}_1 = \hat{T}_{m,1} \hat{T}_{m,2} \cdots \hat{T}_{m,N} \tag{9}\\\ ∴ (6) \space reduces \space to \space (10) : \quad \langle \psi | \hat{T}_1^\dagger \cdots \hat{T}_M^\dagger \hat{\Sigma^{\nu}} \hat{T}_M \cdots \hat{T}_1 | \psi \rangle \tag{10} \\\ evaluate \space (10) \space as \space follows: \text{Tr}\left( \hat{\Sigma}^{\nu} \hat{T}_M \cdots \hat{T}_1 |\psi\rangle \langle \psi| \hat{T}_1^\dagger \cdots \hat{T}_M^\dagger \right) \tag{11}\\ Folded \space Tensor \space Network \space Scheme \space (see \space Figure \space 2(c): \\\ \hat{\Sigma}_{\mu} (Y_1)^{\mu_1} \cdots (Y_N)^{\mu_N} \hat{\sigma}^{(\mu_1)} \cdots \hat{\sigma}^{(\mu_N)} \tag{12} \\\ Afterwards, \space consult \space paper \space for \space local \space tensor \space transformation \space rules \space for \space Y, \space etc. \end{align}$$

Additional context
The key element in stabilizer tensor networks is the ability to alter the basis beyond local rotations, with the tableau algorithm replacing the computational basis with stabilizer states that can have entanglement and decouple qubits from tensors. The authors show that their framework can efficiently simulate scenarios with low entanglement and low stabilizer rank

The authors use stabilizer rank, the minimum $ξ$ for decomposing an arbitrary state $|ψ⟩$ into stabilizer states, and define a pseudo-stabilizer rank $ξ˜$ based on the number of non-zero coefficients in $|ν⟩$.

$$|\psi\rangle = \sum_{i=1}^{\xi} \alpha_i |\psi_S^i\rangle. \tag{13}$$

The alternative approach does not make use of special basis, B(S, D). It needs to be verified whether this is intentional or not and why they have not considered? Is this alternative approach truly different the aforementioned approach? The authors implemented this approach using stim and ITensor to combine stabilizer formalism with Tensor Network methods. Probably, the C++ version of ITensor was used.

[Krastanov]

This would be interesting to build, but it should probably be a whole separate library, at least at first while being prototyped (potentially using QuantumClifford and ITensor as dependencies). It is great functionality, but quite a bit beyond the current scope we have.

A separate library would also benefit from the fact that it can have many early breaking releases as various approaches are being tried out.

[Fe-r-oz]

Well said!

Just to add a quick comment: One month after the aforementioned paper, the alternative approach (now described in alternative methods above) utilized stim and ITensor to combine stabilizer formalism with Tensor Network methods in what the authors call "Stabilizer MPO representation". Probably they used the C++ version of ITensor. This approach seems different (they don't use special basis B(S, D)) from the one discussed above which addresses your point on different approaches currently being developed at the moment of classical (tensor network) algorithms being able to simulate both entanglement and non-stabilizerness.

[Fe-r-oz]

Also, TensorQEC.jl: Circuit Simulation with Tensor Networks