Methods for Reducing Ancilla-Overhead in Block Encodings

Os computadores quânticos prometem resolver problemas que levariam milênios para serem concluídos por máquinas clássicas, mas são notoriamente frágeis. Para realizar cálculos complexos, essas máquinas dependem de uma técnica chamada codificação em bloco (block encoding), que permite representar operações matemáticas que não são perfeitamente reversíveis, uma necessidade para aplicações do mundo real, como simular reações químicas ou resolver equações diferenciais. Pense na codificação em bloco como uma forma de esconder um cálculo complexo e não reversível dentro de um processo quântico maior e reversível, utilizando bits auxiliares extras, conhecidos como ancilas (ancillae). Esses bits auxiliares atuam como um espaço de trabalho temporário, permitindo que o computador quântico manipule dados sem quebrar as leis fundamentais da mecânica quântica. No entanto, à medida que os algoritmos se tornam mais complexos, eles exigem cada vez mais desses bits auxiliares. Como o hardware quântico é atualmente limitado quanto ao número de qubits que pode conter, essa demanda por espaço extra cria um gargalo severo, muitas vezes forçando os pesquisadores a escolher entre executar um cálculo ou ficar sem memória completamente.

Uma equipe de pesquisadores da Universidade da Califórnia, Berkeley, e do Instituto Alfréd Rényi de Matemática, na Hungria, desenvolveu dois novos métodos para reduzir drasticamente o número de bits auxiliares necessários para as codificações em bloco. O trabalho deles aborda o problema de duas maneiras diferentes, oferecendo uma troca entre espaço e tempo no primeiro caso, e entre espaço e precisão no segundo. O primeiro método introduz uma forma de "limpar" o espaço de trabalho após a conclusão de um cálculo. Em muitos algoritmos quânticos, uma vez que uma codificação em bloco é utilizada, os bits auxiliares permanecem em um estado emaranhado e desordenado que não pode ser reutilizado. Os pesquisadores conceberam um protocolo que redefine coerentemente quase todos esses bits auxiliares para um estado zero limpo, liberando-os para uso em partes posteriores do algoritmo. Esse processo não é instantâneo; requer etapas computacionais adicionais, efetivamente trocando tempo extra pelo recurso valioso de espaço extra. O resultado é um sistema que pode realizar as mesmas operações complexas usando apenas um único bit auxiliar, independentemente de quantos eram originalmente necessários, desde que o cálculo não seja perfeitamente preciso, mas suficientemente próximo para uso prático.

A segunda parte do trabalho deles aborda o desafio específico de multiplicar muitos blocos de codificação, um requisito comum para simular como sistemas físicos evoluem ao longo do tempo. Tradicionalmente, multiplicar um grande número dessas codificações exigia um número de bits auxiliares que crescia logaritmicamente com o número de operações, uma demanda que rapidamente ultrapassa o hardware disponível. Os pesquisadores provaram que, para multiplicação exata e perfeita, esse requisito logarítmico é um limite rígido que não pode ser contornado. No entanto, eles mostraram que, se alguém estiver disposto a aceitar uma quantidade mínima e controlada de erro, esse limite pode ser quebrado. Eles introduziram um novo dispositivo (gadget) que realiza essas multiplicações com um número constante e pequeno de bits auxiliares, independentemente de quantas operações estão sendo encadeadas. O erro introduzido por essa compressão é extremamente pequeno e diminui rapidamente à medida que o número de bits auxiliares é aumentado ligeiramente. Essa abordagem é particularmente eficaz para simulações onde os passos individuais já estão muito próximos de não fazer nada, um cenário comum em simulações de física onde pequenos passos de tempo são usados para rastrear mudanças graduais.

Para garantir que esses cálculos comprimidos ainda sejam úteis, os pesquisadores também demonstraram como utilizar uma técnica chamada amplificação de amplitude oblíqua (oblivious amplitude amplification). Este método atua como um filtro que aumenta a probabilidade de o cálculo ter sucesso, transformando efetivamente um processo que poderia falhar frequentemente em um que tem sucesso quase sempre, mesmo utilizando o método comprimido e aproximado. As descobertas sugerem que, ao gerenciar cuidadosamente a troca entre precisão e uso de recursos, os algoritmos quânticos podem se tornar muito mais eficientes. Isso não é apenas um exercício teórico; os métodos são diretamente aplicáveis à simulação da dinâmica de Hamiltoniana, que descreve como a energia se move através de um sistema, e à resolução de equações diferenciais quânticas, que são essenciais para modelar desde a dinâmica de fluidos até reações químicas. Ao reduzir o excesso de ancilas, essas técnicas podem permitir que computadores quânticos atuais e de curto prazo enfrentem problemas que antes estavam fora de alcance devido à falta de memória disponível.