I'm looking for fast code, or a fast algorithm, for checking if a given state vector $A$ can be transformed into another state vector $B$ using only the Pauli operations $X$, $Y$, $Z$.
The naive strategy is to simply iterate through all $4^n$ ways to apply a Pauli operation (or no operation) to each of the $n$ qubits, actually simulate applying the operations ($2^n$ cost for each qubit for each case) to one of the states, and check if the resulting state vector is equivalent to the other state. Surely it's possible to do this in better than worst case $n 8^n$ time?
[Update] I am specifically interested in worst case performance. Heuristics are interesting and useful answers, but won't become the accepted answer.