Algoritmo de Grover

Para este módulo do Qiskit em Sala de Aula, os estudantes precisam ter um ambiente Python funcional com os seguintes pacotes instalados:

• qiskit v2.1.0 ou mais recente
• qiskit-ibm-runtime v0.40.1 ou mais recente
• qiskit-aer v0.17.0 ou mais recente
• qiskit.visualization
• numpy
• pylatexenc

Para configurar e instalar os pacotes acima, consulte o guia Instalar o Qiskit. Para executar jobs em computadores quânticos reais, os estudantes precisam criar uma conta no IBM Quantum®, seguindo as etapas do guia Configure sua conta IBM Cloud.

Este módulo foi testado e utilizou 12 segundos de tempo de QPU. Esta é uma estimativa de boa fé; seu uso real pode variar.

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

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Introdução

O algoritmo de Grover é um algoritmo quântico fundamental que aborda o problema de busca não estruturada: dada uma coleção de $N$ elementos e uma forma de verificar se um determinado elemento é aquele que você está procurando, quão rapidamente você pode encontrar o elemento desejado? Na computação clássica, quando os dados não estão ordenados e não há estrutura que possa ser explorada, a melhor abordagem é verificar cada elemento individualmente, resultando em uma complexidade de consulta de $O(N)$ — em média, você precisará verificar cerca de metade dos elementos antes de encontrar o alvo.

O algoritmo de Grover, introduzido por Lov Grover em 1996, demonstra como um computador quântico pode resolver esse problema de forma muito mais eficiente, precisando de apenas $O(\sqrt{N})$ etapas para encontrar o elemento marcado com alta probabilidade. Isso representa uma aceleração quadrática em relação aos métodos clássicos, o que é significativo para grandes conjuntos de dados.

O algoritmo opera no seguinte contexto:

• Enunciado do problema: Você tem uma função $f(x)$ que retorna 1 quando $x$ é o elemento desejado, e 0 caso contrário. Essa função é frequentemente chamada de oráculo ou caixa preta, pois você só pode aprender sobre os dados consultando $f(x)$.
• Aproveitando a quântica: Enquanto algoritmos clássicos para esse problema exigem em média $N/2$ consultas, o algoritmo de Grover pode encontrar a solução em aproximadamente $\pi\sqrt{N}/4$ consultas, o que é muito mais rápido para grandes $N$.
• Como funciona (em alto nível):
  • O computador quântico primeiro cria uma superposição de todos os estados possíveis, representando todos os elementos possíveis simultaneamente.
  • Em seguida, aplica repetidamente uma sequência de operações quânticas (a iteração de Grover) que amplifica a probabilidade da resposta correta e diminui as demais.
  • Após iterações suficientes, medir o estado quântico fornece a resposta correta com alta probabilidade.

Aqui está um diagrama muito simples do algoritmo de Grover, que omite muitas nuances. Para um diagrama mais detalhado, consulte este artigo.

Algumas coisas a observar sobre o algoritmo de Grover:

• Ele é ótimo para busca não estruturada: nenhum algoritmo quântico pode resolver o problema com menos de $O(\sqrt{N})$ consultas.
• Ele oferece apenas uma aceleração quadrática, não exponencial — ao contrário de alguns outros algoritmos quânticos (por exemplo, o algoritmo de Shor para fatoração).
• Ele tem implicações práticas, como a potencial aceleração de ataques de força bruta a sistemas criptográficos, embora a aceleração não seja suficiente para quebrar a maioria das criptografias modernas por si só.

Para estudantes de graduação familiarizados com conceitos básicos de computação e modelos de consulta, o algoritmo de Grover oferece uma ilustração clara de como a computação quântica pode superar abordagens clássicas para certos problemas, mesmo que a melhoria seja "apenas" quadrática. Ele também serve como porta de entrada para compreender algoritmos quânticos mais avançados e o potencial mais amplo da computação quântica.

A amplificação de amplitude é um algoritmo ou sub-rotina quântica de propósito geral que pode ser usada para obter uma aceleração quadrática em relação a um conjunto de algoritmos clássicos. O algoritmo de Grover foi o primeiro a demonstrar essa aceleração em problemas de busca não estruturada. Formular um problema de busca de Grover requer uma função oráculo que marca um ou mais estados de base computacional como os estados que nos interessam encontrar, e um circuito de amplificação que aumenta a amplitude dos estados marcados e, consequentemente, suprime os estados restantes.

Aqui demonstramos como construir oráculos de Grover e usar o GroverOperator da biblioteca de circuitos do Qiskit para configurar facilmente uma instância de busca de Grover. O primitivo Sampler do Runtime permite a execução contínua de circuitos de Grover.

Matemática

Suponha que exista uma função $f$ que mapeia strings binárias para uma única variável binária, ou seja,

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

Um exemplo, definido em $\Sigma^6$, é

$$f(x)= \begin{cases} 1 \qquad \text{se }x=\{010101\}\\ 0 \qquad \text{caso contrário } \end{cases}$$

Outro exemplo, definido em $\Sigma^{2n}$, é

$$f(x)= \begin{cases} 1 \qquad \text{se há igual quantidade de 1s e 0s na string}\\ 0 \qquad \text{caso contrário } \end{cases}$$

Você é incumbido de encontrar estados quânticos que correspondam aos argumentos $x$ de $f(x)$ que são mapeados para 1. Em outras palavras, encontre todos os $\{x_1\}\in \Sigma^n$ tais que $f(x_1)=1$ (ou, se não houver solução, informe isso). Chamaremos os não-soluções de $x_0$. Claro, faremos isso em um computador quântico, usando estados quânticos, então é útil expressar essas strings binárias como estados:

$$\{|x_1\rangle\} \in |\Sigma^n\rangle$$

Usando a notação de estados quânticos (notação de Dirac), buscamos um ou mais estados especiais $\{|x_1\rangle\}$ em um conjunto de $N=2^n$ estados possíveis, onde $n$ é o número de qubits, e com os não-soluções denominados $\{|x_0\rangle\}.$

Podemos imaginar a função $f$ como fornecida por um oráculo: uma caixa preta que podemos consultar para determinar seu efeito sobre um estado $|x\rangle$. Na prática, frequentemente conheceremos a função, mas ela pode ser muito complexa de implementar, o que significa que reduzir o número de consultas ou aplicações de $f$ pode ser importante. Alternativamente, podemos imaginar um paradigma em que uma pessoa consulta um oráculo controlado por outra pessoa, de modo que não conhecemos a função oráculo, mas apenas seu efeito sobre certos estados por meio de consultas.

Este é um "problema de busca não estruturada", na medida em que não há nada de especial em $f$ que nos ajude em nossa busca. As saídas não estão ordenadas, as soluções não são conhecidamente agrupadas, e assim por diante. Como analogia, considere antigas listas telefônicas em papel. Essa busca não estruturada seria como procurar um determinado número, e não como pesquisar em uma lista de nomes em ordem alfabética.

No caso em que uma única solução é procurada, isso requer classicamente um número de consultas linear em $N$. Claro, você poderia encontrar uma solução na primeira tentativa, ou poderia não encontrar nenhuma solução nas primeiras $N-1$ tentativas, de modo que precisaria consultar a $N$-ésima entrada para ver se há alguma solução. Como as funções não têm estrutura explorável, você precisa de $N/2$ tentativas em média. O algoritmo de Grover requer um número de consultas ou computações de $f$ que escala como $\sqrt{N}$.

Esboço dos circuitos no algoritmo de Grover

Um tratamento matemático completo do algoritmo de Grover pode ser encontrado, por exemplo, em Fundamentals of quantum algorithms, um curso de John Watrous no IBM Quantum Learning. Um tratamento condensado está incluído em um apêndice ao final deste módulo. Mas por ora, apenas revisaremos a estrutura geral do circuito quântico que implementa o algoritmo de Grover.

O algoritmo de Grover pode ser dividido nas seguintes etapas:

• Preparação de uma superposição inicial (aplicação de portas Hadamard em todos os qubits)
• "Marcação" do estado alvo (dos estados alvo) com uma inversão de fase
• Uma etapa de "difusão", em que portas Hadamard e uma inversão de fase são aplicadas a todos os qubits.
• Possíveis repetições das etapas de marcação e difusão para maximizar a probabilidade de medir o estado alvo
• Medição

Frequentemente, a porta de marcação $Z_f$ e as camadas de difusão compostas por $H,$ $Z_{\text{OR}},$ e $H$ são chamadas coletivamente de "operador de Grover". Neste diagrama, apenas uma única repetição do operador de Grover é mostrada.

As portas Hadamard $H$ são bem conhecidas e amplamente utilizadas na computação quântica. A porta Hadamard cria estados de superposição. Concretamente, ela é definida por

$$H|0\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)\\ H|1\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)$$

Sua operação sobre qualquer outro estado é definida por linearidade. Em particular, uma camada de portas Hadamard nos permite ir do estado inicial com todos os qubits em $|0\rangle$ (denotado $|0\rangle^{\otimes n}$) para um estado em que cada qubit tem alguma probabilidade de ser medido em $|0\rangle$ ou $|1\rangle$; isso nos permite explorar o espaço de todos os estados possíveis de forma diferente da computação clássica.

Uma propriedade importante decorrente da porta Hadamard é que uma segunda aplicação pode desfazer tais estados de superposição:

$$H\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)=|0\rangle\\ H\frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)=|1\rangle$$

Isso será importante em breve.

Verifique sua compreensão

Leia a pergunta abaixo, pense em sua resposta e clique no triângulo para revelar a solução.

Partindo da definição da porta Hadamard, demonstre que uma segunda aplicação da porta Hadamard desfaz tais superposições conforme afirmado acima.

Resposta:

Se aplicarmos X ao estado $|+\rangle$, obtemos o valor +1 e ao estado $|-\rangle$ obtemos -1, então se tivéssemos uma distribuição 50-50, obteríamos um valor esperado de 0.

A porta $Z_\text{OR}$ é menos comum e é definida por

$$\text{Z}_\text{OR}|x\rangle = \begin{cases} |x\rangle & \text{se } x = 0^n \\ -|x\rangle & \text{se } x \neq 0^n \end{cases} \qquad \forall x \in \Sigma^n$$

Por fim, a porta $Z_f$ é definida por

$$Z_f:|x\rangle \rightarrow (-1)^{f(x)}|x\rangle \qquad \forall x \in \Sigma^n$$

Note que o efeito disso é que $Z_f$ inverte o sinal em um estado alvo para o qual $f(x) = 1$, deixando outros estados inalterados.

Em um nível muito alto e abstrato, você pode pensar nas etapas do circuito da seguinte maneira:

• Primeira camada Hadamard: coloca os qubits em uma superposição de todos os estados possíveis.
• $Z_f$: marca o estado alvo (os estados alvo) colocando um sinal "-" à frente dele. Isso não altera imediatamente as probabilidades de medição, mas altera como o estado alvo se comportará nas etapas subsequentes.
• Outra camada Hadamard: o sinal "-" introduzido na etapa anterior mudará o sinal relativo entre alguns termos. Como as portas Hadamard convertem uma mistura de estados computacionais $(|0\rangle+|1\rangle)/\sqrt{2}$ em um estado computacional, $|0\rangle,$ e convertem $(|0\rangle-|1\rangle)/\sqrt{2}$ em $|1\rangle$, essa diferença de sinal relativo pode começar a desempenhar um papel em quais estados são medidos.
• Uma última camada de portas Hadamard é aplicada e, em seguida, as medições são realizadas. Veremos com mais detalhes como isso funciona na próxima seção.

Exemplo

Para entender melhor como o algoritmo de Grover funciona, vamos trabalhar um pequeno exemplo com dois qubits. Isso pode ser considerado opcional para aqueles que não estão focados em mecânica quântica e notação de Dirac. Mas para aqueles que esperam trabalhar substancialmente com computadores quânticos, isso é altamente recomendado.

Aqui está o diagrama do circuito com os estados quânticos rotulados em várias posições. Note que com apenas dois qubits, há apenas quatro estados possíveis que poderiam ser medidos em qualquer circunstância: $|00\rangle$, $|01\rangle$, $|10\rangle$ e $|11\rangle$.

Suponha que o oráculo ($Z_f$, desconhecido para nós) marque o estado $|01\rangle$. Vamos trabalhar as ações de cada conjunto de portas quânticas, incluindo o oráculo, e ver qual distribuição de estados possíveis surge no momento da medição. No início, temos

$$|\psi_0\rangle = |00\rangle$$

Usando a definição das portas Hadamard, temos

$$|\psi_1\rangle = \frac{1}{2}\left(|0\rangle+|1\rangle\right)\left(|0\rangle+|1\rangle\right)=\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)$$

Agora o oráculo marca o estado alvo:

$$|\psi_2\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle+|11\rangle\right)$$

Note que nesse estado, todos os quatro resultados possíveis têm a mesma probabilidade de serem medidos. Todos têm um peso de magnitude $1/2,$ o que significa que cada um tem uma chance $|1/2|^2=1/4$ de ser medido. Portanto, embora o estado $|01\rangle$ esteja marcado pela fase "-", isso ainda não resultou em uma probabilidade aumentada de medir esse estado. Continuamos aplicando a próxima camada de portas Hadamard.

$$\begin{aligned} |\psi_3\rangle = &\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Combinando termos semelhantes, encontramos

$$|\psi_3\rangle = \frac{1}{2}\left(|00\rangle+|01\rangle-|10\rangle+|11\rangle\right)$$

Agora $Z_{\text{OR}}$ inverte o sinal em todos os estados exceto $|00\rangle$:

$$|\psi_4\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)$$

E finalmente aplicamos a última camada de portas Hadamard:

$$\begin{aligned} |\psi_5\rangle =&\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Vale a pena trabalhar a combinação desses termos para se convencer de que o resultado é de fato:

$$|\psi_5\rangle =|01\rangle$$

Ou seja, a probabilidade de medir $|01\rangle$ é 100% (na ausência de ruído e erros) e a probabilidade de medir qualquer outro estado é zero.

Este exemplo com dois qubits foi um caso particularmente limpo; o algoritmo de Grover nem sempre funcionará de forma a produzir 100% de chance de medir o estado alvo. Em vez disso, ele amplificará a probabilidade de medir o estado alvo. Além disso, o operador de Grover pode precisar ser repetido mais de uma vez.

Na próxima seção, colocaremos esse algoritmo em prática usando computadores quânticos reais da IBM®.

Ressalva óbvia

Para aplicar o algoritmo de Grover, precisamos construir o operador de Grover, o que significa que precisamos ser capazes de inverter a fase nos estados que satisfazem nossos critérios de solução. Isso levanta a questão: se conhecemos nosso conjunto de soluções tão bem que podemos projetar um circuito quântico para rotular cada uma, o que estamos procurando?! A resposta é tríplice, e revisitaremos isso ao longo do tutorial:

(1) Esses tipos de algoritmos de consulta frequentemente envolvem duas partes: uma que possui o oráculo que define os critérios de solução, e outra que tenta adivinhar/encontrar um estado de solução. O fato de que uma pessoa pode construir o oráculo não nega a necessidade da busca.

(2) Existem problemas para os quais é mais fácil especificar um critério de solução do que encontrar a solução. O exemplo mais conhecido provavelmente é a identificação de fatores primos de números grandes. O algoritmo de Grover não é particularmente eficaz para resolver esse problema específico; usaríamos o algoritmo de Shor para fatoração de primos. Este é apenas um exemplo para apontar que conhecer o critério para o comportamento de um estado nem sempre é o mesmo que conhecer o estado.

(3) O algoritmo de Grover não retorna apenas dados clássicos. Se fizermos uma medição do estado final após $t$ repetições do operador de Grover, provavelmente obteremos informações clássicas que identificam o estado de solução. Mas e se não quisermos informações clássicas; e se quisermos um estado de solução preparado em um computador quântico para uso posterior em outro algoritmo? O algoritmo de Grover de fato produz um estado quântico com soluções fortemente ponderadas. Portanto, você pode esperar encontrar o algoritmo de Grover como uma sub-rotina em algoritmos quânticos mais complexos.

Com isso em mente, trabalharemos vários exemplos. Começamos com um exemplo em que o estado de solução é claramente especificado, para que possamos acompanhar a lógica do algoritmo, e avançaremos para exemplos em que a utilidade do algoritmo de Grover se torna mais evidente.

Importações gerais e abordagem

Começamos importando vários pacotes necessários.

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

Neste e em outros tutoriais, usaremos um framework de computação quântica conhecido como "padrões Qiskit", que divide os fluxos de trabalho nas seguintes etapas:

• Etapa 1: Mapear entradas clássicas para um problema quântico
• Etapa 2: Otimizar o problema para execução quântica
• Etapa 3: Executar com os Primitivos do Qiskit Runtime
• Etapa 4: Pós-processamento e análise clássica

Seguiremos essas etapas em geral, embora nem sempre as rotulemos explicitamente.

Atividade 1: Encontrar um único estado alvo dado

Etapa 1: Mapear entradas clássicas para um problema quântico

Precisamos da porta de consulta de fase para aplicar uma fase global (-1) nos estados de solução e deixar os estados não-solução inalterados. Outra forma de dizer isso é que o algoritmo de Grover requer um oráculo que especifica um ou mais estados de base computacional marcados, onde "marcado" significa um estado com fase -1. Isso é feito usando uma porta Z controlada ou sua generalização com múltiplos controles sobre $N$ qubits. Para ver como isso funciona, considere um exemplo específico de uma string de bits {110}. Queremos um circuito que atue sobre um estado $|\psi\rangle = |q_2,q_1,q_0\rangle$ e aplique uma fase quando $|\psi\rangle = |011\rangle$ (onde invertemos a ordem da string binária, devido à notação do Qiskit, que coloca o qubit menos significativo (frequentemente 0) à direita).

Assim, queremos um circuito $Z_f$ que realize

$$Z_f|\psi\rangle = \begin{cases} -|\psi\rangle \qquad \text{se} \qquad |\psi\rangle = |011\rangle \\ |\psi\rangle \qquad \text{se} \qquad |\psi\rangle \neq |011\rangle\end{cases}$$

Podemos usar a porta Multiple Control Multiple Target (MCMTGate) para aplicar uma porta Z controlada por todos os qubits (inverter a fase quando todos os qubits estão no estado $|1\rangle$). Claro, alguns dos qubits no nosso estado desejado podem estar em $|0\rangle$. Portanto, para esses qubits, precisamos primeiro aplicar uma porta X, depois executar a porta Z com múltiplos controles, e então aplicar outra porta X para desfazer nossa mudança. O MCMTGate tem esta aparência:

mcmt_ex = QuantumCircuit(3)
mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)
mcmt_ex.draw(output="mpl", style="iqp")

Note que muitos qubits podem estar envolvidos no processo de controle (aqui são três qubits), mas nenhum qubit individual é designado como alvo. Isso ocorre porque o estado inteiro recebe um sinal global "-" (inversão de fase); a porta atua equivalentemente em todos os qubits. Isso difere de muitas outras portas de múltiplos qubits, como a porta CX, que tem um único qubit de controle e um único qubit alvo.

No código a seguir, definimos uma porta de consulta de fase (ou oráculo) que faz exatamente o que descrevemos acima: marca um ou mais estados de base de entrada definidos por sua representação em string de bits. A porta MCMT é usada para implementar a porta Z com múltiplos controles.

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bitstring to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bitstring
        zero_inds = [
            ind for ind in range(num_qubits) if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bitstring has a '0' entry
        qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        qc.x(zero_inds)
    return qc

Agora escolhemos um estado "marcado" específico como nosso alvo e aplicamos a função que acabamos de definir. Vamos ver que tipo de circuito ela criou.

marked_states = ["1110"]
oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Quando os qubits 1 a 3 estão no estado $|1\rangle$ e o qubit 0 está inicialmente no estado $|0\rangle$, a primeira porta X inverte o qubit 0 para $|1\rangle$ e todos os qubits estarão em $|1\rangle$. Isso significa que a porta MCMT aplicará uma mudança de sinal global ou inversão de fase, conforme desejado. Para qualquer outro caso, os qubits 1 a 3 estão no estado $|0\rangle$, ou o qubit 0 é invertido para o estado $|0\rangle$, e a inversão de fase não é aplicada. Vemos que esse circuito de fato marca nosso estado desejado $|0111\rangle,$ ou a string de bits {1110}. O operador de Grover completo consiste na porta de consulta de fase (oráculo), camadas Hadamard e o operador $Z_\text{OR}$. Podemos usar o grover_operator integrado para construí-lo a partir do oráculo definido acima.

grover_op = grover_operator(oracle)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

Como argumentamos acima, pode ser necessário aplicar o operador de Grover várias vezes. O número ótimo de iterações, $t,$ para maximizar a amplitude do estado alvo na ausência de ruído pode ser obtido a partir desta expressão:

$$(2t+1)\theta = (2t+1)\sin^{-1}\left( \sqrt{\frac{|A_1|}{N}}\right) \approx (2t+1)\sqrt{\frac{|A_1|}{N}} \approx \frac{\pi}{2}\\ t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

Aqui $A_1$ é o número de soluções ou estados alvo. Em computadores quânticos ruidosos modernos, o número experimentalmente ótimo de iterações pode ser diferente — mas aqui calculamos e usamos esse número teórico ótimo usando $A_1=1$.

optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)
print(optimal_num_iterations)

3

Agora vamos construir um circuito que inclua as portas Hadamard iniciais para criar uma superposição de todos os estados possíveis e aplicar o operador de Grover o número ótimo de vezes.

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

Construímos nosso circuito de Grover!

Etapa 2: Otimizar o problema para execução em hardware quântico

Definimos nosso circuito quântico abstrato, mas precisamos reescrevê-lo em termos de portas nativas do computador quântico que pretendemos usar. Também precisamos especificar quais qubits do computador quântico serão utilizados. Por essas e outras razões, agora precisamos transpilar nosso circuito. Primeiro, vamos especificar o computador quântico que queremos usar.

Abaixo está o código para salvar suas credenciais no primeiro uso. Certifique-se de remover essas informações do notebook após salvá-las no seu ambiente, para que suas credenciais não sejam acidentalmente compartilhadas ao compartilhar o notebook. Consulte Configure sua conta IBM Cloud e Inicialize o serviço em um ambiente não confiável para mais orientações.

# To run on hardware, select the backend with the fewest number of jobs in the queue
from qiskit_ibm_runtime import QiskitRuntimeService

# Syntax for first saving your token.  Delete these lines after saving your credentials.
# QiskitRuntimeService.save_account(channel='ibm_quantum_platform', instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

backend = service.least_busy(operational=True, simulator=False)
backend.name

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.

'ibm_brisbane'

Agora usamos um gerenciador de passagens predefinido para otimizar nosso circuito quântico para o backend selecionado.

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

circuit_isa = pm.run(qc)
# The transpiled circuit will be very large. Only draw it if you are really curious.
# circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Vale destacar neste ponto que a profundidade do circuito quântico transpilado é considerável.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  439
The depth of two-qubit gates is  113

Esses são números bastante grandes, mesmo para este caso simples. Como todas as portas quânticas (e especialmente as portas de dois qubits) sofrem erros e estão sujeitas a ruído, uma série de mais de 100 portas de dois qubits produziria apenas ruído, a menos que os qubits fossem extremamente eficientes. Vamos ver como funcionam.

Executar com os Primitivos do Qiskit

Queremos realizar muitas medições e ver qual estado é mais provável. Tal amplificação de amplitude é um problema de amostragem adequado para execução com o primitivo Sampler do Qiskit Runtime.

Note que o método run() do SamplerV2 do Qiskit Runtime aceita um iterável de Primitive Unified Blocks (PUBs). Para o Sampler, cada PUB é um iterável no formato (circuit, parameter_values). No mínimo, porém, requer uma lista de circuito(s) quântico(s).

# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

Para aproveitar ao máximo essa experiência, recomendamos fortemente que você execute seus experimentos nos computadores quânticos reais disponíveis no IBM Quantum. No entanto, se você tiver esgotado seu tempo de QPU, pode descomentar as linhas a seguir para concluir esta atividade com um simulador.

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Passo 4: Pós-processamento e retorno do resultado no formato clássico desejado

Agora podemos visualizar os resultados do nosso sampling em um histograma.

plot_distribution(dist)

Vemos que o algoritmo de Grover retornou o estado desejado com a maior probabilidade, pelo menos uma ordem de grandeza acima das outras opções. Na próxima atividade, usaremos o algoritmo de uma forma mais consistente com o fluxo de trabalho de duas partes de um algoritmo de consulta.

Verifique sua compreensão

Leia as perguntas abaixo, pense sobre sua resposta e clique no triângulo para revelar a solução.

Acabamos de buscar uma única solução em um conjunto de $2^4=16$ estados possíveis. Determinamos o número ótimo de repetições do operador de Grover como $t=3$. Esse número ótimo aumentaria ou diminuiria se buscássemos (a) uma dentre várias soluções, ou (b) uma única solução em um espaço com mais estados possíveis?

Resposta:

Lembre-se de que, enquanto o número de soluções for pequeno em comparação com o espaço total de soluções, podemos expandir a função seno para ângulos pequenos e usar

$$(2t+1)\theta = (2t+1) \sin^{-1}{\sqrt{\frac{|\mathcal{A}_1|}{N}}}\approx (2t+1) \sqrt{\frac{|\mathcal{A}_1|}{N}} \approx \pi/2\\ t \approx \frac{\pi}{4}\sqrt{\frac{N}{|\mathcal{A}_1|}}-\frac{1}{2}$$

(a) Vemos pela expressão acima que aumentar o número de estados solução diminuiria o número de iterações. Assumindo que a fração $\frac{|\mathcal{A}_1|}{N}$ ainda seja pequena, podemos descrever como $t$ diminuiria: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

(b) Se o espaço de soluções possíveis ($N$) aumentar, o número de iterações necessárias também aumenta, mas apenas como $t~\sqrt{N}$.

Suponha que pudéssemos aumentar o tamanho do bitstring alvo para qualquer comprimento e ainda assim o estado alvo tivesse uma amplitude de probabilidade pelo menos uma ordem de grandeza maior do que qualquer outro estado. Isso significa que poderíamos usar o algoritmo de Grover para encontrar o estado alvo de forma confiável?

Resposta:

Não. Suponha que repetíssemos a primeira atividade com 20 qubits e executássemos o circuito quântico um número de vezes num_shots = 10.000. Uma distribuição de probabilidade uniforme significaria que cada estado teria uma probabilidade de $10.000/2^{20}=0,00954$ de ser medido ao menos uma única vez. Se a probabilidade de medir o estado alvo fosse 10 vezes maior que a das não-soluções (com a probabilidade de cada não-solução ligeiramente reduzida em compensação), haveria apenas cerca de 10% de chance de medir o estado alvo ao menos uma vez. Seria muito improvável medir o estado alvo múltiplas vezes, o que o tornaria indistinguível dos muitos estados de não-solução obtidos aleatoriamente. A boa notícia é que podemos obter resultados com maior fidelidade usando supressão e mitigação de erros.

Atividade 2: Um fluxo de trabalho preciso de algoritmo de consulta

Começamos esta atividade exatamente como a primeira, exceto que agora você se unirá a outro entusiasta do Qiskit. Você escolherá um bitstring secreto, e seu parceiro escolherá um bitstring (em geral) diferente. Cada um gerará um circuito quântico que funciona como oráculo, e vocês os trocarão entre si. Você então usará o algoritmo de Grover com esse oráculo para determinar o bitstring secreto do seu parceiro.

Passo 1: Mapear entradas clássicas para um problema quântico

Usando a função grover_oracle definida acima, construa um circuito oráculo para um ou mais estados marcados. Certifique-se de informar ao seu parceiro quantos estados você marcou, para que ele possa aplicar o operador de Grover o número ótimo de vezes. Não deixe seu bitstring muito longo. 3 a 5 bits devem funcionar sem grandes dificuldades. Bitstrings mais longos levariam a circuitos mais profundos, que exigem técnicas mais avançadas como mitigação de erros.

# Modify the marked states to mark those you wish to target.
marked_states = ["1000"]
oracle = grover_oracle(marked_states)

Agora você criou um circuito quântico que inverte a fase do seu estado alvo. Você pode salvar esse circuito como my_circuit.qpy usando a sintaxe abaixo.

from qiskit import qpy

# Save to a QPY file at a location where you can easily find it.
# You might want to specify a global address.
with open("C:\\Users\\...put your own address here...\\my_circuit.qpy", "wb") as f:
    qpy.dump(oracle, f)

Agora envie esse arquivo ao seu parceiro (por e-mail, serviço de mensagens, repositório compartilhado etc.). Peça também que seu parceiro envie o circuito dele para você. Certifique-se de salvar o arquivo em um local onde você possa encontrá-lo facilmente. Assim que tiver o circuito do seu parceiro, você poderia visualizá-lo — mas isso quebraria o modelo de algoritmo de consulta. Ou seja, estamos modelando uma situação em que você pode consultar o oráculo (usar o circuito oráculo), mas não pode inspecioná-lo para determinar qual estado ele tem como alvo.

from qiskit import qpy

# Load the circuit from your partner's qpy file from the folder where you saved it.
with open("C:\\Users\\...file location here...\\my_circuit.qpy", "rb") as f:
    circuits = qpy.load(f)

# qpy.load always returns a list of circuits
oracle_partner = circuits[0]

# You could visualize the circuit, but this would break the model of a query algorithm.
# oracle_partner.draw("mpl")

Pergunte ao seu parceiro quantos estados alvo ele codificou e insira o valor abaixo.

# Update according to your partner's number of target states.
num_marked_states = 1

Isso será usado na próxima expressão para determinar o número ótimo de iterações de Grover.

grover_op = grover_operator(oracle_partner)
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_marked_states / 2**grover_op.num_qubits)))
)
qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

Passo 2: Otimizar o problema para execução em hardware quântico

Isso ocorre exatamente como antes.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
backend.name

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_partner_isa = pm.run(qc)

Passo 3: Executar usando Primitivos do Qiskit

Isso também é idêntico ao processo da primeira atividade.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_partner_isa]).result()
dist = result[0].data.meas.get_counts()

Passo 4: Pós-processamento e retorno do resultado no formato clássico desejado

Agora exiba um histograma dos seus resultados de sampling. Um ou mais estados devem ter uma probabilidade de medição muito maior do que os demais. Informe-os ao seu parceiro e verifique se você determinou corretamente os estados alvo. Por padrão, o histograma exibido é o do mesmo circuito da primeira atividade. Você deve obter resultados diferentes a partir do circuito do seu parceiro.

plot_distribution(dist)

Verifique sua compreensão

Leia as perguntas ou instruções abaixo, pense sobre sua resposta ou discuta o processo com seu parceiro. Clique no triângulo para ver dicas ou sugestões.

Você deveria ter obtido corretamente o(s) estado(s) alvo do seu parceiro. Caso não tenha, trabalhe com seu parceiro para descobrir o que deu errado. Clique abaixo para algumas ideias.

Dicas:

• Visualize/desenhe o circuito do seu parceiro e certifique-se de que ele foi carregado corretamente.
• Compare os circuitos usados e compare o resultado esperado com o que você obteve.
• Verifique a profundidade dos circuitos usados para garantir que o bitstring não era longo demais ou que o número de iterações de Grover não era excessivamente alto.

Se ainda não o fez, desenhe o circuito oráculo que seu parceiro lhe enviou. Veja se consegue descrever o efeito de cada porta e argumentar qual deve ter sido o estado alvo. Isso será muito mais fácil no caso de um único estado marcado do que para múltiplos.

Dicas:

• Lembre-se de que a função do oráculo é inverter o sinal no estado alvo.
• Lembre-se de que o MCMTGate inverte o sinal em um estado se, e somente se, todos os qubits envolvidos no controle estiverem no estado $|1\rangle$.
• Se o seu estado alvo já tiver $|1\rangle$ em um determinado qubit, você não precisa fazer nada com esse qubit. Se o seu alvo tiver $|0\rangle$ em um determinado qubit e você quiser que o MCMTGate inverta o sinal, você precisa aplicar uma porta X nesse qubit no seu oráculo (e depois desfazer a porta X após o MCMTGate).

Repita o experimento com uma iteração a menos do operador de Grover. Você ainda obtém a resposta correta? Por que sim ou por que não?

Orientação:

Provavelmente sim, embora possa depender do número de soluções codificadas. Isso destaca uma sutileza: o número "ótimo" de iterações de Grover é o número que maximiza a probabilidade de medir o estado marcado. Mas um número menor de iterações pode ainda tornar o estado marcado substancialmente mais provável do que os demais estados. Portanto, você pode se sair bem com menos iterações do que o número ótimo. Isso reduz a profundidade do circuito e, portanto, reduz as taxas de erro.

Por que alguém poderia querer usar menos iterações de Grover do que o "número ótimo" identificado aqui?

Resposta:

O número "ótimo" de iterações de Grover é o número que maximiza a probabilidade de medir o estado marcado na ausência de ruído. Mas um número menor de iterações pode ainda tornar o estado marcado substancialmente mais provável do que os demais estados. Portanto, você pode se sair bem com menos iterações do que o número ótimo. Isso reduz a profundidade do circuito e, portanto, reduz as taxas de erro.

Atividade 3: Critério diferente de um bitstring específico

Como ilustração final de como o algoritmo de Grover pode ser útil no contexto de uma subrotina, imaginemos que precisamos de estados quânticos com um determinado número de 1s na representação em bitstring. Isso é comum em situações que envolvem leis de conservação. Por exemplo, no contexto da química quântica, frequentemente se associa o estado 1 de um qubit à ocupação de um orbital eletrônico. Para que a carga seja conservada, o número total de 1s também deve permanecer constante. Tais restrições são tão comuns que possuem um nome especial: restrições de peso de Hamming, e o número de 1s no estado é chamado de peso de Hamming.

Passo 1:

Vamos primeiro escrever uma função que marca estados com o peso de Hamming desejado. Faremos isso de forma geral para um número não especificado de qubits num_qubits e peso de Hamming alvo target_weight.

from qiskit import QuantumCircuit

def grover_oracle_hamming_weight(num_qubits, target_weight):
    """
    Build a Grover oracle that marks all states with Hamming weight == target_weight.

    Parameters:
        num_qubits (int): Number of qubits in the circuit.
        target_weight (int): The Hamming weight to mark.

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle.
    """
    qc = QuantumCircuit(num_qubits)
    marked_count = 0
    marked_list = []
    for x in range(2**num_qubits):
        bitstr = format(x, f"0{num_qubits}b")
        if bitstr.count("1") == target_weight:
            # Count the number of target states
            marked_count = marked_count + 1
            marked_list.append(bitstr)
            # Reverse for Qiskit bit order (qubit 0 is rightmost)
            rev_target = bitstr[::-1]
            zero_inds = [i for i, b in enumerate(rev_target) if b == "0"]
            # Apply X gates to 'open' controls (where bit is 0)
            qc.x(zero_inds)
            # Multi-controlled Z (as MCX conjugated by H)
            if num_qubits == 1:
                qc.z(0)
            else:
                qc.h(num_qubits - 1)
                qc.mcx(list(range(num_qubits - 1)), num_qubits - 1)
                qc.h(num_qubits - 1)
            # Undo X gates
            qc.x(zero_inds)
    return qc, marked_count, marked_list

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(3, 2)
print(marked_states)
oracle.draw(output="mpl", style="iqp")

['011', '101', '110']

A partir daqui, todo o processo é idêntico ao das duas atividades anteriores. Por brevidade, os passos do padrão Qiskit são mostrados aqui apenas nos comentários do código.

from qiskit_ibm_runtime import SamplerV2 as Sampler

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(4, 2)
oracle.draw(output="mpl", style="iqp")

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)

qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()
qc.draw(output="mpl", style="iqp")

# Step 2: Optimize for running on real quantum computers

service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
print(backend.name)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

# Step 3: Execute using Qiskit primitives
# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:51,686: Default instance not set. Searching all available instances.

ibm_brisbane

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  502
The depth of two-qubit gates is  130

num_marked_states

6

plot_distribution(dist)

Aqui, o algoritmo de Grover de fato preparou os estados com peso de Hamming 2 de forma que sejam muito mais prováveis de serem medidos do que todos os outros estados — aproximadamente uma ordem de grandeza mais prováveis.

Conceitos críticos:

Neste módulo, aprendemos algumas características principais do algoritmo de Grover:

• Enquanto algoritmos clássicos de busca não estruturada requerem um número de consultas que escala linearmente com o tamanho do espaço, $N,$ o algoritmo de Grover requer um número de consultas que escala como $\sqrt{N}$.
• O algoritmo de Grover envolve a repetição de uma série de operações (geralmente chamada de "operador de Grover") um número $t$ de vezes, escolhido para maximizar a probabilidade de medir os estados alvo.
• O algoritmo de Grover pode ser executado com menos de $t$ iterações e ainda amplificar os estados alvo.
• O algoritmo de Grover se encaixa no modelo de computação por consulta e faz mais sentido quando uma pessoa controla a busca e outra controla/constrói o oráculo. Ele também pode ser útil como subrotina em outros cálculos quânticos.

Perguntas

Verdadeiro/Falso:

1. V/F O algoritmo de Grover oferece uma melhoria exponencial sobre os algoritmos clássicos no número de consultas necessárias para encontrar um único estado marcado em uma busca não estruturada.

2. V/F O algoritmo de Grover funciona aumentando iterativamente a probabilidade de que um estado solução seja medido.

3. V/F Quanto mais você itera o operador de Grover, maior a probabilidade de medir um estado solução.

Questões de múltipla escolha:

1. Escolha a melhor opção para completar a frase. A melhor estratégia para usar com sucesso o algoritmo de Grover em computadores quânticos modernos é iterar o operador de Grover...

• a. Apenas uma vez.
• b. Sempre $t$ vezes, para maximizar a amplitude de probabilidade do(s) estado(s) solução.
• c. Até $t$ vezes, embora um número menor possa ser suficiente para que os estados solução se destaquem.
• d. Não menos que 10 vezes.

2. Um circuito de consulta de fase é mostrado abaixo, funcionando como oráculo para marcar um determinado estado com uma inversão de fase. Quais dos seguintes estados são marcados por este circuito?

• a. $|0000\rangle$
• b. $|0101\rangle$
• c. $|0110\rangle$
• d. $|1001\rangle$
• e. $|1010\rangle$
• f. $|1111\rangle$

3. Suponha que você queira buscar três estados marcados em um conjunto de 128. Qual é o número ótimo de iterações do operador de Grover para maximizar as amplitudes dos estados marcados?

• a. 1
• b. 3
• c. 5
• d. 6
• e. 20
• f. 33

Perguntas para discussão:

1. Quais outras condições você poderia usar em um oráculo quântico? Considere condições que sejam fáceis de formular ou de aplicar a um bitstring, mas que não sejam simplesmente a listagem dos bitstrings marcados.

2. Você consegue identificar algum problema ao escalar o algoritmo de Grover em computadores quânticos modernos?