Dan Simon from Université de Montréal, invented an "oracle problem" where quantum computer would be exponentially faster than a conventional traditional computer.
In context, the oracle machine is like a Turing machine, but connected to an oracle, which is an entity capable of solving problems. For example, it can be made to solve decision problems or a function problem. The problems don't have to be computable, because the oracle is not assumed to be a Turing machine, or even a computer program.
Oracle here, is simply a "black box," capable of giving solutions or hints.
The oracle machine includes:
- A work tape, which is a sequence of cells without beginning or end.
- A read/write head that has a single cell of the work tape, which can read and write data, and increment or decrement its position.
- A controller, which can be in one of a finite number of states.
- An oracle tape, which is a semi-infinite tape separate from the work tape.
- An oracle head that is similar to the read/write head, and can move left or right along the oracle tape reading and writing symbols.
- Special states which has the ASK state and the RESPONSE state.
When an oracle is consulted, it will enter the ASK state. Here, the contents of the oracle tape are viewed, and then replaced with the solution that the asked problem. The oracle head then is moved back to the first square on the oracle tape, after which the state of the oracle is changed to RESPONSE.
The main idea for oracle was further developed by Peter Shor's factorization algorithm.