“Quantum algorithms: from large-scale pattern reconstruction to restricted-depth computation

Resumo:

Os algoritmos quânticos aproveitam leis da física quântica para obter uma vantagem de complexidade comparativamente com estratégias clássicas de computação. Nesta tese, apresentamos uma sucessão de trabalhos sobre algoritmos quânticos. Mostramos como acelerar métodos computacionais clássicos com processadores quânticos, desenvolvemos soluções quânticas para problemas de análise de dados, generalizamos uma técnica de simulação de passeios quânticos, reinterpretamos uma interpolação algorítmica clássico-quântica e executamos simulações em computadores quânticos reais.

Um dos principais temas desta tese e acelerar métodos de reconstrução de padrões com processadores quânticos. Desenvolvemos algoritmos quânticos para recuperar padrões escondidos em dados com estrutura de grafos. Estudamos o problema de tracking no contexto de experiências de física de partículas e demonstramos como acelerar um método comum de tracking com técnicas de amplificação de amplitude; propomos uma versão quântica do algoritmo density peak clustering; e desenvolvemos um algoritmo quântico baseado em caminhos para previsão de ligações em redes complexas. Relacionado com o problema de previsão de ligações, mostramos que existe um eficiente algoritmo de simulação de passeios quânticos para grafos que são esparsos a exceção de um número pequeno de hubs.

O outro tema e entender como obter speedups quânticos num futuro próximo, enquanto os computadores quânticos continuarem extremamente vulneráveis a ruído. Procuramos abordagens algorítmicas teóricas para reduzir as profundidades dos circuitos, de forma a expor a computação a menos ruído.

Analisamos um trade-off entre o speedup quântico e profundidade do circuito para o problema de estimação de fase, revelando que este pode ser entendido no contexto do formalismo das transformações quânticas de valores singulares. Também aplicamos uma ferramenta moderna de super-resolução, a “Minimização da Norma Atómica”, a um problema quântico de muitos corpos e mostramos que podemos reduzir significativamente a profundidade dos circuitos envolvidos comparativamente com as técnicas usuais de processamento de sinal.