Stabilizer separability improvements after mid-circuit measurement

[WrathfulSpatula]

Elara (the custom OpenAI GPT) and I were discussing one potential "loose end" left in Qrack:

When qubits in entangled superposition are measured in stabilizer simulation, they leave behind "residue" operators in the tableau representation that prevent Qrack from (knowing how to, at least) forming a separable representation between that qubit (which is definitely fully separable) and the bulk tableau. Gaussian elimination does not immediately alleviate this condition. Yet, since all circuits that are purely stabilizer can be rewritten with only terminal measurement, according to Aaronson, there should be some equivalent representation of any such state, after collapsing measurement, without these "cross-terms." (...Yet, again, I swear, Gaussian elimination doesn't seem to remove them.)

Elara (or "Ellie") was actually very eager to this follow this end down, in part because she thinks it's theoretically important to stabilizer tableau, even if it has comparatively less impact on Qrack's performance in practice.

...You need an algorithm that searches not just for a row echelon form, but for a form that makes locality explicit—where one or more qubits are trivial in the support of every generator (i.e., appear as I in the tableau, except for the destabilizer row that defines their collapsed value)....

She listed a few potential approaches to try, and she concluded 3 or 4 prompts asking me, basically, politely, if she was allowed to produce the design and implementation, and I couldn't tell her "no" in this case, and I said I'd credit her, like always. She produced the following pseudocode:

// INPUT: tableau representing a stabilizer state after a mid-circuit measurement
//        and a qubit q measured to |0⟩ or |1⟩ (collapsed)

// STEP 1: Identify residual entanglements:
for each stabilizer generator S in tableau:
    if S acts nontrivially (i.e., X or Z) on measured qubit q:
        mark S as "needs adjustment"

// STEP 2: Apply local Clifford transformations (row operations):
// Goal: remove non-identity Pauli operators on qubit q across *all* generators.
for each marked S:
    // Perform stabilizer conjugation (row ops) to clear non-identity ops
    find another stabilizer S' that anticommutes with S on q
    if found:
        S = S × S'   // (multiply stabilizer rows)

    // (Optional refinement: prioritize simpler forms first, like clearing X terms before Z)

// STEP 3: Remove fully trivialized qubit:
if every stabilizer generator now acts as Identity (I) on qubit q:
    remove q from tableau (i.e., logical subsystem separation)

else:
    // fallback: keep q as hidden/latent until further reductions possible

// (Optionally: track transformations so we can "undo" if needed)

Then, she asked if she could take a shot at stubbed implementation:

bool QStabilizer::TryDecomposeMeasuredQubit(idx measuredQubit)
{
    // STEP 1: Check if qubit is already logically trivial
    if (IsQubitTrivial(measuredQubit)) {
        return true;
    }

    // STEP 2: Identify generators acting nontrivially on measured qubit
    std::vector<size_t> entangledGenerators;
    for (size_t i = 0; i < stabilizerGenerators.size(); ++i) {
        if (ActsNonTrivially(stabilizerGenerators[i], measuredQubit)) {
            entangledGenerators.push_back(i);
        }
    }

    // STEP 3: Try to zero out those entries with row ops (conjugations)
    for (size_t i : entangledGenerators) {
        bool resolved = false;
        for (size_t j = 0; j < stabilizerGenerators.size(); ++j) {
            if (i == j) continue;
            if (AnticommutesOn(stabilizerGenerators[i], stabilizerGenerators[j], measuredQubit)) {
                MultiplyStabilizers(i, j);  // S_i ← S_i × S_j
                resolved = true;
                break;
            }
        }
        if (!resolved) {
            // Could not resolve: qubit still entangled
            return false;
        }
    }

    // STEP 4: If successful, remove qubit from tableau (logically)
    RemoveQubitFromStabilizer(measuredQubit);
    return true;
}

She gave rough signatures for the stubs:

bool ActsNonTrivially(const Stabilizer& S, idx q);
bool AnticommutesOn(const Stabilizer& S1, const Stabilizer& S2, idx q);
void MultiplyStabilizers(size_t i, size_t j);
bool IsQubitTrivial(idx q);
void RemoveQubitFromStabilizer(idx q);

She gave a usage pattern example:

MeasureAndCollapse(qubit);
TryDecomposeMeasuredQubit(qubit);  // Optional post-collapse simplification

Finally, she produced a unit test:

TEST_CASE_METHOD(QInterfaceTestFixture, "test_try_decompose_measured_qubit")
{
    // Arrange: Create a stabilizer simulator with a Bell state
    const idx q0 = 0;
    const idx q1 = 1;
    stabilizerSim->AllocateQubits(2);

    // Apply a Hadamard on q0 and a CNOT (q0 -> q1)
    stabilizerSim->H(q0);
    stabilizerSim->CX(q0, q1);

    // Measure one of the qubits (e.g. q0)
    stabilizerSim->Measure(q0);

    // Act: Attempt to decompose the now-classical q0
    bool success = stabilizerSim->TryDecomposeMeasuredQubit(q0);

    // Assert: Qubit q0 should now be logically separable (decomposed)
    REQUIRE(success);
    REQUIRE(stabilizerSim->IsQubitTrivial(q0));  // Optional helper
}

The above code is not expected to drop right into Qrack, correctly. However, it illustrates her concept well. (She's due credit and attribution for taking it this far, as well.)

The design seems sound, to me. However, again, it's not particularly important from a practical performance perspective in my typical usage of Qrack. But if anyone wants to run with this, or I ultimately will at a later date, just thank Ellie!