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?

  • $\begingroup$ How is your question related to your title? $\endgroup$ Commented Nov 24, 2018 at 0:42
  • $\begingroup$ 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). $\endgroup$ Commented Jan 16, 2019 at 14:32

1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$ Commented Nov 26, 2018 at 10:41
  • $\begingroup$ 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.) $\endgroup$
    – DaftWullie
    Commented Nov 26, 2018 at 10:46
  • $\begingroup$ 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. $\endgroup$
    – DaftWullie
    Commented Nov 26, 2018 at 10:50
  • $\begingroup$ 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)? $\endgroup$ Commented Nov 26, 2018 at 12:16
  • 1
    $\begingroup$ Yes, that would do. $\endgroup$
    – DaftWullie
    Commented Jan 29, 2019 at 18:43

Your Answer

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

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