Given an arbitrary $n$-qudit state vector $|\psi\rangle =\sum_i c_i| i \rangle \in \mathbb{C}_d^n$ for some orthonormal basis $\{|i\rangle\}$, what is the most efficient way one can:
Here's a necessary condition that might help recognise potential stabilizer states. I'll state it for qubits as that's what I'm used to thinking about, but I suspect it can be generalised:
all the non-zero amplitudes of a stabilizer state must have the same magnitude.
To see this, let's assume that the state $|\psi\rangle$ is an $n$-qubit stabilizer state with linearly independent stabilizers $\Lambda=\{K_i\}_{i=1}^n$. In other words, $K_i|\psi\rangle=|\psi\rangle$, $K_i=K_i^\dagger$ and $[K_i,K_j]=0$. Let $x,y\in\{0,1\}^n$ be such that $\langle x|\psi\rangle\neq 0$ and $\langle y|\psi\rangle\neq 0$.
Now consider $$ |\psi\rangle\langle \psi|x\rangle=\left(\frac{1}{2^n}\prod_{K\in\Lambda}(\mathbb{I}+K)\right)|x\rangle $$ If we multiply out the terms, there are all the different possible products of subsets of stabilizers, each turning $|x\rangle$ into a (possibly different) basis state. Hence, there is at least one subset $S\subseteq\Lambda$ such that $\left(\prod_{K\in S}K\right)|x\rangle=|y\rangle$ up to a global phase.
Finally, what is the amplitude we're after? $$ \langle x|\psi\rangle=\langle x|\left(\prod_{K\in S}K\right)|\psi\rangle=\langle y|\psi\rangle $$ up to a global phase.
Presumably this could put you on a route towards a better-than-brute-force algorithm for determining the stabilizers (I haven't done this myself, hence some vagueness in the statement). If you have a binary string of each of the non-zero basis elements, and the corresponding phase, you know a lot about the group generated by $\Lambda$. A bit of linear algebra should allow you to extract the generators. I would guess that there's even an argument a bit like the one in Simon's algorithm that says you don't need more than $O(n)$ of those basis elements in order to extract the group generators. I'm not sure if this will give you all the information, or just the information about bit-flips. You may also need a Hadamard-rotated version of the state in order to determine the phase flips in the stabilizers.
