Complexidade de algoritmos e computação quântica

A complexidade do algoritmo tá relacionada com o uso de recursos de um algoritmo crescem à medida que o tamanho da input aumenta. Ou seja, é uma medida de eficiênca.

A “Notação Big O” ajuda a visualizar diferentes relações entre o número de operações pra realizar um algoritmo e o tamanho do input.

Como base, a gente pode pensar num algoritmo “marromenos”.

O(n): Tempo linear: cresce juntinho com o input.

Daqui, dá pra classificar bem superficialmente os algoritmos como “bons” e “ruins”.

Exemplos de algoritmos “bons”:

O(1): Tempo constante. Não importa o tamanho da entrada, o algoritmo leva a mesma quantidade de tempo. Show de bola.

O(log n): Tempo logarítmico. (cresce lentamente em relação ao tamanho do input)

Exemplos q começam a azedar:

O(n²): Tempo quadrático (proporcional ao quadrado do tamanho do input)

O(2^n): Tempo exponencial. (ruim q só!)

O(n!): Tempo fatorial (horroroso!)

Visualmente:

Pq isso é importante?

Pq a melhora de eficiência da computação quântica não é a mesma pra diferentes algoritmos, com diferentes complexidades!

Por exemplo, o algoritmo de Shor sai do setor de “muito ruim” pro setor “bom”. Isso é importante pra criptografias, q se usam justamente do fato de certos algoritmos serem muito ineficientes pra codificarem informação de forma segura.

Só q isso não é mais verdade em um computador quântico! Ou seja, algumas criptografias podem se tornar inúteis com a computação quântica. Isso é um problema grave de segurança!

Agora, um outro exemplo é o algoritmo de Grover, que é útil para busca não estuturada. Ele sai de razoável pra bom. Não é AQUELA melhora, mas é alguma melhora.

E ainda tem coisas q não sabemos otimizar muito bem. Por exemplo, lidar com input que não seja quântico em machine learning quântico não é algo muito eficiente e é uma área de pesquisa ativa.

Em resumo:

A computação quântica não melhora todas as operações computacionais da mesma forma!