Autômatos Finitos - com uma introdução aos Autômatos Finitos Quânticos

Abstract

Autômatos Finitos é uma publicação da Editora da Universidade Federal de Campina Grande. O projeto que resultou neste livro teve início no ano de 2008 e foi desenvolvido no Instituto de Estudos em Computação e Informação Quânticas (IQuanta). O objetivo do trabalho consistia em conceber uma obra voltada para alunos de graduação dos cursos de Ciência da Computação e áreas afins, com o intuito de apresentar conceitos da Teoria dos Autômatos e da Computação Quântica.
O livro Autômatos Finitos - com uma introdução aos Autômatos Finitos Quânticos possui 160 páginas, 38 exercícios resolvidos, 40 exercícios propostos, 12 ilustrações, 10 provas de teoremas e 52 referências para outros trabalhos e leituras complementares. Todo este conteúdo está organizado em 5 capítulos, como será mostrado em mais detalhes a seguir.

Type
Publication
Editora da Universidade Federal de Campina Grande.
Date

Visão Geral da Obra

O primeiro capítulo consiste de uma revisão sobre espaços vetoriais e operações sobre estes espaços, enquanto que o segundo capítulo introduz os Postulados da Mecânica Quântica, que determinam as condições para realização de operações por um computador quântico. A introdução dos conceitos sobre Computação Quântica é feita por meio de uma analogia com os chamados “computadores clássicos”, amplamente abordados nos cursos de graduação. A estrutura dos dois primeiros capítulos é mostrada a seguir:

  • Noções Gerais de Álgebra Linear
    • Espaço de Hilbert
    • Espaço Vetorial Finito
    • Produto Interno
    • Produto Tensorial
    • Operadores Lineares
    • Produto Externo
    • Autovalores e autovetores
    • Operadores de Projeção
  • Noções Gerais da Mecânica Quântica
    • Sistemas Quânticos
    • Qubits
    • Superposição
    • Operadores
    • Produto Tensorial de Operadores
    • Reversibilidade
    • Medição

O terceiro capítulo contempla uma revisão dos conceitos básicos sobre Teoria dos Autômatos, motivada por um levantamento de fatos históricos que justificam o surgimento e a necessidade desta teoria. Neste capítulo são apresentados dois modelos de autômatos finitos básicos: o determinístico e o não determinístico. Há também a definição das notações e convenções para representação de autômatos que serão abordados ao longo de toda obra.

  • Teoria dos Autômatos Finitos
    • Breve Histórico
    • Linguagens
    • Autômatos Finitos Determinísticos
    • Diagrama de Estados
    • Notação Matricial
    • Autômatos Finitos não-Determinísticos

Após esta introdução, são apresentados conceitos sobre Autômatos Finitos Probabilísticos, que antecedem os Autômatos Finitos Quânticos. Embora não tenha sido inicialmente o foco do livro, optou-se por abordá-los em detalhes, uma vez que existiam poucas referências nas quais este conteúdo fosse destinado para alunos de graduação.

  • Autômatos Finitos Probabilísticos
    • Breve Introdução
    • Linguagens Estocásticas
    • Ponto de Corte Isolado

Neste capítulo são apresentados os Autômatos Finitos Quânticos unidirecionais de medição única e de múltiplas medições, que apresentam características fundamentais de todos os modelos quânticos de autômatos. Para a melhor compreensão dos conceitos apresentados, este capítulo possui diversas provas de teoremas sobre propriedades dos autômatos, equivalências, classe das linguagens reconhecidas, dentre outros.

  • Autômatos Finitos Quânticos
    • Breve Introdução
    • AFQ de Medição Única (AFQ MO)
    • AFQ de Múltiplas Medições (AFQ MM)
    • Propriedades e Abrangência dos AFQ’s MO e MM
    • Propriedades dos AFQ’s MO
    • Propriedades dos AFQ’s MM
    • AFQ Ancilla
    • Outros Modelos
    • Relevância

Os autores acreditam que a obra produzida é importante em muitos aspectos, pois: * Colabora para a formação dos alunos de Ciência da Computação no que diz respeito ao novo paradigma da Computação Quântica; * Disponibiliza para a comunidade, pesquisadores, professores e alunos material didático de referência nesta área, apresentando o relacionamento da Computação Clássica com a Computação Quântica de forma simples e didática; * Colabora para a divulgação de trabalhos de pesquisa na Computação Quântica; * Produz literatura em Língua Portuguesa, visto que a maioria dos trabalhos nesta área são apresentados em outros idiomas.