How to Implement Shor’s Algorithm on Dynex

This guide provides a step-by-step walkthrough of implementing Shor’s algorithm, a quantum algorithm designed to factorize an integer NNN efficiently. Shor’s algorithm is renowned for its potential to break widely used cryptographic systems by finding the period (or order) of a modular function, which is the key to factorization.

Full source code

1. Introduction to Shor’s Algorithm

Shor’s algorithm leverages quantum computation to solve the integer factorization problem exponentially faster than classical algorithms. The core idea is to find the period of the function axmod Na^x \mod NaxmodN, which directly leads to the factors of NNN. This period-finding task is where quantum mechanics provides a significant advantage, using quantum parallelism and interference.

Why Shor’s Algorithm Matters: Shor’s algorithm is particularly important in the context of cryptography. RSA encryption, one of the most widely used cryptographic protocols, relies on the difficulty of factoring large integers. Shor’s algorithm, if executed on a sufficiently powerful quantum computer, could efficiently break RSA encryption by factoring the large integers it uses.

2. Setting Up the Quantum Circuit

The quantum circuit is designed to simulate the modular exponentiation function and find its period.

• Initialize Qubits: The circuit initializes qubits based on the number NNN to be factorized and the base aaa.
• Hadamard Gates: Hadamard gates are applied to prepare the qubits in a superposition state, allowing the quantum computer to explore all possible periods simultaneously.

import pennylane as qml
from pennylane import numpy as np

a = 12
N = 35
params = [N, a]
wires = 10 + int(np.ceil(np.log2(N)))  # 10 estimated qubits for computing the period (r) 
def _GetU_NA(a, N):
    nQ = int(np.ceil(np.log2(N)))
    uNA = np.zeros([2 ** nQ, 2 ** nQ])
    for k in range(N):
        uNA[(k * a) % N, k] = 1
    for extra in range(N, 2 ** nQ):
        uNA[extra, extra] = 1
    return uNA

3. Constructing the Modular Exponentiation Circuit

The core of Shor’s algorithm is the modular exponentiation operation, which is implemented using controlled unitary operations.

• Controlled Unitary Operations: The circuit applies controlled unitary operations that encode the modular exponentiation into the quantum state.
• Quantum Fourier Transform (QFT): After the modular exponentiation, the QFT is applied to find the period of the function.

def ShorsCircuit(params):
    N, a = int(params[0]), int(params[1])
    uNA = _GetU_NA(a, N)
    nEstimateQUBITS = 10
    nTargetQUBITS = int(np.ceil(np.log2(N)))
    tQ = nEstimateQUBITS + nTargetQUBITS
    estWIRES = range(nEstimateQUBITS)
    tWAIRES = range(nEstimateQUBITS, tQ)
    qml.PauliX(wires=tWAIRES[-1])
    for wire in estWIRES:
        qml.Hadamard(wires=wire)
    for i, wire in enumerate(estWIRES):
        power = 2 ** (nEstimateQUBITS - i - 1)
        qml.ControlledQubitUnitary(qml.math.linalg.matrix_power(uNA, power), 
                                   control_wires=[wire], 
                                   wires=tWAIRES)
    qml.adjoint(qml.QFT)(wires=estWIRES)
    return qml.sample()

Example: Shor’s algorithm circuit

4. Post-Processing the Quantum Results

After running the quantum circuit, classical post-processing is required to extract the period and ultimately factorize NNN.

• Fraction to Float Conversion: The measured quantum output is converted from a binary fraction to a float, representing the phase.
• Period Determination: The classical algorithm estimates the period from the phase and uses it to find the factors of NNN.

def Fraction2Float(sample):
    return np.sum([int(sample[bit]) / 2 ** (bit + 1) for bit in range(len(sample))])

def Phase2Order(phase, max_denominator):
    sR = Fraction(phase)
    order = sR.limit_denominator(max_denominator).denominator
    if order % 2 == 0:
        return order
    else:
        return order + 1  # Get only even Period (correction)

5. Running Shor’s Algorithm

To run Shor’s algorithm, initialize the circuit with the integer NNN to be factorized. The circuit will return the factors of NNN if successful.

N = 35
p, q = SimpleShorsAlgo(N)
print(f"Factorization of {N}: {p} and {q}")

Conclusion

Shor’s algorithm is a powerful demonstration of quantum computing’s potential to solve classically intractable problems. By efficiently factorizing integers, it poses a significant challenge to current cryptographic systems. The implementation of Shor’s algorithm on a quantum computer illustrates the practical application of quantum mechanics in real-world problems, particularly in the field of cryptography.

Why Shor’s Algorithm on Dynex Matters: Executing Shor’s algorithm on the Dynex neuromorphic quantum computing cloud, with its support for quantum circuits, showcases the platform’s capability to handle complex quantum algorithms. This implementation not only demonstrates the power of quantum computing but also serves as a critical testbed for exploring quantum advantage in cryptographic applications.

About Dynex

Dynex is the world’s only accessible neuromorphic quantum computing cloud for solving real-world problems, at scale. The company began as an informal project in September 2020 in collaboration amongst a community of extraordinary minds and quickly evolved into a technological leader ready to scale into global markets. The Dynex n.quantum computing cloud performs quantum computing based algorithms without limitation, executing calculations with unparalleled speed and efficiency, surpassing usual quantum computing constraints. Dynex is dedicated to pushing the boundaries of technology to create sustainable, secure, and innovative solutions that address complex challenges and drive progress. For more information, visit dynex.co.