Deutsch’s algorithm F.A.Q.
Like most people, you may view Deutsch’s algorithm with a bit of skepticism. Is this all we can do with a multi-million-dollar quantum computer? Let’s consider such questions:
- With Deutsch’s algorithm, you evaluate f(x) once instead of twice. Is that time-saving such a big deal?
The time saving is tiny, but tiny time savings add up when you’re doing billions of calculations. Besides, the fact that we can evaluate a function only once and discover something about two possible output values (f(0) and f(1)) is amazing. You have to admit that.
- Deutsch’s algorithm requires circuitry that’s not needed in the classical algorithm. You need a few Hadamard gates and an oracle with two outputs. Does this mean that Deutsch’s algorithm is less efficient than the classical algorithm?
To measure efficiency, computer scientists consider the relationship between the amount of input and the...
