# How to get all combinations of given input?

I'm stuck with a very specific problem that I'm not sure on how to implement using quantum gates. Suppose I have an n qubit circuit and that I want in output a random n qubit string containing exactly k qubits equals to one. E.g. if n=7 and k=3, possible outputs can be $$|0010110\rangle$$ or $$|0101001\rangle$$. In other words, it basically should give one of the possible combinations of the binomial coefficient $$\binom{n}{k}$$. Is there any efficient way to implement this?

• Generalized W state – AHusain Dec 6 '18 at 19:17
• @AHusain I've read about it in another answer, but, even if I knew how to implement it using classical quantum gates, which I don't, it's still a superposition of basis states containing exactly one qubit to one. What I need instead is k qubits to one. – tigerjack89 Dec 6 '18 at 19:57
• That was just the keyword for how to think about this problem/how to look it up in literature. Yes still need to do the generalization from 1 to k. – AHusain Dec 6 '18 at 20:28
• Thanks, I'm trying to figure it out how to continue starting from the basis W state. – tigerjack89 Dec 6 '18 at 20:36
• For classical computers, this is straight out of the classic book Hacker's Delight: computing the next number with the same number of 1-bits hackersdelight.org/hdcodetxt/snoob.c.txt – ahelwer Dec 7 '18 at 4:13

An alternative way to prepare this state is by using amplitude amplification and a circuit to compute the Hamming weight (number of set bits) of a register.

1. Computing the Hamming Weight

You can use a 3-bit adder to fold three qubits of weight W into one qubit of weight W and one qubit of weight 2W (plus some temporary junk). Assume you have this circuit.

To compute the Hamming weight, consider of all the register's qubits to have weight 1. Keep applying the 3-to-2 adder to triplets of remaining weight 1 qubits until you have exactly 1 qubit of weight 1, and N/2 qubits of weight 2. Repeat on the qubits of weight 2, until you have exactly 1 qubit of weight 2, and N/4 qubits of weight 4.

Keep repeating until you have exactly one qubit of each weight class up to weight 2^ceil(log_2(N)). These qubits form your binary Hamming weight register. If you measured that register and it returned ...000110, then you would be projected into an equal superposition containing all the cases where exactly 6 bits are set.

Once you have the weight, you can easily create a qubit that's set or not set depending on if the weight equals the desired weight. Applying a Z gate to this qubit is the crucial step needed for amplitude amplification.

1. Amplitude amplification.

You want to amplify cases where the Hamming weight is equal to the desired weight. We have just defined how to perform an operation that negates the phases of correct states (compute the Hamming weight, compute the 'is it the right weight?' indicator qubit, hit that qubit with a Z, uncompute the indicate and the Hamming weight). If you alternate this with Grover diffusion operations, you will rotate towards the desired state.

Depending on what your target Hamming weight is, this will take different amounts of time. There is one tricky bit during the very last iteration where you want to use partial phasing operations to exactly nail the desired states, but otherwise it's straightforward.

For example, here is a circuit that creates a superposition of all states less than a given value. It only needs to do one partial step, no full steps, because it limits itself to the case where at least half of the values are included:

1. Overview

I am unsure if this approach will be more or less efficient than the inductive approach used in the other answer. It may depend on what your target weight is.

If amplitude amplification is daunting to you, and you're in a very small case, you can avoid it by initializing the register into $$|+\rangle$$ states, measuring the Hamming weight, and keep retrying until it returns the right answer.

• I'm not pretty sure I've understood the algorithm at all. I'm familiar with Grover's algorithm and I think your Z gate is the one used in the diffusion gate, right? However, I don't understand how to compute the Hamming weight of a set of qubits based on your procedure. – tigerjack89 Dec 8 '18 at 15:26

Go inductively like the strategy described in @DaftWullie answer of General construction of W_n state

Say you have the circuits $$U_{n-1,k-1}$$ that take you from $$| 0 \rangle^{\otimes (n-1)}$$ to the state that is an equal superposition of the $$\binom{n-1}{k-1}$$ possibilities with $$k-1$$ ones. That is each with a coefficent $$\frac{1}{\sqrt{\binom{n-1}{k-1}}}$$. Same but for $$k$$ as well with $$U_{n-1,k}$$

Starting from $$| 0 \rangle ^{\otimes n}$$ apply a unitary on the first qubit that gets you in $$\frac{\sqrt{\binom{n-1}{k}}}{\sqrt{\binom{n}{k}}} | 0 \rangle + \frac{\sqrt{\binom{n-1}{k-1}}}{\sqrt{\binom{n}{k}}} | 1 \rangle$$. This is just a 2 by 2 unitary so you can say where $$| 1 \rangle$$ goes by swapping $$0$$ and $$1$$ coefficients and putting the $$-$$ sign. From there figure out the Euler angles to get into standard form.

Now do two controlled unitaries. A controlled version of $$U_{n-1,k-1}$$ when first qubit is 1. Also a controlled version of $$U_{n-1,k}$$ when first qubit is 0. The numerators cancel and you get the desired resulting state. The whole circuit for this would be $$U_{n,k}$$ then.

For small values of $$n$$ and $$k$$ you need the base case of the induction. But that is going to either be $$n=1$$ and $$k=1$$ in which case you do a $$NOT$$ gate. Or $$n=1$$ and $$k=0$$ in which case you do the identity.

Again same caveats about one and two qubit gates and not the most efficient. You can check how $$k=1$$ special case works.

• Thanks. I'm trying to working on it, but at the moment I've not been able to obtain something relevant. Do you have any additional suggestion? – tigerjack89 Dec 7 '18 at 18:20
• I didn't quite get all the steps, so I proceed with an example. Suppose I have n=5,k=3. The binomial coefficient ncr(5;3) is 10. So, first of all I apply the gate you suggested on the first qubit, obtaining in output a 40% chance on $|0\rangle$ and 60% chance on $|1\rangle$. Now, how do I proceed? I'm not sure on what gate to apply to what qubit, and which is/are the controlling qubit/s at each inductive step. – tigerjack89 Dec 8 '18 at 15:00