Inverted Stabilizer Tableaux: Track Application of Inverse Clifford Operation

[Fe-r-oz]

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

The current functionality supports the inversion of Clifford operations using the inv function. However, as highlighted in the discussion of Stim's implementation (2.3.3 Inverting Tableaux), there is an optimization by directly tracking the inverse of the circuit's stabilizer tableau during execution rather than inverting it post hoc. This approach allows measurements commuting with the current stabilizers to execute in linear time instead of quadratic time. It also improves efficiency by eliminating the need for the computational overhead associated with explicit tableau inversion.

The stim documentation of the Inverted Stabilizer Tableau provides a useful reference point: stim tracks the inverse of the stabilizer tableau that was historically used. This improves the asymptotic complexity of deterministic measurement from quadratic to linear. This is beneficial in error correcting codes, because the measurements they perform are usually redundant and so commute with the current stabilizers.

stim implementation of inverse: https://github.com/quantumlib/Stim/blob/87671245fe1777f9b329caa0f82f559926c508fe/src/stim/circuit/circuit.cc#L886

allow_weak_inverse

The allow_weak_inverse flag in the C++ inverse() method simplifies the inversion process by allowing approximate inverses for certain operations like noise and measurements. When it is set to true, operations such as noise gates and measurements are treated as self-inverses, simplifying the inversion without requiring exact reversibility. For example, the weak inverse of gates like MX is just MX, and DETECTOR/OBSERVABLE_INCLUDE are discarded. On the other hand, when allow_weak_inverse is false, the method requires an exact inverse for all operations, meaning non-invertible gates like measurements or resets will cause an error.

The choice of the Stim API (based on C++ code) is depicted in the schematic below. Please click on the right-hand side to enlarge the diagram.

graph LR
    A[Start] --> B{allow_weak_inverse?}
    B -->|Yes| C[Use Weak Inverse]
    B -->|No| D[Use Exact Inverse]
    C --> E{Is invertible?}
    D --> E
    E -->|Yes| F[Add Inverse Gate]
    E -->|No| G{Handle Noise or Measurement?}
    G -->|Yes| H[Treat as Self-Inverse]
    G -->|No| I[Error: Non-Invertible]
    F --> J[Next Operation]
    H --> J
    I --> J
    J --> K[Finish]

Loading

The allow_weak_inverse flag C++ feature is mentioned in: https://github.com/quantumlib/Stim/blob/87671245fe1777f9b329caa0f82f559926c508fe/src/stim/circuit/circuit.h#L154

I'm not sure why the Python API doesn't allow users to have access to allow_weak_inverse the flag, or how to use it if it does. Hopefully, this provides some context for implementing similar functionality here.

cc: @Krastanov, please consider enhancing the solution section by including your insights on the API and how it can be made compatible with the existing functionality. Thank you

Describe the solution you’d like

Implement the ability to track the application of the inverse Clifford operation directly.

• API Considerations
  • Introduce a mechanism to toggle or enable inverse tracking.
  • Ensure compatibility with existing inv functionality
• Documentation
  • Clearly explain the benefits of inverse tracking in the API documentation.
  • Add the plot to prove this "linear" over "quadratic" complexity benefit.
  • Include benchmarks comparing the performance of inverse tracking versus post hoc inversion.
• Implementation
  • Similar set of functionality for flag: allow_weak_inverse
  • Update this inverse tableau as operations are applied.
• Benchmarks
  • Benchmark against stim.Circuit.inverse()
• Tests: Most importantly, write tests to validate improvements.

Additional Context

Below is some sample stim code to use the inverse, which might be helpful.

Example 1

import stim
circuit = stim.Circuit()
circuit.append_operation("H", [0]) 
circuit.append_operation("CX", [0, 1])
nested_block = stim.Circuit()
nested_block.append_operation("H", [1])
nested_block.append_operation("CX", [1, 2])
nested_block.append_operation("S", [2])
for _ in range(3):
    circuit += nested_block
circuit.append_operation("CX", [2, 0])
circuit.append_operation("S_DAG", [0]) 
print("Original Circuit:")
print(circuit)

Original Circuit:
H 0
CX 0 1
H 1
CX 1 2
S 2
H 1
CX 1 2
S 2
H 1
CX 1 2
S 2
CX 2 0
S_DAG 0

inverse_circuit = circuit.inverse()
print("\nInverse Circuit:")
print(inverse_circuit)

Inverse Circuit:
S 0
CX 2 0
S_DAG 2
CX 1 2
H 1
S_DAG 2
CX 1 2
H 1
S_DAG 2
CX 1 2
H 1
CX 0 1
H 0

Example 2

sim = stim.TableauSimulator()
sim.h(0)
sim.current_inverse_tableau()

stim.Tableau.from_conjugated_generators(
    xs=[
        stim.PauliString("+Z"),
    ],
    zs=[
        stim.PauliString("+X"),
    ],
)

sim.cnot(0,1)
sim.s(1)
t = sim.current_inverse_tableau()
t

stim.Tableau.from_conjugated_generators(
    xs=[
        stim.PauliString("+ZX"),
        stim.PauliString("-XY"),
    ],
    zs=[
        stim.PauliString("+X_"),
        stim.PauliString("+XZ"),
    ],
)

t.inverse()

stim.Tableau.from_conjugated_generators(
    xs=[
        stim.PauliString("+Z_"),
        stim.PauliString("+_Y"),
    ],
    zs=[
        stim.PauliString("+XY"),
        stim.PauliString("+ZZ"),
    ],
)

However, it's important to note that the Python API of stim does not currently support the allow_weak_inverse flag. As a result, attempting to add a measurement in the Python API will lead to an error.

circuit = stim.Circuit()
circuit.append_operation('X', [0])
circuit.append_operation('M', [0])
# Try to invert the circuit (this will raise an error because measurements are non-invertible)
try:
    inverted_circuit = circuit.inverse()
    print("Inverse circuit:", inverted_circuit)
except Exception as e:
    print("Error inverting circuit:", e)

Error inverting circuit: The circuit has no well-defined inverse because it contains noise.
For example it contains a 'M 0' instruction.