7

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:

  1. Verify whether the state is a stabilizer state (i.e. can be defined by $n \leq m \leq 2n$ stabilizer generators, with equality for $d=2$), and if so,
  2. Find the state's stabilizer generators (in the form of some tensor product of local Pauli matrices).
glS
  • 24,708
  • 5
  • 34
  • 108
SLesslyTall
  • 1,626
  • 8
  • 26
  • 1
    Presumably you want the stabilizer generators to be tensor products of single-qudit Pauli-like operators? – DaftWullie Jul 24 '18 at 16:13
  • Sure. I think this a natural consequence of the definition of a stabilizer state. – SLesslyTall Jul 24 '18 at 16:34
  • How are you supplied the state? As a quantum state? As a vector of all coefficients? As a quantum circuit? And do you care in any way about the efficiency of the procedure? – Norbert Schuch Jul 24 '18 at 21:16
  • More questions: Do you know in which basis the stabilizer is? (Paulis? Or any rotation thereof?) If Paulis, you can always find out brute force by testing all possible stabilizers. (And likely even if you don't have Paulis by using a suitable discretization.) --- Would this be a satisfactory answer? – Norbert Schuch Jul 24 '18 at 21:21
  • States are provided as known quantum states (i.e. coefficients for some ONB). Not knowing the state's preparation circuit is necessary, as otherwise the question would be trivial (if Clifford circuit => stabilizer state with known generators). Efficiency is also required, as otherwise brute force search of Pauli operators can be straightforwardly applied. – SLesslyTall Jul 24 '18 at 22:44
  • 1
    But if states are provided as a list of coefficients, do you not already have a problem with efficiency? – DaftWullie Jul 25 '18 at 10:18
  • @SLesslyTall To second DaftWullie's comment: If you provide all the coefficient, the problem will necessarily be exponentially hard. (Though brute force is probably doubly exponential?) Also, I don't see why circuits should be easy: It could well be that non-Clifford circuits also yield stabilizers. – Norbert Schuch Jul 25 '18 at 12:30
  • @DaftWullie I guess I was considering "efficient" as excluding the overhead of an exponential number of coefficients. Also, some stabilizer states allow state representations which are not exponentially large. For example, the 3-qubit linear graph state has 2^3=8 computational bases, but only two coefficients for a basis choice of {|+0+>, |-1->}. – SLesslyTall Jul 25 '18 at 14:14
  • @NorbertSchuch As far as I am aware, stabilizer states are by definition those which can be produced by some Clifford circuit (i.e. via Gottesman-Knill theorem). If a state's preparation circuit is composed only of Clifford gates (or has some Clifford-gate decomposition), then surely finding the state's stabilizers is just a matter of Heisenberg evolution of the initial all-zero state's generators? – SLesslyTall Jul 25 '18 at 14:19
  • it's just a problem of understanding how those considerations feed into the formulation of the question. If you can assume you're given a representation in an efficiently chosen basis, that basis choice tells you a lot about the stabilizers, i.e. the work is kind of already done for you. – DaftWullie Jul 25 '18 at 14:41
  • @NorbertSchuch is correct. It could be that a state is specified by a non-Clifford circuit that results in a stabilizer state. Gottesman-Knill conveys that there is also a Clifford circuit that does the job, and part of your question is how you would find that. – DaftWullie Jul 25 '18 at 14:48
  • Ah ok, I would have said a circuit that decomposes into Clifford gates is a Clifford circuit (even if it contains individual non-Clifford gates), but that is a philosophical/semantic debate. Anyway, for simplicity lets assume the state is given as a state vector in some basis, not some preparation circuit. In this case, this splits the problem into two cases: a) when the known basis is minimal; and b) when it is not. I would be interested in an answer for either case, but obviously the more general latter case would be ideal. – SLesslyTall Jul 25 '18 at 14:59
  • I would have said that a state which is an eigenstate of stabilizers is a stablizer state, regardless of how it is described, but that is a philosophical/semantic debate. --- Seriously, just because you know it is the same it is not at all clear how to identify such a property. Isn't that exactly the point of your question? – Norbert Schuch Jul 25 '18 at 15:27
  • Sorry, I don't understand your point. Could you please elaborate on this? – SLesslyTall Jul 25 '18 at 15:38
  • I am just saying that it is a well-defined an maybe non-trivial problem to decide if a state created by some circuit is a stabilizer state or not. I cannot understand why you call this a "semantic" or "philosophical" debate. It is just as much a question as asking whether a SAT formula has a satisfying assignment, or whether a quantum state written on paper is a stabilizer state. – Norbert Schuch Jul 25 '18 at 21:35
  • @SLesslyTall I insist that you need to clarify what you mean by "efficiently"? Linear in the number of coefficients (i.e. exponentially in N)? Otherwise, it is not clear how to even interpret the question. – Norbert Schuch Jul 25 '18 at 21:38
  • 1
    @NorbertSchuch I think you may have misunderstood me; my "semantic" comment was a purely pedantic point on whether one can call a circuit which is decomposable into Clifford gates as non-Clifford, rather than a claim about the problem of deciding if a given circuit produces a stabilizer state, which I agree is non-trivial. W.r.t efficiency, I am mainly concerned with what is the most efficient method to solve the problem, rather than whether an efficient method in N exists (e.g. if, say, you were certified to be given the minimal basis representation of the state) – SLesslyTall Jul 26 '18 at 07:48

1 Answers1

5

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.

DaftWullie
  • 57,689
  • 3
  • 46
  • 124
  • 2
    Another constraint is that all stabilizer measurements are either deterministic or 50/50 random, even after conditioning on other measurements. For example, this means that $1/2 (|000\rangle +|010\rangle+|100\rangle+|111\rangle)$ is not a reachable state despite it having equal non-zero amplitudes, because the third qubit has a 25% chance of being ON if measured. – Craig Gidney Jul 25 '18 at 19:21
  • @CraigGidney Testing all possible stabilizer measurements is probably no more efficient than just testing if your state is an eigenstate for all possible stabilizers, and see if you find the right number. That's doesn't seem efficient. – Norbert Schuch Jul 25 '18 at 21:40
  • @NorbertSchuch Correct, but it was only intended to be an observation that could possibly lead to a simple test. Not an entirely self-contained answer. – Craig Gidney Jul 26 '18 at 00:20