Review Week — 2 & Shor’s Algorithm
#Quantum30 Cohort 04
Day 14
Date: 31st March, 2024.
In the 2nd week of the #quantum30 challenge, we mull over the topics:
1. Principles of Quantum Computing — III : Quantum Circuit and Measurement
"..A quantum computer takes a quantum state as the input and controls the state to increase the probability of finding the answer in the output state for the computation. For instance, Shor’s Algorithm manipulates the quantum states to find prime factors of a large number. A significant difference between a classical (electronic) circuit and a quantum circuit is the intermediate states in the circuits.
2. Quantum Gate and Reversibility
"The basic operation to manipulate an input state for a quantum circuit is called Quantum Gates. Each gate operation can be mathematically represented with a matrix.”
3. No-Cloning Theorem and Entangled State
“..When we consider Quantum Mechanics, the replication of an arbitrary quantum state is not possible.
This restriction is known as the No-Cloning Theorem....where the individual states of qubits are intimately related to one another, is called the entangled state.”
5. Quantum Computations
"..As universal gates allow us to design an arbitrary quantum circuit, the n qubits can be used as the input for a quantum circuit, which performs an arbitrary computation."
6. Grover’s Algorithm
"..Imagine searching a phone book for a specific name. A traditional algorithm would check each entry sequentially until it finds a match. Grover’s algorithm, however, can explore all entries simultaneously, offering a dramatic advantage for larger datasets."7. The Idea of Grover’s Algorithm
“..For example, when a database has 10⁶ items (e.g., for biometric authentications), Grover’s algorithm only needs 1000 steps to search an item while a classical algorithm needs 50,000 steps (Morsch, 2008).”
Shor’s Algorithm
Peter Shor, in 1994 demonstrated that a quantum computer could be used to factor a large integer in polynomial time (Shor, 1994).
Get Bushra Haque’s stories in your inbox
Join Medium for free to get updates from this writer.
His algorithm attracted a great deal of attention from security agencies since, if a quantum computer is developed, it can break the RSA encryption algorithms.
RSA encryption is a widely used public-key encryption algorithm.
It relies on mathematically difficult problems like prime factorization to ensure data security. Public and private keys are used for encryption and decryption, respectively. The public key is shared for anyone to encrypt messages, while the private key is kept secret to decrypt them. This ensures secure communication as only the intended recipient with the private key can decrypt the message.
Shor’s Algorithm consists of classical parts and quantum parts.
To understand how quantum computation is utilised with the classical computation in Shor’s algorithm, we need to understand the RSA encryption algorithm, with the help of an illustration given below:
In order to break the security of the RSA, an eavesdropper (Eve), needs to find the private key d. Since, N and e are in public, all she has to do is to find p and q from N to compute (19).
However, there is no classical algorithm that can factor a large integer in polynomial time.
So, the security of the RSA encryption relies on the difficulty of factoring a large integer.
#Quantum30
#QuantumComputing
#QuantumAlgorithm
#RSAencryption
#Shor’sAlgorithm
