Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I was wondering if anyone knew on whether it is possible to construct a quantum oracle that was able to detect whether a given state vector was "non-negative"? Essentially I have a classical problem where the solution would be a non-negative vector but I am unsure about how to bring this into a quantum mechanical form since we're dealing over the complex field.
If anyone has any papers that they have come across that would be along these lines, would be greatly appreciated!
Your question is vague in several ways.
By a "non-negative vector," do you mean a quantum pure state, all of whose amplitudes are nonnegative real numbers? (Or rather, a state that's equivalent to such a state under multiplication by a complex scalar, which of course is physically unobservable?)
By a "quantum oracle," do you mean a unitary transformation that outputs ACCEPT when fed a non-negative state, and REJECT when fed any other state? With probability close to 1?
If so, then it's immediate that no such oracle exists. Indeed, the probability that the oracle accepts is a continuous (quadratic) function of the amplitudes, but the amplitudes can be arbitrarily close to 0 while still being either positive or negative.
So at the least, you'd need some lower bound on the absolute values of the amplitudes -- together, perhaps, with the assumption that the amplitudes are all real (or if complex, that their angles with each other are either 0 or else sufficiently large). If you impose these conditions, then the "non-negativity oracle" does exist for quantum states of dimension 2: there it's called the "Hadamard gate," or the "Deutsch-Jozsa algorithm"! On the other hand, because of quantum-mechanical linearity, one can prove that the non-negativity oracle won't exist for states of dimension 3 or greater -- or will exist but only with very large probability of error (approaching 1).
