Deriving a state vector from a stabilizer state's generators

Question

When I run a stabilizer simulator such as Scott Aaronson's CHP simulator (defined in https://arxiv.org/abs/quant-ph/0406196), one of the possible outputs is a stabilizer table.

For example:

sim = StabilizerSim(num_qubits=3)
sim.hadamard(2)
sim.cnot(2, 0)
sim.cnot(2, 1)
sim.phase(0)
sim.phase(1)
sim.hadamard(0)
sim.hadamard(1)
sim.hadamard(2)
print(sim)

Prints:

-YII
-IYI
+IIX
----
+XIX
+IXX
+YYZ

Where each of the lines is the Pauli product at the start of the circuit that corresponds to a Z or X observable of a qubit at the end of the circuit.

I would like to convert this representation into an explicit state vector, like shown in the display at the end of this Quirk circuit:

I'd like to get the state vector without having to simulate the circuit in a state vector simulator, because sometimes the number of output qubits is significantly smaller than the number of intermediate qubits and in such cases it would be much cheaper to only convert the final stabilizer state into a state vector.

One possible solution is to take the output stabilizer state, perform a known decomposition into a circuit, then execute the circuit in a state vector simulator. But I doubt that's a particularly efficient approach.

Alternatively, I could perform a series of post-selected projective measurements in the vectir simulator. The initial state would be half of an entangled state, and each measurement (and its outcome) is determined by stabilizers from the table. Like this:

However, this requires doubling the qubit count which is a quadratic space and time overhead in the calculation.

Answer 1

The post-selection idea can be made to work without involving an entangled state. All that matters is that the initial state, before post-selection, has some overlap with the correct final state.

I'm unsure how to find or prove that a specific easy-to-prepare state has overlap with every possible stabilizer state. It seems like just ensuring each qubit is individually not in a stabilizer state is sufficient. For example, by using a pair of non-stabilizer X and Z rotations:

Even if this specific initial state strategy does not work, in practice a random initial state would work just fine.

In summary, here is what you do.

1. Get the stabilizer table from the stabilizer simulator.

   Note that the table comes in two chunks, and you only want the chunk corresponding to the Z observables.

2. In a state vector simulator, create an initial state that overlaps every stabilizer state.

3. In the state vector simulator, measure each of the Z-observable stabilizers from the stabilizer table and post-select on the measurement results being False.

4. Output the state vector simulator's state vector.

The running time of this procedure is $O(n 2^n)$ where $n$ is the number of qubits in the output state. It is unclear if it possible to save the factor of $n$. Space usage is $O(2^n)$, which is optimal because that's the output size.