I was recently doing a search on Oracle and came down to Quantum Oracles.

The subject of quantum computing intrigued me since my student days.  I still remember the Mathematica quantum machine simulation packages and the vector maths associated with the theory.  The thing is, the paradoxes of quantum mechanics were stimulating and – sometimes – funny, as Richard Feynman once pointed out to his students

What I am going to tell you about is what we teach our physics students in the third or fourth year of graduate school—and you think I’m going to explain it to you  so you can understand it? No, you’re not going to be able to understand it. Why, then, am I going to bother you with all this? Why are you going to sit here all this time, when you won’t be able to understand what I am going to say? It is my task to convince you not to turn away because you don’t understand it. You see, my physics students don’t understand it either.

That is because I don’t understand it. Nobody does.

I couldn’t have imagined a better motivation to try to understand this theory.  It was not surprising then that Feymann also came up with the concept of quantum computers in 1982, but it took more than a decade to propose a practical implementation, in 1993.  I can still  recall Roger Penrose’s disappointment on his book “The emperor’s new mind” relative to the Deutsche discovery of an universal quantum computer

So far these results are a little disappointing for such a striking idea, but these are early days yet.

That was in 1990.  We are now in 2010.

20 years later, where are we ?

Quantum computers present a very powerful property:  the qubits can be in a coherent superposition state of the basic 1 and 0 values. This means that by performing a single operation on a qubit, we could simultaneously perform an operation on two distinct values.  You can see the inherent parallelism and the power when the number of qubits increases.

The problem is that when a qubit in a coherent state is observed, it decoheres and collapeses to a classical state.  This is why to get the solution to a problem from a quantum computer can be as hard as the problem itself.

But how are the quantum computers going to be used, if ever ?

In classical computational theory, all computers are universal Turing machines in essence.  The Church-Turing thesis states that

Everything computable can be computable by a Turing machine.

How does this links to quantum computing ?

After Feynman’s discovery that classical Turing machines would take exponential time to simulate quantum phenomena, advocating that his quantum computer would not,  David Deutsch published a revolutionary paper around 1985 where he states

A class of model computing machines that is the quantum generalization of the class of Turing machines is described, and it is shown that quantum theory and the ‘universal quantum computer’ are compatible with the principle. Computing machines resembling the universal quantum computer could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine.

So, what’s an quantum Oracle, anyway  ?

That’s a quantum circuit able to recognize solutions to a given problem.  And practical implementations are slowly emerging, mainly based on optics and the so-called Josephson junctions.  Only small-scale experiments are possible so far due to the extreme fragile nature of such systems (high rate of failures, decoherence,…).

So how can these Oracles be useful ?  They could be really useful, provided that they use quantum algorithms.

And such algorighms, as Shor or Grover‘s, are extremely powerful. if they are implemented.

The practical applications of such implementations are astonishing:

  • Number factorisation (and hence, calculate private keys from public keys on all current classic cryptosystems) and cryptography in general.
  • Unsorted search
  • Quantum communication
  • Data storage

And the future ?  there are already people working hard to explore the limits of quantum computing, as for example Seth Lloyd, from the Extreme Quantum IT research center (XQIT).

Maybe we will see, in a not so far future, Oracle Corporation unveiling his new Quantum Oracle Machine at the Open World conference ? 🙂

Interesting links

History of the Church-Turing thesis

A brief history of quantum computing