# In Deutsch–Jozsa algorithm, why one can safely ignore the last qubit of oracle output?

Wikipedia article about Deutsch-Jozsa algorithm says, under the section Algorithm, that:

At this point the last qubit, $$\frac{|0\rangle - |1\rangle}{\sqrt{2}}$$ may be ignored.

Does it mean that, if we can factor (written in terms of tensor product) out some bits, not involving the oracle function $$U_f$$, then we can always ignore when doing measurements, because it doesn't change the probability of the states?

• Yes that’s right. Commented Aug 6, 2023 at 12:21
• @MarkSpinelli at this example, the measurement is done for only top bit. What if the final measure is done for both top and bottom bit? Can we still ignore all such bits? (Factored out bit without involving any oracle function) Commented Aug 6, 2023 at 18:59

TL;DR: Yes, if the registers $$x$$ and $$y$$ are in a product state (as is the case in Deutsch-Jozsa algorithm) then the outcome of any measurement on $$x$$ is independent of the state of $$y$$.

Consider an observable on the Hilbert space of $$x$$ described by a Hermitian operator $$A_x:=\sum_i\lambda_i P_i$$ where $$\lambda_i\in\mathbb{R}$$ are the eigenvalues and $$P_i$$ are the corresponding eigenprojectors. Suppose we perform a measurement described by $$A_x$$ on $$x$$ while the two registers are in a product state $$\rho_x\otimes\sigma_y$$. Then the probability of outcome $$\lambda_i$$ is \begin{align} p_i&=\mathrm{tr}((A_x\otimes I_y)(\rho_x\otimes\sigma_y))\tag1\\ &=\mathrm{tr}((A_x\rho_x)\otimes(I_y\sigma_y))\tag2\\ &=\mathrm{tr}(A_x\rho_x)\cdot\mathrm{tr}(\sigma_y)\tag3\\ &=\mathrm{tr}(A_x\rho_x)\tag4\\ \end{align} where $$I_y$$ is the identity operator on the Hilbert space of $$y$$ describing the fact that we do not interfere with the register $$y$$. Since $$\sigma_y$$ falls out of the last equation, we conclude that if the registers $$x$$ and $$y$$ are in a product state then the outcome of any measurement on $$x$$ is independent of the state of $$y$$.

Welcome to QCSE. Versions of this question have been asked many times on this site. Most quantum algorithms have this odd feel where work is done and evaluated into a bottom (second) register, but only the top (first) register needs to be measured. There are some exceptions, but the "big three" of Deutsch-Jozsa, Simon, and Shor don't need their bottom register measured at all.

Indeed, a way to tell that the bottom register need not be measured, just by looking at the circuit, is to envision sending those qubits in the bottom register off to Alpha Centauri. Your algorithm should still work regardless of whether the qubits are measured upon arrival at Alpha Centauri or not.

It shouldn't matter whether we measure the bottom register before measuring the top register, or after the top register, or not at all.