3

To measure, observe that you are simply projecting a quantum state onto some basis set of vectors. First, I will note that this state is not normalized. Let us first define the following quantum state. $$|\psi_i\rangle = \begin{pmatrix}1\\-1\\0\\0\end{pmatrix}.$$ Then, calculating the corresponding probability yields: $$|\langle \psi_i|\psi_i\rangle|^2 = (...


3

Yes, it will depend on $n$ because sampling with replacement is assumed in the proof, which doesn't make sense if $n$ is finite. Intuitively, if a function $f$ really is balanced, and first output corresponding to certain random input is $0$ or $1$, then the probability that the second output corresponding to some other random input will be the same is less ...


2

I will try to give an answer from complexity theory's point of view. This question should be asked in cs.stackexchange by the way. The Deutsch-Jozsa problem has an efficient algorithm on quantum computation and on a classical probabilistic Turing machine, so it is in BQP and BPP. There is no result that says: if you show a problem A in BQP and not in P, then ...


1

Indeed, the formula assumes that $n=\infty$, and is approximately correct if $2^n \gg k$


Only top voted, non community-wiki answers of a minimum length are eligible