How does this measurement in the Hadamard basis look like?

Question

I am reading this paper by Mahadev. In going from (19) to (20) the author does a Hadamard measurement on two registers. I don't understand what exactly the Hadamard measurement does.

The (simplified) claim is as follows. Let's start with the following state

$$\vert 0\rangle\vert x_0\rangle + \vert1\rangle\vert x_1\rangle.$$

If one applies the Hadamard measurement to the second register, one obtains

$$\vert 0\rangle + (-1)^{d(x_0\oplus x_1)}\vert 1\rangle,$$

where $d$ is the "measurement outcome".

I've removed some other terms that exist in the original paper but I beleive the above is correct. Is there a way to see why this claim holds? I see it for the case where $x_0$ and $x_1$ are bits but the argument is for bit strings too and I'm not sure why.

1. For the general case, is $|d|=|x_i|$ i.e. if $x_i$ are $k$-bit strings, then we have $k$ possible measurement outcomes?
2. If 1. is true, why does the phase $d.(x_o\oplus x_1)$ emerge?

This is also discussed in this video.

Answer 1

Answer refined based on updated question

Your updated question boils down to something like “if we take a Hadamard transform of a superposition of two basis states and measure, why is our string related to the bitwise XOR of the two basis states?”

But this much has been known since Simon's algorithm. Simon proposed a very restrictive promise on his oracle $U_f$, while the more modern tests use a trapdoor claw-free function - but either way it's the same idea. The Hadamard test reveals XOR patterns hidden in the output of a function.

For example, if you have a wavefunction $|\psi\rangle$ on a register of $k$ qubits that's a superposition of two random basis states with $x_i\in\{0,1\}^k$:

$$|\psi\rangle=\frac{1}{\sqrt 2}\big(|x_0\rangle+|x_1\rangle\big),$$

then taking the Hadamard transform of each qubit in $|x_i\rangle$ and measuring each qubit in the computational basis will return a random $k$-length string $d$ that with high probability is not $\bf 0$ and further satisfies the equation:

$$d\cdot(x_0\oplus x_1)=0.$$

As a Boolean equation this says that if we (1) take the bitwise XOR of the two strings $x_0$ and $x_1$, (2) take the bitwise AND of the string $d$ with this XOR, and (3) find the parity of the number of $1$'s in the AND of the above, the parity will always be $0$. This is because the phase always gets kicked back and the Hadamard transform effectively takes the Fourier transform over the Boolean cube.

To answer your specific questions, if $x_i$ are $k$-bit strings then we have $2^{k-1}$ possible random outcomes for our measured string $d$ and without something like the Simon promise then half of the possible strings satisfy the Boolean equation. The phase emerges as a kick-back via the Hadamard transform.

Here, I concatenate your first qubit with the rest of the register $x_i$ but the argument carries through if you were to Hadamard even the first qubit.