I understand that quantum physics supports the concept that the probability of a qubit collapsing into (say) 1, can be negative or positive… and that quantum computing uses this as a feature, adding opposing probabilities together to cancel them out. [If that is wrong, please say so; I understand that to be fundamental.]
I have been trying to understand Grover’s Algorithm. Apparently, it is all about an “unknown” diagonal matrix — “U” — with only 1 of $-1$, and every other (diagonal) position being $1$.
Broadly, I can see how the algorithm works to amplify the (“unknown”) negative value, relative to the other values. (I have not yet strained by brain to figure out the “second Grover step”, that takes the negative and makes it large and positive.)
What is bothering me is thinking about what would actually happen, in an actual quantum computer, if one performed the operation that was represented by the above “U” matrix.
The thing is… I am pretty confident that matrices and tensor products are strictly confined to the representation of what goes on inside a quantum computer. One can not find tensor products (nor matrices) by looking inside a quantum computer, so to speak. (Of course, that is not to deny that the former do represent the latter.) [Again, if that is wrong, please say so.]
Suppose we perform the first couple of steps in the Grover Algorithm. (Stipulatively) the correct answer is {11}, and that would be represented by the tensor product {0001} — the 4th item is marked as the value represented by those q-bits. Thus, our diagonal matrix has {1,1,1,-1}.
We set our q-bits to 0, and put them into superposition [which of course changes all the items in the tensor product], and perform U. This marks the 4th item in the tensor product with a “-” sign.
Again, quantum physics supports quantum computing having probabilities with a negative sign associated with them… but the concept of the tensor product having a negative sign exists only within the descriptive system of matrices and tensor products [as I understand it]. (That is… it might represent something, but it does not represent a negative probability in a q-bit.) Thus, the tensor product tells us that there is an equal probability of the four possible outcomes — {00}, {01}, {10} and {11}. It is not possible to say that the tensor product marks the {11} as having negative probability — as a statement about the pertinent q-bits — as that would violate factorisation [I think]. (How would it be if we had 8 q-bits, and we marked “10011011” as negative? If we make all the pertinent q-bit probabilities negative, this must surely affect the other product items that include them… not to mention that they would cancel themselves out. If we mark only 1 value for 1 q-bit as negative, that would make half of the tensor product negative, not just 1 item… not to mention the fact that the negative item in the tensor product is picking out (something about) every q-bit.)
The tensor product supports negative probabilities, and quantum computing supports negative probabilities… but the negative probability in the tensor product does not directly represent a negative probability in one q-bit… because each and every item in the tensor product represents every q-bit. If, conversely, it does affect one of the two probabilities in every q-bit, that would make negative every product with an odd number of those marked probabilities.
The point is that applying the described function (U) in an actual quantum computer appears to me to lose the negative sign.
What gives, please?
