8
$\begingroup$

The generalized W state:

$$W_n=\frac{1}{\sqrt{n}}(|100\cdots 0\rangle + |010\cdots 0\rangle + \ldots + |00\cdots 01\rangle)$$

is often thought of as the uniform superposition over all "one-hot" basis vectors, as each such vector has a single qubit in the $|1\rangle$ state with all others in the $|0\rangle$ state.

Reviewing this question it appears that the generalized W state on $n$ qubits can be prepare from the all-zeroes ket with roughly a linear number of non-Clifford gates. This is in some contrast to the generalized GHZ state/cat state, which can similarly be prepared but only with a single Hadamard and a linear number of CNOT/SWAP gates.

In considering this question I proposed that a generalized superposition over all "two-hot" basis states, e.g.:

$$\frac{1}{\sqrt{n(n-1)/2}}(|1100\cdots 0\rangle + |1010\cdots 0\rangle + \ldots + |0\cdots 0011\rangle)$$

may require a quadratic number of non-Clifford gates to prepare, starting from the all-zeroes ket. My intuition is that there are $n\choose 2$ such states, and accordingly there may be a quadratic number of gates required.

Is this guess correct? In general, does it take a minimum of roughly $n\choose k$ gates to prepare a uniform superposition of all "$k$-hot" vectors on $n$ qubits, starting from some canonical state such as the all-zeroes ket?

This question is borne out of idle curiosity more than anything, to be honest, but it is perhaps interesting to ponder simple states that are a bit hard - but not too hard - to prepare, especially now in the NISQ era where generalized GHZ states are often prepared as test cases, as they are the most sensitive to decoherence, but such cat states can nonetheless be produced with "easier" Clifford gates.

EDIT

Hmmm... it appears that what I call the "$k$-hot" state is also known as a Dicke state. In "Deterministic Preparation of Dicke States" by Andreas Bärtschi and Stephan Eidenbenz can prepare just such a state with only $O(nk)$ gates. This Quirk circuit from their paper gives the $3$-hot Dicke state on five qubits.

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you mean "is there a circuit of this size", or "is this provably the minimum circuit size" (which are very different things)? $\endgroup$
    – DaftWullie
    Nov 18, 2022 at 7:45
  • $\begingroup$ I mean the latter. I’ll edit later to make that clearer. $\endgroup$
    – Mark Spinelli
    Nov 18, 2022 at 12:00
  • $\begingroup$ I think the unsorting technique used in arxiv.org/abs/1711.10460 can be used to do this task in $O(n \lg^2 \frac{n}{\epsilon})$ gates and $O(n \lg \frac{n}{\epsilon})$ space for any $k$. $\endgroup$
    – Craig Gidney
    Nov 18, 2022 at 15:55

1 Answer 1

Reset to default
3
$\begingroup$

This can be done efficiently by using amplitude amplification.

We are going to want to rotate each qubit such that it has a $2/n$ chance of being ON. For that it helps to have this class of gates:

$\text{Odds}_{a:b} = \begin{bmatrix}\sqrt{\frac{a}{a+b}} & -\sqrt{\frac{b}{a+b}} \\ \sqrt{\frac{b}{a+b}} & \sqrt{\frac{a}{a+b}}\end{bmatrix}$.

First step is to initialize all qubits to $|0\rangle$ and apply $\text{Odds}_{2:n-2}$ to every qubit.

If we were to measure the population count of the qubits at this point, and get a result of 2, then we would be done. The chance of that occurring approaches $2/e^2 \approx 25\%$ as $n$ increases. So it would be a perfectly acceptable repeat-until-success strategy to do it that way, with an expected non-Clifford count of $8n$ ($n$ from the odds gates, $n$ from the Hamming weight measurement, and a factor of 4 from the retries).

Instead of doing that, we are going to phase the states that have hamming weight 2 by around 135 degrees, apply $\text{Odds}_{2:n-2}^{-1}$ to every qubit, phase the $|0\rangle$ state by around 135 degrees, and apply $\text{Odds}_{2:n-2}$ to every qubit. This isn't exactly amplitude amplification, but it seems to work pretty well.

After these steps the overlap with $\left|{n \atop 2}\right\rangle$ is above 99%. I think you can get as close as you want to 100% by more carefully tuning that 135 degree rotation. It should limit to some specific angle as $n$ increases. Regardless, being above 99% is more than good enough to retry until success.

So now the expected non-Clifford count is $6.06n$, with $3n$ coming from the three layers of odds gates, $2n$ coming from the two times we had to compute the population count (once to phase it and once to postselect on it), $1n$ coming from phasing $|000...0\rangle$, and the last $0.06n$ coming from retries.

A particularly nice property of this construction is that the $6.06n$ non-Clifford gates can be all be Toffoli gates, instead of arbitrarily complex or accurate non-Clifford gates that are hard to distill. For this to work you'd pre-pay $O(\lg^2 \frac{1}{\epsilon})$ T gates to prepare phase gradient registers used for Hamming weight phasing.

Here's a quirk circuit showing it works:

enter image description here

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks! What is the simplest class of states that require $O(n^2)$ or $O(n^k)$ non-Clifford gates to prepare if not these Dicke states? $\endgroup$
    – Mark Spinelli
    Nov 18, 2022 at 17:05
  • 1
    $\begingroup$ @MarkS any class of states that has at least n 4^n members must have members that take at least n^2 gates to prepare. $\endgroup$
    – Craig Gidney
    Nov 18, 2022 at 18:36
  • $\begingroup$ @CraigGidney what do you mean by “members”? $\endgroup$
    – Lior
    Nov 18, 2022 at 18:48
  • 1
    $\begingroup$ @Lior There is a set of states that may need to be prepared. The number of members is the cardinality of the set. For example, for n qubits, there are n+1 Dicke states, so the number of members would be n+1. $\endgroup$
    – Craig Gidney
    Nov 18, 2022 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.