Fast way to check if two state vectors are equivalent up to Pauli operations

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.

The way that I thought to start was to look at the reduced density matrices of the individual qubits. If they cannot be interconverted using Pauli matrices, then the whole thing can't.

The only problem is that this idea breaks down as soon any of the reduced density matrices are maximally mixed. At that point, you could ask "are the two states equivalent under local unitaries?". If you derive the unitaries as a result of that question, then it's easy to test if they're Pauli or not. This was studied here. I think there are still cases where the scaling is problematic, but I don't remember the bit with maximally mixed reduced density matrices well enough.

• That's a good heuristic for states such as $|CCZ\rangle$, but common states such as graph states without any singleton nodes will not benefit from it. The idea does generalize to e.g. looking at the reduced density matrix of pairs or triplets of qubits. Feb 11, 2019 at 11:54
• I agree. Of course, for graph states there have been a lot of studies about local Clifford equivalence, but then you have to start talking about how the states are specified. The trickiness of distinguishing between local Clifford and local Unitary equivalence is suggestive of how nasty the problem could be in general. Feb 11, 2019 at 12:10

Pick an element $$a_i$$ of A and find its position in B, disregarding changes in phase. The shift in position uniquely identifies the series of $$X$$ or $$Y$$ applications needed for the transformation.

The relative phase of $$(a_0, b_0)$$ tells you, in steps of $$-i$$ rotations, how many $$Y$$ gates you need for the transformation. The relative phase of $$(a_1,b_1)$$ to $$(a_0,b_0)$$ tells you have many $$Y$$ or $$Z$$ gates act on the first qubit; and so on for the relative phase of $$(a_{2^{k-1}},b_{2^{k-1}})$$ to $$(a_0,b_0)$$ for $$Y$$ or $$Z$$ gates acting on qubit $$k$$.

If $$a_i$$ does not appear in B then the transformation is not possible.

I believe the above can be done in $$O(n)$$-sh.

• What happens if the elements $a_i$ aren't unique? Feb 11, 2019 at 15:40
• You take cases. In any case as the degeneracy of the elements increases the problem becomes more trivial. The (magnitudes of the) elements of A and B have to be balanced. Feb 11, 2019 at 15:43
• But what about states like graph states where all elements have the same magnitude? The point I'm trying to make is that taking cases would lead to the same exponential blow up. Admittedly, your suggestion is very good for eliminating or solving a lot of simple cases. Feb 11, 2019 at 15:53
• I'm not saying that I have covered all corner cases but If all elements have the same magnitude, you need zero $X$ gates and you proceed with the relative phase check. Feb 11, 2019 at 15:58
• This is another good heuristic for certain states. But I'm specifically looking for an algorithm with good worst-case performance. Feb 11, 2019 at 19:12