1. Introdução e Revisão do Paralelismo Quântico [0]

thumbnail

  1. Boas-vindas e Continuidade do Curso [0]

    1. O curso de computação quântica continua na sessão da tarde. [0]
    2. O foco da manhã foi o paralelismo quântico. [2]

  2. Limitação do Paralelismo Quântico [3]

    1. A superposição uniforme permite calcular em vários pontos simultaneamente. [2]
    2. Medir o estado colapsa o resultado para um único ponto. [3]
    3. Isso não oferece vantagem sobre a computação clássica sozinha. [4]
    4. Desenvolver algoritmos quânticos não é trivial. [5]

2. Algoritmo de Deutsch [6]

thumbnail

2.1. Ideia Central e Ganho Modesto [6]

  1. Objetivo do Algoritmo de Deutsch [9]
    1. A função é binária (entrada binária, saída binária). [9]
    2. Queremos saber se é igual ou diferente de . [9]
    3. Classicamente, são necessárias duas consultas ao oráculo (caixa preta). [10]
    4. Quanticamente, é necessária apenas uma consulta. [13]
    5. O ganho é modesto, mas o algoritmo é teoricamente importante. [7]

2.2. Circuito e Análise Passo a Passo [15]

  1. Preparação do Circuito [15]

    1. Assume-se um circuito pronto para calcular . [17]
    2. O circuito de Deutsch envolve Hadamard, e Hadamard novamente. [18]

  2. Aplicação de Hadamard Inicial [20]

    1. Inicia-se com no primeiro qubit e no segundo. [20]
    2. Aplica-se Hadamard em ambos os qubits. [20]
    3. O estado resultante é (anotação abreviada). [21]

  3. Aplicação do Oráculo $U_f$ [23]

    1. é aplicado linearmente em cada termo da superposição. [24]
    2. Usa-se a identidade: . [26]
    3. O resultado da função aparece como uma fase no cat. [28]

  4. Análise das Fases Resultantes [29]

    1. O estado final após depende de e . [29]
    2. Se , o estado é proporcional a . [32]
    3. Se , o estado é proporcional a . [34]
    4. Fases globais (multiplicadores complexos de norma 1) podem ser ignoradas. [35]

  5. Aplicação Final de Hadamard e Medição [37]

    1. Aplica-se Hadamard novamente no estado resultante. [37]
    2. Se , o primeiro qubit mede com certeza. [38]
    3. Se , o primeiro qubit mede com certeza. [40]
    4. O primeiro qubit determina a resposta com probabilidade 1 (algoritmo determinístico). [41]

2.3. Conclusões do Algoritmo de Deutsch [42]

  1. Exploração de Fenômenos Quânticos [43]

    1. O ganho não veio só do paralelismo quântico. [43]
    2. O fenômeno explorado foi a interferência. [43]
    3. A interferência permitiu que o primeiro qubit indicasse a propriedade global. [44]

  2. Natureza do Ganho [45]

    1. O algoritmo foi bem-sucedido ao focar em uma propriedade global de . [46]
    2. Não foi um uso ingênuo de paralelismo. [47]
    3. É um dos primeiros algoritmos com ganho modesto sobre o clássico. [48]

3. Generalização do Algoritmo de Deutsch (Deutsch-Jozsa) [49]

thumbnail

3.1. Definição do Problema e Ganho Exponencial [49]

  1. Objetivo do Algoritmo Generalizado [51]

    1. Função leva uma string de bits a um único bit. [51]
    2. O objetivo é saber se é constante ou balanceada. [51]
    3. Constante: Sempre retorna o mesmo valor (0 ou 1). [52]
    4. Balanceada: Retorna 0 para metade das entradas e 1 para a outra metade. [54]
    5. Deve haver uma promessa de que é uma destas duas. [55]

  2. Comparação Clássica vs. Quântica [60]

    1. Classicamente, são necessárias consultas para ter certeza. [60]
    2. Quanticamente, é necessária apenas uma consulta com certeza. [61]
    3. Isso representa um ganho exponencial na complexidade das consultas. [61]

3.2. Ressalvas sobre o Ganho Exponencial [64]

  1. Consideração de Algoritmos Probabilísticos Clássicos [65]

    1. Se relaxarmos a exigência de certeza absoluta, o clássico melhora. [65]
    2. Um algoritmo probabilístico clássico usa consultas em tempo polinomial. [66]
    3. Ele teria alta probabilidade de sucesso, mas com chance de erro. [66]

  2. Conclusão Prática [67]

    1. Na prática, o ganho quântico é polinomial sobre o clássico probabilístico. [67]
    2. O algoritmo mantém grande importância teórica. [67]

3.3. Perguntas e Respostas sobre Medição [68]

  1. Medição na Base Mais Menos [69]
    1. É possível medir diretamente na base . [69]
    2. Se o hardware só oferece medição na base computacional , usa-se Hadamard. [70]
    3. A porta Hadamard funciona como uma mudança de base para medição. [72]
    4. A medição na base computacional corresponde a observar . [73]

3.4. Analogia com a Função Delta de Dirac [76]

  1. Comparação com a Função Delta de Dirac [76]
    1. A função Delta de Dirac depende de um único ponto . [78]
    2. O algoritmo de Deutsch-Jozsa avalia uma propriedade global (constante vs. balanceada). [79]
    3. A analogia parece ser mais forte com o algoritmo de Grover. [80]

3.5. Modelo de Circuito Recorrente [86]

  1. Padrão Comum em Algoritmos Quânticos [86]
    1. O circuito se assemelha a um padrão repetitivo. [87]
    2. O padrão inclui: Hadamard inicial Oráculo Pós-processamento Medição. [87]

3.6. Execução Detalhada do Deutsch-Jozsa [88]

  1. Configuração Inicial [89]

    1. Inicia-se com o primeiro registrador em . [89]
    2. O segundo registrador (o de avaliação) entra com . [90]

  2. Aplicação de Hadamard [91]

    1. Aplica-se Hadamard em todos os qubits. [91]
    2. O primeiro registrador entra em superposição uniforme de estados. [96]
    3. O segundo registrador se torna o estado . [93]

  3. Aplicação do Oráculo $U_f$ [97]

    1. é aplicado linearmente ao estado . [97]
    2. O resultado é multiplicado por cada termo do somatório. [98]
    3. Termos com ficam positivos; termos com ficam negativos. [100]

  4. Aplicação Final de Hadamard [102]

    1. Aplica-se Hadamard novamente em todos os qubits. [101]
    2. Utiliza-se uma identidade para Hadamard em strings binárias . [103]
    3. A resposta do problema aparece diretamente no primeiro registrador. [113]

  5. Análise da Probabilidade de Medição [114]

    1. A probabilidade de medir no primeiro registrador é calculada. [114]
    2. Se $f$ é constante: Todos os termos do somatório são iguais (). [117]
    3. Probabilidade de medir é 1 (certeza). [118]
    4. Se $f$ é balanceada: Metade dos termos são , metade são . [119]
    5. Os termos se cancelam, probabilidade de medir é 0. [123]
    6. Se o resultado for diferente de , a função é balanceada. [125]
    7. Uma única consulta ao oráculo resolve a propriedade global da função. [128]

4. Algoritmo de Grover (Busca Não Ordenada) [131]

thumbnail

4.1. Conceito e Vantagem Quadrática [132]

  1. Objetivo do Algoritmo de Grover [138]

    1. Buscar um elemento em uma lista não ordenada. [138]
    2. Classicamente, busca-se por força bruta, exigindo consultas. [139]
    3. Quanticamente, basta consultas, um ganho quadrático. [142]

  2. Metáfora para Problemas NP [144]

    1. A busca não ordenada é uma metáfora para problemas sem estrutura. [144]
    2. Problemas NP são verificáveis eficientemente (dado um candidato, verifica-se a solução). [149]
    3. O oráculo em Grover verifica se um candidato é a solução. [140]
    4. Grover acelera a busca por soluções em problemas NP difíceis. [157]

4.2. Estrutura do Circuito de Grover [161]

  1. Registradores Necessários [161]

    1. O primeiro registrador precisa de bits para representar todos os elementos da lista (). [162]
    2. O segundo registrador precisa de apenas um qubit. [166]

  2. Passo 1: Superposição Uniforme [169]

    1. Aplica-se Hadamard em todos os qubits. [169]
    2. O estado resultante tem amplitude igual para todos os itens da lista (). [169]
    3. Medir neste ponto não oferece vantagem (probabilidade ). [171]

  3. Visualização Geométrica Inicial [174]

    1. O estado atual é a soma de dois vetores: (elemento procurado) e (outros estados). [174]
    2. O estado atual está mais próximo de do que de . [176]
    3. É preciso aumentar a amplitude de . [177]

4.3. O Operador de Grover [178]

  1. Composição do Operador $G$ [179]

    1. é composto por e um operador de reflexão . [179]
    2. deve ser repetido vezes. [183]

  2. Ação do Oráculo $U_f$ (Marcação) [185]

    1. O oráculo identifica o elemento marcado . [185]
    2. aplica uma fase negativa (inverte o sinal) apenas no estado . [189]
    3. Isso reflete o vetor de estado para baixo em torno do vetor . [191]
    4. A probabilidade de medir ainda é baixa (). [191]

  3. Ação do Operador de Reflexão $U$ [193]

    1. O operador reflete o vetor em torno do estado de superposição uniforme . [194]
    2. Isso joga o vetor refletido para cima, aumentando sua proximidade com . [196]

  4. Iteração e Rotação [198]

    1. A aplicação sucessiva de rotaciona o vetor de estado no sentido anti-horário. [198]
    2. O vetor se aproxima cada vez mais de . [199]
    3. Deve-se parar no ponto ótimo (próximo ao máximo) e medir. [200]
    4. Se continuar aplicando após o ponto ótimo, a probabilidade de sucesso diminui. [204]

4.4. Generalizações e Aplicações do Grover [206]

  1. Múltiplos Elementos Marcados [206]

    1. Se houver mais de um elemento procurado, o número de repetições de muda. [207]
    2. É preciso saber o número de soluções para não passar do ponto ótimo. [209]
    3. O algoritmo de Shor pode ser usado para estimar a contagem de soluções. [210]

  2. Exemplo Didático ($N=4$) [213]

    1. Exemplo com lista de tamanho 4, elemento procurado é 3 (). [213]
    2. O oráculo simplificado inverte o bit de saída apenas para a entrada . [215]
    3. Crítica: O oráculo simplificado parece "roubado" por já conhecer a resposta. [217]
    4. Em problemas reais (NP), o oráculo verifica a solução sem conhecê-la previamente. [220]
    5. Exemplos de verificação NP: Fatoração (multiplicação) ou Coloração de Grafos (checar vizinhos). [223]

4.5. Implementação de Portas Lógicas [229]

  1. Portas de Controle [234]

    1. CNOT (CX): Um controle inverte o alvo. [235]
    2. Porta Toffoli (CCNOT): Dois controles, se ambos forem , inverte o alvo. [236]
    3. Controle Negativo: Inverte o alvo se o controle for . [238]
    4. Controle negativo pode ser implementado com portas NOT antes e depois do alvo. [241]

  2. Finalização do Circuito de Grover (Exemplo) [243]

    1. Aplica-se Hadamard novamente para mudar a base de medição. [243]
    2. Espera-se obter no final, pois o elemento procurado era o marcado. [243]

5. Implementação com Qiskit [246]

thumbnail

5.1. Ambiente e Instalação do Qiskit [247]

  1. Ambiente de Execução [247]

    1. O curso utiliza o Quantum Lab da IBM, um ambiente pronto. [247]
    2. Tutoriais adaptados de exemplos existentes no sistema IBM. [255]

  2. Qiskit Terra [259]

    1. Qiskit é o kit de desenvolvimento da IBM, composto por módulos. [259]
    2. O pacote fundamental é o Terra, contendo componentes básicos de programação. [260]
    3. Pode ser executado no ambiente IBM ou instalado localmente (via pip). [261]

  3. Instalação Local e Acesso Remoto [264]

    1. Instalação local usa pip install qiskit. [264]
    2. Recomenda-se instalar com [visualization] opcionalmente. [266]
    3. Acesso remoto aos sistemas IBM requer um Token de credenciais. [268]
    4. O token é usado uma vez para salvar credenciais no computador local. [269]
    5. A versão do Qiskit no Quantum Lab é 0.37.1. [277]

  4. Módulos de Aplicação [272]

    1. Módulos como Aqua foram substituídos por pacotes de aplicações individuais (ex: Finanças, Machine Learning). [273]
    2. O software está preparado para a evolução do hardware com correção de erros. [275]

5.2. Construção e Simulação de Circuitos [277]

  1. Criação de Circuito e Estado GHZ [277]

    1. Importa-se o módulo QuantumCircuit do Qiskit. [278]
    2. Cria-se um circuito com três qubits. [279]
    3. Prepara-se um estado GHZ usando portas Hadamard e CNOTs. [280]
    4. O circuito pode ser visualizado usando mpl ou latex (mais lento). [284]

  2. Simulação com Backends [289]

    1. State Vector Simulator: Simula o circuito como álgebra linear (lápis e papel). [293]
    2. Retorna o vetor de estado, útil para conferir contas (ex: ). [304]
    3. Ferramentas de visualização como plot_state auxiliam no estudo. [307]
    4. Matrix Simulator: Calcula a matriz que representa as portas. [310]

  3. Simulação com Medição (OpenQASM) [312]

    1. O computador quântico real só retorna resultados de medições. [314]
    2. O circuito é refeito, adicionando um registrador clássico e portas de medição. [316]
    3. A função transpile converte o circuito em portas básicas para o hardware. [325]
    4. A execução retorna um objeto Job, cujo resultado é um dicionário de counts. [326]
    5. Para o estado GHZ simulado, os resultados foram 500 ocorrências para cada estado. [327]

5.3. Execução em Computadores Quânticos Reais [331]

  1. Ambiente de Execução Real [331]

    1. A interface é similar ao Jupyter Notebook, permitindo misturar texto e código. [332]
    2. Para rodar em hardware real, é preciso carregar credenciais (load_account). [337]
    3. O provider disponibiliza os sistemas da IBM (ex: Armond, Bogotá, Lagos). [340]

  2. Implementação do Grover (Exemplo) [348]

    1. Circuito implementado com dois registradores quânticos e um clássico. [348]
    2. O oráculo simplificado usa portas NOT para simular controle negativo. [354]
    3. Execução no Simulador: Resultado foi 2048 medições no estado (elemento procurado). [357]
    4. O simulador ideal encontrou a resposta com certeza. [365]

  3. Execução no Hardware Real (Lagos) [366]

    1. A variável real aponta para o backend Lagos agendado. [366]
    2. O job ficou 1.2 segundos na fila e rodou por 59 segundos. [371]
    3. Resultado Real: O resultado esperado era . [382]
    4. O resultado correto () ocorreu cerca de 73-74% das vezes. [382]
    5. O erro se deve ao ruído do sistema quântico real. [384]
    6. Circuitos mais profundos (listas maiores) ficam inviáveis devido ao ruído. [385]

6. Algoritmo de Shor (Fatoração de Inteiros) [387]

thumbnail

6.1. Contexto e Importância [387]

  1. Algoritmo de Shor [403]

    1. É um algoritmo muito famoso, colocou a computação quântica no radar. [404]
    2. Tem grande aplicação na criptografia. [405]
    3. Seu ingrediente principal é a Transformada de Fourier Quântica (QFT). [405]

  2. Relação com a Ordem de um Número [410]

    1. A ideia é reduzir a fatoração ao problema de achar a ordem de um número. [410]
    2. Ordem : Menor inteiro positivo tal que . [410]
    3. A grande sacada de Shor foi achar a ordem de forma eficiente quanticamente. [416]

  3. Exemplo de Ordem [418]

    1. (resto 1 ao dividir por 7). [418]
    2. A ordem de 2 módulo 7 é, na verdade, 3, pois . [421]

  4. Fatoração Usando a Ordem [425]

    1. Se a ordem é conhecida, usa-se um algoritmo clássico para fatorar. [425]
    2. Exemplo: Fatorar 21. Se (ordem de 2 mod 21), calcula-se . [428]
    3. O algoritmo quântico calcula a ordem, não fatora diretamente. [431]

  5. Cálculo do Período com QFT [432]

    1. O cálculo da ordem explora o caráter periódico da função . [432]
    2. O circuito aplica o oráculo que calcula em paralelo. [433]
    3. A Transformada de Fourier calcula o período da função. [434]
    4. O resultado permite extrair o denominador da fração, que é o período . [435]

6.2. Perguntas sobre Grover e Bancos de Dados [390]

  1. Vantagem de Grover em Banco de Dados Clássicos [391]

    1. Buscar em banco de dados clássico já indexado não ganha vantagem com Grover. [393]
    2. O problema é o custo de carregar dados clássicos para a memória quântica (State Preparation). [393]
    3. Se a lista clássica for ordenada, a busca é mais eficiente (). [395]

  2. Utilidade de Grover [397]

    1. Grover é útil para acelerar a busca em problemas sem estrutura (força bruta). [396]
    2. É uma versão quântica da busca por força bruta. [401]
    3. Não é útil para problemas estruturados como Distinct Elements. [398]

7. Encerramento e Agradecimentos [436]

thumbnail

  1. Disponibilidade de Material [436]

    1. O palestrante espera ter coberto os pontos principais para iniciantes. [437]
    2. Sugestão: Deixar os cadernos Jupyter no site do evento para download. [444]

  2. Agradecimentos Finais [448]

    1. Agradecimentos ao grupo de pesquisa da UFSC. [448]
    2. Próxima palestra será sobre Mercado de Finanças e Computação. [452]