O algoritmo de Deutsch-Jozsa

O algoritmo de Deutsch supera todos os algoritmos clássicos para um problema de consulta, mas a vantagem é bastante modesta: uma consulta contra duas. O algoritmo Deutsch-Jozsa amplia essa vantagem e, de fato, pode ser usado para resolver alguns problemas de consulta diferentes.

Aqui está uma descrição do circuito quântico do algoritmo Deutsch-Jozsa. Uma etapa adicional clássica de pós-processamento, não mostrada na figura, também pode ser necessária, dependendo do problema específico que está sendo resolvido.

É claro que ainda não discutimos quais problemas esse algoritmo resolve; isso será feito nas duas seções a seguir.

O problema de Deutsch-Jozsa

Começaremos com o problema de consulta que o algoritmo Deutsch-Jozsa foi originalmente planejado para resolver, conhecido como o problema Deutsch-Jozsa.

A função de entrada para este problema tem a forma $f:\Sigma^n \rightarrow \Sigma$ , para um inteiro positivo arbitrário $n$ . Assim como no problema de Deutsch, a tarefa consiste em gerar a saída $0$ se $f$ for constante e $1$ se $f$ for equilibrado, o que, mais uma vez, significa que o número de cadeias de caracteres de entrada para as quais a função assume o valor $0$ é igual ao número de cadeias de caracteres de entrada para as quais a função assume o valor $1$ .

Observe que, quando $n$ é maior que $1$ , existem funções da forma $f:\Sigma^n \rightarrow \Sigma$ que não são nem constantes nem equilibradas. Por exemplo, a função $f:\Sigma^2\rightarrow\Sigma$ definida como

\begin{aligned} f(00) & = 0 \\ f(01) & = 0 \\ f(10) & = 0 \\ f(11) & = 1 \end{aligned}

não se enquadra em nenhuma dessas duas categorias. No caso do problema Deutsch-Jozsa, simplesmente não nos preocupamos com funções como essa - elas são consideradas entradas "indiferentes". Ou seja, para esse problema, temos a promessa de que $f$ é constante ou equilibrado.

Deutsch-Jozsa problem

Entrada: uma função $f:\{0,1\}^n\rightarrow\{0,1\}$ \ Promessa: $f$ é constante ou equilibrada \ Saída: $0$ se $f$ for constante, $1$ se $f$ for equilibrado

O algoritmo de Deutsch-Jozsa, com sua única consulta, resolve esse problema da seguinte maneira: se todos os resultados da medição $n$ forem $0$ , então a função $f$ é constante; e, caso contrário, se pelo menos um dos resultados da medição for $1$ , então a função $f$ é equilibrada. Outra forma de expressar isso é dizer que o circuito descrito acima é seguido por uma etapa clássica de pós-processamento, na qual se calcula a operação OR dos resultados das medições para produzir o bit de saída do problema de Deutsch-Jozsa.

Análise de algoritmos

Para analisar o desempenho do algoritmo Deutsch-Jozsa para o problema Deutsch-Jozsa, é útil começar pensando na ação de uma única camada de portas Hadamard. Uma operação Hadamard pode ser expressa como uma matriz da maneira usual,

H = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix},

mas também podemos expressar essa operação em termos de sua ação nos estados da base padrão:

\begin{aligned} H \vert 0\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} \vert 1 \rangle\\[3mm] H \vert 1\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle - \frac{1}{\sqrt{2}} \vert 1 \rangle. \end{aligned}

Essas duas equações podem ser combinadas em uma única fórmula,

H \vert a \rangle = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} (-1)^a \vert 1 \rangle = \frac{1}{\sqrt{2}} \sum_{b\in\{0,1\}} (-1)^{ab} \vert b\rangle,

o que é válido para ambas as opções de $a\in\Sigma$ .

Agora, suponha que, em vez de apenas um único qubit, tenhamos $n$ qubits e que uma operação Hadamard seja realizada em cada um deles. A operação combinada nos $n$ qubits é descrita pelo produto tensorial $H\otimes \cdots \otimes H$ ( $n$ vezes), que escrevemos como $H^{\otimes n}$ para fins de concisão e clareza. Usando a fórmula acima, seguida de expansão e simplificação, podemos expressar a ação dessa operação combinada nos estados da base padrão dos $n$ qubits da seguinte forma:

\begin{aligned} & H^{\otimes n} \vert x_{n-1} \cdots x_1 x_0 \rangle \\ & \qquad = \bigl(H \vert x_{n-1} \rangle \bigr) \otimes \cdots \otimes \bigl(H \vert x_{0} \rangle \bigr) \\ & \qquad = \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{n-1}\in\Sigma} (-1)^{x_{n-1} y_{n-1}} \vert y_{n-1} \rangle \Biggr) \otimes \cdots \otimes \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{0}\in\Sigma} (-1)^{x_{0} y_{0}} \vert y_{0} \rangle \Biggr) \\ & \qquad = \frac{1}{\sqrt{2^n}} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle. \end{aligned}

Aqui, aliás, estamos escrevendo cadeias binárias de comprimento $n$ como $x_{n-1}\cdots x_0$ e $y_{n-1}\cdots y_0$ , seguindo a convenção de indexação do Qiskit.

Essa fórmula nos fornece uma ferramenta útil para analisar o circuito quântico acima. Após a execução da primeira camada de portas Hadamard, o estado dos $n+1$ qubits (incluindo o qubit mais à esquerda/inferior, que é tratado separadamente do restante) é

\bigl( H \vert 1 \rangle \bigr) \bigl( H^{\otimes n} \vert 0 \cdots 0 \rangle \bigr) = \vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \vert x_{n-1} \cdots x_0 \rangle.

Quando a operação $U_f$ é realizada, esse estado é transformado em

\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \vert x_{n-1} \cdots x_0 \rangle

exatamente pelo mesmo fenômeno de retorno de fase que vimos na análise do algoritmo de Deutsch.

Em seguida, a segunda camada de portas Hadamard é executada, o que (pela fórmula acima) transforma esse estado em

\vert - \rangle \otimes \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0) + x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle.

Essa expressão parece um pouco complicada, e não é possível tirar muitas conclusões sobre as probabilidades de se obter diferentes resultados de medição sem saber mais sobre a função $f$ .

Felizmente, tudo o que precisamos saber é a probabilidade de que cada um dos resultados da medição seja $0$ - porque essa é a probabilidade de que o algoritmo determine que $f$ é constante. Essa probabilidade tem uma fórmula simples.

\Biggl\vert \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \Biggr\vert^2 = \begin{cases} 1 & \text{if $f$ is constant}\\[1mm] 0 & \text{if $f$ is balanced} \end{cases}

Observe que esses valores correspondem à probabilidade de se medir o estado $\vert 0^{\otimes n} \rangle$ , e não diretamente ao bit de saída clássico final do problema de Deutsch-Jozsa. O algoritmo gera o resultado “ $0$ ” quando todos os resultados das medições são “ $0$ ” (indicando que “ $f$ ” é constante) e, caso contrário, gera “ $1$ ” (indicando que “ $f$ ” está em equilíbrio).

Mais detalhadamente, se $f$ for constante, então ou $f(x_{n-1}\cdots x_0) = 0$ para toda string $x_{n-1}\cdots x_0$ , caso em que o valor da soma é $2^n$ , ou $f(x_{n-1}\cdots x_0) = 1$ para toda string $x_{n-1}\cdots x_0$ , caso em que o valor da soma é $-2^n$ . Dividindo por $2^n$ e elevando ao quadrado o valor absoluto, obtém-se $1$ .

Se, por outro lado, $f$ for equilibrada, então $f$ assume o valor $0$ em metade das sequências $x_{n-1}\cdots x_0$ e o valor $1$ na outra metade; assim, os termos $+1$ e $-1$ na soma se cancelam, e ficamos com o valor $0$ .

Concluímos que o algoritmo funciona corretamente desde que a promessa seja cumprida.

Dificuldade clássica

O algoritmo Deutsch-Jozsa funciona todas as vezes, sempre nos dando a resposta correta quando a promessa é cumprida, e requer uma única consulta. Como isso se compara aos algoritmos de consulta clássicos para o problema Deutsch-Jozsa?

Primeiro, qualquer algoritmo clássico determinístico que resolva corretamente o problema Deutsch-Jozsa deve fazer um número exponencial de consultas: $2^{n-1} + 1$ consultas são necessárias no pior dos casos. O raciocínio é que, se um algoritmo determinístico consultar $f$ em $2^{n-1}$ ou menos cadeias de caracteres diferentes e obtiver o mesmo valor de função todas as vezes, então ambas as respostas ainda serão possíveis. A função pode ser constante ou equilibrada, mas, por azar, todas as consultas retornam o mesmo valor de função.

A segunda possibilidade pode parecer improvável, mas para algoritmos determinísticos não há aleatoriedade ou incerteza, portanto, eles falharão sistematicamente em determinadas funções. Portanto, temos uma vantagem significativa dos algoritmos quânticos em relação aos clássicos nesse aspecto.

No entanto, há um problema: os algoritmos clássicos probabilísticos podem resolver o problema Deutsch-Jozsa com uma probabilidade muito alta usando apenas algumas consultas. Em particular, se simplesmente escolhermos algumas cadeias diferentes de comprimento $n$ aleatoriamente e consultarmos $f$ nessas cadeias, é improvável que obtenhamos o mesmo valor de função para todas elas quando $f$ estiver equilibrado.

Para ser mais específico, se escolhermos $k$ sequências de entrada $x^1,\ldots,x^k \in \Sigma^n$ de forma aleatória e uniforme, calcularmos $f(x^1),\ldots,f(x^k)$ e respondermos $0$ caso os valores da função sejam todos iguais, e $1$ caso contrário, estaremos sempre corretos quando $f$ for constante, e errados no caso em que $f$ for equilibrada com probabilidade de apenas $2^{-k + 1}$ . Se considerarmos $k = 11$ , por exemplo, esse algoritmo responderá corretamente com probabilidade superior a $99.9$ %.

Por esse motivo, ainda temos uma vantagem bastante modesta dos algoritmos quânticos em relação aos clássicos, mas, ainda assim, é uma vantagem quantificável que representa um aprimoramento em relação ao algoritmo de Deutsch.

Deutsch-Jozsa com Qiskit

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
import numpy as np

Para implementar o algoritmo Deutsch-Jozsa no Qiskit, começaremos definindo uma função dj_query que gera um circuito quântico implementando uma porta de consulta, para uma função selecionada aleatoriamente que satisfaça a promessa do problema Deutsch-Jozsa. Com 50% de chance, a função é constante, e com 50% de mudança, a função é equilibrada. Para cada uma dessas duas possibilidades, a função é selecionada uniformemente entre as funções desse tipo. O argumento é o número de bits de entrada da função.

def dj_query(num_qubits):
    # Create a circuit implementing for a query gate for a random function
    # satisfying the promise for the Deutsch-Jozsa problem.

    qc = QuantumCircuit(num_qubits + 1)

    if np.random.randint(0, 2):
        # Flip output qubit with 50% chance
        qc.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance
        return qc

    # Choose half the possible input strings
    on_states = np.random.choice(
        range(2**num_qubits),  # numbers to sample from
        2**num_qubits // 2,  # number of samples
        replace=False,  # makes sure states are only sampled once
    )

    def add_cx(qc, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc.x(qubit)
        return qc

    for state in on_states:
        qc.barrier()  # Barriers are added to help visualize how the functions are created.
        qc = add_cx(qc, f"{state:0b}")
        qc.mcx(list(range(num_qubits)), num_qubits)
        qc = add_cx(qc, f"{state:0b}")

    qc.barrier()

    return qc

Podemos mostrar a implementação do circuito quântico da porta de consulta usando o método draw como de costume.

display(dj_query(3).draw(output="mpl"))

Output:

Em seguida, definimos uma função que cria o circuito Deutsch-Jozsa, tendo como argumento uma implementação de circuito quântico de uma porta de consulta.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in the Deutsch-Jozsa algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)
    qc.h(range(n + 1))
    qc.compose(function, inplace=True)
    qc.h(range(n))
    qc.measure(range(n), range(n))
    return qc

Por fim, é definida uma função que executa o circuito Deutsch-Jozsa uma vez.

def dj_algorithm(function: QuantumCircuit):
    # Determine if a function is constant or balanced.

    qc = compile_circuit(function)

    result = AerSimulator().run(qc, shots=1, memory=True).result()
    measurements = result.get_memory()
    if "1" in measurements[0]:
        return "balanced"
    return "constant"

Podemos testar nossa implementação escolhendo uma função aleatoriamente, exibindo a implementação do circuito quântico de uma porta de consulta para essa função e, em seguida, executando o algoritmo Deutsch-Jozsa nessa função.

f = dj_query(3)
display(f.draw("mpl"))
display(dj_algorithm(f))

Output:

'balanced'

O problema de Bernstein-Vazirani

A seguir, discutiremos um problema conhecido como problema de Bernstein-Vazirani. Ele também é chamado de problema de amostragem de Fourier, embora existam formulações mais gerais desse problema que também têm esse nome.

Primeiro, vamos apresentar algumas notações. Para quaisquer duas cadeias binárias $x = x_{n-1} \cdots x_0$ e $y = y_{n-1}\cdots y_0$ de comprimento $n$ , definimos

x \cdot y = x_{n-1} y_{n-1} \oplus \cdots \oplus x_0 y_0.

Vamos nos referir a essa operação como o produto de ponto binário. Uma maneira alternativa de defini-lo é assim.

x \cdot y = \begin{cases} 1 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ is odd}\\[0.5mm] 0 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ is even} \end{cases}

Observe que essa é uma operação simétrica, o que significa que o resultado não muda se trocarmos $x$ e $y$ ; portanto, podemos fazer isso sempre que for conveniente. Às vezes, é útil pensar no produto escalar binário $x \cdot y$ como sendo a paridade dos bits de $x$ nas posições em que a sequência $y$ contém um $1$ , ou, de forma equivalente, a paridade dos bits de $y$ nas posições em que a sequência $x$ contém um $1$ .

Com essa notação em mãos, podemos agora definir o problema de Bernstein-Vazirani.

Bernstein-Vazirani problem

Entrada: uma função $f:\{0,1\}^n\rightarrow\{0,1\}$ \ Promessa: existe uma string binária $s = s_{n-1} \cdots s_0$ para a qual $f(x) = s\cdot x$ para todos os $x\in\Sigma^n$ \ Saída: a string $s$

Na verdade, não precisamos de um novo algoritmo quântico para esse problema; o algoritmo Deutsch-Jozsa o resolve. Para fins de clareza, vamos nos referir ao circuito quântico acima, que não inclui a etapa clássica de pós-processamento de computação do OU, como o circuito Deutsch-Jozsa.

Análise de algoritmos

Para analisar como o circuito Deutsch-Jozsa funciona para uma função que satisfaz a promessa do problema Bernstein-Vazirani, começaremos com uma observação rápida. Usando o produto de ponto binário, podemos, alternativamente, descrever a ação de $n$ Hadamard gates nos estados de base padrão de $n$ qubits da seguinte forma.

H^{\otimes n} \vert x \rangle = \frac{1}{\sqrt{2^n}} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert y\rangle

Semelhante ao que vimos ao analisar o algoritmo de Deutsch, isso ocorre porque o valor $(-1)^k$ para qualquer número inteiro $k$ depende apenas do fato de $k$ ser par ou ímpar.

Voltando ao circuito Deutsch-Jozsa, após a execução da primeira camada de portas Hadamard, o estado dos $n+1$ qubits é

\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} \vert x \rangle.

A porta de consulta é então executada, o que (por meio do fenômeno de retrocesso de fase) transforma o estado em

\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} (-1)^{f(x)} \vert x \rangle.

Usando nossa fórmula para a ação de uma camada de portas Hadamard, vemos que a segunda camada de portas Hadamard transforma esse estado em

\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{f(x) + x \cdot y} \vert y \rangle.

Agora podemos fazer algumas simplificações no expoente de $-1$ dentro da soma. Foi-nos prometido que $f(x) = s\cdot x$ para uma determinada sequência $s = s_{n-1} \cdots s_0$ , de modo que podemos expressar o estado como

\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{s\cdot x + x \cdot y} \vert y \rangle.

Como $s\cdot x$ e $x\cdot y$ são valores binários, podemos substituir a adição pelo exclusivo-OR - novamente porque a única coisa que importa para um número inteiro no expoente de $-1$ é se ele é par ou ímpar. Usando a simetria do produto de ponto binário, obtemos essa expressão para o estado:

\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\cdot x) \oplus (y \cdot x)} \vert y \rangle.

(Os parênteses foram adicionados para fins de clareza, embora não sejam realmente necessários, pois é convencional tratar o produto de ponto binário como tendo precedência mais alta do que o exclusivo-OR)

Neste ponto, usaremos a seguinte fórmula.

(s\cdot x) \oplus (y \cdot x) = (s \oplus y) \cdot x

Podemos obter a fórmula por meio de uma fórmula semelhante para bits,

(a c) \oplus (b c) = (a \oplus b) c,

juntamente com uma expansão do produto de ponto binário e do bitwise exclusive-OR:

\begin{aligned} (s\cdot x) \oplus (y \cdot x) & = (s_{n-1} x_{n-1}) \oplus \cdots \oplus (s_{0} x_{0}) \oplus (y_{n-1} x_{n-1}) \oplus \cdots \oplus (y_{0} x_{0}) \\ & = (s_{n-1} \oplus y_{n-1}) x_{n-1} \oplus \cdots \oplus (s_{0} \oplus y_{0}) x_{0} \\ & = (s \oplus y) \cdot x \end{aligned}

Isso nos permite expressar o estado do circuito imediatamente antes das medições da seguinte forma:

\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle.

O passo final é utilizar mais uma fórmula, que funciona para qualquer sequência binária $z = z_{n-1}\cdots z_0$ .

\frac{1}{2^n} \sum_{x \in \Sigma^n} (-1)^{z \cdot x} = \begin{cases} 1 & \text{if $z = 0^n$}\\ 0 & \text{if $z\neq 0^n$} \end{cases}

Aqui, estamos usando uma notação simples para cadeias de caracteres que utilizaremos várias outras vezes nesta aula: $0^n$ é a cadeia composta inteiramente por zeros, de comprimento $n$ .

Uma maneira simples de demonstrar que essa fórmula funciona é considerar os dois casos separadamente. Se $z = 0^n$ , então $z\cdot x = 0$ para toda string $x\in\Sigma^n$ ; portanto, o valor de cada termo da soma é $1$ , e obtemos $1$ somando e dividindo por $2^n$ . Por outro lado, se qualquer um dos bits de $z$ for igual a $1$ , então o produto escalar binário $z\cdot x$ é igual a $0$ para exatamente metade das opções possíveis de $x\in\Sigma^n$ e $1$ para a outra metade — porque o valor do produto escalar binário $z\cdot x$ inverte-se (de $0$ para $1$ ou de $1$ para $0$ ) se invertemos qualquer bit de $x$ em uma posição em que $z$ tenha um $1$ .

Se agora aplicarmos essa fórmula para simplificar o estado do circuito antes das medições, obteremos

\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle = \vert - \rangle \otimes \vert s \rangle,

devido ao fato de que $s\oplus y = 0^n$ se, e somente se, $y = s$ . Assim, as medições revelam precisamente a sequência $s$ que estamos procurando.

Dificuldade clássica

Enquanto o circuito Deutsch-Jozsa resolve o problema Bernstein-Vazirani com uma única consulta, qualquer algoritmo de consulta clássico precisa fazer pelo menos $n$ consultas para resolver esse problema.

Isso pode ser explicado por meio do chamado argumento da teoria da informação, que é muito simples nesse caso. Cada consulta clássica revela um único bit de informação sobre a solução, e há $n$ bits de informação que precisam ser descobertos - portanto, são necessárias pelo menos $n$ consultas.

De fato, é possível resolver o problema de Bernstein-Vazirani de forma clássica, consultando a função para cada uma das sequências $n$ que contenham um único $1$ , em cada posição possível, e $0$ para todos os demais bits, o que revela os bits de $s$ um por um. Portanto, a vantagem dos algoritmos quânticos em relação aos clássicos para esse problema é de uma consult $1$ , contra consultas $n$ .

Bernstein-Vazirani com Qiskit

Já implementamos o circuito de Deutsch-Jozsa acima e, aqui, vamos utilizá-lo para resolver o problema de Bernstein-Vazirani. Primeiro, definiremos uma função que implementa um portão de consulta para o problema de Bernstein-Vazirani, dada qualquer sequência binária $s$ .

def bv_query(s):
    # Create a quantum circuit implementing a query gate for the
    # Bernstein-Vazirani problem.

    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc


display(bv_query("1011").draw(output="mpl"))

Output:

Agora podemos criar uma função que executa o circuito Deutsch-Jozsa na função, usando a função compile_circuit que foi definida anteriormente.

def bv_algorithm(function: QuantumCircuit):
    qc = compile_circuit(function)
    result = AerSimulator().run(qc, shots=1, memory=True).result()
    return result.get_memory()[0]


display(bv_algorithm(bv_query("1011")))

Output:

'1011'

Observação sobre a nomenclatura

No contexto do problema Bernstein-Vazirani, é comum que o algoritmo Deutsch-Jozsa seja chamado de "algoritmo Bernstein-Vazirani" Isso é um pouco enganoso, pois o algoritmo é o algoritmo Deutsch-Jozsa, como Bernstein e Vazirani deixaram bem claro em seu trabalho.

O que Bernstein e Vazirani fizeram depois de mostrar que o algoritmo Deutsch-Jozsa resolve o problema de Bernstein-Vazirani (como foi dito acima) foi definir um problema muito mais complicado, conhecido como problema de amostragem recursiva de Fourier. Esse é um problema altamente planejado em que as soluções para diferentes instâncias do problema efetivamente desbloqueiam novos níveis do problema organizados em uma estrutura semelhante a uma árvore. O problema de Bernstein-Vazirani é essencialmente apenas o caso básico desse problema mais complicado.

O problema de amostragem recursiva de Fourier foi o primeiro exemplo conhecido de um problema de consulta em que os algoritmos quânticos têm a chamada vantagem superpolinomial sobre os algoritmos probabilísticos, superando assim a vantagem do quântico sobre o clássico oferecida pelo algoritmo Deutsch-Jozsa. Intuitivamente falando, a versão recursiva do problema amplia a vantagem $1$ versus $n$ dos algoritmos quânticos para algo muito maior.

O aspecto mais desafiador da análise matemática que estabelece essa vantagem é mostrar que os algoritmos de consulta clássicos não conseguem resolver o problema sem fazer muitas consultas. Isso é bastante comum; para muitos problemas, pode ser muito difícil descartar abordagens clássicas criativas que os resolvam de forma eficiente.

O problema de Simon e o algoritmo para ele descrito na próxima seção fornecem um exemplo muito mais simples de uma vantagem superpolinomial (e, na verdade, exponencial) do quantum em relação aos algoritmos clássicos e, por esse motivo, o problema de amostragem recursiva de Fourier é discutido com menos frequência. No entanto, esse é um problema computacional interessante por si só.

Esta página foi útil?

Relate um bug, erro de digitação ou solicite conteúdo no GitHub.