Nota

Esta página fue generada a partir de tutorials/algorithms/06_grover.ipynb.

Algoritmo de Grover y Amplificación de Amplitud

El algoritmo de Grover es uno de los algoritmos cuánticos más famosos introducido por Lov Grover en 1996 [1]. Inicialmente, se propuso para problemas de búsqueda no estructurados, es decir, para encontrar un elemento marcado en una base de datos no estructurada. Sin embargo, el algoritmo de Grover es ahora una subrutina de varios otros algoritmos, como Grover Adaptive Search [2]. Para obtener más información sobre el algoritmo de Grover, consulta Grover’s Algorithm en el libro de texto de Qiskit.

Qiskit implementa el algoritmo de Grover en la clase Grover. Esta clase también incluye la versión generalizada, Amplificación de Amplitud [3], y permite configurar iteraciones individuales y otros meta-ajustes para el algoritmo de Grover.

Referencias:

[1]: L. K. Grover, A fast quantum mechanical algorithm for database search. Proceedings 28th Annual Symposium on the Theory of Computing (STOC) 1996, pp. 212-219. https://arxiv.org/abs/quant-ph/9605043

[2]: A. Gilliam, S. Woerner, C. Gonciulea, Grover Adaptive Search for Constrained Polynomial Binary Optimization. https://arxiv.org/abs/1912.04088

[3]: Brassard, G., Hoyer, P., Mosca, M., & Tapp, A. (2000). Quantum Amplitude Amplification and Estimation. http://arxiv.org/abs/quant-ph/0005055

Algoritmo de Grover

El algoritmo de Grover utiliza el operador de Grover \(\mathcal{Q}\) para amplificar las amplitudes de los estados correctos:

\[\mathcal{Q} = \mathcal{A}\mathcal{S_0}\mathcal{A}^\dagger \mathcal{S_f}\]

Aquí, * \(\mathcal{A}\) es el estado de búsqueda inicial para el algoritmo, que es solo Hadamards, \(H^{\otimes n}\) para la búsqueda de Grover del libro de texto, pero puede ser más elaborado para la Amplificación de Amplitud * \(\mathcal{S_0}\) es la reflexión sobre todo el estado 0

\[\begin{split}|x\rangle \mapsto \begin{cases} -|x\rangle, &x \neq 0 \\ |x\rangle, &x = 0\end{cases}\end{split}\]

* \(\mathcal{S_f}\) es el oráculo que se aplica

\[|x\rangle \mapsto (-1)^{f(x)}|x\rangle\]

donde \(f(x)\) es 1 si \(x\) es un estado correcto y de lo contrario 0.

En pocas palabras, el algoritmo de Grover aplica diferentes potencias de \(\mathcal{Q}\) y después de cada ejecución verifica si se ha encontrado una solución correcta.

Ejecutar el algoritmo de Grover

Para ejecutar el algoritmo de Grover con la clase Grover, en primer lugar, necesitamos especificar un oráculo para el circuito del algoritmo de Grover. En el siguiente ejemplo, usamos QuantumCircuit como el oráculo del algoritmo de Grover. Sin embargo, hay varias otras clases que podemos usar como oráculo del algoritmo de Grover. Hablamos de ellos más adelante en este tutorial.

Ten en cuenta que el oráculo para Grover debe ser un oráculo de cambio de fase. Es decir, multiplica las amplitudes de los «estados correctos» por un factor de \(-1\). Más adelante explicamos cómo convertir un oráculo bit-flip en un oráculo de cambio de fase.

from qiskit import QuantumCircuit
from qiskit.algorithms import AmplificationProblem

# the state we desire to find is '11'
good_state = ['11']

# specify the oracle that marks the state '11' as a good solution
oracle = QuantumCircuit(2)
oracle.cz(0, 1)

# define Grover's algorithm
problem = AmplificationProblem(oracle, is_good_state=good_state)

# now we can have a look at the Grover operator that is used in running the algorithm
# (Algorithm circuits are wrapped in a gate to appear in composition as a block
# so we have to decompose() the op to see it expanded into its component gates.)
problem.grover_operator.decompose().draw(output='mpl')

Luego, especificamos un backend y llamamos al método run de Grover con un backend para ejecutar los circuitos. El tipo de resultado devuelto es un GroverResult.

Si la búsqueda fue exitosa, el atributo oracle_evaluation del resultado será True. En este caso, la medida más muestreada, top_measurement, es uno de los «estados correctos». De lo contrario, oracle_evaluation será False.

from qiskit.algorithms import Grover
from qiskit.primitives import Sampler


grover = Grover(sampler=Sampler())
result = grover.amplify(problem)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Result type: <class 'qiskit.algorithms.amplitude_amplifiers.grover.GroverResult'>

Success!
Top measurement: 11

En el ejemplo, el resultado de top_measurement es 11 que es un «estado correcto». Por lo tanto, logramos encontrar la respuesta usando Grover.

Usando los diferentes tipos de clases como el oráculo de Grover

En el ejemplo anterior, usamos QuantumCircuit como el oráculo de Grover. Sin embargo, también podemos usar qiskit.quantum_info.Statevector como oráculo. Todos los siguientes ejemplos son cuando \(|11\rangle\) es el «estado correcto»

from qiskit.quantum_info import Statevector
oracle = Statevector.from_label('11')
problem = AmplificationProblem(oracle, is_good_state=['11'])

grover = Grover(sampler=Sampler())
result = grover.amplify(problem)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Result type: <class 'qiskit.algorithms.amplitude_amplifiers.grover.GroverResult'>

Success!
Top measurement: 11

Internamente, el vector de estado se asigna a un circuito cuántico:

problem.grover_operator.oracle.decompose().draw(output='mpl')

Qiskit permite una fácil construcción de oráculos más complejos: * PhaseOracle: para analizar expresiones lógicas como '~a | b'. Esto es especialmente útil para resolver problemas de 3-SAT y se muestra en el tutorial Ejemplos de Grover adjunto.

Aquí usaremos el PhaseOracle para el ejemplo simple de encontrar el estado \(|11\rangle\), que corresponde a 'a & b'.

from qiskit.circuit.library.phase_oracle import PhaseOracle
from qiskit.exceptions import MissingOptionalLibraryError

# `Oracle` (`PhaseOracle`) as the `oracle` argument
expression = '(a & b)'
try:
    oracle = PhaseOracle(expression)
    problem = AmplificationProblem(oracle)
    display(problem.grover_operator.oracle.decompose().draw(output='mpl'))
except MissingOptionalLibraryError as ex:
    print(ex)

Observamos que este oráculo implementa un cambio de fase cuando el estado es \(|11\rangle\)

Como se mencionó anteriormente, el algoritmo de Grover requiere un oráculo de cambio de fase. Un oráculo de cambio de bits cambia el estado de un qubit auxiliar si los otros qubits cumplen la condición. Para usar este tipo de oráculos con Grover, necesitamos convertir el oráculo de cambio de bit en un oráculo de cambio de fase intercalando el qubit auxiliar del oráculo de cambio de bit con las compuertas \(X\) y \(H\).

Nota: Esta transformación de un oráculo de cambio de bit a un cambio de fase se mantiene en general y puedes usar esto para convertir tu oráculo en la representación correcta.

Amplificación de amplitud

El algoritmo de Grover usa compuertas Hadamard para crear la superposición uniforme de todos los estados al comienzo del operador de Grover \(\mathcal{Q}\). Si se dispone de alguna información sobre los estados correctos, puede resultar útil no comenzar en una superposición uniforme, sino solo inicializar estados específicos. Esta versión generalizada del algoritmo de Grover se conoce como Amplificación de Amplitud.

En Qiskit, el estado de superposición inicial se puede ajustar fácilmente configurando el argumento state_preparation.

Preparación del estado

Se utiliza un argumento state_preparation para especificar un circuito cuántico que prepara un estado cuántico para el punto de inicio de la amplificación de amplitud. Por defecto, un circuito con \(H^{\otimes n}\) se usa para preparar una superposición uniforme (por lo que será la búsqueda de Grover). El circuito de difusión de la amplificación de amplitud refleja el state_preparation automáticamente.

import numpy as np

# Specifying `state_preparation`
# to prepare a superposition of |01>, |10>, and |11>
oracle = QuantumCircuit(3)
oracle.ccz(0, 1, 2)

theta = 2 * np.arccos(1 / np.sqrt(3))
state_preparation = QuantumCircuit(3)
state_preparation.ry(theta, 0)
state_preparation.ch(0,1)
state_preparation.x(1)
state_preparation.h(2)

# we only care about the first two bits being in state 1, thus add both possibilities for the last qubit
problem = AmplificationProblem(oracle, state_preparation=state_preparation, is_good_state=['110', '111'])

# state_preparation
print('state preparation circuit:')
problem.grover_operator.state_preparation.draw(output='mpl')

state preparation circuit:

grover = Grover(sampler=Sampler())
result = grover.amplify(problem)
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Success!
Top measurement: 111

Flexibilidad total

Para un uso más avanzado, también es posible especificar todo el operador Grover configurando el argumento grover_operator. Esto podría ser útil si conoces una implementación más eficiente para \(\mathcal{Q}\) que la construcción predeterminada a través de la reflexión cero, el oráculo y la preparación del estado.

El qiskit.circuit.library.GroverOperator puede ser un buen punto de partida y ofrece más opciones para una construcción automatizada del operador Grover. Por ejemplo, puedes * establecer el mcx_mode * ignorar qubits en la reflexión cero configurando reflection_qubits * intercambiar explícitamente los operadores \(\mathcal{S_f}, \mathcal{S_0}\) y \(\mathcal{A}\) usando los argumentos oracle, zero_reflection y state_preparation

Por ejemplo, imagina que el estado correcto es un estado de tres qubits \(|111\rangle\) pero usamos 2 qubits adicionales como qubits auxiliares.

oracle = QuantumCircuit(5)
oracle.ccz(0, 1, 2)
oracle.draw(output='mpl')

Luego, por defecto, el operador Grover implementa la reflexión cero en los cinco qubits.

from qiskit.circuit.library import GroverOperator
grover_op = GroverOperator(oracle, insert_barriers=True)
grover_op.decompose().draw(output='mpl')

Pero sabemos que solo debemos considerar los tres primeros:

grover_op = GroverOperator(oracle, reflection_qubits=[0, 1, 2], insert_barriers=True)
grover_op.decompose().draw(output='mpl')

Sumergirse en otros argumentos de Grover

Grover tiene otros argumentos además de oracle y state_preparation. Los explicaremos en este apartado.

Especificar el good_state

good_state se utiliza para comprobar si el resultado de la medición es correcto o no internamente. Puede ser una lista de cadenas binarias, una lista de enteros, Statevector y Callable. Si la entrada es una lista de cadenas de bits, cada cadena de bits de la lista representa un estado correcto. Si la entrada es una lista de números enteros, cada número entero representa el índice del estado correcto que será \(|1\rangle\). Si es un Statevector, representa una superposición de todos los estados correctos.

# a list of binary strings good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = ['11', '00']
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))

True

# a list of integer good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = [0, 1]
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))

True

from qiskit.quantum_info import Statevector

# `Statevector` good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = Statevector.from_label('11')
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))

True

# Callable good state
def callable_good_state(bitstr):
    if bitstr == "11":
        return True
    return False

oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))

True

El número de iterations

El número de repeticiones de aplicar el operador de Grover es importante para obtener el resultado correcto con el algoritmo de Grover. El número de iteraciones se puede establecer mediante el argumento iteration de Grover. Se admiten las siguientes entradas: * un número entero para especificar una sola potencia del operador Grover que se aplica * o una lista de enteros, en la que todas estas diferentes potencias del operador Grover se ejecutan consecutivamente y después de cada ejecución comprobamos si se ha encontrado una solución correcta

Además, existe el argumento sample_from_iterations. Cuando es True, en lugar de la potencia específicada en iterations, se utiliza un número entero aleatorio entre 0 y el valor en iteration como el operador de potencia de Grover. Este enfoque es útil cuando ni siquiera sabemos la cantidad de soluciones.

Para obtener más detalles sobre el algoritmo que utiliza sample_from_iterations, consulta [4].

Referencias:

[4]: Boyer et al., Tight bounds on quantum searching arxiv:quant-ph/9605034

# integer iteration
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'])
grover = Grover(iterations=1)

# list iteration
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'])
grover = Grover(iterations=[1, 2, 3])

# using sample_from_iterations
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'])
grover = Grover(iterations=[1, 2, 3], sample_from_iterations=True)

Cuando se conoce el número de soluciones, también podemos usar un método estático optimal_num_iterations para encontrar el número óptimo de iteraciones. Ten en cuenta que las iteraciones de salida son un valor aproximado. Cuando el número de qubits es pequeño, las iteraciones de salida pueden no ser óptimas.

iterations = Grover.optimal_num_iterations(num_solutions=1, num_qubits=8)
iterations

12

Aplicar post_processing

Podemos aplicar un posprocesamiento opcional a la medición superior para facilitar la lectura. Se puede utilizar, por ejemplo, para convertir de la representación de bits de la medición [1, 0, 1] a un formato DIMACS CNF [1, -2, 3].

def to_DIAMACS_CNF_format(bit_rep):
    return [index+1 if val==1 else -1 * (index + 1) for index, val in enumerate(bit_rep)]

oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'], post_processing=to_DIAMACS_CNF_format)
problem.post_processing([1, 0, 1])

[1, -2, 3]

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
qiskit-terra	0.23.0.dev0+0f6c75e
qiskit-aer	0.11.1
qiskit-optimization	0.5.0
System information
Python version	3.9.10
Python compiler	Clang 13.1.6 (clang-1316.0.21.2.5)
Python build	main, Aug 9 2022 18:26:17
OS	Darwin
CPUs	10
Memory (Gb)	64.0
Fri Nov 25 21:25:09 2022 JST

This code is a part of Qiskit

© Copyright IBM 2017, 2022.

This code is licensed under the Apache License, Version 2.0. You may
obtain a copy of this license in the LICENSE.txt file in the root directory
of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.

Any modifications or derivative works of this code must retain this
copyright notice, and modified files need to carry a notice indicating
that they have been altered from the originals.