Dissertação
Quantum Computation for Artificial Intelligence EVALUATED
Existem métodos da computação quântica capazes de obter uma aceleração quadrática na eficiência-temporal de uma pesquisa clássica (e.g., o algoritmo de Grover). Em Inteligência Artificial (IA), isto equivale à divisão por dois na profundidade de procura garantindo uma solução. Infelizmente, o estudo destes modelos encontra-se frequentemente circunscrito às comunidades da matemática e física. Uma vez o aparecimento do primeiro computador quântico ser apenas uma questão de tempo, propomo-nos investigar os benefícios dos seus métodos na resolução de problemas de IA, partindo da sua perspectiva simbólica. Neste documento, apresentamos uma introdução aos princípios da computação quântica. Seguidamente, descrevemos como um algoritmo quântico/clássico, Procura em Profundidade Iterativa Quântica, pode ser utilizado em tarefas de IA não-triviais. São propostas duas aplicações do mesmo, passando de um nível concreto de representação para um mais abstracto, nomeadamente: um sistema de solução para instâncias de n-blocos do Blocks World; e um sistema híbrido de inferência proposicional, que a partir de frases nesta linguagem, consegue provar outras expressões. Para o primeiro, exploramos também como melhorar os requisitos de espaço, e sugerimos uma nova perspectiva no uso de heurísticas para computação quântica. O sistema de resolução do Blocks World encontra soluções num espaço de estados de tamanho N em tempo O(\sqrt{N}). Em semelhança, para bases de dados proposicionais de grandes proporções, o sistema de inferência apresentado obtém provas em tempo O(\sqrt{N}), sendo N o número de sequências de dedução possíveis. Ambos exibem aceleração quadrática relativamente aos seus congéneres exaustivos clássicos, cujos requisitos temporais se estendem a O(N) verificações.
março 3, 2017, 10:0
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
Departamento de Engenharia Informática (DEI)
Professor Auxiliar