TL;DR: If you have two entangled qubits in the state $|00\rangle + |11\rangle$, what is the result of applying the Hadamard gate on the second qubit, and why?
I am trying to understand $\text{PSPACE} \subseteq \text{QIP}(3)$ (Watrous, 2003), and have troubles understanding the following.
Hadamard gate: Given some qubit, one can test that it is in a uniform superposition by applying the Hadamard gate on it as it will map it to $|0\rangle$ in this case, $$H(|0\rangle + |1\rangle) = |0\rangle.$$ By measuring it, you have some probability to get a $1$ iff. the qubit was not in a perfectly uniform state.
With entanglement: Now, the paper claims that you can use the Hadamard gate to detect entanglement as well. Given two qubits, $x,y$, that are perfectly entangled, you can have them in the superposition $$xy = |00\rangle + |11\rangle.$$ I understand that if you measure $x$, then apply the Hadamard gate to $y$, it will not map it to $|0\rangle$ as it will be entirely determinated by the measurement made on $x$.
What I don't understand: They do not claim to be able to measure/collapse the qubits that are entangled with the qubits they want to test, so how does it work? If you have two entangled qubits in the state $|00\rangle + |11\rangle$, what is the result of applying the Hadamard gate on the second qubit, and why?
Where is it in the paper:
- When skecthing the protocol at the end of the introduction section (End of first paragraph, page 2):
If there is significant correlation between the low-index prover responses and the high-index verifier-messages, the uniformity test [Hadamard gate, measure 0s] will fail with high probability
- When discussing the completeness of the protocol, in particular step 2. of the verifier (start of page 8):
Next, the verifier applies the Hadamard transform to every qubit in each register of $\bar{R^u}$. If $\bar{R^u}$ now contains only 0 values, the verifier accepts, otherwise the verifier rejects. In short, the verifier is projecting the state of $\bar{R^u}$ onto the state where $\bar{R^u}$ is uniformly distributed over all possible values. It is easy to check that in the case of the honest prover the registers $\bar{R^u}$ are not entangled with any other registers, as each register of $P^u$ depends only on those of $R^u$, and are in a uniform superposition over all possible values. Thus, the verifier accepts with certainty in this case.
- Also in the proof of soundess, same page