Una de las primera pruebas que hice con ChatGPT fue ver si estaba al tanto de la computación cuántica y Qiskit. Así que, en un primer intento pregunté: «Could write a program in Python using qiskit to look for prime numbers?» Lo hice en inglés, y habría que ver si obtendría la misma respuesta si lo hago en español (cosa de otro post). En su respuesta, chatGPT señala:

• Although searching for prime numbers is not typically done using quantum computers, we can still use Qiskit to demonstrate the implementation. Keep in mind that for larger prime numbers, classical methods are more efficient.
• Here’s an example program that uses the Quantum Fourier Transform (QFT) algorithm, which is one of the building blocks of Shor’s algorithm for factoring large numbers.

from qiskit import QuantumCircuit, transpile, Aer, execute
from qiskit.visualization import plot_histogram

def is_prime(n):
    """Check if a number n is prime."""
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def prime_search(n):
    """Search for prime numbers up to n using Qiskit."""
    num_qubits = n.bit_length()
    circuit = QuantumCircuit(num_qubits, num_qubits)

    for i in range(num_qubits):
        circuit.h(i)

    for i in range(num_qubits):
        circuit.measure(i, i)

    backend = Aer.get_backend('qasm_simulator')
    job = execute(circuit, backend, shots=1)
    result = job.result()
    counts = result.get_counts()

    primes = []
    for binary_str in counts:
        number = int(binary_str, 2)
        if is_prime(number):
            primes.append(number)

    return primes

n = 20  # Search for primes up to 20
primes = prime_search(n)
print("Prime numbers found:", primes)

La generación del programa va acompañada de una descripción que destaca:

• In this program, we define two functions: is_prime(n) checks if a number n is prime using a classical algorithm, and prime_search(n) performs the prime number search using Qiskit.
• In the prime_search function, we create a quantum circuit with a number of qubits equal to the bit length of n. We apply Hadamard gates (circuit.h(i)) to put all qubits in a superposition of states. Then, we measure the qubits (circuit.measure(i, i)) to collapse the superposition and obtain classical outputs.
• We use the QASM simulator backend provided by Qiskit (Aer.get_backend('qasm_simulator')) to execute the circuit once (shots=1). After obtaining the measurement results, we convert the binary strings to integer numbers and check if each number is prime using the is_prime function. The prime numbers found are stored in the primes list and returned.
• In the example above, the program searches for prime numbers up to 20. You can modify the value of n to search for primes up to a different number.
• Please note that for larger prime numbers, classical algorithms like the Sieve of Eratosthenes or the Miller-Rabin primality test are more efficient. Quantum computers have other applications where they excel, but prime number searching is not typically one of them.

El último punto es el que me llamó la atención pues lo que uno lee sobre las computadoras y el cómputo cuántico es que son más rápidas que las clásicas y aprovechan la superposición cuántica para trabajar en paralelo (aunque no si éste sea el término apropiado o si debería hablar de un «trabajo superpuesto»). Un poco decepcionado por la respuesta, traté de hacer un refinamiento: «How could you modify your answer to use the quantum computer to test the primality and not to just generate the numbers?» La respuesta fue (resalto lo importante):

I apologize for the confusion in my previous response. Currently, there is no known efficient quantum algorithm specifically designed for testing the primality of numbers. Prime factorization algorithms, such as Shor’s algorithm, can indirectly determine primality by finding the factors of a composite number.

If you want to test the primality of a number using a quantum computer, you can employ quantum algorithms for prime factorization, like Shor’s algorithm, and check if the number has any non-trivial factors. However, it’s important to note that Shor’s algorithm requires a large-scale, fault-tolerant quantum computer, which is not yet available.

Nevertheless, I can provide you with an example program that demonstrates how to use Qiskit to factorize a composite number using Shor’s algorithm. This can indirectly determine if the number is prime or composite.

y el código:

from qiskit import QuantumCircuit, transpile, Aer, execute
from qiskit.aqua import QuantumInstance
from qiskit.aqua.algorithms import Shor

def is_prime(n):
    """Check if a number n is prime."""
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def prime_factorization(n):
    """Factorize a composite number n using Shor's algorithm."""
    if is_prime(n):
        return [n]

    backend = Aer.get_backend('aer_simulator')
    quantum_instance = QuantumInstance(backend)

    shor = Shor(quantum_instance=quantum_instance)
    factors = shor.factorize(n)

    return factors

n = 35  # Number to factorize
factors = prime_factorization(n)
print("Prime factors:", factors)

así como de su explicación:

In this program, we define the is_prime(n) function to check if a number n is prime using a classical algorithm. The prime_factorization(n) function utilizes Qiskit’s Aqua module to perform prime factorization using Shor’s algorithm.

We first check if the input number n is prime using the is_prime function. If it is prime, we return [n] as the factorization result.

If n is not prime, we set up the backend to use Qiskit’s Aer simulator (Aer.get_backend('aer_simulator')) and create a QuantumInstance object. We then initialize the Shor algorithm with the quantum instance.

We call shor.factorize(n) to run Shor’s algorithm on the composite number n and obtain the factors. The factors are returned as a list.

In the example above, the program factorizes the number 35. You can modify the value of n to factorize a different composite number.

Please keep in mind that the efficiency and feasibility of prime factorization using quantum computers heavily depend on the size of the number to be factorized and the availability of a large-scale, fault-tolerant quantum computer.

Una búsqueda en Google por algoritmos cuánticos de primalidad (términos «quantum», «algorithm», «primality») devuelve, al momento de escribir esto 288,000 resultados (muchos repetidos) pero deja ver que hay mucho trabajo al respecto. Si, como dice ChatGPT no hay un algoritmo conocido que valide la primalidad de un número es algo que no puedo corroborar, pero es un hecho entonces que este chatbot no tiene una capacidad inventiva