# Notation for two entangled registers

Suppose I have two registers x and y, of length m and n bits respectively. I want to initialize my system to contain an equal superposition of all $$2^{n+m}$$ states, then apply an oracle function (in superposition). How do I notate this correctly?

For example:

Consider the system $$|\psi\rangle=|x_{m-1}\rangle...|x_0\rangle|y_{n-1}\rangle...|y_0\rangle = |x\rangle|y\rangle$$

and quantum oracle $$F(x,y)\rightarrow \{0,1\}$$

1. Initialize the system to $$|\psi_0\rangle=|0\rangle|0\rangle$$

2. Apply the Hadamard gate to obtain uniform superposition over all states

$$|s\rangle$$ = $$H|\psi_0\rangle = \frac{1}{\sqrt{2^{n+m}}}\sum_{x=0}^{2^m}\sum_{y=0}^{2^n}|x\rangle|y\rangle$$

3. Compute $$|\phi\rangle = F(|s\rangle) = \alpha|0\rangle + \beta|1\rangle$$, for $$\alpha,\beta \in \mathbb{C}$$

I hope the algorithmic steps I'm describing are relatively clear but is this the correct way to notate it?

• How is your question related to your title? – Norbert Schuch Nov 24 '18 at 0:42
• A more general answer to the question, why can't the state of the extra qubit be written in the form α|0⟩+β|1⟩ can be found in Chapter 10 of Rieffel & Polack, Quantum Computing - a gentle introduction (link to pdf). – Sideshow Bob Jan 16 at 14:32

Your notation is OK up to and including step 2, except for the range of summation. You need $$|s\rangle=\frac{1}{\sqrt{2^{n+m}}}\sum_{x=0}^{2^n-1}\sum_{y=0}^{2^m-1}|x\rangle|y\rangle$$ Now the problem is how to write down the effect of the oracle, and you cannot just write down the output qubit. I think you probably know this from the title of the question, because entanglement will appear that you're not describing. So, you have an oracle that acts as $$|x\rangle|y\rangle|0\rangle\xrightarrow{\text{oracle}}|x\rangle|y\rangle|F(x,y)\rangle.$$ Hence, if the input is some superposition state such as $$|s\rangle$$, we have $$|s\rangle|0\rangle\xrightarrow{\text{oracle}}|\Psi\rangle=\frac{1}{\sqrt{2^{n+m}}}\sum_{x=0}^{2^n-1}\sum_{y=0}^{2^m-1}|x\rangle|y\rangle|F(x,y)\rangle.$$ You absolutely cannot describe (except in very special cases of $$F$$) the last qubit in the form $$\alpha|0\rangle+\beta|1\rangle$$ because it is entangled with the other registers.

The question seems to be evolving into

If I'm not measuring $$x$$ or $$y$$, why can't the state of the extra qubit be written in the form $$\alpha|0\rangle+\beta|1\rangle$$?

There are several ways that this might be answered. Normally, I'd take the partial trace and calculate the reduced density matrix, but I infer from comments that the OP doesn't know this technique. Thus, let us try another route.

Let us assume that the extra qubit can be written in the form $$|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$$. This means that we could define a measurement $$P_\psi=|\psi\rangle\langle\psi|\qquad P_{\perp}=|\psi^\perp\rangle\langle\psi^\perp|$$ where $$|\psi^\perp\rangle=\beta^{\star}|0\rangle-\alpha^\star|1\rangle$$ is orthogonal to $$|\psi\rangle$$. If we can guarantee that the extra qubit is in that state, then we are guaranteed to get the measurement result $$P_{\psi}$$. In other words, $$\langle\Psi|\mathbf{I}\otimes\mathbf{I}\otimes P_{\psi}|\Psi\rangle=1.$$ (The identity operations are how we say that we're not measuring the $$x$$ and $$y$$ systems.) I claim that there are no satisfying $$\alpha,\beta$$ where $$|\alpha|^2+|\beta|^2=1$$, unless $$F(x,y)$$ is a constant function.

So, we start to evaluate \begin{align*} \langle\Psi|\mathbf{I}\otimes\mathbf{I}\otimes P_{\psi}|\Psi\rangle&=\frac{1}{2^{n+m}}\sum_x\sum_y\langle F(x,y)|P_{\psi}|F(x,y)\rangle \\ &=\frac{1}{2^{n+m}}\left(\sum_{x,y:F(x,y)=0}|\alpha|^2+\sum_{x,y:F(x,y)=1}|\beta|^2\right) \\ &= \frac{1}{2^{n+m}}(M|\alpha|^2+(2^{n+m}-M)(1-|\alpha|^2)) \end{align*} Where $$M$$ is the number of values such that $$F(x,y)=0$$. Setting this equal to 1, we can rearrange for $$|\alpha|^2$$: $$|\alpha|^2=\frac{M}{2M-2^{n+m}}$$ For $$|\alpha|^2$$ to be a valid value, it must be $$0\leq|\alpha|^2\leq 1$$. One has to be careful in the analysis here. If we assume that $$2M>2^{n+m}$$, then the denominator is positive, and $$|\alpha|^2\leq 1$$ implies $$M\geq 2^{n+m}.$$ This only happens if $$M=2^{n+m}$$, in other words, $$F(x,y)=0$$ for all $$x$$ and $$y$$. On the other hand, if $$2M<2^{n+m}$$, the denominator is negative, and so $$|\alpha|^2\geq 0$$ implies $$M\leq 0$$. This can only happen if $$M=0$$, i.e. all answers $$F(x,y)$$ give answer 1.

We conclude that unless $$F(x,y)$$ is constant, there is no valid $$\alpha,\beta$$ so that the measurement gives probability 1, which means there is no pure state description of that qubit.

• Thank you, this is useful. Suppose I do not care about, and do not measure the state of $|x\rangle|y\rangle$ after applying F: can I then revert to $\alpha|0\rangle+\beta|1\rangle$ for my description of the oracle output? i.e. there is a certain probability to measure each that I will estimate via Brassard mean estimation? – Sideshow Bob Nov 26 '18 at 10:41
• No, you cannot revert to $\alpha|0\rangle+\beta|1\rangle$. If you want to describe only the state of the extra qubit, then you have to trace out the other registers, and that will return a mixed state description. Think about it another way: is there a projective measurement that you can do on that single qubit that gives an answer with probability 1? (No.) – DaftWullie Nov 26 '18 at 10:46
• That said, if you start your extra qubit in one of the states $(|0\rangle\pm|1\rangle)/\sqrt{2}$, it will always come out on the state that you put it in as. – DaftWullie Nov 26 '18 at 10:50
• Not sure I understand your first comment. (1) What does it mean to "trace out the other registers"? (2) any measurement on that qbit will give sometimes 1 and sometimes 0 (for nontrivial F) so I think I'm missing why your second question is relevant? (3) whether or not I can use the $\alpha,\beta$ notation is there any reason I can't estimate the proportion of 1s and 0s I will measure on that bit using Brassard's algorithm (obviously re-running F as needed)? – Sideshow Bob Nov 26 '18 at 12:16
• Yes, that would do. – DaftWullie Jan 29 at 18:43