Na teoria da complexidade computacional, o problema do caixeiro viajante (PCV) é um problema da classe NP-complexo em otimização combinatória, importante na ciência da computação teórica e na pesquisa operacional. Devido à natureza do problema, apresenta um grande número de variáveis, o que aumenta de forma significante o custo computacional, desta forma, optou-se pela computação quântica, como base para estruturação de um algoritmo para resolução viável deste problema. Não obstante, a partir utilizando uma nova técnica que alude à denominada codificação em múltiplas bases, o que dá permissividade para resolver o problema com um número menor de qubits e desta forma reduzindo-se o custo computacional para a resolução deste problema com quatro e cinco instâncias. O presente trabalho contou com a técnica seminal da codificação em múltiplas bases, ideia egressa das redes neurais e que se mostra profícua na resolução de problemas de optimização combinatória.
A Teoria da Informação Quântica é uma área de pesquisa a qual considera o estudo dos limites máximos possíveis para o processamento e transmissão da informação, considerando que esta última encontra-se representada de acordo com as leis da Mecânica Quântica. Uma das maneiras de contribuir com esta área de pesquisa é no desenvolvimento de contrapartidas quânticas para os conceitos da Teoria da Informação Clássica. Graças a esta abordagem é que foi proposta a Teoria da Informação Quântica Erro-Zero, a qual considera o uso e as condições para que canais quânticos ruidosos possam transmitir informação clássica sem erros de decodificação. Apesar da proposição desta teoria e dos progressos recentes, foi identificado que o conhecimento das potencialidades, limitações e aplicações desta teoria ainda é incipiente. Na tentativa de minimizar este problema, esta tese apresenta dois novos conceitos ligados à Teoria da Informação Quântica Erro-Zero: (i) a capacidade quântica de sigilo erro-zero; e a (ii) informação acessível erro-zero de fontes quânticas. Em relação à primeira contribuição, tem-se o estabelecimento das condições necessárias para enviar informação por canais quânticos ruidosos sem que haja erros de decodificação e com sigilo absoluto, identificando uma nova capacidade de canais quânticos, estabelecendo a relação desta capacidade com a Teoria dos Grafos e identificando as situações em que esta possui caracterização de letra isolada. A segunda contribuição trata da proposição de uma medida de informação sobre fontes quânticas, a qual mensura o potencial de decodificar, sem erros, estados quânticos emitidos por estas fontes. Obter esta medida é um problema análogo ao de calcular a capacidade erro-zero de canais clássicos equivalentes e não há medida equivalente na Teoria da Informação Erro-Zero Clássica. Os conceitos propostos colaboram para o desenvolvimento da Teoria da Informação Quântica Erro-Zero em termos teóricos e práticos, uma vez que é possível considerar implementações de ambas contribuições com tecnologia existente atualmente. Além disto, intersecções da Teoria da Informação Quântica Erro-Zero junto à Criptografia, Teoria dos Grafos e Ciência da Computação são identificadas. O estabelecimento de tais contribuições colabora diretamente para a resolução de um dos desafios da Teoria da Informação Quântica, o qual trata da determinação de limites para a classe de tarefas de processamento de informação que são possíveis considerando a utilização da Mecânica Quântica.
A computação quântica vem se destacando como uma das inovações tecnológicas mais relevantes do século XXI, oferecendo novas abordagens para o processamento de informações e apresentando desempenho superior à computação clássica em problemas de alta complexidade. Baseada nos fundamentos da mecânica quântica, especialmente nos princípios de superposição e entrelaçamento, essa tecnologia possibilita representar e manipular múltiplos estados de informação de forma simultânea. Considerando sua importância crescente na ciência e na engenharia, este trabalho tem como objetivo analisar o estado atual, os desafios e as principais aplicações da computação quântica, com ênfase em suas repercussões em áreas estratégicas como a segurança digital, a inteligência artificial e a simulação de materiais. A pesquisa foi conduzida por meio de uma revisão bibliográfica. Os resultados mostram que a computação quântica tende a redefinir os limites da ciência computacional, abrindo novas possibilidades em campos como a criptografia, o aprendizado de máquina e as ciências dos materiais. Observou-se, contudo, que a consolidação dessa tecnologia ainda depende da superação de obstáculos técnicos, como a instabilidade dos qubits, os processos de correção de erros e a escalabilidade dos sistemas. Conclui-se que o avanço da computação quântica requer a integração entre pesquisa científica, desenvolvimento tecnológico e formação interdisciplinar, fatores indispensáveis para que essa área se firme como base dos sistemas computacionais do futuro.