Cryptography
A quantum computer with 300 qubits for example, can represent a superposition of up to 2 300 states where each state is equivalent of 300 bits representing 0s and 1s. Any calculation performed through the quantum gates therefore operates on 2 300 states so any operation that would require 2 300 rounds of operations on a normal computer requires only one round of operation on a quantum computer. This greatly reduces the time complexity of every operation that occurs on a quantum computer. Peter Shor, who was a mathematician working for AT&T, published Shor’s algorithm that was destined to break an RSA algorithm. The algorithm consists of 3 parts: the first is performed on a normal computer in polynomial time. However, the second part needs to make use of the quantum circuits to perform quantum computation needed to find the value needed for the third part, which allows you to work out the prime factors of the integer on a normal computer. The first part of the algorithm is transforming the problem of the prime factorization into a solvable, equivalent problem which is the period of a modular operation (for example f(x) = f(x + 10), the function repeats itself every 10 values, so it has a period of 10). This can be done on a normal computer. However, due to the time it would take, it would be pointless. Shor was able to prove that the second part of his algorithm using a quantum computer could calculate this period and reduce the time complexity exponentially, and thus a normal computer could use it to find the prime factors o f any integer. If n is the quantity of digits of a number, Shor’s algorithm can factor that number in n 10 seconds. For example, a two-digit number would take 2 10 or 1024 seconds. A normal computer can factor the number in 10 n seconds, so for a two-digit number it would take 100 seconds, which at a low digit number is quicker than Shor’s algorithm. However, at a greater length of digits, Shor’s algorithm factor izes the same number millions of times faster. This means that the power of Shor’s algorithm and th e use of enough qubits will be able to break RSA encryption. In conclusion, quantum computing poses a threat to the security of cryptographic algorithms such as RSA and ECC which are the foremost encryption methods used today. However, the number of qubits needed in a quantum computer to crack a key is extraordinarily large. Similarly, to implement Shor’s algorithm, you need to have a quantum computer with relatively little error. Google’s Sycamore computer has about 50 qubits, which is minute compared to the number of qubits needed to break a 2048-bit RSA key. This would take a 20 million qubit computer 8 hours. Many researchers believe that it will take about a decade or two to reach this point. The biggest drawback of quantum computing is maintaining the large number of qubits to prevent the distortion of a quantum state which is an expensive physical limitation. This does pose a serious threat to the security of our data transmission methods in the future. However, at this moment our methods of encryption are secure enough, and, if quantum computers with enough qubits are ever built, thenmodern day cryptography will be rendered useless and every message will be able to be decrypted with ease. This will pose further threats to economies and governments when secret information is stolen or uncovered to the public. To combat this potential cryptographic apocalypse, it may be necessary to use quantum computers to encrypt the information and protect it from quantum cracking.
185
Made with FlippingBook Digital Publishing Software