# Was Deutsch contemplating a positive-operator valued measurement to distinguish balancedness from constancy?

This is a follow up to a couple of questions on Deutsch's foundational paper on quantum Turing machines. In it, he determines $$f(0)\oplus f(1)$$ with a single query by measuring a state prepared as $$\frac{1}{\sqrt 2}|0,f(0)\rangle+\frac{1}{\sqrt 2}|1,f(1)\rangle$$.

But as explained by John Watrous, the phase-kickback trick was not yet developed, while a constant state such as $$|\psi\rangle=\frac{1}{\sqrt 2}|0,0\rangle+\frac{1}{\sqrt 2}|1,0\rangle$$ is not orthogonal to a balanced state such as $$|\phi\rangle=\frac{1}{\sqrt 2}|0,1\rangle+\frac{1}{\sqrt 2}|1,0\rangle$$. Hence Deutsch refers to a measurement (program) $$\zeta$$ that, when it succeeds, with 100% certainty distinguishes between $$|\phi\rangle$$ and $$|\psi\rangle$$ (but that only succeeds half of the time).

What is this measurement that Deutsch envisioned? Is it a POVM that also indicates success or failure? Deutsch wasn't speaking in terms of gates or circuits yet, but is there an obvious circuit that may or may not use ancillas and that can, if it succeeds, distinguish $$|\psi\rangle$$ from $$|\phi\rangle$$?

Basically I'd like to learn more about positive-operator valued measurements and when to use them (or how to build them). If we do a Hadamard gate on the first qubit and it measures as $$|1\rangle$$ then we know with certainty that our state was originally constant, while if we measure as $$|0\rangle$$ then we cannot conclude, with certainty, that our state was originally balanced. How could we "improve" the Hadamard test to know both with certainty (at the cost of us succeeding only half of the time?)

Deutsch is explicit that what he is doing is a projective measurement, namely $$\{|+-\rangle, |--\rangle, |++\rangle, |-+\rangle\},$$ where the first outcome indicates the function is constant, the second indicates that the function is balanced, the third outcome indicates that it was inconclusive, and the fourth outcome is impossible to occur if the quantum computer is noiseless.
• But if our state is $|\psi\rangle=\frac{1}{\sqrt 2}|0,0\rangle+\frac{1}{\sqrt 2}|1,0\rangle=|+,0\rangle$, then, after Hadamard'ing both qubits independently, aren't we left with $|0,+\rangle$ and not $|+,-\rangle$, or am I missing something stupid? Jan 24 at 16:37
• After Hadamard'ing both qubits you have to measure in the computational basis, not in the $\{|+\rangle,|-\rangle\}$ basis. So either you compute the probability of getting $|+-\rangle$ with your original state $|+0\rangle$, or the probability of getting $|0,1\rangle$ with the Hadamard'ed state $|0+\rangle$. Both alternatives are equivalent, and give you probability 1/2, because that's the best Deutsch could do, he didn't know it was possible to make it work with probability 1. Jan 24 at 16:53