O problema de Deutsch–Jozsa prometia que f:{0,1}^n→{0,1} era constante ou balanceada. Constante significava mesma saída para toda entrada; balanceada, exatamente metade zero e metade um. Funções fora dessas classes eram excluídas pela promessa.
Hadamards preparavam superposição uniforme. O oráculo de fase multiplicava cada |x⟩ por (−1)^{f(x)}. Uma segunda camada de Hadamards fazia a amplitude de |0…0⟩ ser a média de todos esses sinais.
Se f fosse constante, os sinais seriam todos iguais e a medida retornaria 0…0 com certeza. Se balanceada, metade cancelaria a outra e a amplitude desse resultado seria zero. Uma consulta ideal distinguia as classes sem listar a tabela.
Lia comparou com um algoritmo clássico determinista exato: no pior caso, ele precisaria consultar mais da metade das entradas para garantir a resposta. O contraste de consultas era exponencial sob essa exigência de certeza e o oráculo prometido.
Tomás acrescentou o limite omitido em apresentações populares. Um algoritmo clássico aleatório com erro limitado amostra poucas entradas e identifica uma função balanceada com alta confiança. Assim, Deutsch–Jozsa é uma demonstração cristalina de interferência e separação exata, não evidência direta de aceleração prática ampla.
Construir um oráculo para uma tabela arbitrária também pode custar exponencialmente. A vantagem de consulta só se traduz em vantagem total quando a função possui implementação compacta e o modelo de acesso corresponde à tarefa real.
A promessa dividiu o universo de funções e tornou uma propriedade global legível numa amplitude. Lia guardou a lição certa: algoritmos quânticos podem reorganizar fases de muitas entradas, mas sua vantagem depende da pergunta e das regras de acesso.