Dissertação
{en_GB=Quantum Computation for Artificial Intelligence} {} EVALUATED
{pt=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., en=Quantum computation methods (e.g., Grover's algorithm) are capable of quadratically improving the time-performance of classical search procedures. For Artificial Intelligence (AI) problems, this is roughly equivalent to halving the depth necessary for guaranteeing a solution. Unfortunately, study of these models is frequently left to those in the mathematics/physics communities, despite the aforementioned advantages. However, quantum computers will one day become a reality. Thus, we propose exploring how their methodologies may aid us in solving problems in AI, assuming the latter's symbolic outlook. In this document, we provide scientists interested in quantum computing models with a brief introduction to operating principles, upon which we describe how a hybrid quantum/classical algorithm, Quantum Iterative Deepening Search (QIDS), can be employed for solving interesting AI tasks within the standard-circuit quantum computation paradigm. We present two different applications, one possessing a more concrete representation, another that is more abstract, namely: a solver for the n-blocks generalization of Blocks World; and a hybrid system of inference, able to prove statements in Propositional Calculus given a knowledge-base of assertions in that language. We also investigate how space-efficiency may be improved in the former, and suggest a new heuristic perspective for quantum computing frameworks. Our n-blocks solver can find solutions within an N-sized state-space in O(\sqrt{N}) time. Similarly, for large datasets, our inference system is able to prove a propositional statement in O(\sqrt{N}) time, with N the number of possible deduction sequences. Both exhibit a quadratic speed-up with regards to blind classical approaches, which require O(N) evaluations.}
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