Path: blob/main/translations/pt/intro/why-quantum-computing.ipynb
3860 views
Por que computação quântica?
O que é um computador?
Visto que você conseguiu acessar esta página, você já deve saber o que é um computador. Hoje, os computadores assumem muitas formas: de laptops e telefones aos sistemas que controlam os semáforos. Parece que os computadores podem fazer qualquer coisa! Esses sistemas podem ser muito complexos e especializados, mas todos eles têm uma coisa em comum: um computador executa um conjunto de instruções sobre algumas informações de entrada para nos fornecer novas informações (de saída).
As instruções que damos aos computadores precisam ser muito específicas e inequívocas. Chamamos esses conjuntos de instruções de algoritmos, e grande parte da pesquisa em computadores é sobre o comportamento de diferentes algoritmos. Neste curso, consideraremos apenas os computadores em sua forma mais simples; sem teclados, mouses ou telas - apenas informações e algoritmos.
Classificando algoritmos de computador
Para entender o papel dos computadores quânticos perante os computadores tradicionais modernos, primeiro precisamos aprender como medimos o desempenho de diferentes algoritmos.
Na ciência da computação, classificamos os algoritmos de acordo com a forma como os recursos que eles usam crescem com o tamanho da entrada. Chamamos isso de complexidade do algoritmo. Por exemplo, um algoritmo que decide se um número é par só precisa olhar para o último dígito desse número. Nesse caso, a 'entrada' é um número e a saída é 'Par' ou 'Ímpar'. Chamamos isso de algoritmo de tempo constante , porque o tempo que o algoritmo leva para ser concluído não depende do tamanho do número de entrada. Pode levar tempos diferentes para computadores diferentes para obter esse resultado, mas isso se deve a outros fatores e não ao comprimento da entrada.
Vejamos um exemplo diferente. Desta vez, a entrada são dois números de igual comprimento, e o problema é somá-los. Nesse caso, a saída será um novo número. Ao adicionar dois números de vários dígitos, um algoritmo comum que você provavelmente aprendeu na escola começa com o dígito mais à direita de cada número e os soma. Em seguida, ele move um dígito para a esquerda (transportando um '1' se o resultado for maior que 9) e repete o processo. O computador repete isso até que não haja mais dígitos para adicionar e o algoritmo termina.
Quão complexa é a adição?
O tempo que esse algoritmo de adição leva para ser concluído...
...cresce linearmente (proporcionalmente) com o comprimento do número de entrada (tempo linear).
...não é afetado pelo comprimento do número de entrada (tempo constante)
...não é afetado pelo comprimento do número de entrada (tempo quadrático)
Novamente, computadores diferentes executarão esse algoritmo em velocidades diferentes; um laptop pode realizar adição milhões de vezes mais rápido do que um humano. Mas se você pode fazer um milhão de operações por segundo ou apenas uma, a taxa de crescimento será a mesma.
Aqui está um exemplo final que é particularmente interessante para nós. Digamos que eu tenha um número secreto (como um PIN) e o problema seja adivinhar esse número. Nesse caso, o tamanho do problema é o comprimento do número.
Digamos que a única maneira de verificarmos se nossa resposta está correta é digitando-a em um teclado. Como não temos informações sobre qual pode ser esse número, o melhor algoritmo para encontrar esse número secreto usa um método de 'força bruta', o que significa que não faz nada inteligente e simplesmente tenta todos os números possíveis.
Quanto tempo isso levaria? Em teoria, poderíamos ter sorte e adivinhar a resposta de uma só vez, mas isso é muito improvável. Na média, teríamos que tentar cerca de metade das entradas possíveis, então o tempo de execução do nosso algoritmo é proporcional ao número de combinações possíveis. A questão agora é: como o número de combinações possíveis cresce com o tamanho do número secreto?
Cada dígito que adicionamos ao nosso número secreto multiplica o número de combinações possíveis por 10. Por exemplo, um número secreto com 1 dígito tem 10 valores possíveis (0, 1, 2, 3, 4, 5, 6, 7, 8 & 9), e um número secreto com 2 dígitos tem 100 valores possíveis. Assumindo que o tempo necessário para adivinhar cada dígito leva a mesma quantidade de tempo (independentemente do comprimento), podemos representar isso matematicamente assim:
ParseError: KaTeX parse error: Undefined control sequence: \cssId at position 1: \̲c̲s̲s̲I̲d̲{T}{T} \cssId{p…Você notará que o número de dígitos (d) é o expoente nesta equação e, como tal, dizemos que este é um algoritmo de tempo exponencial e que o tempo de execução cresce exponencialmente com o comprimento da entrada.
Por que medimos algoritmos dessa forma?
Diferentes computadores têm diferentes pontos fortes; certas operações podem ser mais rápidas em um computador do que em outro. Ao estudar o crescimento versus o tamanho da entrada, podemos ignorar detalhes específicos do dispositivo e realmente medir o algoritmo , em vez da combinação específica de algoritmo e computador. É importante ressaltar que saber como um algoritmo é dimensionado com o tamanho da entrada também nos diz se o algoritmo crescerá de forma gerenciável ou não.
Vamos pensar no algoritmo de adição de tempo linear que vimos acima. Se pudéssemos somar dois números de 10 dígitos em um segundo, devido à taxa linear de crescimento, poderíamos somar dois números de 20 dígitos em dois segundos. Cada 10 dígitos extras deve adicionar aproximadamente mais um segundo ao nosso tempo de computação.
Para contrastar, imagine que você pode encontrar um PIN de 10 dígitos em 1 segundo usando o algoritmo de pesquisa de tempo exponencial acima. Isso significa que seu computador é rápido o suficiente para tentar ~ 5.000.000.000 combinações por segundo. Esperaríamos que este computador usando esse algoritmo levasse aproximadamente 5.000.000.000 segundos (~150 anos) para encontrar um PIN de 20 dígitos. Adicionar outros 10 dígitos aumenta isso para cerca de 150.000.000.000 anos (~ 120x a idade do universo). Algoritmos de tempo exponencial com uma entrada de tamanho modesto (neste caso ~ 30 dígitos) podem se tornar não apenas difíceis, mas literalmente impossíveis de realizar.
Embora esse problema de adivinhação de PIN seja um exemplo artificial que pretendíamos ser o mais simples possível, existem muitos problemas reais em ciência da computação para os quais temos apenas algoritmos ineficientes. Apesar da impressionante velocidade dos computadores atuais, esses problemas intratáveis podem ser muito difíceis até mesmo para os maiores supercomputadores.
Mas se pudermos encontrar algoritmos que cresçam com mais eficiência, esses problemas intratáveis podem se tornar subitamente gerenciáveis, mesmo com computadores relativamente lentos ou não confiáveis. É aí que entra a computação quântica.
Como a computação quântica pode ajudar?
Até agora, pensamos em algoritmos de uma maneira muito abstrata, mas os computadores que executam esses algoritmos devem existir no mundo real. Quer esses computadores sejam microchips de alta potência ou humanos com canetas e papel, todos os computadores são governados pelas leis da física, e as operações que eles podem realizar limitam os algoritmos que podemos criar.
A física é uma tentativa de descobrir o conjunto de regras que tudo no universo segue. Por volta do início do século 20, por meio de experimentos delicados em laboratórios, os físicos viram comportamentos estranhos que sua física atual não conseguia explicar. Isso significava que as regras não eram muito precisas, então eles desenvolveram a física 'quântica' mais completa, que descreve muito bem esse comportamento.
Os físicos criaram a física quântica para explicar o comportamento que nunca tinham visto antes, e os cientistas da computação descobriram que poderiam (em teoria) explorar esse comportamento recém-descoberto para criar algoritmos mais eficientes. Como resultado, existem certos problemas que acreditamos serem intratáveis para computadores convencionais, mas são gerenciáveis para um computador 'quântico' que pode explorar esse comportamento. Um desses problemas é a fatoração de inteiros .
Digamos que temos um inteiro que chamaremos de ''. Um algoritmo de fatoração encontra os inteiros e tais que . Isso às vezes é fácil; você pode dizer de relance que , mas se é o produto de dois números primos grandes, esse problema se torna muito difícil. Quando falamos sobre fatoração de inteiros, vamos assumir o cenário mais difícil (pior caso). Na célula de código abaixo, estamos atribuindo um número de 250 dígitos à variável x :
Em 2020, os pesquisadores fatoraram esse número usando um supercomputador clássico e cerca de 2.700 core-years de poder de processamento. Este foi um grande esforço que quebrou recordes no momento da escrita. Podemos verificar seus resultados na célula de código abaixo (felizmente, temos algoritmos eficientes para multiplicação!):
A saída mostrada é o valor da última linha da célula. Nesse caso, podemos ver que p*q == x é avaliado como True . Embora não comprovado matematicamente, temos certeza de que não há algoritmo eficiente para fatorar esses números em computadores tradicionais. Na verdade, grande parte da criptografia da Internet se baseia na suposição de que esse problema é intratável e que fatorar um número RSA de 617 dígitos é impossível. Em contraste, conhecemos algoritmos de fatoração eficientes para computadores quânticos que, uma vez que tivermos computadores quânticos grandes o suficiente, estimamos que poderiam fatorar esses números em menos de um dia.
Onde estamos agora?
Agora sabemos que os computadores quânticos podem executar algoritmos mais eficientes, mas os computadores quânticos que temos hoje são muito pequenos e instáveis para apresentar vantagens sobre os computadores tradicionais.
Em um nível muito simples, existem dois fatores que limitam o tamanho dos problemas que nossos computadores quânticos podem resolver. A primeira é a quantidade de dados que eles podem armazenar e trabalhar, que geralmente medimos em qubits . Se não tivermos qubits suficientes, simplesmente não podemos armazenar e operar problemas acima de um determinado tamanho. A segunda é a taxa de erro do nosso computador quântico; como só vemos o comportamento quântico em experimentos de laboratório delicados, criar computadores quânticos é um processo delicado. Os computadores quânticos que temos agora são ruidosos, o que significa que muitas vezes erram e introduzem ' ruído ' em nossos resultados. Muito ruído e nossos resultados serão absurdos!
No momento, os computadores quânticos que temos são experimentais. Eles são limitados por contagens de qubits e taxas de erro, portanto, os maiores problemas que podemos resolver atualmente ainda são facilmente gerenciáveis para computadores convencionais.
Em algum momento no futuro, isso vai mudar. Alcançaremos a 'vantagem quântica', na qual fará sentido econômico resolver um problema usando um computador quântico ao invés de um computador convencional. Como nós sabemos? Porque medimos algoritmos por sua taxa de crescimento! Sabemos que, enquanto os computadores quânticos continuarem se desenvolvendo de forma progressiva, eles acabarão ultrapassando os computadores clássicos.
A estimativa para fatorar um número RSA de 617 dígitos em menos de um dia assumiu ~ 20 milhões de qubits ruidosos. No momento da redação deste artigo, a IBM possui atualmente um computador quântico de 65 qubits e pretende criar um sistema com mais de 1.000 qubits até 2023. Existem outros algoritmos que acreditamos que nos darão uma vantagem quântica muito antes desse marco, mas ainda pode parecer que estamos muito longe.
Devemos nos lembrar de onde vieram os computadores convencionais. Abaixo está uma foto do primeiro transistor , criado em 1947. Os transistores são os blocos de construção dos processadores de computador modernos.
Crédito da imagem: Funcionário federal Link, Domínio Público .
70 anos depois, nossos chips de computador modernos podem conter bilhões de transistores.
No restante deste curso, exploraremos os efeitos quânticos que nos permitem criar algoritmos mais eficientes. Ao final deste curso, você será capaz de usar o pacote de software, Qiskit , para programar um computador quântico para executar um desses algoritmos.
Questionário rápido
Computadores quânticos eventualmente...
...fazer cálculos que são muito difíceis para computadores convencionais.
...substituir computadores convencionais.
...aumentar a velocidade dos computadores convencionais.