Sumário
207 / 216
Salvando leitura…
Algoritmos ideais encontraram limites físicos antes da máquina final

O atalho ainda precisava de uma estrada

Deutsch, Grover e Shor sem mitologia

Deutsch–Jozsa mostrara interferência sob uma promessa; Grover oferecera ganho quadrático ótimo em consultas; Shor encontrara tempo polinomial para problemas sem algoritmo clássico conhecido comparável. Nenhum deles dizia que computadores quânticos vencem em tudo.

O impacto criptográfico de Shor atingia fatoração e logaritmo discreto usados em sistemas de chave pública quando máquinas tolerantes a falhas fossem grandes o bastante. Criptografia simétrica sofre redução quadrática genérica por Grover e pode compensar com chaves maiores; os detalhes dependem do modelo de ataque.

Lia distinguiu ameaça futura de quebra instantânea atual. Recursos lógicos exigem muitos qubits físicos corrigidos, portas e tempo. Ainda assim, migrar criptografia leva anos e dados cifrados podem ser armazenados hoje para ataque posterior; planejamento não deve esperar a máquina pronta.

Tomás voltou à régua. Contagens de qubits físicos, taxa de erro, compilação, conectividade e volume de código determinariam a estrada. Algoritmos assintóticos eram mapas indispensáveis, mas não asfalto.

O ganho também podia desaparecer se carregar dados, preparar estados ou obter precisão custasse mais que a parte acelerada. Afirmações de vantagem precisam incluir o pipeline ponta a ponta e a melhor alternativa clássica atualizada.

Uma rajada de ruído atravessou o circuito e apagou os picos de Fourier. Lia viu a última barreira: amplitudes úteis eram delicadas, e algoritmos longos precisavam detectar e corrigir erros sem medir a informação lógica diretamente.

O atalho terminava diante de uma estrada quebrada. O último capítulo construiria redundância sem clonagem, síndromes sem revelar o estado e portas que continuassem corretas mesmo quando componentes falhassem.

Fontes desta página

  1. David Deutsch e Richard Jozsa (1992). Rapid Solution of Problems by Quantum Computation.Proceedings of the Royal Society A, 439, 553–558. Apresenta um algoritmo que distingue exatamente funções prometidas como constantes ou balanceadas com uma consulta quântica ao oráculo.
  2. Lov K. Grover (1997). Quantum Mechanics Helps in Searching for a Needle in a Haystack.Physical Review Letters, 79, 325–328. Desenvolve a interpretação por interferência da busca quântica e demonstra o ganho quadrático para encontrar um item em dados não ordenados.
  3. Peter W. Shor (1994). Algorithms for Quantum Computation: Discrete Logarithms and Factoring.35th Annual Symposium on Foundations of Computer Science, 124–134. Apresenta algoritmos quânticos polinomiais para fatoração e logaritmo discreto por redução a estimação de período e transformada quântica de Fourier.