Abstrato

ANÁLISE COMPARATIVA DA MÁQUINA DE TURING E DA MÁQUINA DE TURING QUÂNTICA

Tirtharaj Dash e Tanistha Nayak

Hoje em dia, todo o dispositivo de computação é baseado na Máquina de Turing. Sabe-se que a física clássica é suficiente para explicar fenómenos macroscópicos, mas não para explicar fenómenos microscópicos como a interferência de eletrões. Hoje em dia, a aceleração e a redução do tamanho dos dispositivos de computação têm sido realizadas com recurso a efeitos físicos quânticos; no entanto, os princípios de computação nestes dispositivos também se baseiam na física clássica. Este artigo tenta analisar matematicamente a possibilidade de a Máquina Quântica de Turing Universal (UQTM) ser capaz de computar mais rapidamente do que qualquer outro modelo clássico de computação. Basicamente focamo-nos no estudo comparativo do poder computacional da Universal Turing Machine (UTM) e da UQTM. Ou seja, na igualdade, tentamos mostrar que o UQTM pode resolver qualquer problema NP-completo em tempo polinomial. A análise dos resultados mostrou que o UQTM é mais rápido para qualquer cálculo.