Durante as últimas décadas, as mais diversas atividades humanas têm se tornado cada vez mais dependentes de sistemas computacionais, e é improvável que essa tendência se reverta em um futuro próximo. Com esse fenômeno, tem havido um crescimento no interesse sobre segurança computacional. O campo de fluxo de informação quantitativo (QIF) tem interesse em medir e controlar vazamentos de informação em sistemas computacionais. Inicialmente, a pesquisa na área tinha predominantemente como objetivo determinar se um sistema vaza alguma informação sensível. Essa abordagem, contudo, não foi ampla o suficiente. Em certas situações, seja por desenho ou necessidade, alguns sistemas tem alta probabilidade de vazar um pouco de conteúdo sigiloso. Portanto, é natural medir a quantidade de informação que esses sistemas vazam para avaliar o quão seguro eles realmente são. Muitas maneiras de medir vazamentos de informação foram desenvolvidas através dos anos. Desenvolvido recentemente, o arcabouço de g-leakage, em particular, mostrou-se capaz de medir vazamentos de informação em um vasto número de cenários, e é considerado o estado da arte em QIF. Apesar do grande esforço devotado pela comunidade acadêmica ao estudo de suas propriedades matemáticas, a pesquisa em g-leakage tem majoritariamente seguido a abordagem, tradicional em QIF, de modelar sistemas como canais de teoria da informação indivisíveis, e muito pouco se sabe sobre o que acontece quando esses canais são compostos de alguma forma. Contudo, obter um bom entendimento sobre o comportamento de composições de canais em relação ao arcabouço de g-leakage é bastante desejável, uma vez que muitos sistemas na vida real consistem em uma coleção de partes que interagem entre si, sendo portanto melhor representados por uma junção de vários canais do que por apenas um. Nessa dissertação, estudamos o o comportamento da g-leakage em composições de canais que capturam interações típicas de sistemas da vida real. Em particular, estudamos composição em paralelo, escolha visível, escolha invisível, if-then-else visível e if-then-else invisível. Nós começamos nosso trabalho estabelecendo algumas propriedades algébricas dessas composições, que serão úteis para a análise de sistemas descritos por múltiplas composições de canais. Em seguida, derivamos equivalências e limites que descrevem o vazamento de informação dessas composições em termos do vazamento de seus componentes. Esses resultados podem ser ferramentas poderosas para avaliar as propriedades de sistemas grandes ou complicados, uma vez que eles se baseiam na análise de seus componentes, mais simples e menores. Um outro aspecto crucial acerca de composições de canais é estabelecer monotonicidade, ou seja, determinar se a substituição de um componente por um mais seguro compromete a segurança do sistema como um todo. Nossos resultados mostram, talvez surpreendentemente, que monotonicidade não é sempre uma garantia, uma vez que em certos casos é possível tornar um sistema menos seguro ao aumentar a segurança de um dos seus componentes isoladamente. Nós estabelecemos se cada composição citada acima respeita monotonicidade. Finalmente, nós utilizamos o nosso arcabouço para modelar dois protocolos de segurança bastante conhecidos na literatura, os protocolos Dining Cryptographers e Crowds. Os nossos resultados possibilitam algoritmos simples para a construção de seus respectivos canais e, para o segundo protocolo, um algoritmo mais rápido do que aqueles do estado da arte na literatura.
Durante as últimas décadas, as mais diversas atividades humanas têm se tornado cada vez mais dependentes de sistemas computacionais, e é improvável que essa tendência se reverta em um futuro próximo. Com esse fenômeno, tem havido um crescimento no interesse sobre segurança computacional. O campo de fluxo de informação quantitativo (QIF) tem interesse em medir e controlar vazamentos de informação em sistemas computacionais. Inicialmente, a pesquisa na área tinha predominantemente como objetivo determinar se um sistema vaza alguma informação sensível. Essa abordagem, contudo, não foi ampla o suficiente. Em certas situações, seja por desenho ou necessidade, alguns sistemas tem alta probabilidade de vazar um pouco de conteúdo sigiloso. Portanto, é natural medir a quantidade de informação que esses sistemas vazam para avaliar o quão seguro eles realmente são. Muitas maneiras de medir vazamentos de informação foram desenvolvidas através dos anos. Desenvolvido recentemente, o arcabouço de g-leakage, em particular, mostrou-se capaz de medir vazamentos de informação em um vasto número de cenários, e é considerado o estado da arte em QIF. Apesar do grande esforço devotado pela comunidade acadêmica ao estudo de suas propriedades matemáticas, a pesquisa em g-leakage tem majoritariamente seguido a abordagem, tradicional em QIF, de modelar sistemas como canais de teoria da informação indivisíveis, e muito pouco se sabe sobre o que acontece quando esses canais são compostos de alguma forma. Contudo, obter um bom entendimento sobre o comportamento de composições de canais em relação ao arcabouço de g-leakage é bastante desejável, uma vez que muitos sistemas na vida real consistem em uma coleção de partes que interagem entre si, sendo portanto melhor representados por uma junção de vários canais do que por apenas um. Nessa dissertação, estudamos o o comportamento da g-leakage em composições de canais que capturam interações típicas de sistemas da vida real. Em particular, estudamos composição em paralelo, escolha visível, escolha invisível, if-then-else visível e if-then-else invisível. Nós começamos nosso trabalho estabelecendo algumas propriedades algébricas dessas composições, que serão úteis para a análise de sistemas descritos por múltiplas composições de canais. Em seguida, derivamos equivalências e limites que descrevem o vazamento de informação dessas composições em termos do vazamento de seus componentes. Esses resultados podem ser ferramentas poderosas para avaliar as propriedades de sistemas grandes ou complicados, uma vez que eles se baseiam na análise de seus componentes, mais simples e menores. Um outro aspecto crucial acerca de composições de canais é estabelecer monotonicidade, ou seja, determinar se a substituição de um componente por um mais seguro compromete a segurança do sistema como um todo. Nossos resultados mostram, talvez surpreendentemente, que monotonicidade não é sempre uma garantia, uma vez que em certos casos é possível tornar um sistema menos seguro ao aumentar a segurança de um dos seus componentes isoladamente. Nós estabelecemos se cada composição citada acima respeita monotonicidade. Finalmente, nós utilizamos o nosso arcabouço para modelar dois protocolos de segurança bastante conhecidos na literatura, os protocolos Dining Cryptographers e Crowds. Os nossos resultados possibilitam algoritmos simples para a construção de seus respectivos canais e, para o segundo protocolo, um algoritmo mais rápido do que aqueles do estado da arte na literatura.
A elevada dependência das tecnologias de informação que se constata em quase todos setores de atividade, conduz à necessidade de aprimoramento de segurança nas redes de tele- comunicações. Muito se tem feito para o aprimoramento da segurança no nível de aplicação. Os siste- mas de autenticação são cada vez mais robustos e os algoritmos de encriptação são cada vez mais complexos. Mas o crescente aumento da capacidade dos processadores, a utilização de clouds para o processamento concorrente de informação, bem como o advento da computação quântica, deixam claro que é apenas uma questão de tempo para que qualquer algoritmo de encriptação seja quebrado. Por outro lado, uma informação encriptada pode ser detectada por um agente externo e mesmo que não consiga decifrar pode usar técnicas de processamento de sinal para compro- meter a integridade ou a disponibilidade da mesma. Assim sendo, não se pode confiar a segurança apenas à camada de aplicação, antes deve- se ter uma abordagem de segurança em profundidade. Portanto, a segurança no nível físico com recurso ao formalismo quântico surge como uma proposta complementar de segurança. A presente dissertação explorará a propriedade da sobreposição de estados lógicos dos qubits, para alterar a probabilidade de observação dos sinais transmitidos, de modo a tornar o sinal indetetável e indecifrável sem o conhecimento prévio da chave criptográfica. Para que seja um sistema de segurança forte, os qubits serão representados por wavelets pseudoaleató- rias com todas as caraterísticas estatísticas de ruído branco gaussiano.
brilhantes.Agradeço por todos os momentos de descontração e principalmente pelo futebol.Aos meus colegas e amigos do MathFoundQ, pelas ótimas discussões.Em especial, agradeço ao Marcelo, pelos importantes ensinamentos, e ao Pedro, Carlos Humberto e Carlos de Gois pela essencial colaboração e amizade.Por fim, agradeço a todos aqueles que não foram citados, mas que de alguma forma exerceram alguma influência positiva. ResumoA mecânica quântica é fundamentalmente definida por meio de seu formalismo matemático: espaços de Hilbert, funções de onda e operadores.No entanto, outras teorias físicas, tal como a relatividade especial, podem ser formuladas por meio de princípios físicos.Um dos mais importantes problemas em fundamentos de mecânica quântica é, então, a procura por um princípio físico que seja capaz de destacar a mecânica quântica de teorias probabilísticas mais gerais.Com esse propósito, muitos princípios vem sendo propostos recentemente dentre os quais está o princípio da causalidade da informação.Em linhas gerais, este princípio estabelece o seguinte: se uma parte, Alice, envia uma mensagem à outra parte, Bob, o ganho potencial de informação de Bob é limitado pela informação contida na mensagem, mesmo quando recursos não-locais, tal como estados quânticos emaranhados, são permitidos.Foi mostrado que a mecânica quântica obedece o princípio da causalidade da informação, entretanto, não se sabe se todas as teorias que permitem recursos supra-quânticos o violam, geralmente devido à dificuldade de encontrar critérios matemáticos que formalizem a ideia por trás do princípio.Recentemente, uma nova abordagem, a qual combina teoria da causalidade, teoria da informação clássica e geometria convexa, foi proposta como uma ferramenta poderosa para encontrar tal critério.Nesta dissertação, estudamos em detalhes a formulação acerca do princípio da causalidade da informação.Desta forma, apresentamos sua formulação matemática e conceitual, bem como apresentamos a teoria matemática relacionada à mais recente abordagem informacional-geométrica.Além disso, investigamos algumas perguntas em aberto dentro desse contexto e aplicamos esta nova abordagem informacional a fim de formular novos critérios matemáticos para o princípio da causalidade da informação em novos cenários e investigar como tal critério é capaz de excluir teorias não-locais supra-quânticas.
O objetivo do trabalho é estudar algoritmos quânticos de busca, usados em computadores quânticos. Até então, algoritmos de busca utilizados em computadores clássicos dependem da estrutura na qual os dados estão organizados para serem ou não eficientes. Para conjuntos de dados não estruturados, o único jeito é verificar cada elemento do conjunto procurando o elemento passado na entrada do algoritmo, e dependendo da quantidade de elementos nesse conjunto, pode-se levar muito tempo, mesmo para computadores muito rápidos. Portanto, algoritmos que realizem busca de maneira eficiente são um atrativo e tanto para cientistas da computação, que podem pensar em inúmeras aplicações dos mesmos e tornar vários softwares cada vez mais eficientes. Tendo isso em vista, a computação quântica traz artifícios inexistentes na computação clássica que podem acelerar esse processo, como, por exemplo, o paralelismo quântico. Basicamente, consiste na capacidade de sobrepor todos os dados do conjunto em um único registrador, ou a grosso modo, analisar todos ao mesmo tempo, apesar de não ser tão simples quanto isso. É baseado nisso que temos o Algoritmo de Grover, que utilizando o paralelismo quântico, e reflexões no conjunto de dados, através do uso de transformações unitárias feitas por portas quânticas, temos uma probabilidade alta de que quando medirmos este registrador quântico, termos como resultado o dado procurado.
Desde a primeira vez que computação quântica foi concetualizada por Feynman, simulação quântica tem estado na vanguarda das possiveis aplicações de interesse. Os custos proibitivos de simular sistemas quânticos com computadores classicos são uma forte motivação para a investigação em computação quântica. Ao longo da última década, tem-se observado um progresso notável no desenvolvimento de hardware quantico. No entanto, os obstáculos entre nos e a era de vantagem quantica util mantem-se essencialmente os mesmos: A informação quântica e fragil, e protegê-la é um desafio. Visto que os dispositivos quânticos atuais são ruidosos e tem um número limitado de qubits, desenvolver algoritmos que possam ser executados neles e uma area de investigação importante. Por resultarem em circuitos de preparação de estado (ansatze) pouco profundos e treinaveis, algoritmos quânticos variacionais (VQAs) adaptativos são uma opção promissora. O primeiro algoritmo nesta classe, o ADAPT-VQE, pode ser utilizado para problemas de estrutura eletronica, otimização combinatoria, materia condensada, sistemas periódicos no tempo, entre outros. Nesta tese, são propostas varias melhorias para VQAs adaptativos, com o objetivo de diminuir os custos e aumentar a viabilidade a curto prazo. Propõe-se um otimizador quasi-Newton para VQAs adaptativos que reduz os custos de medição necessários para implementar estes algoritmos em hardware quântico, bem como o tempo necessario para os simular classicamente. Propõe-se ainda um novo conjunto de operadores — “operatores de intercambio acoplado” (CEOs) — que resulta no menor numero de portas quanticas e na menor profundidade de circuito entre todas as propostas na literatura. Combina-se varios desenvolvimentos-chave e mostra-se uma redução dramatica dos recursos computacionais quânticos necessários em comparação com as primeiras versões do algoritmo ou com ansätze estáticos para VQE. Adicionalmente, propõe-se uma versão codesenhada do ADAPT-VQE (Co-ADAPT-VQE) onde o hardware quântico e tido em consideração na construção do ansatz. Este paradigma pode ser utilizado para otimizar circuitos de preparação de estado em qualquer dispositivo, colmatando limitações como conetividade limitada, tempos de coerencia curtos, e erros nas portas quanticas. Finalmente, propomos estrategia para mitigar “vales de gradientes”, um problema de convergência especifico ao ADAPT-VQE.
Este trabalho investiga aspectos fundamentais da teoria quântica. Começamos estabelecendo um formalismo independente de teoria para o estudo de teorias físicas, inspirado pelas chamadas teorias probabilísticas generalizadas (GPTs). Nossa abordagem diverge das GPTs tanto em termos de conceitos primitivos quanto na forma como as teorias físicas são compreendidas. Consideramos observável como conceito primitivo e entendemos teorias como formalismos nos quais leis físicas ou empíricas - expressões matemáticas relacionando quantidades físicas que podem ser mensuradas em conjunto - podem ser formuladas. Além dos observáveis, nosso formalismo inclui estados e um mecanismo de atualização de estados como conceitos primitivos. Estados atribuem probabilidades a proposições sobre medições subsequentes de quantidades físicas, enquanto a atualização de estado reconstrói estados para garantir a veracidade de tais proposições. Assim como nas GPTs, nossa análise é restrita a quantidades com um número finito de valores possíveis. Sistemas quânticos de dimensão finita estão dentro do escopo do nosso formalismo. Demonstramos que a estrutura algébrica da mecânica quântica emerge localmente a partir das condições de consistência que fundamentam nossa definição independente de teoria de sistema físico, onde \"localmente\" se refere a aspectos da álgebra (parcial) de observáveis que não envolvem operações entre operadores incompatíveis. Especificamente, mostramos que observáveis possuem norma e espectro; que existe uma relação de compatibilidade para observáveis, juntamente com operações algébricas entre aqueles que são compatíveis; projeções existem e formam um conjunto parcialmente ordenado com álgebras Booleanas locais; observáveis compatíveis dois a dois estão contidos em álgebras de Banach comutativas geradas por um único observável; estados definem funcionais parcialmente lineares no conjunto de observáveis; observáveis admitem decomposição espectral, entre outros. Esses resultados contribuem para a importante linha de pesquisa centrada em derivar o formalismo quântico a partir de suposições simples. Além disso, eles destacam uma diferença fundamental entre nosso formalismo e as GPTs, já que estas últimas são conhecidas por comumente não incluírem operações algébricas e projetores. A emergência local da estrutura algébrica da mecânica quântica tem implicações significativas para o problema das correlações quânticas, ou seja, o problema de se identificar princípios que expliquem as correlações produzidas por sistemas quânticos. Essa estrutura local nos permite provar que princípios importantes que governam as correlações quânticas, como a não-perturbatividade, a não-sinalização, o princípio de Specker, o princípio da exclusividade e o princípio da ortogonalidade local, são inerentemente satisfeitos em nosso formalismo. Consequentemente, nenhuma teoria dentro do escopo da nossa descrição pode violá-los, e as correlações por elas produzidas não podem estar consideravelmente distantes do chamado conjunto quântico. Exemplos notáveis de correlações pós-quânticas, como caixas PR e correlações quase-quânticas, são automaticamente excluídos. Concluímos nosso trabalho abordando o problema das variáveis ocultas. Provamos um teorema de impossibilidade para modelos de variáveis ocultas com base em uma única condição de consistência: o modelo deve atualizar estados via probabilidade condicional, o que, conforme argumentamos, segue de nossa descrição do mecanismo de atualização de estados. Este teorema estabelece uma ligação direta entre a incompatibilidade e a ausência de variáveis ocultas, mostrando que modelos de variáveis ocultas que atualizam estados existem se, e somente se, os observáveis em questão forem dois a dois compatíveis. Com base nisso, analisamos afirmações de cunho ontológico e metafísico tipicamente associadas a contextualidade, não-localidade e psi-ontologia.
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.