ALGORITMOS DE BÚSQUEDA CLÁSICOS Y CUÁNTICO

algbcq

Resumen Realizar búsquedas de uno o varios elementos en una estructura de datos es un método indispensable en los algoritmos o funciones que se utilizan en los sistemas de cómputo, por lo tanto conocer el funcionamiento de algunos algoritmos de búsqueda clásica permitirá ver las ventajas que puedan llegar a tener los algoritmos de búsqueda cuántica. En este documento se presentarán algunos de los algoritmos clásicos más utilizados, junto con un algoritmo de búsqueda cuántico de los cuales se dará una visión fácil y rápida de cómo implementarlos   en el lenguaje de programación Python; y se describirá paso a paso cómo realizar múltiples búsquedas con el algoritmo de Grover usando Qiskit en un Notebook.

Palabras clave: Estructuras de datos, notación asintótica, algoritmos de búsqueda clásicos, Grover.

Introducción Los algoritmos de búsqueda se basan generalmente en la estructura de datos en la que hayan sido almacenados los datos para realizar las búsquedas. Por lo tanto determinar la estructura en la que los datos se van a encontrar es un factor que determinara la eficiencia del algoritmo de búsqueda, en este documento se presentarán las características y el funcionamiento de los algoritmos de búsqueda clásicos  y cuántico más importantes, también se explica el uso de big O para determinar el tiempo que tardan en buscar un elemento; en la primera parte se describen los tipos de estructuras de datos más utilizadas, luego se explica el uso de la notación asintótica, seguido de  una explicación sobre qué son los algoritmos de búsqueda clásicos y cuántico junto con los pasos que se deben de tener en cuenta a la hora de implementar el algoritmo de Grover, además la correspondiente implementación de cada algoritmo en el lenguaje Python.

1) Tipos de estructuras de datos

Existen numerosos tipos de estructura de datos como: vectores, tabla hash o vector asociativo, registro o tupla, conjunto, multi conjunto, grafo, árbol, entre otros. Determinar el tiempo de búsqueda en los algoritmos, se da mediante el uso de la big O  con lo cual se puede decir que O(n) es una expresión de crecimiento lineal que indica el crecimiento en complejidad del algoritmo y es proporcional al tamaño del input.

2) Notación asintótica

La notación asintótica nos permite simplificar las funciones que representan la tasa de crecimiento de un algoritmo, es decir un número decimal se puede redondear de (4.88 a 5) y este redondeo se puede realizar hacia arriba o hacia abajo. Se pueden utilizar diferentes notaciones asintóticas dependiendo de lo que nos interesa si el límite superior o un límite inferior o los dos, también en esta notación asintótica se debe tomar al final del resultado el término más significativo. Ejemplo: $2n^2$+ 2n+1  solo tomamos el más significativo en este caso 2$n^2$, quitando cualquier número que esté multiplicando a n, generando O($n^2$).

Big O (cota superior)

Métrica que se utiliza para describir la eficiencia de los algoritmos ya que permite ver el límite superior “big O”,  representando el comportamiento en el peor de los casos del algoritmo; y con el big O se identifica cómo se comporta el algoritmo dependiendo del input o entrada de datos que este tenga y así  poder clasificar a los algoritmos con diferentes complejidades.

Si el algoritmo es O($n^2$) indica que entre más datos de entrada más tiempo tardará el algoritmo en procesar esos datos.

Y si los mismos datos se ingresan en un algoritmo de O(log N) o O(1) el algoritmo va a tardar menos tiempo en procesar los datos.

Cualquier función o línea de código se considera O(1) o tiempo constante siempre y cuando no tenga ciclos, recursividad o realice una llamada a una función que no sea de tiempo constante. Ejemplos conocidos de notaciones big O:


3) ¿Qué son los algoritmos de búsqueda clásicos?

Los algoritmos de búsqueda clásicos son instrucciones que se utilizan para determinar si algún o algunos elemento(s) se encuentran o no dentro de un conjunto de datos. Las búsquedas se pueden clasificar en internas o externas, según la ubicación de los datos.

Búsquedas internas: Se dan cuando todos los elementos se encuentran en la memoria principal del computador, estos pueden estar en estructuras estáticas como arreglos o dinámicas como listas ligadas o árboles.

Búsquedas externas: Si los elementos se encuentran en una memoria secundaria como en una usb o en la nube.

En este documento se presentarán los algoritmos de búsquedas internos más relevantes y se generarán los códigos correspondientes en el lenguaje Python.

Existe una gran variedad de algoritmos de búsqueda interna y la elección de este algoritmo depende principalmente de la forma en que se encuentran organizados los datos es decir si están en forma aleatoria, si se ignora su disposición o si están ordenados y en qué tipo de estructuras estáticas se encuentran estos datos. Si el conjunto de datos fue almacenado de forma aleatoria comúnmente se hace uso de la búsqueda secuencial de lo contrario se puede hacer uso de las búsquedas binarias, exponenciales, interpolación, salto, lineal  o ternaria.

Algoritmos de búsquedas internas

Búsqueda Lineal o Secuencial: Consiste en comparar cada elemento del conjunto de datos con el valor deseado hasta que este sea encontrado o hasta recorrer todo el conjunto de datos, también se lo puede aplicar a conjuntos de datos desordenados. Este algoritmo es el más sencillo y fácil de implementar pero es el menos eficiente.

Complejidad del  tiempo: O(n).

b1

def busqueda_lineal(lista, x):
    i = 0
    for z in lista:	
        if z == x:	
	   return i 
	i=i+1	

     return -1

print(busqueda_lineal([5, 15, 25, 30, 88, 45, 50, 78, 100, 150], 150))

Búsqueda Binaria o dicotómica: Este algoritmo tiene dos pre-requisitos que se deben cumplir a) que el conjunto de datos esté ordenado, b) se disponga de acceso aleatorio. Dado que el algoritmo compara el dato buscado con el elemento central, dividiendo al conjunto de datos en dos sub listas, si el elemento se encuentra en la mitad este retorna la posición, de lo contrario salta a la sub lista de izquierda o derecha y hace el mismo procedimiento hasta encontrar el elemento.

Complejidad del tiempo: O(log(n)).

b2

def busqueda_binaria(lis, val):  

    ini = 0
    fin = len(lis)-1
    index = -1

    while (ini <= fin) and (index == -1):	
        mit = (ini+fin)//2					
        
        if lis[mit] == val:
            index = mit
        else:
            if val < lis[mit]:
                fin = mit -1
            else:
                ini = mit +1
    
    return index

print(busqueda_binaria([5, 15, 25, 30, 45, 50, 67, 78, 88, 100, 150], 78)

Búsqueda Exponencial o al galope: Se usa para buscar el rango donde pueda encontrarse el dato a buscar, si S e I son el límite superior e inferior de la lista respectivamente luego S e I son potencias de 2 donde I es la última posición de la lista, por lo tanto es el exponencial. Después de encontrar el rango específico, se utiliza el algoritmo de búsqueda binaria para encontrar la posición exacta del elemento de búsqueda.

Complejidad del tiempo: O(log i) donde i es la posición donde se encuentra el elemento buscado.

b3

def busqueda_exponencial(lis, val):
    arr = []

    if lis[0] == val:
        return 0
    else:   
        index = 1

        while index < len(lis) and lis[index] <= val:
            index *= 2
            print(index)
    return busqueda_binaria(arr[:min(index, len(lis))], val)

print(busqueda_exponencial([1,2,3,4,5,6,7,8],3))

Búsqueda de Interpolación: Este algoritmo tratará de localizar la posición exacta usando la fórmula de interpolación lineal ($ f(x|x_1; x_2) = f(x_1) + \frac{ f(x_2)-f(x_1)} {x_2-x_1} * (x – x_1)  $). Luego de encontrar la posición estimada se puede dividir la lista usando esa posición, mientras intenta encontrar la posición exacta cada vez, reduciendo el tiempo de búsqueda, si el conjunto de datos están distribuidos uniformemente el algoritmo puede encontrar fácilmente los elementos.

Complejidad del tiempo: O(n) para el peor de los casos, cuando los datos tienen una distribución exponencial.

b4

def busqueda_interpolacion(lis, val):  
    x1 = 0
    x2 = (len(lis) - 1)
    
    while x1 = lis[x1] and val <= lis[x2]:
        index = x1 + int(((float(x2 - x1) / ( lis[x2] - lis[x1])) * ( val - lis[x1])))
        if lis[index] == val:
            return index
        if lis[index] < val:
            x1 = index + 1;
        else:
            x2 = index - 1;
            
    return -1

print(busqueda_interpolacion([1,2,3,4,5,6,7,8], 6))

Búsqueda de Salto: Funciona en los conjuntos de datos ordenados, este algoritmo crea un bloque de datos e intenta encontrar el elemento en ese bloque de datos, si el elemento no se encuentra en ese bloque se desplaza todo el bloque. El tamaño del bloque se basa según la longitud del conjunto de datos; si el tamaño del conjunto de datos es n entonces el tamaño del bloque será $\sqrt{ n }$ y después de encontrar el bloque correcto este encuentra el elemento usando el algoritmo de búsqueda lineal. La búsqueda de salto se encuentra entre la búsqueda lineal y la búsqueda binaria dependiendo del rendimiento.

Complejidad del tiempo: O($\sqrt{ n }$).

b6

import math

def busqueda_salto(lis, val):  
    
    v1 = len(lis)
    salto = int(math.sqrt(v1))
    izq, der = 0, 0
    
    while izq < v1 and lis[izq] <= val:
        
        der = min(v1 - 1, izq + salto)
        
        if lis[izq] = val:
            break
        izq += salto;
    
    if izq >= v1 or lis[izq] > val:
        return -1
    
    der = min(v1 - 1, der)
    i = izq
    
    while i <= der and lis[i] <= val:
        if lis[i] == val:
            return i
        i += 1
    
    return -1

print(busqueda_salto([1,2,3,4,5,6,7,8,9], 5))

Búsqueda Ternaria: Este algoritmo divide la lista en tres partes usando dos valores medios intermedios, como la lista tiene estas subdivisiones se reduce el tiempo de búsqueda del elemento a encontrar, ya que se determina que el extremo que se busca no puede estar en el primer tercio o en el último tercio del conjunto de datos.

Complejidad del tiempo: O(log n).

b6

def busqueda_ternaria(f, l, r, absolutePrecision):   
    
    while True:
        #l and r son los límites actuales; el máximo está entre ellos
        if abs(r - l) < absolutePrecision:
            return (l + r)/2

        m1 = l + (r - l)/3
        m2 = r - (r - l)/3

        if f(m1) < f(m2):
            l = m1
        else:
            r = m2

print(busqueda_ternaria([1,2,3,4,5,6,7,8,9], 5))

Búsqueda por transformación de claves o Hash: Este algoritmo tiene dos pre requisitos que se deben cumplir a) una función hash que sea fácil de calcular y distribuya uniformemente las claves, b) un método para resolver colisiones. Si estas se presentan se contará con un método que generará posiciones alternativas.

Una tabla hash es una colección de ítems que se almacenan de tal manera que sea más fácil encontrarlos. Cada posición de la tabla hash, a menudo llamada una dirección, puede contener un ítem y se llama por un valor entero que inicia en 0.

La correspondencia entre un ítem y la dirección a la que pertenece ese ítem en la tabla hash se denomina función hash, la función hash tomará cualquier ítem del conjunto de datos y devolverá un número entero entre el rango de números de las direcciones, entre 0 y n-1.

Supongamos que tenemos el conjunto de ítems enteros [54, 26, 93, 17, 77, 71]. Nuestra primera función hash, a veces denominada “método del residuo”, simplemente toma un ítem y lo divide por el tamaño de la tabla, devolviendo el residuo como su valor hash (h (item) = item%n).

El método del residuo (módulo aritmético) estará típicamente presente en alguna forma en todas las funciones hash, ya que el resultado debe estar en el rango de números de las direcciones. Ahora, cuando queramos buscar un ítem, simplemente usamos la función hash para calcular el número de la dirección para el ítem y luego verificamos la tabla hash para ver si está presente. Esta operación de búsqueda es O(1), ya que se requiere una cantidad de tiempo constante para calcular el valor hash y luego indexar  la tabla hash en esa ubicación. Consiguiendo un algoritmo de búsqueda de tiempo constante.

b7

Cuando se tienen claves que no son numéricas o cuando las claves representan valores muy grandes o no se corresponden con los índices de los arreglos, se utilizará una función hash que permita transformar la clave para obtener una dirección apropiada, esta función hash debe también generar posiciones diferentes dadas dos claves diferentes si esto no se cumple (H($K_1$) = d, H($K_2$) = d y $K_1$ es diferente de $K_2$) lo que genera una colisión que significa que se asignó la misma dirección a dos o más claves distintas.

Complejidad del tiempo: O(1).

dic = {}
lish = [54, 26, 93, 17, 77, 31]
numele = 11

for c in range(0, numele):
    dic[c] = 'Null'

print(dic)

for i in lish:
    h = i % len(dic)
    dic[h] = i
    #print(i,'=',h)
print(dic)

Búsqueda en List: Los list sonun tipo de estructuras de datos de tipo listas utilizadas en Python las cuales son secuencias  mutables y tienen una gran variedad de operaciones muy útiles. La notación para las listas es una secuencia de valores encerrados entre corchetes y separados por comas. Lista1 = [3, 4, 5, 6, 7, 8, 9] si se deja la lista sin elementos tendríamos una lista vacía lista1 = [], para luego agregar los valores.

Para realizar búsquedas sobre este tipo de listas se usa la operación in, con lo cual se tendrá 8 in lista1 que retornara un valor booleano de True o False. En esta búsqueda se utiliza un algoritmo de comparación que tarda cada vez más a medida que la lista se hace más larga.

Para averiguar la posición de un valor dentro de las listas se puede utilizar la operación index() el cual retorna un valor entero entre 0 y n-1, lista1.index(5), o usar un enumerador para obtener un índice iterable dentro de un bucle.

Complejidad del tiempo: O(n)

b8

lis1 = [1,2,3,4,5,6,7,8,9]

print(8 in lis1)
print(lis1.index(8))

Búsqueda en Diccionarios: Los diccionarios son estructuras de datos de tipo dict en Python y tienen gran variedad de operaciones muy útiles. La notación para los diccionarios consiste en definir el conjunto de miembros que va a contener y se encierra el listado de valores entre llaves, la clave y el valor se separan con (:) y las parejas de clave y valor se separan con comas, formando el diccionario de la siguiente manera d1 = {‘a’: 50, ‘b’: 60, ‘c’: 80}.

Para declarar un diccionario vacío y luego ingresar valores, se lo declara como un par de llaves sin ningún elemento, y luego se asignan valores directamente a los índices dic1 = {}, agregamos valores de la siguiente forma d1[«d»] = [90, 100].

Las búsquedas del valor asociado en estos diccionarios se realizan mediante la clave elegida en este caso  d1[«d»] lo cual nos traerá los valores relacionados a esa clave.

El algoritmo que usa Python internamente para buscar un elemento en un diccionario es muy distinto que el que utiliza para buscar en listas.

Para buscar en diccionarios se utiliza el algoritmo de hash, sin importar cuántos elementos tenga el diccionario, el tiempo de búsqueda es siempre aproximadamente igual. El algoritmo de hash es también la razón por la cual las claves de los diccionarios deben ser inmutables, ya que la operación hecha sobre las claves debe dar siempre el mismo resultado, y si se utilizara una variable mutable esto no sería posible.

Los diccionarios no están ordenados. Si bien se los puede recorrer, el orden en el que se tomarán los elementos no está determinado.

Complejidad del tiempo: O(1).

b9

d1 = {'a': 50, 'b': 60, 'c': 80}
d1['d'] = [90, 100]

print(d1['d'])

4) ¿Qué son los algoritmos de búsqueda cuánticos? Los algoritmos de búsqueda cuántica son similares a los algoritmos de búsqueda clásica con la diferencia de que usan algunas propiedades de la física cuántica para encontrar algún o algunos elementos dentro de un conjunto de datos, y estos algoritmos parten de un problema de búsqueda el cual se define a continuación.

Problema de búsqueda

Dada una colección de objetos se pedirá de entre ellos obtener al menos uno que cumpla una cierta propiedad.

Es decir dado el conjunto de enteros positivos {1, 2, 3,…[w],…} encontrar el elemento w el cual también pertenece a los enteros positivos. Los elementos de los conjuntos se podrían codificar por cadenas de n ceros y unos. Y la propiedad es $f: \left\lbrace {0,1} \right\rbrace^n$ -> {0,1} «donde {0,1} son el resultado de la función», la cual retorna 1 si el estado verifica la propiedad y cero en el caso contrario.

Para lo cual se deberá formalizar el concepto anterior de la siguiente forma:

  • Sea w un entero positivo y $O_f$ un Oracle para calcular la función $f: \left\lbrace {0,1} \right\rbrace^n$ -> {0,1}, el problema de búsqueda asociado a estos datos será encontrar X ε $\left\lbrace {0,1} \right\rbrace^n$  tal que f(x) = 1 si x=w.

Una vez formalizado el problema debemos definir cuántas llamadas a $O_f$ se necesitan para resolver este problema.

Algoritmo de Grover

GmUna de las muchas ventajas que tiene una computadora cuántica sobre una computadora clásica es su velocidad superior de búsqueda en las bases de datos. El algoritmo de Grover demuestra esta capacidad. acelerando  cuadráticamente un problema de búsqueda no estructurada y esto puede utilizarse como una  subrutina general para obtener mejoras en el tiempo de ejecución cuadrático para una variedad de diferentes algoritmos, utilizando la amplificación de amplitud.

Aplicando Grover al problema de búsqueda planteado anteriormente podemos encontrar el elemento seleccionado en un O($\sqrt{ n }$) utilizando los elementos $O_f$ y la amplificación de amplitud.

Componentes del algoritmo de Grover:

  • Crear una superposición de todos los estados bases computacionales $ 2^n $ aplicando la compuerta H en cada qubit partiendo del estado $ \big|0\big>^{⊗_n} $ donde el exponente $⊗_n$  significa que se tiene un producto tensorial de los estados de n qubits.
  • Se aplica el operador Oracle para marcar el elemento seleccionado dentro de los $ 2^n $ elementos, el Oracle aplica el coeficiente de -1 a cada uno de los elementos seleccionados.
  • Se aplica el operador Difusor el cual invierte la amplitud de todos los elementos sobre la amplitud promedio.

Con todos estos componentes y aplicando los operadores Oracle y Difusor ($\sqrt{ N = 2^n }$) veces el algoritmo permitirá determinar exitosamente los elementos que fueron marcados por el operador Oracle con una alta probabilidad.

Construcción del Oracle

Recordemos que la acción del operador Oracle es agregar la fase de -1 a todos los estados que representan al elemento seleccionado, dejando a los otros estados sin cambios.

Una forma fácil de implementar el operador Oracle es creando la matriz identidad de todos los n qubits las dimensiones de la matriz serían $2^n$  y luego se cambian estos elementos de la diagonal a -1 que corresponden al elemento seleccionado, luego se convierte esta matriz unitaria a un operador.

Se creará una función operador_oracle el cual tendrá dos argumentos; el primer argumento n dará el número de qubits del circuito cuántico, el segundo argumento elemento_select es la lista de índices cuyos elementos serán marcados por el operador_oracle con la fase de -1, usando estas entradas se creará una matriz identidad de  $2^n$ x $2^n$ y se aplicará la fase de -1 a los elementos de la diagonal dados por la posición del elemento_select.

Construcción del Difusor

  • Se definirá al difusor cuyo efecto es reflejar todas las amplitudes sobre la amplitud media, para realizarlo llamamos a el operador_oracle con solo el estado cero $ \big|0\big>^{⊗_n} $ como el elemento marcado e intercalarlo entre las puertas Hadamard ya aplicadas a todos qubits.

Número óptimo de llamadas

  • Para terminar el algoritmo se necesita determinar cuántas llamadas r serán necesarias para encontrar el elemento seleccionado con lo cual tenemos:

r = $ \left \lfloor \frac{ \pi} {4} \sqrt{ \frac{n} {m} } \right \rfloor $ donde k es el número de elementos seleccionados y  significa redondear hacia abajo el número.

Ejemplo: consideremos el uso de 6 qubits se tendría (N = $2^6$) y dos elementos seleccionados    (K = 2) dando como resultado que (r = 4), por lo tanto el Oracle y el Difusor se aplicaran 4 veces.

Complejidad del tiempo:

O($\sqrt{ \frac{n} {m} }$)

b10

from qiskit import *
from qiskit.quantum_info import Operator
from qiskit import Aer, execute
from qiskit.visualization import plot_histogram
from qiskit import QuantumCircuit
import numpy as np

def phase_oracle(n, indices_to_mark, name = 'Oracle'):
    
    # create a quantum circuit on n qubits
    qc = QuantumCircuit(n, name=name)
    # create the identity matrix on n qubits 32
    oracle_matrix = np.identity(2**n)
    # add the -1 phase to marked elements
    for index_to_mark in indices_to_mark:
        oracle_matrix[index_to_mark, index_to_mark] = -1
    # convert your matrix (called oracle_matrix) into an operator, and add it to the quantum circuit
    qc.unitary(Operator(oracle_matrix), range(n))
    
    gate = qc.to_gate()
    gate.name = "oracle"
    
    return gate

def diffuser(n):
    
    # create a quantum circuit on n qubits
    qc = QuantumCircuit(n, name='Diffuser')    
    # apply hadamard gates to all qubits
    qc.h(range(n))
    # call the phase oracle applied to the zero state
    qc.append(phase_oracle(n, [0]), range(n))
    
    # apply hadamard gates to all qubits
    qc.h(range(n))
    
    gate = qc.to_gate()
    gate.name = "difusor"
    
    return gate

def Grover(n, indices_of_marked_elements):
    
    # Create a quantum circuit on n qubits
    qc = QuantumCircuit(n)    
    # Determine r
    r = int(np.floor(np.pi/4*np.sqrt(2**n/len(indices_of_marked_elements))))
    print(f'{n} qubits, basis states {indices_of_marked_elements} marked, {r} rounds')
    
    # step 1: apply Hadamard gates on all qubits
    qc.h(range(n))
    
    # step 2: apply r rounds of the phase oracle and the diffuser
    for i in range(r):
        qc.append(phase_oracle(n, indices_of_marked_elements), range(n))
        qc.append(diffuser(n), range(n))
        
    # step 3: measure all qubits
    #qc.measure(range(n), range(n))
    
    gate = qc.to_gate()
    gate.name = "G"
    
    return gate

########################################################
#Main
#########################################################
n = 6
marked =  [45,40]

addr = QuantumRegister(n,'dir')

c = ClassicalRegister(n)
qc = QuantumCircuit(addr,c)

qc.append(Grover(n,marked),addr[:])

qc.measure(range(n), range(n))

qc.draw()

5) Discusión

Tomando la complejidad del tiempo big O o cota superior de los algoritmos de búsqueda clásica encontramos que:

Búsqueda

BigO

Lineal o Secuencial

O(n)

Binaria o dicotómica

O(log(n))

Exponencial o al galope

O(log i)

Interpolación

O(n)

Salto

O(√n)

Ternaria

O(log n)

transformación de claves o Hash

O(1)

List

O(n)

Diccionarios

O(1)

Donde la complejidad del tiempo de los algoritmos de búsqueda por Hash y los diccionarios tienen un bigO de O(1) siendo estos los más rápidos.

 Y tomando la cota superior del algoritmo de búsqueda cuántica obtenemos:

Búsqueda

BigO

Grover un solo elemento

O($\sqrt{ n }$)

Grover varios elementos

O($\sqrt{\frac{n} {m}}$)

Con lo cual la complejidad del tiempo del algoritmo de Grover brinda una reducción de  para la búsqueda de un solo elemento y  para la búsqueda de varios elementos consiguiendo con esto una reducción de la mitad del tiempo respecto a los algoritmos de búsqueda clásica.

6) Conclusiones

Los algoritmos de búsqueda clásica permiten realizar búsquedas con una cota superior de O(n)  los cuales dependen de la cantidad de datos que conforman el conjunto de datos por lo tanto si el tamaño de este conjunto de datos es muy grande los tiempos de búsqueda serán proporcionales a este conjunto de datos, por lo que tener una opción cuántica como el algoritmo de Grover proporcionaría una muy buena respuesta a estos tiempos de búsqueda que son muy altos.

Búsqueda

BigO

Lineal o Secuencial

O(n)

Binaria o dicotómica

O(log(n))

Exponencial o al galope

O(log i)

Interpolación

O(n)

Salto

O(√n)

Ternaria

O(log n)

Transformación de claves o Hash

O(1)

List

O(n)

Diccionarios

O(1)

Grover un elemento

O($\sqrt{ n }$)

Grover varios elementos

O($\sqrt{\frac{n} {m}}$)

Basándonos en estas cotas superiores se mira de manera muy fácil que el algoritmo cuántico  proporciona la mitad del tiempo en buscar uno o varios elementos con respecto a los algoritmos de búsqueda clásica, además si el tamaño del conjunto de datos es mayor se tendrá un rendimiento mejor con el algoritmo mecánico.

Por consiguiente no es descabellado ni prematuro invertir tiempo tanto las empresas como cualquier persona en aprender estos nuevos conceptos de la computación cuántica ya que permitirán con el tiempo crear nuevos y más sofisticados algoritmos que permitirán crear innovadoras soluciones cuánticas a problemas del diario vivir, siendo este uno de los momentos indicados para embarcarse en este nuevo mundo de la computación cuántica.

Referencias:

  1. https://wiki.python.org/moin/TimeComplexity
  2. https://qiskit.org/textbook/ch-algorithms/grover.html
  3. http://ual.dyndns.org/biblioteca/Estructura%20de%20Datos/Pdf/09%20Metodos%20de%20busqueda.pdf
  4. https://pixabay.com/es/vectors/viruta-icono-micro-procesador-1710300/
  5. https://pixabay.com/es/vectors/lupa-b%C3%BAsqueda-ampliaci%C3%B3n-zoom-1083378/
  6. https://github.com/jj-13/qh/blob/main/AlgoritmosBCQ.ipynb

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *