Correct way of expressing a measurement in a different computational basis

Question

Sometimes we find that the result we want from a quantum algorithm is expressed in terms of a basis that is different from the usual computational basis, which I will call

$$ B_C = \left\{ \lvert 0 \rangle, \lvert 1 \rangle \right\} = \left\{ \left(\begin{array}{c}1\\0\end{array}\right),\left(\begin{array}{c}0\\1\end{array}\right) \right\}. $$

For example, at the end of the Deutsch's algorithm, the first qubits is in the state

$$ \lvert\psi\rangle = (-1)^{f(0)} \dfrac{\lvert 0 \rangle + (-1)^{f(0) \oplus f(1)} \lvert 1 \rangle}{\sqrt{2}}, $$

which can be expressed in terms of the Hadamard's basis

$$ B_H = \{ \lvert + \rangle, \lvert - \rangle \} = \left\{ \dfrac{1}{\sqrt{2}} \left( \begin{array}{c}1\\1\end{array} \right), \dfrac{1}{\sqrt{2}} \left( \begin{array}{c}1\\-1\end{array} \right) \right\} $$

$$ \begin{cases} f(0) \oplus f(1) = 0 \quad\Rightarrow\quad \lvert\psi\rangle = (-1)^{f(0)} \lvert + \rangle \\ f(0) \oplus f(1) = 1 \quad\Rightarrow\quad \lvert\psi\rangle = (-1)^{f(0)} \lvert - \rangle \end{cases} $$

Therefore, we can get the value of $f(0) \oplus f(1)$ just by measuring $\lvert\psi\rangle$ on $B_H$. Since we can only perform physical measurements on $B_C$, this can be achieved performing a change of basis.

Given two basis $A$ and $B$, if the matrix that transforms the elements of $A$ to the elements of $B$ is the matrix $M$, this is also the matrix that maps the coordinates of vectors with respect to $B$ to their coordinates with respect to $A$. Hence, which of these propositions is the correct to express the change of basis we must do to perform the measurement on $B_H$ knowing that physical measurements are actually performed in $B_C$?

1. We must apply the Hadamard's gate, because the matrix $H$ maps $\left\{ \lvert 0 \rangle,\lvert 1 \rangle \right\}$ to $\left\{ \lvert + \rangle, \lvert - \rangle \right\}$, and therefore it transforms the components $\lvert\psi\rangle_{B_H}$ to $\lvert\psi\rangle_{B_C}$.

2. We must apply the Hadamard's gate, because the matrix $H$ maps $\left\{ \lvert + \rangle,\lvert - \rangle \right\}$ to $\left\{ \lvert 0 \rangle, \lvert 1 \rangle \right\}$, and therefore it transforms the components $\lvert\psi\rangle_{B_C}$ to $\lvert\psi\rangle_{B_H}$.

Answer 1

If you want to measure $|\phi\rangle$ in some basis $U|b_1\rangle,...,U|b_n\rangle$ instead of $|b_1\rangle,...,|b_n\rangle$, then you need to rotate the state "backward", i.e. measure $U^{-1}|\phi\rangle$ in $|b_1\rangle,...,|b_n\rangle$.
The simple rule to find the direction of rotation is to consider the state and the required measurement basis together $\{|\phi\rangle, U|b_1\rangle,...,U|b_n\rangle\}$. Then If you what to perform the same measurement in a different basis you need to rotate the whole system altogether.

Answer 2

Say you have two bases $B_1$ and $B_2$. Let $U$ be the unitary that transforms the orthonormal basis vectors in $B_1$ to the basis vectors in $B_2$. So, it is obvious that $U^{\dagger}$ will be the unitary that transforms the basis vectors in $B_2$ to that in $B_1$. For instance let $B_1 = \{|0\rangle, |1\rangle\}$ (the computational basis) and let $B_2 = \{|\uparrow\rangle, |\downarrow\rangle\}$ where $|\uparrow\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\ i\end{pmatrix}$ and $|\downarrow\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\ -i\end{pmatrix}$. Notice that the matrix $U = \frac{1}{\sqrt{2}}\begin{bmatrix}1& 1\\ i & -i\end{bmatrix}$ is the matrix that transforms the basis vectors in $B_1$ to that in $B_2$, i.e., $U|0\rangle = |\uparrow\rangle$ and $U|1\rangle = |\downarrow\rangle$. So we also have $U^{\dagger}|\uparrow\rangle = |0\rangle$ and $U^{\dagger}|\downarrow\rangle = |1\rangle$. Also notice that $U\neq U^{\dagger}$.

For notational convenience, let $$|0\rangle = \begin{pmatrix}1\\ 0\end{pmatrix}_{B_1} ~~\text{ and }~~~~ |1\rangle = \begin{pmatrix}0\\ 1\end{pmatrix}_{B_1}.$$ Also let, $$|\uparrow\rangle = \begin{pmatrix}1\\ 0\end{pmatrix}_{B_2} ~~\text{ and }~~~~ |\downarrow\rangle = \begin{pmatrix}0\\ 1\end{pmatrix}_{B_2}.$$ Now, if you have a state $|\psi\rangle$ in basis $B_1$, say $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$ we can represent this as $|\psi\rangle = \begin{pmatrix}\alpha \\ \beta\end{pmatrix}_{B_1}$. Now notice that the state $|\psi\rangle$ can also be given as $$|\psi\rangle = \alpha|0\rangle + \beta|1\rangle = \alpha U^{\dagger}|\uparrow\rangle + \beta U^{\dagger}|\downarrow\rangle = U^{\dagger}(\alpha|\uparrow\rangle + \beta|\downarrow\rangle).$$ This in vector notation can be given as $$|\psi\rangle = U^{\dagger} \begin{pmatrix}\alpha'\\ \beta'\end{pmatrix}_{B_2}=\begin{pmatrix}\alpha\\ \beta\end{pmatrix}_{B_1}.$$

So for a state that is given in basis $B_1$, to represent the state in $B_2$ basis, we apply $U^{\dagger}$ on the state vector corresponding to the basis $B_1$. Similarly for a state that is given in basis $B_2$, to represent the state in $B_1$ basis, we apply $U$ on the state vector corresponding to the basis $B_2$ where $U$ is the matrix that transforms the basis vectors of basis $B_1$ to the basis vectors of the basis $B_2$.