Is there a circuit which certainly distinguishes between $|0\rangle$ and $|+\rangle$ states? Suppose I have a qubit $| \theta \rangle$ which equals to $| 0 \rangle$ or to
$| + \rangle = \frac{(|0 \rangle + |1 \rangle )}{\sqrt{2}}$.
Is it possible to build a quantum circuit C:
$C(| 0 \rangle \otimes | \textbf{x} \rangle) = |0 \rangle  \otimes | \textbf{y} \rangle$
$C(|+ \rangle \otimes | \textbf{x} \rangle) = |1 \rangle  \otimes | \textbf{z} \rangle$
so that I could measure the first qubit of an outcome and know for sure which state
$| \theta \rangle$ was in?
($|\textbf{x} \rangle$ are a few extra qubits supplied of my choice, $| \textbf{y} \rangle$ and $ | \textbf{z} \rangle$ are junk qubits that the circuit produces)
If no, what would be a proof that this is not possible?
 A: No, this is not possible. You are proposing a protocol that will take a system state $|s\rangle$ (where $s=0,+$), couple it with some ancilla state $|a\rangle$, and then evolve it to
$$
|s\rangle\otimes |a\rangle \mapsto U |s\rangle\otimes |a\rangle
$$
through some global unitary $U$ such that
\begin{align}
U |0\rangle\otimes |a\rangle & = |0\rangle\otimes |b\rangle \\
U |+\rangle\otimes |a\rangle & = |1\rangle\otimes |c\rangle.
\end{align}
However, because $U$ needs to be unitary, it needs to preserve the scalar product
$$
(\langle +|\otimes \langle a|)( |0\rangle\otimes |a\rangle)=\frac{1}{\sqrt{2}},
$$
whereas your target states have
$$
(\langle 1|\otimes \langle c|)( |0\rangle\otimes |b\rangle)=0.
$$
Moreover, since any arbitrary quantum channel is an incoherent mixture of unitaries-plus-projective-measurements, and each individual component of that mixture is limited as above, any quantum channel is similarly limited.
A: There is a solution if CTC (closed timelike curve) exists. You can find that if CTC exists, then the no cloning and no distinguishment of nonorthogonal states are not valid any more, since CTC leads to nonlinear QM. You can easily find papers on this issue on arxiv. 
