Thread: Quantum Computation Problem

I'm stuck on the following problem:

Suppose we are given a qubit |q> in an unknown state, but we know it is either |0> or
1/sqrt(2)(|0> + |1>). We would like to devise a circuit to determine, with certainty,
which of the two is the case, using any number of unitary and measurement
operations.

Either explain how to construct such a circuit, or prove that no such circuit is
possible.

Can somebody give me a suggestion for tackling this? My intuition tells me that it shouldn't be possbile and I'd like to prove by contradiction, but I haven't yet been able to come up with anything.

Thanks

Well, after a lot of googling for a push in the right direction (I didn't
find a proof but an assertion), it turns out to be impossible! I think this
is why:

Assume that there is such a circuit described by the unitary operator A.
Then given two input vectors |S1> and |S2>, without loss of generalisation
let:

| A>|S1> -> U|A>|s1> = |A1>|S1>
| A>|S2> -> U|A>|s2> = |A2>|S2>

Now since U is unitary, it is norm preserving so that

<A,S1|A,S2> = <A1,S1|A2,S2> but <A,S1|A,S2> = <A|A><S1|S2> = <S1|S2> and
<A1,S1|A2,S2> = <A1|A2><S1|S2>

so we have <S1|S2> = <A1|A2><S1|S2>

Clearly either A1=A2 or <S1|S2> = 0

But by assumption, our circuit differentiates between S1 and S2, so we must
have A1!=A2. It follows that <S1|S2>=0. Clearly the vectors in the question
are non-orthogonal, so no such circuit exists.