General construction of $W_n$-state

Question

Two of the most well known entangled states are the GHZ-state $|\psi\rangle = 1/\sqrt{2}\left( |0\rangle^{\otimes n} + |1\rangle^{\otimes n}\right)$ and the $W_n$-state, with $W_3 = 1/\sqrt{3}\left(|100\rangle + |010\rangle + |001\rangle\right)$.

Constructing the GHZ-state is simple for arbitrary $n$. However, implementing the $W_n$-state is more difficult. For $n=2$ it is easy, and for $n=4$ we can use

H q[0,3]
X q[0,3]
Toffoli q[0],q[3],q[1]
X q[0,3]
Toffoli q[0],q[3],q[2]
CNOT q[2],q[0]
CNOT q[2],q[3]

Even for $n=3$ we have implementations, see this answer for instance. However, I have not found an algorithm that, given an $n$, outputs the circuit for constructing the $W_n$-state.

Does such an algorithm, defined by single- and two-qubit gates, exist? And if so, what is it?

Answer 1

Yes, there are several implementations of this algorithm in the Superposition quantum kata (tasks 14 and 15):

• For $n = 2^k$, you can use a recursive algorithm: create a W state on the first $2^{k-1}$ qubits, allocate an ancilla qubit in $|+\rangle$ state, do some controlled SWAPs to set the state of the second $2^{k-1}$ qubits, and then some controlled NOTs to reset the ancilla back to $|0\rangle$ (WState_PowerOfTwo_Reference operation).
• For an arbitrary $n$, you can use a recursive algorithm as described by DaftWullie (WState_Arbitrary_Reference operation).
• There is also a neat trick you can use to create a $W_n$ state for an arbitrary $n$ using the first recursive algorithm. Allocate extra qubits to pad the $n$ given ones to $2^k$, create a state $W_{2^k}$ on them and measure the extra qubits; if all qubits measure to 0, the state of the original qubits is $W_n$, otherwise reset and repeat the process (WState_Arbitrary_Postselect operation).

This is my favorite task of that kata, because it allows so many different approaches.

Answer 2

The conceptually simplest way to produce a W state is somewhat analogous to classical reservoir sampling, in that it involves a series of local operations that ultimately create a uniform effect.

Basically, you look at each qubit in turn and consider "how much amplitude do I have left in the all-0s state, and how much do I want to transfer into the just-this-qubit-is-ON state?". It turns out that the family of rotations you need is what I'll call the "odds gates" which have the following matrix:

$$M(p:q) = \sqrt{\frac{1}{p+q}} \begin{bmatrix} \sqrt{p} & \sqrt{q} \\ -\sqrt{q} & \sqrt{p} \end{bmatrix}$$

Using these gates, you can get a W state with a sequence of increasingly-controlled operations:

This circuit is somewhat inefficient. It has cost $O(N^2 + N \lg(1/\epsilon))$ where $N$ is the number of qubits and $\epsilon$ is the desired absolute precision (since, in an error corrected context, the odds gates are not native and must be approximated).

We can improve the efficiency by switching from a "transfer out of what was left behind" strategy to a "transfer out of what is traveling along" strategy. This adds a fixup sweep at the end, but only requires single controls on each operation. This reduces the cost to $O(N \lg(1/\epsilon))$:

It is still possible to do better, but it starts to get complicated. Basically, you can use a single partial Grover step to get $N$ amplitudes equal to $\sqrt{1/N}$ but they will be encoded into a binary register (we want a one-hot register with a single bit set). Fixing this requires a binary-to-unary conversion circuit.

The partial grover step (from "Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity"):

The binary to unary conversion:

Using this more complicated approach reduces the cost from $O(N \lg(1/\epsilon))$ to $O(N + \lg(1/\epsilon))$.

Answer 3

You can define the sequence recursively. Conceptually, what you want to do is:

• Create the initial state $|0\rangle^{\otimes N}$

• On qubit 1, apply the gate $$ \frac{1}{\sqrt{N}}\left(\begin{array}{cc} 1 & \sqrt{N-1} \\ \sqrt{N-1} & -1 \end{array}\right) $$

• Controlled off qubit 1, apply "make $|W_{N-1}\rangle$" on qubits 2 to $N$ (i.e. on do this if qubit 1 is in the $|1\rangle$ state, otherwise do nothing)

• Apply a bit-flip gate on qubit 1.

This algorithm, as expressed, is not made up of only one- and two-qubit gates, but it can certainly be broken down as such by standard universality constructions.

Also, this may not be the most efficient algorithm you could come up with. For example, if $N=2^n$, you could use just $n$ layers of square-root of swap gates to produce what you want -- start with a $|1\rangle$ on a single qubit. Root-swap with a second qubit, and you've got the $|W_2\rangle$ (up to phases that you'll need to take care of). Put an ancilla next to both of these, and do root swaps between W-ancilla pairs, and you've got $|W_4\rangle$, repeat and you've got $|W_8\rangle$, and so on. I believe this is basically what they do experimentally here. You should be able to incorporate this algorithm into the first one to make it more efficient ($O(\log N)$) for any arbitrary size, but I've never stopped to work out the details with any great care.

Answer 4

Based on this paper, I have implemented the W state for n-qubits by Qiskit. Here is my code:

• Create $|W_n\rangle$ state: link
• Create F gate and $|W_3\rangle$ state: link