Aprofundir en els coneixements de computació quàntica, tant des del vessant de la física com des del vessant de la teoria de la computació, que em situïn en un punt de "pre-recerca".\nTenir un mapa de les diferents aproximacions a llenguatges de programació quàntica que s'han fet en els últims anys. Distingir els pros/contres i limitacions d'aquestes aproximacions.\nInvestigar els avenços recents relacionats amb complexitat de la CQ i els seus límits des del punt de vista de la teoria de la computació.\nInvestigar les diferents propostes de simulació de CQ en ordinadors actuals.
Aprofundir en els coneixements de computació quàntica, tant des del vessant de la física com des del vessant de la teoria de la computació, que em situïn en un punt de "pre-recerca".\nTenir un mapa de les diferents aproximacions a llenguatges de programació quàntica que s'han fet en els últims anys. Distingir els pros/contres i limitacions d'aquestes aproximacions.\nInvestigar els avenços recents relacionats amb complexitat de la CQ i els seus límits des del punt de vista de la teoria de la computació.\nInvestigar les diferents propostes de simulació de CQ en ordinadors actuals.
[CA] Els qubits, les unitats bàsiques de la informació en la computació quàntica, no són sistemes aïllats sinó que interactuen amb el seu entorn. Aquesta interacció genera errors de decoherència i dissipació, que afecten el processament quàntic. La teoria dels sistemes quàntics oberts proporciona un marc matemàtic per estudiar aquestes interaccions i modelar diferents tipus de soroll. Emprarem l'equació mestra de Lindblad, resultat d'aquesta teoria, per a modelar la dissipació i la decoherència, i establir l'origen dels temps T_1 i T_2 que són dues mètriques que caracteritzen el temps màxim que un qubit pot realitzar operacions.
El propòsit d'aquest article és exposar les nocions essencials de la computació quàntica en termes purament matemàtics. En particular, definim les nocions de q-computació, q-mesura, q-procediment, q-computador i q-algorisme, i cadascuna s'il.lustra amb diversos exemples. A més d'alguns q-algorismes de baix nivell, discutim en detall una bona mostra dels més rellevants que s'han descobert. Aquests inclouen un q-algorisme per a la transformada de Fourier discreta i els q-algorismes de Deutsch (que resol un problema de decisió per a certes funcions booleanes), de Grover (cerca en una base de dades), de Kitaev (per estimar la fase d'un valor propi d'un vector propi d'un operador unitari), i els celebrats q-algorismes de Shor (per trobar l'ordre multiplicatiu d'un enter mòdul un altre i per factoritzar nombres enters). Les possibles realitzacions físiques del model, i el seu ús potencial per a obtenir guanys respecte de la computació clàssica (en ocasions fins i tot guanys exponencials), s'analitzen en termes d'una formulació axiomàtica de la teoria quàntica per a espais hermítics de dimensió finita.
XambóResum: El propòsit d'aquest article és exposar les nocions essencials de la compu- tació quàntica en termes purament matemàtics.En particular, definim les nocions de q-computació, q-mesura, q-procediment, q-computador i q-algorisme, i cadascuna s'il .lustra amb diversos exemples.A més d'alguns q-algorismes de baix nivell, discutim en detall una bona mostra dels més rellevants que s'han descobert.Aquests inclouen un q-algorisme per a la transformada de Fourier discreta i els q-algorismes de Deutsch (que resol un problema de decisió per a certes funcions booleanes), de Grover (cerca en una base de dades), de Kitaev (per estimar la fase d'un valor propi d'un vector propi d'un operador unitari), i els celebrats q-algorismes de Shor (per trobar l'ordre multiplicatiu d'un enter mòdul un altre i per factoritzar nombres enters).Les possibles realitzacions físiques del model, i el seu ús potencial per a obtenir guanys respecte de la computació clàssica (en ocasions fins i tot guanys exponencials), s'analitzen en termes d'una formulació axiomàtica de la teoria quàntica per a espais hermítics de dimensió finita.Paraules clau: computació quàntica, algorísmica, factorització de nombres enters. Classificació MSC2010: 68Q12,
Els diversos avenços en el camp de la física quàntica dels darrers anys han fet que puguem tenir a l’abast, en un futur proper, els ordinadors quàntics. Aquests desenvolupaments tenen una enorme importància per a la criptografia. En aquest treball es dona una introducció a aquests temes: la computació clàssica i la quàntica, la criptografia i els efectes que la computació quàntica té en els seus algoritmes, i la nova criptografia quàntica. Es discuteix com els algoritmes clàssics de la criptografia estan en perill, i com d’altres basats en la física quàntica emergeixen amb un gran potencial per garantir la privacitat de les comunicacions. Paraules clau: física quàntica, comunicacions quàntiques, criptografia, criptografia quàntica,algoritme BB84.
A Computação Quântica é um tópico relativamente recente e pouco conhecido, principalmente no meio da Computação.Seu estudo surgiu na tentativa de físicos simularem sistemas regidos pela Mecânica Quântica por computadores clássicos, o que se conjecturou inviável.Portanto, um novo modelo computacional que utiliza a estrutura quântica da matéria para computar foi teorizado para suprir estas deficiências.Este trabalho tem como objetivo principal estudar as influências da Computação Quântica na Teoria da Computação.Para atingir tal objetivo, primeiramente são expostos os conhecimentos básicos da Mecânica Quântica através de uma linguagem voltada para Teóricos de Computação sem conhecimento prévio na área, de forma a remover a barreira inicial sobre o tema.Em seguida, serão apresentadas inovações na área da Teoria de Computação oriundas da Computação Quântica.Começaremos com os principais Algoritmos Quânticos desenvolvidos até hoje, que foram os primeiros passos para demonstrar a possível superioridade computacional do novo modelo.Dentre estes algoritmos, apresentaremos o famoso Algoritmo de Shor, que fatora números em tempo polinomial.Adicionalmente, neste trabalho foram estudados tópicos mais avançados e atuais em Computabilidade e Complexidade Quânticas.Sobre Autômatos Quânticos, foram estudados aspectos de um modelo que mistura estados clássicos e quânticos, focando na comparação do poder computacional em relação aos Autômatos Finitos Clássicos.Do ponto de vista de Classes de Complexidade, será abordada a questão se em linguagens da classe QMA, o análogo quântico da classe NP, consegue-se atingir probabilidade de erro nulo na aceitação de instâncias positivas.