display | more...

In the early days of quantum computation research Feynman proposed that a quantum computer would be faster at certain tasks than a conventional computer. David Deutsch came up with an elegant thought problem where this would be true. He reasoned that if a person was looking for a property of all answers and not a single answer a quantum algorithm would be more efficient. For the specific problem there is a 1 bit input and 1 bit output black box. The user wants to know if the black box function (which takes a long time to run) is dependent on the inputs (balanced), or whether it is constant. In a conventional computer the function would have to be run twice, and then both answers compared. In the quantum case a superposition of 1 and 0 is input and the output is weather it is balanced or constant. It is able to solve this black box problem in half the time. It is interesting to note that the user has no information about what the answers actually are (if it is constant, not known if constant 1 or constant 0).

Log in or register to write something here or to contact authors.