0
$\begingroup$

There is a machine called oracle which appears in a lot of algorithm of quantum computing, such as Deutsch's algorithm, QFT period-finding. This oracle machine really makes me confused. I've read something about computing theory, and in that, it mentions the oracle as a machine which have a super magic power that can solve a specific question.

If I am not not wrong, I remember the oracle machine firstly appears in Turing's paper, it is a black box which can solve a specific hard question. But Turing just use it to do some mathematical deduction and develop a mathematical theory, that's fine.

But here comes the triky part, if these quantum algorithms depends on such a super magic power machine, doesn't that mean that all these algorithms are no use in real life? Since we don't have the magic to make that oracle.

How can we implement that oracale machine in the real world? You can use Deutsch's algorithm as an example to illustrate this idea.

Cross-posted on physics.stackexchange

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ see eg quantumcomputing.stackexchange.com/q/175/55 and links therein $\endgroup$
    – glS ♦
    Commented Mar 28 at 13:48
  • 2
    $\begingroup$ Please mark crossposts. $\endgroup$
    – Norbert Schuch
    Commented Mar 29 at 2:32
  • 1
    $\begingroup$ @glS "and links therein"? ;-o $\endgroup$
    – Norbert Schuch
    Commented Mar 29 at 3:39
  • 2
    $\begingroup$ I’m voting to close this question because it’s crossposted on physics.stackedchange.com without any indication thereto. $\endgroup$
    – Mark Spinelli
    Commented Mar 30 at 0:42
  • 1
    $\begingroup$ @MarkSpinelli: I understand your reason, however, this question seems to me very important, especially for newcomers to quantum computing. Therefore, I would left it open. $\endgroup$
    – Martin Vesely
    Commented Mar 30 at 8:02

1 Answer 1

Reset to default
5
$\begingroup$

There are a couple of different bits of the philosophy of how we use oracles that we need to touch on here:

  • when we use an oracle, it's often trying to make some claims about how fast the algorithm would run if we had such an oracle. In a sense, it doesn't really matter if you can build such a device or not. Is it unfair to give a quantum computer access to a magical device? What we're comparing it to is a classical computer with access to (more or less*) the same magical device. So long as the two are compared on as equal a footing as possible, that's all that matters.

  • the value of an oracle is not usually about how magical it is or not. All the standard ones in quantum computing are very non-magical: they're just classical function evaluations which are easily constructed. Instead, the value of the oracle is to put you in a straight jacket and say "you must solve the problem like this..", so that you can make conclusions "when I solve the problem like this, quantum is faster than classical by some factor ...". Of course, in the real world, you can solve the problem in whatever way you want. Generally, the oracles are designed to replicate they way we would expect to do the computation in reality, but we cannot generally prove there isn't a better way.

As for the example of Deutsch's algorithm, your oracle has to have two bits of input ($x,y$) and two bits of output ($x,y\oplus f(x)$) for some function $f(x)$. We need to examples, a constant function and a balanced function. For the constant function, let's assume that $f(0)=f(1)=0$. Then the output is $x,y$. In other words, exactly the same as the input. This "magic" is just two quantum wires.

For the balanced function, let's take $f(x)=x$. Then all we have to do is apply a controlled-not, controlled off the $x$ qubit and targeting the $y$ qubit.

*The quantum and classical oracles can be defined to behave in exactly the same way on classical inputs, i.e. $(x,y)\rightarrow (x,y\oplus f(x))$. Of course, the quantum oracle is a little different as it has to also act on superpositions of inputs. Not everyone feels like this makes a fair comparison.

Improve this answer
$\endgroup$
6
  • $\begingroup$ no, you didn't get my point. I understand what you said. but the problem, we can't assume we have the oracle, since the oracle is so strong that the complexity of itself would exceed the complexity of quantum computer. So if we want to prove our quantum algorithm is efficient. we can't assume the existence of the oracle, that would make our provement invalid. And you said our classical computer use the same magic device, this is not the truth, our classical computer didn't use any magic device at all.. $\endgroup$
    – tangyao
    Commented Mar 28 at 13:21
  • 1
    $\begingroup$ @tangyao please consider reviewing Kothari's tutorial quantum algorithms here. In it he answers some questions from the audience related to the same position you are taking. $\endgroup$
    – Mark Spinelli
    Commented Mar 28 at 13:31
  • $\begingroup$ @Mark Spinelli I have go through that video, yes, it did clarified my doubt, it gives an algorithm called uncomputation which can do that. But this fact just show that the name of Oracle is not really accurate, it is not suitable for this situation and it is misleading. $\endgroup$
    – tangyao
    Commented Mar 28 at 16:04
  • $\begingroup$ @tangyao, when we are learning a new field the terminologies used may appear frustrating and confusing, and indeed even long-term practitioners in the field may agree that certain terms are inadequate and improper, but most take a "normative" approach to the terminology and say they use these terms for consistency or for historical reasons. But it can be an uphill battle to change these terms - that's not to say that such terms should never be retired but just that it's difficult. For example, I prefer CCNOT over Toffoli, but I use and accept both. "Oracle" is pretty well established... $\endgroup$
    – Mark Spinelli
    Commented Mar 28 at 17:56
  • $\begingroup$ ... and may be hard to retire, at least within the theoretical computer science community, even though many would agree that it's not an ideal term. You can use another term for it if you would like - people use black-box complexity or query-complexity sometimes - but I'd counsel you against blanket statements such as "it is not suitable for this situation and it is misleading", as many people have used the term and will probably continue to use. Regardless, this is not the forum to discuss or march for prescriptive change. Maybe reddit or your own papers, etc. Otherwise, good luck! $\endgroup$
    – Mark Spinelli
    Commented Mar 28 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.