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.

Teoria

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

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

Answer

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®.

A imagem geométrica

O exemplo de dois qubits acima mostrou como a álgebra funciona para um caso pequeno, mas há uma maneira muito mais intuitiva de entender o algoritmo de Grover: como uma sequência de reflexões geométricas em um plano bidimensional. A seguir, descrevemos essa imagem. Você também pode consultar o curso de John Watrous Fundamentos de Algoritmos Quânticos para mais detalhes.

Configurando o plano. Podemos decompor o estado de superposição inicial $|\psi\rangle$ em dois componentes. O estado correto — aquele que estamos procurando — chamamos de $|A_1\rangle$. Todos os outros estados, agrupados juntos, chamamos de $|A_0\rangle$. Por definição, $|A_1\rangle$ e $|A_0\rangle$ são ortogonais entre si, portanto podemos representá-los como eixos perpendiculares em um espaço abstrato bidimensional. Como $|\psi\rangle$ é uma combinação linear desses dois componentes, ele se encontra em um pequeno ângulo $\theta$ em relação ao eixo $|A_0\rangle$ — próximo a $|A_0\rangle$, pois no início apenas uma fração ínfima do estado está no componente correto $|A_1\rangle$.

Reflexões. O fato matemático essencial que precisamos é que um operador da forma

$$2|v\rangle\langle v| - I$$

reflete qualquer estado em torno do eixo definido por $|v\rangle$. Para ver por quê, considere dois casos: um estado ao longo de $|v\rangle$ permanece inalterado, e um estado perpendicular a $|v\rangle$ tem seu sinal invertido. Qualquer outro estado pode ser decomposto nesses dois componentes, e o operador age em cada um deles correspondentemente — o que é exatamente uma reflexão em torno de $|v\rangle$.

Resulta que tanto o oráculo quanto as etapas de difusão no algoritmo de Grover podem ser expressos como reflexões nessa imagem geométrica.

O oráculo como reflexão. O oráculo inverte o sinal do estado $|A_1\rangle$ e deixa todo o resto inalterado. Isso equivale a uma reflexão em torno do eixo $|A_0\rangle$.

Difusão como reflexão. É um pouco mais difícil ver como o operador de difusão também é uma reflexão. O operador de difusão é

$$H^{\otimes n}\, Z_{\text{OR}}\, H^{\otimes n}$$

$Z_{\text{OR}}$ por si só é uma reflexão em torno do estado de todos os zeros, pois inverte o sinal de todo estado que não seja $|0\rangle^{\otimes n}$. Isso pode ser escrito como $2|0\rangle\langle 0| - I$. As camadas Hadamard ao redor efetivamente realizam uma mudança de base, transformando o eixo da reflexão. Lembre-se de que $H^{\otimes n}$ mapeia $|0\rangle^{\otimes n}$ para a superposição uniforme $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$. Como a porta Hadamard é sua própria inversa, a expressão completa se torna

$$H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n} = 2|u\rangle\langle u| - I$$

que é uma reflexão em torno de $|u\rangle$. Como $|u\rangle$ é muito próximo de $|\psi\rangle$ (ambos estão quase ao longo de $|A_0\rangle$), essa segunda reflexão envia o estado para um ângulo $2\theta$ a partir de onde ele estava.

Rotação por $2\theta$. O efeito combinado dessas duas reflexões é uma rotação por $2\theta$ em direção a $|A_1\rangle$. Cada iteração sucessiva do operador de Grover rotaciona o estado em mais $2\theta$.

Número ótimo de iterações. Nosso objetivo é rotacionar o estado o mais próximo possível de $|A_1\rangle$, o que significa rotacionar por um total de aproximadamente $\pi/2$ radianos (um quarto de volta). Se cada iteração contribui $2\theta$, o número ótimo de iterações $t$ satisfaz

$$(2t + 1)\theta \approx \frac{\pi}{2}$$

Para uma única solução entre $N$ estados, o ângulo inicial é $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (para $N$ grande). Substituindo,

$$t \approx \frac{\pi}{4}\sqrt{N} - \frac{1}{2}$$

É aqui que a famosa aceleração de $\sqrt{N}$ vem: precisamos apenas de $O(\sqrt{N})$ iterações para atingir o alvo, em vez das $O(N)$ verificações que uma busca clássica exigiria.

De forma mais geral, se houver $|A_1|$ estados de solução entre $N$ estados totais, o número ótimo de iterações é

$$t \approx \frac{\pi}{4}\sqrt{\frac{N}{|A_1|}} - \frac{1}{2}$$

Note que se você aplicar iterações demais, rotacionará além de $|A_1\rangle$ e a probabilidade de encontrar o estado alvo começará a diminuir novamente. Encontrar o número correto de iterações é importante, embora em hardware quântico ruidoso o número experimentalmente ótimo possa diferir dessa fórmula ideal.

Por que o algoritmo de Grover é útil?

Neste ponto, você pode estar se perguntando: acabamos de construir um oráculo que marca um estado alvo — mas para construí-lo, precisávamos conhecer o estado alvo. Então, o que estamos realmente buscando?

Esta é uma pergunta legítima, e há várias boas respostas.

• O modelo de consulta é uma ferramenta teórica. O modelo de computação por consulta nunca foi projetado para ser diretamente prático. Seu propósito é nos fornecer uma maneira clara de analisar a complexidade algorítmica, separando um problema em duas partes: o oráculo e todo o resto. Quão difícil é a busca, dado que a verificação é gratuita? Como o número de consultas escala com o tamanho da entrada? Essas são perguntas úteis mesmo que nenhum sistema real funcione exatamente dessa forma.

• Você também pode pensar nisso como uma atividade de duas partes: uma pessoa conhece o estado alvo e constrói o oráculo; a outra pessoa tem a tarefa de encontrar a resposta usando o oráculo como uma caixa preta, sem espiar por dentro. Na Atividade 2 abaixo, você fará exatamente isso com um parceiro.

• A amplificação de amplitude é uma sub-rotina amplamente útil. Mesmo que esta primeira demonstração pareça circular, o mecanismo subjacente — chamado de amplificação de amplitude — aparece repetidamente na computação quântica. O que estamos realmente construindo aqui é uma intuição para uma ferramenta que aparece como sub-rotina em muitos algoritmos quânticos mais complexos.

• Existem problemas em que você pode construir um oráculo sem conhecer a resposta. O insight fundamental é que existe toda uma classe de problemas para os quais é muito difícil encontrar uma solução, mas muito fácil verificar que uma determinada solução está correta. A fatoração é um exemplo: dado um produto de dois primos grandes, é extremamente difícil determinar quais são esses primos, mas, uma vez que você os tenha, pode facilmente multiplicá-los para verificar. (Temos um algoritmo melhor que o de Grover para fatoração especificamente — veja o algoritmo de Shor — mas este está longe de ser o único problema com essa característica.) Sudoku, satisfação de restrições e até o clássico jogo Campo Minado são todos problemas difíceis de resolver, mas fáceis de verificar.

Por que isso é relevante? Significa que podemos conhecer todas as condições e requisitos que uma solução deve satisfazer, e podemos codificar esses requisitos em um circuito quântico que serve como oráculo — mesmo sem conhecermos a solução em si. O algoritmo de Grover a encontrará para nós.

Com essas ideias em mente, trabalharemos vários exemplos. Começaremos com um exemplo em que o estado de solução é claramente especificado para que possamos acompanhar a lógica do algoritmo. Em seguida, passaremos para uma atividade de duas partes e, por fim, para um exemplo em que o oráculo é construído a partir de restrições do problema, e não do conhecimento da resposta.

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, QuantumRegister, ClassicalRegister
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 discutimos na imagem geométrica 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 é

$$t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

onde $|A_1|$ é o número de estados de solução e $N=2^n$ é o número total de estados. 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.

Etapa 3: 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

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?

Answer

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?

Answer

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

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.

Hints

• 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.

Hints

• 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?

Guidance

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?

Answer

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: Resolver uma grade de Campo Minado com o algoritmo de Grover

Na seção anterior, observamos que o algoritmo de Grover se torna genuinamente útil quando podemos construir um oráculo a partir das restrições de um problema, e não do conhecimento da resposta. Campo Minado é um exemplo perfeito: as células numeradas nos dizem quantas minas estão adjacentes, e essas restrições determinam completamente onde as minas devem estar — mas encontrar a configuração requer busca.

Foi provado que Campo Minado é NP-completo: é difícil de resolver, mas fácil de verificar. Isso o torna um candidato natural para o algoritmo de Grover. É claro que ainda não podemos resolver uma grade completa de 9$\times$9 em um computador quântico ruidoso — os circuitos seriam muito profundos. Em vez disso, usaremos uma grade minúscula como demonstração ilustrativa de como se abordaria um tabuleiro maior em uma máquina tolerante a falhas no futuro.

Algumas ressalvas importantes. O algoritmo de Grover oferece apenas uma aceleração quadrática em relação à busca clássica não estruturada. Campo Minado quase certamente tem estrutura explorável que um algoritmo clássico inteligente poderia aproveitar. E para um espaço de busca de crescimento exponencial, mesmo a melhoria de $\sqrt{N}$ tem seus limites. Mas deixemos essas preocupações de lado e usemos esse problema ilustrativo para mostrar como as restrições do problema são codificadas em um oráculo quântico.

A grade

Aqui está nossa grade de Campo Minado simplificada:

Cada célula em branco pode ser representada por uma variável binária que indica se contém uma mina. Rotulamos essas variáveis como $x_0$, $x_1$ e $x_2$, onde $x_i = 1$ significa que há uma mina nessa célula e $x_i = 0$ significa que não há:

Poderíamos resolver isso mentalmente em meio segundo, mas estamos usando esse problema ilustrativo para mostrar como um tabuleiro muito mais difícil poderia ser abordado com um computador quântico.

Codificar as restrições

Cada célula numerada impõe uma condição sobre as células em branco adjacentes. Precisamos expressar essas condições como expressões booleanas que possam ser codificadas em um circuito quântico.

A célula "1" adjacente a $x_0$ e $x_1$ diz que exatamente uma delas contém uma mina. Essa é precisamente a operação OU Exclusivo (XOR), $\oplus$, que retorna verdadeiro quando exatamente uma de suas entradas é verdadeira:

$$(x_0 \oplus x_1)$$

Da mesma forma, a outra célula "1" (adjacente a $x_1$ e $x_2$) nos dá:

$$(x_1 \oplus x_2)$$

A célula "2" diz que duas das três células em branco devem conter minas. Como o XOR é uma operação de paridade, $x_0 \oplus x_1 \oplus x_2$ retorna verdadeiro quando um número ímpar de variáveis é verdadeiro. Queremos que um número par (especificamente dois) seja verdadeiro, então negamos com $\lnot$:

$$\lnot(x_0 \oplus x_1 \oplus x_2)$$

Por si só, essa expressão seria satisfeita por zero ou dois qubits no estado $|1\rangle$, pois é uma afirmação sobre paridade. Mas combinada com as outras duas cláusulas, que exigem ao menos uma mina cada, a única atribuição que satisfaz todas tem exatamente duas minas.

Todas as três condições devem ser satisfeitas simultaneamente, então as unimos com o símbolo E $\land$:

$$(x_0 \oplus x_1) \;\land\; (x_1 \oplus x_2) \;\land\; \lnot(x_0 \oplus x_1 \oplus x_2)$$

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

Agora precisamos codificar essa expressão booleana em um circuito quântico que serve como oráculo. A versão quântica do XOR pode ser realizada com portas CX (CNOT): aplicar duas portas CX dos qubits de dados a um qubit de espaço de trabalho (ancilla) efetivamente computa o XOR deles e armazena o resultado no ancilla.

Introduzimos três qubits de espaço de trabalho — um para cada cláusula. Armazenamos o resultado de cada expressão booleana no qubit de espaço de trabalho correspondente e, em seguida, usamos uma porta Z multi-controlada para inverter a fase do estado de três qubits que faz todos os três qubits de espaço de trabalho ficarem em $|1\rangle$ (significando que todas as cláusulas estão satisfeitas simultaneamente).

Na primeira célula de código abaixo, construímos a metade de "computação" do oráculo — a parte que avalia cada cláusula e escreve o resultado nos qubits de espaço de trabalho.

x = QuantumRegister(3, "x")
a = QuantumRegister(3, "a")
qc = QuantumCircuit(x, a)

# Clause 1: x0 XOR x1 -> stored in a[0]
qc.cx(x[0], a[0])
qc.cx(x[1], a[0])

# Clause 2: x1 XOR x2 -> stored in a[1]
qc.cx(x[1], a[1])
qc.cx(x[2], a[1])

# Clause 3: NOT(x0 XOR x1 XOR x2) -> stored in a[2]
qc.cx(x[0], a[2])
qc.cx(x[1], a[2])
qc.cx(x[2], a[2])
qc.x(a[2])  # The NOT

qc.draw("mpl", style="iqp")

Neste ponto, o resultado de cada cláusula está armazenado no qubit de espaço de trabalho correspondente. Agora precisamos que o estado de dados de três qubits que faz todos os três qubits de espaço de trabalho ficarem em $|1\rangle$ adquira um sinal de menos. Fazemos isso com uma porta Z multi-controlada (implementada como uma porta MCX envolvida por portas Hadamard no alvo).

Após aplicar a inversão de fase, precisamos descomputar — desfazer todos os passos de avaliação de cláusulas em ordem inversa — para redefinir os qubits de espaço de trabalho de volta a $|0\rangle$. Isso é essencial para que os qubits de espaço de trabalho estejam limpos para as iterações subsequentes do operador de Grover.

# Multi-controlled Z: flip phase if all workspace qubits are |1>
qc.h(a[2])
qc.mcx([a[0], a[1]], a[2])
qc.h(a[2])

# Uncompute clause 3: NOT(x0 XOR x1 XOR x2)
qc.x(a[2])
qc.cx(x[2], a[2])
qc.cx(x[1], a[2])
qc.cx(x[0], a[2])

# Uncompute clause 2: x1 XOR x2
qc.cx(x[2], a[1])
qc.cx(x[1], a[1])

# Uncompute clause 1: x0 XOR x1
qc.cx(x[1], a[0])
qc.cx(x[0], a[0])

qc.draw("mpl", style="iqp")

Este circuito é nosso oráculo: ele inverte a fase do estado dos qubits de dados que satisfaz todas as três restrições do Campo Minado e deixa os qubits de espaço de trabalho de volta em $|0\rangle$.

Agora construímos o operador de Grover completo a partir desse oráculo. Note o argumento reflection_qubits: passamos apenas os qubits de dados x, pois os qubits de espaço de trabalho não fazem parte do espaço de busca. Seu trabalho está concluído após a aplicação do oráculo.

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

Com três qubits de dados e um estado de solução, o número ótimo de iterações de Grover é $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$, então usamos duas iterações. Aplicamos portas Hadamard aos qubits de dados para criar a superposição inicial, compomos o operador de Grover duas vezes e medimos apenas os qubits de dados.

x = QuantumRegister(3, "x")
a = QuantumRegister(4, "a")
meas = ClassicalRegister(3, "meas")

qc = QuantumCircuit(x, a, meas)
# Create superposition over the data qubits only
qc.h(x)
# Apply 2 iterations of the Grover operator
qc.compose(grover_op.power(2), inplace=True)
# Measure only the data qubits
qc.measure(x, meas)
qc.decompose().draw(output="mpl", style="iqp")

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

Como antes, transpilamos o circuito para o backend alvo.

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)

Agora podemos verificar a profundidade do circuito transpilado. Como o oráculo do Campo Minado usa qubits de espaço de trabalho e múltiplas portas CX, o circuito transpilado será mais profundo do que os das atividades anteriores.

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),
)

Etapa 3: Executar com os Primitivos do Qiskit

# 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()

# 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()

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

plot_distribution(dist)

O estado 101 deve aparecer com probabilidade muito maior do que qualquer outro, indicando que há minas em $x_0$ e $x_2$. Usamos um computador quântico para resolver um pequeno jogo de Campo Minado!

Claro, os melhores algoritmos clássicos para Campo Minado são melhores do que uma busca por força bruta em todas as configurações possíveis de minas — eles exploram a estrutura da grade. O algoritmo de Grover só ofereceria uma vantagem em tabuleiros extremamente difíceis, projetados para serem maximamente ambíguos, e mesmo assim, a aceleração quadrática não consegue acompanhar o crescimento exponencial indefinidamente. Mas a verdadeira conclusão é a técnica: codificar restrições do problema em um oráculo quântico é um padrão poderoso que se estende à satisfação de restrições, otimização combinatória e muitos outros domínios.

Perguntas e conceitos críticos:

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.
• Um oráculo pode ser construído a partir de restrições do problema, e não do conhecimento da solução, como demonstrado com o exemplo do Campo Minado.

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 outros problemas você poderia formular como uma busca de Grover? Pense em problemas em que é difícil encontrar uma solução, mas fácil verificá-la.

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