En una frase
Gives the first problem a quantum computer provably solves exponentially faster than any deterministic classical algorithm.
Puntos clave
- ▸Determines whether a hidden function is constant or balanced in a single query.
- ▸Any deterministic classical algorithm may need exponentially many queries in the worst case.
- ▸Demonstrates quantum parallelism and interference as concrete computational resources.
En lenguaje sencillo
Imagine a black box that takes a string of bits and returns 0 or 1, and you are promised it either always returns the same answer or returns each answer exactly half the time. Classically, in the worst case you must poke the box an enormous number of times to be sure which. Deutsch and Jozsa showed a quantum computer can query it once: put the input into superposition so the box is evaluated on every string at the same time, then use interference to make the wrong possibilities cancel out. Nobody needs this specific answer, but it was the first ironclad proof that quantum computation is a genuinely different kind of computing.
Por qué importa
The problem itself is artificial and has no practical use, but it was the first hard proof that quantum computers are not merely faster — they are asymptotically more powerful for some tasks. It set the template Shor and Grover later followed.
Términos del glosario relacionados
Superposition
FundamentalsThe ability of a quantum system to exist in multiple states at the same time.
Hadamard Gate
GatesThe H gate — creates an equal superposition of |0⟩ and |1⟩ from a basis state.
Quantum Circuit
FundamentalsA sequence of quantum gates applied to a register of qubits, followed by measurements.
Quantum Advantage
FundamentalsA demonstrated speedup or improvement where a quantum computer outperforms the best classical algorithm on a practical task.