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?)


1 Answer 1


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.

This has indeed an effect identical to the unambiguous state discrimination POVM. It's just that in this case no dilation is necessary to do the unambiguous state discrimination, the optimal POVM is just a projective measurement.

  • $\begingroup$ Thanks! Can we say that he independently applies a Hadamard gate to each qubit separately, and then measures in the computational basis? Or is this measurement more subtle than separate Hadamard gates on different qubits? $\endgroup$ Commented Jan 24 at 15:45
  • $\begingroup$ No subtlety, what he is doing is literally applying a Hadamard to each qubit and measuring in the computational basis. $\endgroup$ Commented Jan 24 at 16:23
  • $\begingroup$ 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? $\endgroup$ Commented Jan 24 at 16:37
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jan 24 at 16:53
  • $\begingroup$ Oh, now I understand the comment about dilation not being necessary. We don’t have to go to the church of the higher Hilbert space with any ancillary measurements. $\endgroup$ Commented Jan 25 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.