Factoring 77 with Shor's Algorithm (Simplified) on IBM's 127-Qubit Quantum Computer

Code:

# Imports
import numpy as np
import pandas as pd
import json
import logging
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister, transpile
from qiskit_ibm_runtime import QiskitRuntimeService, Session, SamplerV2
from qiskit.circuit.library import QFT
from qiskit.visualization import plot_histogram
import matplotlib.pyplot as plt

# Logging 
logging.basicConfig(level=logging. INFO, format='%(asctime)s - %(levelname)s - %(message)s')
logger = logging.getLogger(__name__)

# Calibration file path
calibration_file = '/Users/Downloads/ibm_brisbane_calibrations_2025-01-10T15_20_30Z.csv'

# Load calibration data
def load_calibration_data(file_path):
    logger. info("Loading calibration data from %s", file_path)
    calibration_data = pd. read_csv(file_path)
    calibration_data.columns = calibration_data.columns.str.strip()  # Strip spaces
    logger. info("Calibration data loaded successfully")
    return calibration_data

# Parse calibration data and select best qubits
def select_best_qubits(calibration_data, num_qubits):
    logger. info("Selecting the best qubits based on T1, T2, and error rates")
    sort_columns = ['√x (sx) error', 'T1 (us)', 'T2 (us)']
    
    # Columns 
    for col in sort_columns:
        if col not in calibration_data.columns:
            raise KeyError(f"Column '{col}' not found in calibration data. Check your CSV file.")
    
    sorted_qubits = calibration_data.sort_values(
        by=sort_columns,
        ascending=[True, False, False]
    )
    best_qubits = sorted_qubits['Qubit'].head(num_qubits).tolist()
    logger. info("Selected qubits: %s", best_qubits)
    return best_qubits

# IBMQ 
service = QiskitRuntimeService(
    channel='ibm_quantum',
    instance='ibm-q/open/main',
    token='YOUR_IBMQ_API_KEY_O-`'  
)

backend_name = 'ibm_brisbane'
backend = service.backend(backend_name)
logger. info("Backend selected: %s", backend_name)

# Shors circuit
def create_shors_circuit(n, a, num_qubits):
    logger. info(f"Creating Shor's circuit for factoring {n} with base {a} and {num_qubits} qubits")
    qc = QuantumCircuit(num_qubits, num_qubits)

    # Apply Hadamard gates
    for i in range(num_qubits // 2):
        qc.h(i)

    # Apply QFT on the first half
    qc.append(QFT(num_qubits // 2).to_gate(), range(num_qubits // 2))

    # Measurement
    qc.measure(range(num_qubits // 2), range(num_qubits // 2))
    return qc

# Transpile / optimize 
def optimize_circuit(qc, backend):
    logger. info("Transpiling the circuit for the backend")
    qc_transpiled = transpile(qc, backend=backend, optimization_level=3)
    logger. info("Circuit transpilation complete")
    return qc_transpiled

# Run Shors 
def run_shors_experiment(n, a, num_qubits, calibration_data, shots=16384):
    logger. info(f"Running Shor's algorithm to factor {n} with base {a}")

    # Select best qubits based on calibration data
    best_qubits = select_best_qubits(calibration_data, num_qubits)

    # Create circuits
    qc = create_shors_circuit(n, a, num_qubits)
    qc_transpiled = optimize_circuit(qc, backend)

    # Execute 
    with Session(service=service, backend=backend) as session:
        sampler = SamplerV2(session=session)
        logger. info("Executing the circuit on the backend")
        job = sampler. run([qc_transpiled], shots=shots)
        job_result = job.result()

        # Data_bin 
        data_bin = job_result._pub_results[0]['__value__']['data']

        # Parse data 
        bit_array = data_bin['c']  # Extract the BitArray object
        counts = bit_array.get_counts()  # Use get_counts method to extract counts

        # Results
        result_file_path = f'/Users/Documents/Shors_77_0.json'
        with open(result_file_path, 'w') as f:
            json.dump(counts, f, indent=4)
        logger. info(f"Results saved to {result_file_path}")

        # Visual 
        plot_histogram(counts)
        plt.title(f"Results for Shor's Algorithm (n={n})")
        plt. show()

        return counts

# Calibration
logger. info("Loading calibration data")
calibration_data = load_calibration_data(calibration_file)

# Parameters
n = 77
a = 2
num_qubits = 32  

# Run
result = run_shors_experiment(n, a, num_qubits, calibration_data)

Code to Test Results to Find Factors
# Imports
import json
import numpy as np
from math import gcd

# Load the results from Json 
file_path = '/Users/Documents/Shors_77_0.json'
with open(file_path, 'r') as file:
    data = json.load(file)

# Convert binary strings to decimal
counts = {int(key, 2): value for key, value in data.items()}

# Sort by frequency to analyze the most likely results
sorted_counts = sorted(counts.items(), key=lambda x: x[1], reverse=True)

# Display the top results 
print("Top results (decimal):")
for result, count in sorted_counts[:10]:
    print(f"Value: {result}, Count: {count}")

# Parameters
n = 77 
a = 2   
observed_values = [key for key, _ in sorted_counts[:10]]

# Compute candidate periods and factors
for observed in observed_values:
    r = observed  # Period candidate
    if r != 0:
        # Calculate the factors using the observed period
        factor1 = gcd(a**(r//2) - 1, n)
        factor2 = gcd(a**(r//2) + 1, n)
        print(f"Observed: {observed}, Factors: {factor1}, {factor2}")

        # Verify if these are valid factors
        if factor1 * factor2 == n:
            print(f"Valid factors found: {factor1}, {factor2}")

# End