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 em vez de duas. O algoritmo de Deutsch-Jozsa amplia essa vantagem — e, de fato, pode ser usado para resolver alguns problemas de consulta diferentes.

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

Claro, ainda não discutimos quais problemas esse algoritmo resolve; isso é feito nas duas seções a seguir.

O problema de Deutsch-Jozsa

Vamos começar com o problema de consulta que o algoritmo de Deutsch-Jozsa foi originalmente criado para resolver, conhecido como o problema de Deutsch-Jozsa.

A função de entrada para esse problema tem a forma $f:\Sigma^n \rightarrow \Sigma$ para um inteiro positivo arbitrário $n.$ Assim como no problema de Deutsch, a tarefa é retornar $0$ se $f$ for constante e $1$ se $f$ for balanceada, o que novamente significa que o número de strings de entrada nas quais a função assume o valor $0$ é igual ao número de strings de entrada nas 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 balanceadas. 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. Para o problema de Deutsch-Jozsa, simplesmente não nos preocupamos com funções assim — elas são consideradas entradas "não importa". Ou seja, para esse problema temos uma promessa de que $f$ é constante ou balanceada.

Problema de Deutsch-Jozsa

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

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

Análise do algoritmo

Para analisar o desempenho do algoritmo de Deutsch-Jozsa para o problema de 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 forma 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 sobre os 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,$$

que vale para ambas as escolhas de $a\in\Sigma.$

Agora suponha que, em vez de apenas um único qubit, temos $n$ qubits, e uma operação Hadamard é executada em cada um. 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 concisão e clareza. Usando a fórmula acima e expandindo e simplificando, podemos expressar a ação dessa operação combinada sobre os estados da base padrão de $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 strings 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 dos demais) é

$$\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$ é executada, 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$$

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 concluir muito sobre as probabilidades de obter diferentes resultados de medição sem saber mais sobre a função $f.$

Felizmente, tudo o que precisamos saber é a probabilidade de que todos os resultados de medição sejam $0$ — pois essa é a probabilidade de o algoritmo determinar 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}$$

Em mais detalhes, 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 calculando o quadrado do valor absoluto, obtemos $1.$

Se, por outro lado, $f$ for balanceada, então $f$ assume o valor $0$ em metade das strings $x_{n-1}\cdots x_0$ e o valor $1$ na outra metade, de modo que os termos $+1$ e $-1$ na soma se cancelam e ficamos com o valor $0.$

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

Dificuldade clássica

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

Primeiro, qualquer algoritmo clássico determinístico que resolva corretamente o problema de Deutsch-Jozsa deve fazer um número exponencialmente grande de consultas: $2^{n-1} + 1$ consultas são necessárias no pior caso. O raciocínio é que, se um algoritmo determinístico consulta $f$ em $2^{n-1}$ ou menos strings diferentes, e obtém o mesmo valor da função em todos os casos, então ambas as respostas ainda são possíveis. A função pode ser constante, ou pode ser balanceada mas, por azar, todas as consultas retornam o mesmo valor.

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

Há, no entanto, uma ressalva: algoritmos clássicos probabilísticos conseguem resolver o problema de Deutsch-Jozsa com probabilidade muito alta usando apenas algumas consultas. Em particular, se simplesmente escolhermos algumas strings diferentes de comprimento $n$ aleatoriamente e consultarmos $f$ nessas strings, é improvável que obtenhamos o mesmo valor da função para todas elas quando $f$ for balanceada.

Para ser mais preciso, se escolhermos $k$ strings de entrada $x^1,\ldots,x^k \in \Sigma^n$ uniformemente ao acaso, avaliarmos $f(x^1),\ldots,f(x^k),$ e respondermos $0$ se os valores da função forem todos iguais, e $1$ caso contrário, estaremos sempre corretos quando $f$ for constante, e errados no caso em que $f$ é balanceada com probabilidade de apenas $2^{-k + 1}.$ Se tomarmos $k = 11,$ por exemplo, esse algoritmo responderá corretamente com probabilidade superior a $99,9$%.

Por essa razão, ainda temos uma vantagem bastante modesta dos algoritmos quânticos sobre os clássicos — mas é, mesmo assim, uma vantagem quantificável que representa uma melhoria em relação ao algoritmo de Deutsch.

Deutsch-Jozsa com Qiskit

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer

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

Para implementar o algoritmo de Deutsch-Jozsa no Qiskit, vamos começar definindo uma função dj_query que gera um circuito quântico implementando um porta de consulta, para uma função selecionada aleatoriamente que satisfaça a promessa do problema de Deutsch-Jozsa. Com 50% de chance, a função é constante, e com 50% de chance a função é balanceada. Para cada uma dessas duas possibilidades, a função é selecionada de forma uniforme dentre as funções daquele 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 visualizar a implementação em Circuit quântico do porta de consulta usando o método draw como de costume.

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

A seguir, definimos uma função que cria o circuito do Deutsch-Jozsa, recebendo como argumento um circuito quântico que implementa um 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, definimos uma função que executa o circuito do Deutsch-Jozsa uma única 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 em Circuit quântico do porta de consulta para essa função e, em seguida, executando o algoritmo de Deutsch-Jozsa sobre ela.

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

'balanced'

O problema de Bernstein-Vazirani

A seguir, vamos discutir um problema conhecido como o 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 recebem esse nome.

Primeiro, vamos introduzir uma notação. Para quaisquer duas strings 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 interno binário. Uma forma alternativa de defini-lo é a seguinte.

$$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, ou seja, o resultado não muda se trocarmos $x$ e $y,$ o que nos dá liberdade para fazer isso sempre que for conveniente. Às vezes é útil pensar no produto interno binário $x \cdot y$ como a paridade dos bits de $x$ nas posições em que a string $y$ tem um $1,$ ou equivalentemente, a paridade dos bits de $y$ nas posições em que a string $x$ tem 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 todo $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 de Deutsch-Jozsa já o resolve. Para maior clareza, vamos nos referir ao Circuit quântico descrito acima — que não inclui a etapa de pós-processamento clássico de calcular o OR — como o Circuit de Deutsch-Jozsa.

Análise do algoritmo

Para analisar como o circuito de Deutsch-Jozsa funciona para uma função que satisfaz a promessa do problema de Bernstein-Vazirani, vamos começar com uma observação rápida. Usando o produto interno binário, podemos descrever de forma alternativa a ação de $n$ Gates Hadamard sobre os estados da base computacional de $n$ qubits da seguinte maneira.

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

Assim como vimos na análise do algoritmo de Deutsch, isso se deve ao fato de que o valor $(-1)^k$ para qualquer inteiro $k$ depende apenas de $k$ ser par ou ímpar.

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

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

O porta de consulta é então aplicado, o que (por meio do fenômeno de phase kickback) 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 Gates Hadamard, vemos que a segunda camada de Gates 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. Nos é prometido que $f(x) = s\cdot x$ para alguma string $s = s_{n-1} \cdots s_0,$ então 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 ou-exclusivo — novamente porque o que importa para um inteiro no expoente de $-1$ é apenas se ele é par ou ímpar. Fazendo uso da simetria do produto interno binário, obtemos a seguinte 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 maior clareza, embora não sejam estritamente necessários, pois é convencional tratar o produto interno binário como tendo precedência maior do que o ou-exclusivo.)

Neste ponto, faremos uso da seguinte fórmula.

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

Podemos obter essa fórmula a partir de uma fórmula análoga para bits,

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

junto com uma expansão do produto interno binário e do ou-exclusivo bit a bit:

$$\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 é usar mais uma fórmula, que vale para toda string 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 strings que usaremos mais algumas vezes nesta lição: $0^n$ é a string de comprimento $n$ composta inteiramente de zeros.

Uma maneira simples de verificar 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,$ logo o valor de cada termo da soma é $1,$ e obtemos $1$ ao somar e dividir por $2^n.$ Por outro lado, se algum dos bits de $z$ for igual a $1,$ então o produto interno binário $z\cdot x$ é igual a $0$ para exatamente metade das possíveis escolhas de $x\in\Sigma^n$ e igual a $1$ para a outra metade — pois o valor do produto interno binário $z\cdot x$ se inverte (de $0$ para $1$ ou de $1$ para $0$) quando invertemos qualquer bit de $x$ em uma posição onde $z$ tem um $1.$

Ao aplicar essa fórmula para simplificar o estado do circuito antes das medições, obtemos

$$\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,$$

pois $s\oplus y = 0^n$ se e somente se $y = s.$ Assim, as medições revelam exatamente a string $s$ que estávamos procurando.

Dificuldade clássica

Enquanto o circuito de Deutsch-Jozsa resolve o problema de 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 demonstrado por meio de um argumento chamado de teórico da informação, que é bastante simples neste 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 classicamente consultando a função em cada uma das $n$ strings que possuem um único $1,$ em cada posição possível, e $0$ em todos os outros bits, o que revela os bits de $s$ um por vez. Portanto, a vantagem do algoritmo quântico sobre o clássico para este problema é de $1$ consulta contra $n$ consultas.

Bernstein-Vazirani com Qiskit

Já implementamos o circuito de Deutsch-Jozsa acima, e aqui vamos usá-lo para resolver o problema de Bernstein-Vazirani. Primeiro, vamos definir uma função que implementa um gate de consulta para o problema de Bernstein-Vazirani a partir de qualquer string 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"))

Agora podemos criar uma função que executa o circuito de Deutsch-Jozsa sobre a função, usando a função compile_circuit 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")))

'1011'

Observação sobre nomenclatura

No contexto do problema de Bernstein-Vazirani, é comum que o algoritmo de Deutsch-Jozsa seja chamado de "algoritmo de Bernstein-Vazirani". Isso é um pouco enganoso, pois o algoritmo é o algoritmo de Deutsch-Jozsa — e os próprios Bernstein e Vazirani foram bem claros sobre isso em seu trabalho.

O que Bernstein e Vazirani fizeram, após demonstrar que o algoritmo de Deutsch-Jozsa resolve o problema de Bernstein-Vazirani (como enunciado acima), foi definir um problema muito mais complexo, conhecido como o problema de amostragem de Fourier recursiva. Trata-se de um problema bastante artificial, em que as soluções para diferentes instâncias do problema desbloqueiam efetivamente novos níveis, organizados em uma estrutura de árvore. O problema de Bernstein-Vazirani é, essencialmente, apenas o caso base desse problema mais complexo.

O problema de amostragem de Fourier recursiva foi o primeiro exemplo conhecido de um problema de consulta em que algoritmos quânticos possuem uma vantagem dita super-polinomial sobre algoritmos probabilísticos, superando assim a vantagem quântica sobre a clássica oferecida pelo algoritmo de Deutsch-Jozsa. De forma intuitiva, a versão recursiva do problema amplifica a vantagem de $1$ versus $n$ dos algoritmos quânticos para algo muito maior.

O aspecto mais desafiador da análise matemática que estabelece essa vantagem é demonstrar que algoritmos clássicos de consulta não conseguem resolver o problema sem fazer muitas consultas. Isso é bastante típico: 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, fornece um exemplo bem mais simples de uma vantagem super-polinomial (e, na verdade, exponencial) dos algoritmos quânticos sobre os clássicos — e, por essa razão, o problema de amostragem de Fourier recursiva é menos frequentemente discutido. Ainda assim, é um problema computacional interessante por mérito próprio.