<p>Your question is vague in several ways.</p>

<p>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?)</p>

<p>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?</p>

<p>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.</p>

<p>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" <i>does</i> 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).</p>

CC BY-SA 3.0
2013-01-02T20:56:17.540Z
thanks for this!  i appreciate your time on this question.
user1898014
CC BY-SA 3.0
2013-01-02T06:17:45.757Z
2013-01-02T06:17:45.757Z
Scott Aaronson
<p>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.  </p>

<p>If anyone has any papers that they have come across that would be along these lines, would be greatly appreciated!</p>

<quantum-computing>
Quantum oracle for non-negative vector
user1898014
# Quantum oracle for non-negative vector

(Asked by: username_0 on 2013-01-02)

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!

**Tags:** quantum-computing

---

## 1 answers

### Answer by username_1 on 2013-01-02. Score: 10 | Accepted answer

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).

> **Comments:**
> **username_0**: thanks for this!  i appreciate your time on this question.  

---

