O modelo de consulta de computação

Quando modelamos computações em termos matemáticos, geralmente temos em mente o tipo de processo representado pela figura a seguir, em que informações são fornecidas como entrada, uma computação ocorre e uma saída é produzida.

Embora seja verdade que os computadores que usamos hoje recebem entradas e produzem saídas continuamente, interagindo essencialmente tanto com nós quanto com outros computadores de uma forma não refletida pela figura, a intenção não é representar o funcionamento contínuo dos computadores. Pelo contrário, é criar uma abstração simples de computação, focando em tarefas computacionais isoladas. Por exemplo, a entrada pode codificar um número, um vetor, uma matriz, um grafo, a descrição de uma molécula, ou algo mais complexo, enquanto a saída codifica a solução para a tarefa computacional que temos em mente.

O ponto central é que a entrada é fornecida à computação, geralmente na forma de uma cadeia binária, sem que nenhuma parte dela seja ocultada.

Descrição do modelo

No modelo de consulta de computação, a entrada completa não é fornecida à computação como no modelo mais padrão sugerido acima. Pelo contrário, a entrada é disponibilizada na forma de uma função, que a computação acessa fazendo consultas. Alternativamente, podemos ver as computações no modelo de consulta como tendo acesso aleatório a bits (ou segmentos de bits) da entrada.

Frequentemente nos referimos à entrada como sendo fornecida por um oráculo ou caixa-preta no contexto do modelo de consulta. Ambos os termos sugerem que uma descrição completa da entrada está oculta da computação, sendo a única forma de acessá-la fazer perguntas. É como se estivéssemos consultando o Oráculo de Delfos sobre a entrada: ela não nos conta tudo que sabe, ela apenas responde perguntas específicas. O termo caixa-preta faz sentido especialmente quando pensamos na entrada como sendo representada por uma função; não podemos olhar dentro da função e entender como ela funciona, só podemos avaliá-la nos argumentos que escolhemos.

Vamos trabalhar exclusivamente com cadeias binárias nesta lição, em vez de cadeias contendo símbolos diferentes, então vamos escrever $\Sigma = \{0,1\}$ daqui em diante para nos referirmos ao alfabeto binário por conveniência. Vamos pensar sobre diferentes problemas computacionais, com alguns exemplos simples descritos em breve, mas para todos eles a entrada será representada por uma função da forma

$$f:\Sigma^n \rightarrow \Sigma^m$$

para dois inteiros positivos $n$ e $m.$ Naturalmente, poderíamos escolher um nome diferente no lugar de $f,$ mas vamos manter $f$ ao longo de toda a lição.

Dizer que uma computação faz uma consulta significa que alguma cadeia $x \in \Sigma^n$ é selecionada, e então a cadeia $f(x)\in\Sigma^m$ é disponibilizada para a computação pelo oráculo. A forma precisa como isso funciona para algoritmos quânticos será discutida em breve — precisamos garantir que isso seja possível de fazer com uma operação quântica unitária que permita que as consultas sejam feitas em superposição — mas por ora podemos pensar nisso de forma intuitiva em alto nível.

Por fim, a forma como mediremos a eficiência de algoritmos de consulta é simples: vamos contar o número de consultas que eles requerem. Isso está relacionado ao tempo necessário para realizar uma computação, mas não é exatamente o mesmo, pois estamos ignorando o tempo para operações além das consultas, e também estamos tratando as consultas como se cada uma tivesse custo unitário. Podemos levar em conta as operações além das consultas se quisermos (e isso é feito algumas vezes), mas restringir nossa atenção apenas ao número de consultas ajuda a manter as coisas simples.

Exemplos de problemas de consulta

Aqui estão alguns exemplos simples de problemas de consulta.

• OR. A função de entrada tem a forma $f:\Sigma^n \rightarrow \Sigma$ (portanto $m=1$ para este problema). A tarefa é produzir $1$ se existir uma cadeia $x\in\Sigma^n$ para a qual $f(x) = 1,$ e produzir $0$ se não existir tal cadeia. Se pensarmos na função $f$ como representando uma sequência de $2^n$ bits aos quais temos acesso aleatório, o problema é computar o OR desses bits.

• Paridade. A função de entrada novamente tem a forma $f:\Sigma^n \rightarrow \Sigma.$ A tarefa é determinar se o número de cadeias $x\in\Sigma^n$ para as quais $f(x) = 1$ é par ou ímpar. Para ser preciso, a saída requerida é $0$ se o conjunto $\{x\in\Sigma^n : f(x) = 1\}$ tem um número par de elementos e $1$ se tem um número ímpar de elementos. Se pensarmos na função $f$ como representando uma sequência de $2^n$ bits aos quais temos acesso aleatório, o problema é computar a paridade (ou OR exclusivo) desses bits.

• Mínimo. A função de entrada tem a forma $f:\Sigma^n \rightarrow \Sigma^m$ para quaisquer escolhas de inteiros positivos $n$ e $m.$ A saída requerida é a cadeia $y \in \{f(x) : x\in\Sigma^n\}$ que vem primeiro na ordem lexicográfica (isto é, de dicionário) de $\Sigma^m.$ Se pensarmos na função $f$ como representando uma sequência de $2^n$ inteiros codificados como cadeias de comprimento $m$ em notação binária aos quais temos acesso aleatório, o problema é computar o mínimo desses inteiros.

Também consideramos problemas de consulta onde temos uma promessa sobre a entrada. O que isso significa é que temos algum tipo de garantia sobre a entrada, e não somos responsáveis pelo que acontece quando essa garantia não é satisfeita. Outra forma de descrever este tipo de problema é dizer que algumas funções de entrada (aquelas para as quais a promessa não é satisfeita) são consideradas entradas "não importa". Nenhum requisito é imposto aos algoritmos quando recebem entradas "não importa".

Aqui está um exemplo de um problema com promessa:

• Busca única. A função de entrada tem a forma $f:\Sigma^n \rightarrow \Sigma,$ e é prometido que existe exatamente uma cadeia $z\in\Sigma^n$ para a qual $f(z) = 1,$ com $f(x) = 0$ para todas as cadeias $x\neq z.$ A tarefa é encontrar essa cadeia única $z.$

Todos os quatro exemplos recém-descritos são naturais, no sentido de que são fáceis de descrever e podemos imaginar uma variedade de situações ou contextos em que eles poderiam surgir.

Em contraste, alguns problemas de consulta não são "naturais" assim. De fato, no estudo do modelo de consulta, às vezes chegamos a problemas muito complexos e altamente artificiais onde é difícil imaginar que alguém realmente quereria resolvê-los na prática. Isso não significa que os problemas não sejam interessantes, porém! Coisas que podem parecer artificiais ou não naturais à primeira vista podem fornecer pistas inesperadas ou inspirar novas ideias. O algoritmo quântico de Shor para fatoração, que foi inspirado pelo algoritmo de Simon, é um ótimo exemplo. Também é uma parte importante do estudo do modelo de consulta buscar extremos, o que pode lançar luz tanto sobre as potenciais vantagens quanto sobre as limitações da computação quântica.

Portas de consulta

Quando descrevemos computações com circuitos, as consultas são feitas por portas especiais chamadas portas de consulta.

A forma mais simples de definir portas de consulta para circuitos Booleanos clássicos é simplesmente permitir que elas computem a função de entrada $f$ diretamente, como sugere a figura a seguir.

Quando um circuito Booleano é criado para um problema de consulta, a função de entrada $f$ é acessada por meio dessas portas, e o número de consultas que o circuito faz é simplesmente o número de portas de consulta que aparecem no circuito. Os fios de entrada do próprio circuito Booleano são inicializados com valores fixos, que devem ser considerados como parte do algoritmo (em oposição a serem entradas para o problema).

Por exemplo, aqui está um circuito Booleano com portas de consulta clássicas que resolve o problema de paridade descrito acima para uma função da forma $f:\Sigma\rightarrow\Sigma$:

Este algoritmo faz duas consultas porque há duas portas de consulta. A forma como funciona é que a função $f$ é consultada nos dois possíveis valores de entrada, $0$ e $1,$ e os resultados são inseridos em um circuito Booleano que computa o XOR. (Este circuito específico apareceu como exemplo de circuito Booleano na lição Circuitos quânticos do curso Fundamentos de informação quântica.)

Para circuitos quânticos, essa definição de portas de consulta não funciona, porque essas portas serão não-unitárias para algumas escolhas da função $f.$ Então, o que fazemos em vez disso é definir portas de consulta unitárias que operam como sugere esta figura sobre estados da base padrão:

Aqui, nossa suposição é que $x\in\Sigma^n$ e $y\in\Sigma^m$ são cadeias arbitrárias. A notação $y\oplus f(x)$ refere-se ao OR exclusivo bit a bit de duas cadeias, que têm comprimento $m$ neste caso. Por exemplo, $001 \oplus 101 = 100.$

De forma intuitiva, o que a porta $U_f$ faz (para qualquer função $f$ escolhida) é ecoar a cadeia de entrada superior $x$ e aplicar XOR do valor da função $f(x)$ sobre a cadeia de entrada inferior $y,$ o que é uma operação unitária para toda escolha da função $f.$ De fato, é uma operação determinística, e é sua própria inversa. Isso implica que, como matriz, $U_f$ é sempre uma matriz de permutação, ou seja, uma matriz com um único $1$ em cada linha e cada coluna, com todas as outras entradas sendo $0.$ Aplicar uma matriz de permutação a um vetor simplesmente embaralha as entradas do vetor (daí o termo matriz de permutação), e portanto não altera a norma euclidiana desse vetor — revelando que matrizes de permutação são sempre unitárias.

Vale destacar que, quando analisamos algoritmos de consulta simplesmente contando o número de consultas que um algoritmo de consulta faz, estamos completamente ignorando a dificuldade de construir fisicamente as portas de consulta — tanto para as versões clássicas quanto quânticas recém-descritas. De forma intuitiva, a construção das portas de consulta faz parte da preparação da entrada, não parte de encontrar uma solução.

Isso pode parecer irrazoável, mas devemos ter em mente que não estamos tentando descrever a computação prática nem contabilizar completamente os recursos necessários. Pelo contrário, estamos definindo um modelo teórico que ajuda a lançar luz sobre as potenciais vantagens da computação quântica. Teremos mais a dizer sobre este ponto na lição seguinte a esta, quando voltarmos nossa atenção para um modelo de computação mais padrão, onde as entradas são fornecidas explicitamente aos circuitos como cadeias binárias.