Medindo o custo computacional

A seguir, vamos discutir um arcabouço matemático pelo qual o custo computacional pode ser medido, com foco estreito nas necessidades deste curso. A análise de algoritmos e a complexidade computacional são áreas de estudo por si mesmas e têm muito mais a dizer sobre essas noções.

Como ponto de partida, considere a figura a seguir da lição anterior, que representa uma abstração de alto nível de uma computação.

A computação em si pode ser modelada ou descrita de várias formas, como por um programa escrito em Python, uma máquina de Turing, um circuito booleano ou um circuito quântico. Nosso foco será em circuitos (tanto booleanos quanto quânticos).

Codificações e comprimento da entrada

Vamos começar com a entrada e a saída de um problema computacional, que vamos assumir serem strings binárias. Outros símbolos poderiam ser usados, mas vamos manter as coisas simples para os propósitos desta discussão, restringindo nossa atenção a entradas e saídas em strings binárias. Por meio de strings binárias, podemos codificar uma variedade de objetos interessantes que os problemas que queremos resolver podem envolver, como números, vetores, matrizes e grafos, além de listas desses e de outros objetos.

Por exemplo, para codificar inteiros não negativos, podemos usar a notação binária. A tabela a seguir lista a codificação binária dos primeiros nove inteiros não negativos, junto com o comprimento (ou seja, o número total de bits) de cada codificação.

Número	Codificação binária	Comprimento
0	0	1
1	1	1
2	10	2
3	11	2
4	100	3
5	101	3
6	110	3
7	111	3
8	1000	4

Podemos estender facilmente essa codificação para lidar com inteiros positivos e negativos acrescentando um bit de sinal às representações, se quisermos. Às vezes também é conveniente permitir que representações binárias de inteiros não negativos tenham zeros à esquerda, que não alteram o valor codificado, mas permitem que as representações preencham uma string ou palavra de tamanho fixo.

Usar a notação binária para representar inteiros não negativos é tanto comum quanto eficiente, mas se quiséssemos poderíamos escolher uma forma diferente de representar inteiros não negativos usando strings binárias, como as sugeridas na tabela a seguir. Os detalhes dessas alternativas não são importantes para esta discussão — o objetivo é apenas esclarecer que temos escolhas quanto às codificações que usamos.

Número	Codificação unária	Codificação lexicográfica
0	$\varepsilon$	$\varepsilon$
1	0	0
2	00	1
3	000	00
4	0000	01
5	00000	10
6	000000	11
7	0000000	000
8	00000000	001

(Nesta tabela, o símbolo $\varepsilon$ representa a string vazia, que não possui símbolos e tem comprimento igual a zero. Naturalmente, para evitar uma fonte óbvia de confusão, usamos um símbolo especial como $\varepsilon$ para representar a string vazia em vez de literalmente não escrever nada.)

Outros tipos de entradas, como vetores e matrizes, ou objetos mais complexos como descrições de moléculas, também podem ser codificados como strings binárias. Assim como fizemos para inteiros não negativos, uma variedade de esquemas de codificação diferentes pode ser selecionada ou inventada. Para qualquer esquema que desenvolvamos para codificar entradas de um dado problema, interpretamos o comprimento de uma string de entrada como representando o tamanho da instância do problema sendo resolvida.

Por exemplo, o número de bits necessários para expressar um inteiro não negativo $N$ em notação binária, às vezes denotado por $\operatorname{lg}(N),$ é dado pela fórmula a seguir.

$$\operatorname{lg}(N) = \begin{cases} 1 & N = 0\\ 1 + \lfloor \log_2 (N) \rfloor & N \geq 1 \end{cases}$$

Assumindo que usamos a notação binária para codificar a entrada do problema de fatoração de inteiros, o comprimento da entrada para o número $N$ é portanto $\operatorname{lg}(N).$ Note, em particular, que o comprimento (ou tamanho) da entrada $N$ não é $N$ em si; quando $N$ é grande, não precisamos de tantos bits assim para expressar $N$ em notação binária.

De um ponto de vista estritamente formal, sempre que consideramos um problema ou tarefa computacional, deve-se entender que um esquema específico foi selecionado para codificar quaisquer objetos fornecidos como entrada ou produzidos como saída. Isso permite que computações que resolvem problemas interessantes sejam vistas abstratamente como transformações de entradas em strings binárias para saídas em strings binárias.

Os detalhes de como os objetos são codificados como strings binárias necessariamente precisam ser importantes para essas computações em algum nível. Geralmente, porém, não nos preocupamos muito com esses detalhes quando analisamos o custo computacional, para evitar entrar em detalhes de importância secundária. O raciocínio básico é que esperamos que o custo computacional de converter entre esquemas de codificação "razoáveis" seja insignificante em comparação com o custo de resolver o problema em si. Nas situações em que isso não é o caso, os detalhes podem (e devem) ser esclarecidos.

Por exemplo, uma computação muito simples converte entre a representação binária de um inteiro não negativo e sua codificação lexicográfica (que não explicamos em detalhes, mas pode ser inferida da tabela acima). Por essa razão, o custo computacional da fatoração de inteiros não diferiria significativamente se decidíssemos trocar de uma dessas codificações para a outra para a entrada $N.$ Por outro lado, codificar inteiros não negativos em notação unária implica um aumento exponencial no número total de símbolos necessários, e por essa razão não consideraríamos isso um esquema de codificação "razoável".

Operações elementares

Agora vamos considerar a computação em si, representada pelo retângulo azul na figura acima. A forma como mediremos o custo computacional é contar o número de operações elementares que cada computação requer. Intuitivamente, uma operação elementar é aquela que envolve um número pequeno e fixo de bits ou qubits, e que pode ser realizada com rapidez e facilidade — como calcular o AND de dois bits. Em contraste, executar a função factorint não é razoavelmente vista como uma operação elementar.

Formalmente, existem diferentes escolhas para o que constitui uma operação elementar dependendo do modelo computacional utilizado. Nosso foco será em modelos de circuitos, especificamente em circuitos quânticos e booleanos.

Conjuntos universais de portas

Para modelos de computação baseados em circuitos, é típico que cada porta seja vista como uma operação elementar. Isso leva à questão de quais portas exatamente permitimos em nossos circuitos. Focando por ora em circuitos quânticos, vimos várias portas até agora nesta série, incluindo as portas $X,$ $Y,$ $Z,$ $H,$ $S$ e $T,$ portas swap, versões controladas de portas (incluindo CNOT, Toffoli e portas de Fredkin), além de portas que representam medições na base padrão. No contexto do jogo CHSH, também vimos algumas portas de rotação adicionais.

Também discutimos portas de consulta no contexto do modelo de consulta, e vimos ainda que qualquer operação unitária $U,$ agindo sobre qualquer número de qubits, pode ser vista como uma porta se quisermos — mas desconsideraremos ambas as opções para os propósitos desta discussão. Não trabalharemos no modelo de consulta (embora a implementação de portas de consulta usando operações elementares seja discutida mais adiante na lição), e ver portas unitárias arbitrárias, potencialmente agindo sobre milhões de qubits, como operações elementares não leva a noções significativas ou realistas de custo computacional.

Limitando-nos a portas quânticas que operam sobre pequenos números de qubits, uma abordagem para decidir quais delas serão consideradas elementares é estabelecer um critério preciso — mas essa não é a abordagem padrão nem a que adotaremos. Em vez disso, simplesmente fazemos uma escolha.

Aqui está uma escolha padrão, que adotaremos como conjunto de portas padrão para circuitos quânticos:

• Portas unitárias de um qubit desta lista: $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T$ e $T^{\dagger}$
• Portas CNOT
• Medições de um qubit na base padrão

Uma alternativa comum é considerar as portas Toffoli, Hadamard e $S$ como elementares, além das medições na base padrão. Às vezes todas as portas de um qubit são consideradas elementares, embora isso leve a um modelo irrealisticamente poderoso quando a precisão com que as portas são executadas não é devidamente levada em conta.

As portas unitárias em nossa coleção padrão formam o que se chama de conjunto de portas universal. Isso significa que podemos aproximar qualquer operação unitária sobre qualquer número de qubits com qualquer grau de precisão que desejarmos, usando circuitos compostos apenas por essas portas. Para ser claro, a definição de universalidade não impõe nenhum requisito sobre o custo dessas aproximações, ou seja, o número de portas do nosso conjunto que precisamos. De fato, um argumento bastante simples baseado na noção matemática de medida revela que a maioria das operações unitárias deve ter custo extremamente alto. Provar a universalidade de conjuntos de portas quânticas não é simples e não será abordado neste curso.

Para circuitos booleanos, adotaremos as portas AND, OR, NOT e FANOUT como representando operações elementares. Na verdade, não precisamos de ambas as portas AND e OR — podemos usar as leis de De Morgan para converter de uma para a outra colocando portas NOT em todos os três fios de entrada/saída — mas mesmo assim é comum e conveniente permitir ambas as portas AND e OR. As portas AND, OR, NOT e FANOUT formam um conjunto universal para computações determinísticas, o que significa que qualquer função de qualquer número fixo de bits de entrada para qualquer número fixo de bits de saída pode ser implementada com essas portas.

O princípio da medição adiada

Portas de medição na base padrão podem aparecer dentro de circuitos quânticos, mas às vezes é conveniente adiá-las até o final. Isso nos permite ver computações quânticas como consistindo de uma parte unitária (representando a computação em si), seguida de uma fase simples de leitura onde os qubits são medidos e os resultados são emitidos como saída. Isso sempre pode ser feito, desde que estejamos dispostos a adicionar um qubit extra para cada medição na base padrão. Na figura a seguir, o circuito à direita ilustra como isso pode ser feito para a porta à esquerda.

Especificamente, o bit clássico no circuito à esquerda é substituído por um qubit à direita (inicializado no estado $\vert 0\rangle$), e a medição na base padrão é substituída por uma porta CNOT, seguida de uma medição na base padrão no qubit inferior. O ponto é que a medição na base padrão no circuito à direita pode ser empurrada para o final do circuito. Se o bit clássico no circuito à esquerda for usado posteriormente como bit de controle, podemos usar o qubit inferior no circuito à direita como controle em vez disso, e o efeito geral será o mesmo. (Estamos assumindo que o bit clássico no circuito à esquerda não é sobrescrito após a medição por outra medição — mas se fosse, poderíamos sempre usar um novo bit clássico em vez de sobrescrever um que foi usado para uma medição anterior.)

Tamanho e profundidade de circuitos

Tamanho do circuito

O número total de portas em um circuito é chamado de tamanho desse circuito. Assim, assumindo que as portas em nossos circuitos representam operações elementares, o tamanho de um circuito representa o número de operações elementares que ele requer — ou, em outras palavras, seu custo computacional. Escrevemos $\operatorname{size}(C)$ para nos referir ao tamanho de um dado circuito $C.$

Por exemplo, considere o seguinte circuito booleano para calcular o XOR de dois bits.

O tamanho deste circuito é 7 porque há 7 portas no total. (Operações de fanout nem sempre são contadas como portas, mas para os propósitos desta lição as contaremos como portas.)

Tempo, custo e profundidade de circuitos

O tempo é um recurso criticamente importante, ou uma limitação, para as computações. Os exemplos acima, como a tarefa de fatorar RSA1024, reforçam esse ponto de vista. A função factorint não deixa de fatorar RSA1024 em si — é simplesmente que não temos tempo suficiente para deixá-la terminar.

A noção de custo computacional, como o número de operações elementares necessárias para realizar uma computação, é uma representação abstrata do tempo necessário para implementar uma computação. Cada operação elementar requer certa quantidade de tempo para ser executada, e quanto mais delas uma computação precisar, mais tempo ela levará, ao menos em geral. No interesse da simplicidade, continuaremos a fazer essa associação entre custo computacional e o tempo necessário para executar algoritmos.

Mas observe que o tamanho de um circuito não corresponde necessariamente de forma direta ao tempo que leva para ser executado. No nosso circuito booleano para calcular o XOR de dois bits, por exemplo, as duas portas FANOUT poderiam ser executadas simultaneamente, assim como as duas portas NOT, bem como as duas portas AND. Uma forma diferente de medir a eficiência de circuitos, que leva em conta essa possibilidade de paralelização, é pela sua profundidade. Essa é a quantidade mínima de camadas de portas necessárias no circuito, onde as portas em cada camada operam em fios diferentes. De forma equivalente, a profundidade de um circuito é o número máximo de portas encontradas em qualquer caminho de um fio de entrada para um fio de saída. Para o circuito acima, por exemplo, a profundidade é 4.

A profundidade de circuitos é uma forma de formalizar o tempo de execução de computações paralelas. É um tópico avançado, e existem construções de circuitos muito sofisticadas conhecidas por minimizar a profundidade necessária para determinadas computações. Há também algumas perguntas fascinantes sem resposta sobre a profundidade de circuitos. (Por exemplo, muito ainda é desconhecido sobre a profundidade de circuito necessária para calcular MDCs.) Não teremos muito mais a dizer sobre a profundidade de circuitos nesta série, além de incluir alguns fatos interessantes sobre ela ao longo do caminho, mas deve-se reconhecer claramente que a paralelização é uma fonte potencial de vantagens computacionais.

Atribuindo custos a diferentes portas

Uma nota final sobre o tamanho de circuitos e o custo computacional é que é possível atribuir custos diferentes a portas, em vez de ver cada porta como contribuindo igualmente para o custo total.

Por exemplo, como já mencionado, as portas FANOUT são frequentemente vistas como gratuitas para circuitos booleanos — ou seja, poderíamos escolher que as portas FANOUT tenham custo zero. Como outro exemplo, quando trabalhamos no modelo de consulta e contamos o número de consultas que um circuito faz a uma função de entrada (na forma de uma caixa preta), estamos efetivamente atribuindo custo unitário às portas de consulta e custo zero a outras portas, como as portas Hadamard. Um exemplo final é que às vezes atribuímos custos diferentes a portas dependendo de quão difíceis elas são de implementar, o que pode variar dependendo do hardware considerado.

Embora todas essas opções sejam sensatas em diferentes contextos, para esta lição manteremos as coisas simples e nos ateremos ao tamanho do circuito como representação do custo computacional.

Custo como função do comprimento da entrada

Estamos principalmente interessados em como o custo computacional escala à medida que as entradas ficam cada vez maiores. Isso nos leva a representar os custos dos algoritmos como funções do comprimento da entrada.

Famílias de circuitos

Entradas para um dado problema computacional podem variar em comprimento, potencialmente crescendo de forma arbitrária. Cada circuito, por outro lado, tem um número fixo de portas e fios. Por essa razão, quando pensamos em algoritmos em termos de circuitos, geralmente precisamos de famílias infinitamente grandes de circuitos para representar algoritmos. Por família de circuitos, entendemos uma sequência de circuitos que crescem em tamanho, permitindo que entradas cada vez maiores sejam acomodadas.

Por exemplo, imagine que temos um algoritmo clássico para fatoração de inteiros, como o usado pela função factorint. Como todo algoritmo clássico, esse algoritmo pode ser implementado com circuitos booleanos — mas para fazer isso precisaremos de um circuito separado para cada comprimento de entrada possível. Se observássemos os circuitos resultantes para diferentes comprimentos de entrada, veríamos que seus tamanhos crescem naturalmente à medida que o comprimento da entrada cresce — refletindo o fato de que fatorar inteiros de 4 bits é muito mais fácil e requer muito menos operações elementares do que fatorar inteiros de 1024 bits, por exemplo.

Isso nos leva a representar o custo computacional de um algoritmo por uma função $t,$ definida de forma que $t(n)$ é o número de portas no circuito que implementa o algoritmo para entradas de $n$ bits. Em termos mais formais, um algoritmo no modelo de circuito booleano é descrito por uma sequência de circuitos $\{C_1, C_2, C_3,\ldots\},$ onde $C_n$ resolve qualquer problema que estejamos discutindo para entradas de $n$ bits (ou, mais geralmente, para entradas cujo tamanho é parametrizado de alguma forma por $n$), e a função $t$ representando o custo desse algoritmo é definida como

$$t(n) = \operatorname{size}(C_n).$$

Para circuitos quânticos a situação é semelhante, onde circuitos cada vez maiores são necessários para acomodar strings de entrada cada vez mais longas.

Exemplo: adição de inteiros

Para explicar melhor, vamos tomar um momento para considerar o problema da adição de inteiros, que é muito mais simples do que a fatoração de inteiros ou mesmo o cálculo de MDCs.

Adição de inteiros

Entrada: inteiros $N$ e $M$
Saída: $N+M$

Como poderíamos projetar circuitos booleanos para resolver esse problema?

Para simplificar, vamos restringir nossa atenção ao caso em que $N$ e $M$ são inteiros não negativos representados por strings de $n$ bits usando notação binária. Permitiremos qualquer número de zeros à esquerda nessas codificações, de modo que

$$0\leq N,M\leq 2^n - 1.$$

A saída será uma string binária de $(n+1)$ bits representando a soma, que é o número máximo de bits necessários para expressar o resultado.

Começamos com um algoritmo — o algoritmo padrão para adição de representações binárias — que é o análogo na base $2$ da forma como a adição é ensinada nas escolas primárias ao redor do mundo. Esse algoritmo pode ser implementado com circuitos booleanos da seguinte forma.

Começando pelos bits menos significativos, podemos calcular seu XOR para determinar o bit menos significativo da soma. Em seguida, calculamos o bit de carry, que é o AND dos dois bits menos significativos de $N$ e $M.$ Às vezes, essas duas operações juntas são conhecidas como um meio somador.

Usando o circuito XOR que já vimos algumas vezes junto com uma porta AND e duas portas FANOUT, podemos construir um meio somador com 10 portas. Se por algum motivo mudássemos de ideia e decidíssemos incluir portas XOR em nosso conjunto de operações elementares, precisaríamos de 1 porta AND, 1 porta XOR e 2 portas FANOUT para construir um meio somador.

Passando para os bits mais significativos, podemos usar um procedimento semelhante, mas desta vez incluindo o bit de carry de cada posição anterior em nosso cálculo. Ao encadear dois meio somadores e tomar o OR dos bits de carry que eles produzem, podemos criar o que é conhecido como um somador completo.

Isso requer 21 portas no total: 2 portas AND, 2 portas XOR (cada uma exigindo 7 portas para ser implementada), uma porta OR e 4 portas FANOUT.

Por fim, ao encadear os somadores completos, obtemos um circuito booleano para adição de inteiros não negativos. Por exemplo, o circuito a seguir calcula a soma de dois inteiros de 4 bits.

Em geral, isso requer

$$21 (n-1) + 10 = 21 n - 11$$

portas. Se tivéssemos decidido incluir portas XOR em nosso conjunto de operações elementares, precisaríamos de $2n-1$ portas AND, $2n-1$ portas XOR, $n-1$ portas OR e $4n-2$ portas FANOUT, para um total de $9n-5$ portas. Se além disso decidíssemos não contar as portas FANOUT, seriam $5n-3$ portas.

Notação assintótica

Por um lado, é bom saber precisamente quantas portas são necessárias para realizar várias computações, como no exemplo da adição de inteiros acima. Esses detalhes são importantes para realmente construir os circuitos.

Por outro lado, se realizarmos análises com esse nível de detalhe para todas as computações que nos interessam, incluindo aquelas para tarefas muito mais complicadas do que a adição, nos veremos rapidamente enterrados em detalhes. Para manter as coisas gerenciáveis, e para intencionalmente suprimir detalhes de importância secundária, tipicamente usamos a notação Big-O ao analisar algoritmos. Por meio dessa notação, podemos expressar a ordem em que as funções crescem.

Formalmente, se temos duas funções $g(n)$ e $h(n),$ escrevemos que $g(n) = O(h(n))$ se existir um número real positivo $c > 0$ e um inteiro positivo $n_0$ tais que

$$g(n) \leq c\cdot h(n)$$

para todo $n \geq n_0.$ Tipicamente $h(n)$ é escolhido para ser uma expressão tão simples quanto possível, de modo que a notação possa ser usada para revelar o comportamento limite de uma função em termos simples. Por exemplo, $17 n^3 - 257 n^2 + 65537 = O(n^3).$

Esta notação pode ser estendida a funções com múltiplos argumentos de forma bastante direta. Por exemplo, se temos duas funções $g(n,m)$ e $h(n,m)$ definidas em inteiros positivos $n$ e $m,$ escrevemos que $g(n,m) = O(h(n,m))$ se existir um número real positivo $c > 0$ e um inteiro positivo $k_0$ tais que

$$g(n,m) \leq c\cdot h(n,m)$$

sempre que $n+m \geq k_0.$

Conectando essa notação ao exemplo da adição de inteiros não negativos, concluímos que existe uma família de circuitos booleanos $\{C_1, C_2,\ldots,\},$ onde $C_n$ soma dois inteiros não negativos de $n$ bits, tal que $\operatorname{size}(C_n) = O(n).$ Isso revela a característica mais essencial de como o custo da adição escala com o tamanho da entrada: ela escala linearmente.

Note também que isso não depende do detalhe específico de se consideramos que as portas XOR têm custo unitário ou custo $7.$ Em geral, usar a notação Big-O nos permite fazer afirmações sobre custos computacionais que não são sensíveis a esses detalhes de baixo nível.

Mais exemplos

Aqui estão mais alguns exemplos de problemas da teoria computacional dos números, começando com a multiplicação.

Multiplicação de inteiros

Entrada: inteiros $N$ e $M$
Saída: $NM$

Criar circuitos booleanos para esse problema é mais difícil do que criar circuitos para adição — mas pensando sobre o algoritmo padrão de multiplicação, podemos criar circuitos de tamanho $O(n^2)$ para esse problema (assumindo que $N$ e $M$ são ambos representados por representações binárias de $n$ bits). De forma mais geral, se $N$ tem $n$ bits e $M$ tem $m$ bits, existem circuitos booleanos de tamanho $O(nm)$ para multiplicar $N$ e $M.$

Existem, de fato, outras formas de multiplicar que escalam melhor. Por exemplo, o algoritmo de multiplicação de Schönhage-Strassen pode ser usado para criar circuitos booleanos para multiplicar dois inteiros de $n$ bits com custo $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n))).$ A complexidade desse método causa muito overhead, porém, tornando-o prático apenas para números com dezenas de milhares de bits.

Outro problema básico é a divisão, que interpretamos como calcular tanto o quociente quanto o resto dado um divisor e um dividendo inteiros.

Divisão de inteiros

Entrada: inteiros $N$ e $M\neq0$
Saída: inteiros $q$ e $r$ satisfazendo $0\leq r < |M|$ e $N = q M + r$

O custo da divisão de inteiros é semelhante ao da multiplicação: se $N$ tem $n$ bits e $M$ tem $m$ bits, existem circuitos booleanos de tamanho $O(nm)$ para resolver esse problema. E assim como na multiplicação, métodos assintoticamente superiores são conhecidos.

Podemos agora comparar algoritmos conhecidos para calcular MDCs com os de adição e multiplicação. O algoritmo de Euclides para calcular o MDC de um número $N$ de $n$ bits e um número $M$ de $m$ bits requer circuitos booleanos de tamanho $O(nm),$ semelhante aos algoritmos padrão para multiplicação e divisão. Também semelhante à multiplicação e divisão, existem algoritmos de MDC assintoticamente mais rápidos — incluindo aqueles que requerem $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ operações elementares para calcular o MDC de dois números de $n$ bits.

Uma computação um pouco mais custosa que surge na teoria dos números é a exponenciação modular.

Exponenciação modular de inteiros

Entrada: inteiros $N,$ $K$ e $M$ com $K\geq 0$ e $M\geq 1$
Saída: $N^K \hspace{1mm} (\text{mod }M)$

Por $N^K\hspace{1mm} (\text{mod }M)$ queremos dizer o resto quando $N^K$ é dividido por $M,$ ou seja, o único inteiro $r$ satisfazendo $0\leq r < M$ e $N^K = q M + r$ para algum inteiro $q.$

Se $N$ tem $n$ bits, $M$ tem $m$ bits e $K$ tem $k$ bits, esse problema pode ser resolvido por circuitos booleanos de tamanho $O(k m^2 + nm).$ Isso não é nada óbvio. A solução não é primeiro calcular $N^K$ e depois tomar o resto, o que necessitaria de exponencialmente muitos bits apenas para armazenar o número $N^K.$ Em vez disso, podemos usar o algoritmo de exponenciação rápida (conhecido alternativamente como método binário e exponenciação por quadratura repetida), que usa a representação binária de $K$ para realizar toda a computação módulo $M.$ Assumindo que $N,$ $M$ e $K$ são todos números de $n$ bits, obtemos um algoritmo $O(n^3)$ — ou um algoritmo de tempo cúbico. E novamente, existem algoritmos conhecidos que são mais complexos mas assintoticamente mais rápidos.

Custo da fatoração de inteiros

Em contraste com os algoritmos recém-discutidos, os algoritmos clássicos conhecidos para fatoração de inteiros são muito mais custosos — como esperaríamos a partir da discussão anterior na lição.

Uma abordagem simples para fatorar é a divisão tentativa, onde um algoritmo busca pela lista $2,\ldots,\sqrt{N}$ para encontrar um fator primo de um número de entrada $N.$ Isso requer $O(2^{n/2})$ iterações no pior caso quando $N$ é um número de $n$ bits. Cada iteração requer uma divisão tentativa, o que significa $O(n^2)$ operações elementares por iteração (usando um algoritmo padrão para divisão de inteiros). Acabamos com circuitos de tamanho $O(n^2 2^{n/2}),$ que é exponencial no tamanho da entrada $n.$

Existem algoritmos para fatoração de inteiros com melhor escalabilidade. O crivo do corpo de números mencionado anteriormente, por exemplo, que é um algoritmo que faz uso de aleatoriedade, é geralmente acreditado (mas não rigorosamente comprovado) que requer

$$2^{O(n^{1/3} (\operatorname{lg}(n))^{2/3})}$$

operações elementares para fatorar inteiros de $n$ bits com alta probabilidade. Embora seja bastante significativo que $n$ esteja elevado à potência $1/3$ no expoente dessa expressão, o fato de que ele aparece no expoente ainda é um problema que causa escalabilidade ruim — e explica em parte por que o RSA1024 permanece fora de seu domínio de aplicabilidade.

Custo polinomial versus exponencial

Algoritmos clássicos para adição, multiplicação, divisão de inteiros e cálculo de máximos divisores comuns nos permitem resolver esses problemas em um piscar de olhos para entradas com milhares de bits. A adição tem custo linear, enquanto os outros três problemas têm custo quadrático (ou custo subquadrático usando algoritmos assintoticamente rápidos). A exponenciação modular é mais cara, mas ainda pode ser feita de forma bastante eficiente, com custo cúbico (ou custo sub-cúbico usando algoritmos assintoticamente rápidos).

Todos esses são exemplos de algoritmos com custo polinomial, o que significa que têm custo $O(n^c)$ para alguma escolha de uma constante fixa $c > 0.$ Como uma aproximação grosseira de primeira ordem, algoritmos com custo polinomial são abstratamente vistos como representando algoritmos eficientes.

Em contraste, algoritmos clássicos conhecidos para fatoração de inteiros têm custo exponencial. Às vezes o custo do crivo do corpo de números é descrito como subexponencial porque $n$ está elevado à potência $1/3$ no expoente, mas em teoria da complexidade é mais típico reservar esse termo para algoritmos cujo custo é

$$O\bigl(2^{n^{\varepsilon}}\bigr)$$

para todo $\varepsilon > 0.$ Os chamados problemas NP-completos são uma classe de problemas que não se sabe (e amplamente se conjectura que não) ter algoritmos de custo polinomial. Uma formulação baseada em circuitos da hipótese do tempo exponencial postula algo ainda mais forte, que é que nenhum problema NP-completo pode ter um algoritmo de custo subexponencial.

A associação de algoritmos de custo polinomial com algoritmos eficientes deve ser entendida como uma abstração ampla. Claro, se o custo de um algoritmo escala como $n^{1000}$ ou $n^{1000000}$ para entradas de tamanho $n,$ então é exagero descrever esse algoritmo como eficiente. No entanto, mesmo um algoritmo com custo que escala como $n^{1000000}$ deve estar fazendo algo inteligente para evitar ter custo exponencial, que é geralmente o que esperamos de algoritmos baseados de alguma forma em "força bruta" ou "busca exaustiva." Mesmo os refinamentos sofisticados do crivo do corpo de números, por exemplo, não conseguem evitar essa escalabilidade exponencial em custo. Algoritmos de custo polinomial, por outro lado, conseguem tirar vantagem da estrutura do problema de alguma forma que evita uma escalabilidade exponencial.

Na prática, a identificação de um algoritmo de custo polinomial para um problema é apenas um primeiro passo rumo à eficiência real. Por meio de refinamentos algorítmicos, algoritmos de custo polinomial com expoentes grandes às vezes podem ser melhorados dramaticamente, reduzindo o custo para uma escalabilidade polinomial mais "razoável". Às vezes as coisas ficam mais fáceis quando se sabe que são possíveis — portanto, a identificação de um algoritmo de custo polinomial para um problema também pode ter o efeito de inspirar novos algoritmos ainda mais eficientes.

Ao considerarmos as vantagens da computação quântica sobre a computação clássica, nossos olhos se voltam geralmente primeiro para vantagens exponenciais, ou pelo menos super-polinomiais — idealmente encontrando algoritmos quânticos de custo polinomial para problemas que não se sabe ter algoritmos clássicos de custo polinomial. Vantagens teóricas dessa ordem têm as maiores chances de levar a vantagens práticas reais — mas identificar tais vantagens é um desafio extremamente difícil. Apenas alguns exemplos são atualmente conhecidos, mas a busca continua.

Vantagens polinomiais (mas não super-polinomiais) no custo computacional de quântico sobre clássico também são interessantes e não devem ser descartadas — mas dado o atual fosso entre a tecnologia de computação quântica e clássica, elas parecem um tanto menos convincentes no momento presente. Um dia, porém, elas poderiam se tornar significativas. O algoritmo de Grover, por exemplo, que é abordado em uma lição posterior, oferece uma vantagem quadrática do quântico sobre o clássico para a chamada busca não estruturada, e tem potencial para amplas aplicações.

Um custo oculto da computação com circuitos

Há uma última questão que vale a pena mencionar, embora não nos preocupemos mais com ela neste curso. Existe um custo computacional "oculto" quando trabalhamos com circuitos, e ele diz respeito às especificações dos próprios circuitos. À medida que as entradas ficam cada vez mais longas, circuitos cada vez maiores são necessários — mas precisamos ter em mãos as descrições desses circuitos de alguma forma se vamos implementá-los.

Para todos os exemplos que discutimos, ou que discutiremos em lições subsequentes, existe um algoritmo subjacente do qual os circuitos são derivados. Geralmente os circuitos em uma família seguem algum padrão básico que é fácil de extrapolar para entradas cada vez maiores, como encadear somadores completos para criar circuitos booleanos para adição ou realizar camadas de portas Hadamard e outras portas em algum padrão de fácil descrição.

Mas o que acontece se houver custos computacionais proibitivos associados aos padrões nos próprios circuitos? Por exemplo, a descrição de cada membro $C_n$ em uma família de circuitos poderia, em princípio, ser determinada por alguma função de $n$ extremamente difícil de calcular.

A resposta é que isso é de fato um problema — e por isso devemos impor restrições adicionais às famílias de circuitos além de ter custo polinomial para que elas realmente representem algoritmos eficientes. A propriedade de uniformidade para circuitos faz isso estipulando que, em várias formulações precisas, deve ser computacionalmente fácil obter a descrição de cada circuito em uma família. Todas as famílias de circuitos que discutiremos têm essa propriedade — mas esta é, no entanto, uma questão importante a se ter em mente em geral ao estudar modelos de circuitos de computação de um ponto de vista formal.