# Synthesize superposition state using generalized Grover algorithm

I'm following the paper by Grover (L. K. Grover, Phys. Rev. Lett., 85:2000) and trying to synthesize the following superposition state $$|\psi\rangle = \frac{2|00\rangle - 3|01\rangle - 4i|10\rangle + 5i|11\rangle}{\sqrt{54}}$$

Following the paper, if I understand correctly, one should expect $$Q|00\rangle = |\psi\rangle$$ where $$Q = -I_sU^{-1}I_tU$$ with $$U = U_2U_1\;,\;\;U_1 = H^{\otimes2}$$ However, I don't understand the part where the author construct $$U_2$$.

Can anyone gives some tips?

Followups: Suppose the last qubit is the ancilla qubit. Then $$ccR_Y(00) = \begin{bmatrix} I_6 & \\ & \cos(\theta_{00}/2) & -\sin(\theta_{00}/2) \\ & \sin(\theta_{00}/2) & \cos(\theta_{00}/2) \end{bmatrix}$$ Then $$U_2 = ccR_Y(11)\cdot ccR_Y(10)\cdot ccR_Y(01)\cdot ccR_Y(00)$$ and so $$U = U_2U_1 = U_2\cdot(H^{\otimes2}\otimes I)$$

I'd say that the paper is pretty clear about what you have to do. First, you introduce an extra qubit, so you start in $$|0\rangle|00\rangle$$. $$U_2$$ is specified (in your case) as a set of 4 controlled-$$Y$$ rotations, controlled off the two qubits on which you're creating the state and targeting the ancilla. (You'll be able to simplify this slightly).

Fr example, take the $$|00\rangle$$ term in your target state. Because the target amplitude is $$2/\sqrt{54}$$, you want to perform a controlled-$$Y$$ rotation, controlled off the two controls both being 0, implementing a $$Y$$ rotation such $$R_Y$$ such that $$R_Y|0\rangle=\frac{2}{\sqrt{54}}|0\rangle+\sqrt{\frac{50}{54}}|1\rangle.$$ Now repeat for your other 3 basis states.

$$I_t$$ is a $$Z$$ gate applied to the ancilla qubit. $$I_s$$ is, effectively, a controlled-controlled-$$Z$$ gate, but it gives the -1 term only when all 3 qubits are in $$|0\rangle$$.

Simplification: Once you have calculated the four rotations $$R_Y(\theta_i)$$ which are all controlled off two qubits, you can simplify this a bit. Instead of c-c-$$R_Y(\theta_{00})$$, just apply $$R_Y(\theta_{00})$$ and set all other $$\theta_i\rightarrow\theta_i-\theta_{00}$$.

Then take one of the others, say c-c-$$R_Y(\theta_{10})$$ and instead apply c-$$R_Y(\theta_{10})$$ controlled off the first qubit being in the 1 state, and replace $$\theta_{11}\rightarrow\theta_{11}-\theta_{10}$$. Overall, that just reduces the number of multi-control gates you need.

To be more explicit, I am proposing the following circuit (the two different circuits are equivalent ways of writing the same thing), where the ancilla is at the bottom: For this to work, you need $$\cos\frac{\theta_{00}}2=\frac{2}{\sqrt{54}}, \cos\frac{\theta_{01}}2=-\frac{3}{\sqrt{54}}, \cos\frac{\theta_{10}}2=-\frac{4}{\sqrt{54}}, \cos\frac{\theta_{11}}2=\frac{5}{\sqrt{54}}.$$ Also note that I added an $$S$$ gate into the circuit. This was because I missed in the original problem specification that two of the amplitudes were imaginary. You could have alternatively used cc-$$R_x$$ gates.

Note that, in general, this is a really bad way to make a two-qubit state, where you never need more than one controlled-not gate (based on the Schmidt decomposition of the state).

• I still can't understand it well. I tried my best and wrote down $U$ based on your answer. Could you take a look? Nov 16, 2021 at 22:37