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.


1 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.

  • $\begingroup$ Thank you for the answer. I get that updating the signs of the inverse tableau when a gate is prepended consist in appending the inverse gate onto the inverse tableau. Instead of prepending a gate to the tableau, I would like to append a gate to the tableau and update the inverse tableau accordingly. I concede that both situations are equivalent, so to be more specific and to rephrase my initial problem, how to update the signs of a tableau in linear time when prepending an operation? I would be grateful if you could provide some explanations about that or link some references explaining it. $\endgroup$
    – user22310
    Oct 30, 2022 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.