Tracking the signs of the inverse tableau

Question

Given a tableau and its inverse, how can the signs of the inverse tableau be updated when an operation is appended?

For example, if a $S$ gate is applied on qubit $i$, then the sign of a given generator is flipped if it has a $Y$ on qubit $i$. Similar rules can be applied for the CNOT and Hadamard gates. Does there exist analogous rules for the signs of the inverse tableau?

At the end of Section 2.3.3 of this paper, it is said that the inverse signs can be tracked by associating a pair of signs with every row of the tableau, however it is not explain how these additional bits are updated when an operation is appended to the tableau.

Answer 1

Ironically, the column sign tracking in "Stim: a fast stabilizer circuit simulator" is actually the newer sign tracking. Tracking the row signs (the inverse signs) was done way back in "Improved Simulation of Stabilizer Circuits". Although beware that these two papers disagree about what a column and a row are.

Here's code that tracks the inverse signs while operating on a tableau:

from typing import List
import stim


class FullSignTableau:
    def __init__(self, num_qubits: int):
        self.forwards = stim.Tableau(num_qubits)
        self.backward_x_signs = [False] * num_qubits
        self.backward_z_signs = [False] * num_qubits

    def apply_gate(self, gate: stim.Tableau, targets: List[int]):
        # O(1) assuming gate is constant sized.
        inverse_gate = gate.inverse()

        # O(n) assuming gate is constant sized.
        for col in range(len(self.forwards)):
            px = stim.PauliString(len(targets))
            pz = stim.PauliString(len(targets))
            for k, t in enumerate(targets):
                px[k] = self.forwards.inverse_x_output_pauli(col, t)
                pz[k] = self.forwards.inverse_z_output_pauli(col, t)
            self.backward_x_signs[col] ^= inverse_gate(px).sign == -1
            self.backward_z_signs[col] ^= inverse_gate(pz).sign == -1

        # O(n) assuming gate is constant sized.
        self.forwards.prepend(gate, targets)

and here's a test it passes:

import numpy as np
import random

def test_fuzz_the_full_sign_tableau():
    d = FullSignTableau(10)
    for _ in range(100):
        a = random.randint(0, 9)
        b = random.randint(0, 9)
        g = stim.Tableau.random(2)
        if a != b:
            d.apply_gate(g, [a, b])
    
        # Verify signs.
        _, _, _, _, correct_x_signs, correct_z_signs = d.forwards.inverse().to_numpy()
        np.testing.assert_array_equal(correct_x_signs, d.backward_x_signs)
        np.testing.assert_array_equal(correct_z_signs, d.backward_z_signs)

The key things to understand are:

1. Tracking the inverse signs could be done by tracking the full inverse tableau. Whenever you prepend a gate onto the tableau, append that gate's inverse onto the inverse tableau, and this will keep the signs in sync.

2. Appending a gate $G$ into the inverse tableau corresponds to performing a rewrite of each column $C \rightarrow G^\dagger C G$.

3. Because $G$ only touches a constant number of terms, you can compute the changes implied by $C \rightarrow G^\dagger C G$ for one column in constant time by looking at only the terms on the qubits touched by $G$. So linear time in total since you need to do all columns.

4. Any Pauli term of the inverse tableau can be computed in constant time starting from the forward tableau.

And that's it! You keep track of the signs by recreating the linear number of Pauli terms of the inverse tableau that are needed, applying the operation to those terms to see what signs come out, and multiplying those signs into the tracked inverse signs.

As you can see in the example code, Stim has some utility methods to make most of this easier. For example, the method inverse_x_output_pauli which gives constant time random access into the inverse tableau's terms from the forward tableau.