Trudeau, Shor and a lot of qubits
When Justin Trudeu’s speech explaining Quantum Computing and qubits showed up on my news feed, I initially thought that it was because of my recent searches on web regarding the same. However when it went viral and more people started sharing the same, I realized that it is a global phenomenon. Even the very small advances in Quantum Computing have been heavily hitting news desks recently. The importance given to the same isn’t totally unreasonable even though the technology doesn’t look so feasible in the near future. It is believed that if we are able to make a stable Quantum Computing system which can hold sufficient number of qubits, it can not only make computing multifold faster but also could crash the most widely used security systems which rely on Public Key Cryptography. This article intend to detail the Shor’s algorithm — a Quantum Computing algorithm which can resolve one way mathematical functions such as Discrete Logarithm, Prime Factorization & Elliptic Curve Discrete Logarithm calculations efficiently. Even though the intention of the article was to explain the concept with the least possible number of mathematical equations, I am unsure how far I have succeeded in it. However I believe that readers who are not familiar with the complex math behind the quantum computing will at least get a fair idea on the steps behind the same.
As it is not recommended to jump directly into a complex quantum algorithm, I would start with a primer on the need for Quantum Computing, Basics of Quantum Mechanics and a few words on math behind Public Key Cryptographic algorithms.
Need for Quantum Computing
Necessity is apparently the mother of all inventions. Inventions which aren’t necessary for the time wouldn’t survive. Discontinued Google glass can serve as a good example here. So what apparently is the need for quantum computing? To understand that we have to rewind a bit to the famous Moore’s law. Moore’s law predicted a proportional increase in number of transistors per chip with time. All of our gadgets run on processors which has integrated thousands of transistors to a small silicon chip. But recently the chip manufacturers have been facing a bottle neck in integrating more transistors per chip as the transistor size has already reached nano scale. The atomic radius of a Silicon atom is 117.6 pico meter or 0.1176 nm. Even though it is predicted that there would be technologies which would allow us to create 7 or even 5 nm transistors, at some point in time getting smaller is going to get affected by a quantum mechanical phenomenon known as Quantum Tunneling.
Since this physical limitation in getting smaller can stall the growth of computing, scientists had to think of an alternative. The idea started sprouting when Paul Benioff described quantum mechanical Hamiltonian models of computers in 70’s. In 1980, when Yuri Manin proposed an idea of quantum computing, the world started listening. The basic idea was to use qubits instead of conventional bits as qubits could carry more data due to the uncertainties associated with quantum states.
Basics of Quantum Computing
This will cover only the very basic quantum mechanical phenomena which are needed to explain Quantum computing or Shor’s algorithm in particular. Those who want to learn more about the same may explore many good YouTube Videos and research papers. I will list a few related literature at the end.
In conventional digital computing, calculations are done on bits. A bit can have either of the two values — 0 or 1 characterized by high or low voltages/current or whatever parameter the corresponding system measures. So the number of values x bits can possibly have is 2^x. That is, 2 bits can have 2^2 = 4 possible values as shown in the following figure. However at a time, they can store only one value.
Quantum computing systems on the other hand utilizes the amazing quantum mechanical phenomena called ‘superposition’ of any two level quantum system. Electron spin system which has positive spin [+1/2] or a negative spin [-1/2] or a single photon whose polarization can either be vertical or horizontal are the common examples. Like the Schrodinger’s cat, which was dead and alive simultaneously while inside the box, quantum states are also uncertain before they are measured. The moment we measure the quantum state of a particle, the quantum state assumes one of the probable states. It is said that a qubit [which is apparently the quantum state of a photon/electron] can have both the possible values simultaneously until they are measured. From the macro world perspective, where the flip –flops can only store one of the two binary values at a time, this might seem a little difficult to comprehend. But at quantum level, classical physical laws are irrelevant.
As a result of the above while a conventional bit could have only one value of the possible two values at a time, a qubit can store 0 and 1 simultaneously. 2 qubits could store 4 values simultaneously, 3 could store 8 values simultaneously and so on. This would increase the computational capabilities multifold. While on a first look this might look complicated yet simple, performing calculations with a superposed quantum system is still tricky.
Qubit Representation
While conventional bits are represented by 0 or 1, qubit representation isn’t that flexible as we have to consider superposition of two distinct states. The best way to denote qubit is as a linear combination of two distinct state vectors |0> & |1>. The vector representation of a qubit in superposition would be as follows.
|v>= a.|0> +b.|1>
Where a and b are the quantum probabilities of system collapsing into |0> or |1> respectively if the qubits are measured. It is to be noted that a and b are complex numbers.
|v> is also a unit vector. So the magnitude of superposed qubit vector ,
mag(|v>)=√(a^2+b^2 )
= 1
Which implies the probability of the qubit being one of the definite states would be the magnitude of its complex co efficient.
ie; the real probability of qubit being |0> would be the magnitude of complex coefficient a = a2
So the graphical representation on X-Y plane would be as follows. [This is just a representative diagram to make it simple. Qubits are usually not represented in x-y plain as they have complex co efficient. ]
Even though the representation consider a base with |0> & |1>, due to vector properties it should also be noted that qubit vector |v> can be represented by any orthonormal basis.
To get a holistic view of quantum computing, we need to understand how qubits are represented using Bloch spheres.
|Ψ> is the qubit vector where |0> and |1> are the definite states |Ψ> can collapse to when the same is measured.
Qubit registers
A lone qubit is as trivial as an empty wallet as we cannot perform any interesting calculations with the same. To perform calculations quantum bit registers which can hold multiple qubits are necessary. So far there exists qubit registers which can hold 5 bits and expanding the size beyond that is the major bottleneck practical quantum computing systems are facing.
Mathematical representation of qubit registers also are a bit different from conventional binary representation. Similar to vector qubit representation registers are also expressed as vector combination. An n qubit register is represented by a superposition of all 2n possibilities.
For example a 2 qubit register would be represented as follows
x⃗ = a. |00> + b. |01> + c. |10> + d. |11>
Where a, b, c and d are quantum probabilities of |00>, |01>, |10> and |11> respectively. And similar to qubits, the probability of each qubit in the register would be the square of coefficient.
Quantum Logic Gates
For many of the conventional logic gates, there exists no equivalent quantum gates. However there are a few gates which are only applicable to qubits.
Measurement Gate: This gate collapses a superposed qubit into one of the finite states according to the probability co efficient.
Swap Gate: It takes two qubits as inputs and swap between the qubits.
Pauli X Gate: Flips the qubit in the opposite direction. |1> to |0> and vice versa and a superposed qubit to a superposition in the opposite direction.
Hardmard Gate: Takes any qubit in a finite state and convert it to a right superposed qubit. [With equal probability to collapse to |1> or |0> when measured.
Calculations on a conventional digital computer with logic gates
To understand how mathematical operations can be faster in Quantum computing systems, we need to understand how a conventional computing system performs mathematical calculations. All the calculations are the result of basic arithmetic operations addition and subtraction. Repeated addition would result in multiplication, repeated multiplication in exponentiation and so on. A traditional system uses logic gates to perform these calculations. For example a classic bit to bit addition is performed with a half adder which uses a single XOR gate and an AND gate. XOR gate takes two inputs A & B and gives the output S & C as shown in the following logic tables.
Calculation with Quantum Logic Gates
It is clear that different values of inputs will give different results at the output. Interestingly in quantum computing systems all the inputs will superpose both 0 and 1 at the same time. The quantum gates will preserve the superposition and the results at S and C will also be superposed. Ultimately only one of those superposed values can be measured at the output. Since when we measure the superposed states will tend to assume one of the finite values 0 or 1, it is possible that we may not get the result we want. But, it is also observed that probabilities can be assigned to qubits [probability of being 1 or 0] and by efficiently manipulating the probabilities desired output can be obtained. By now you might have figured out why this wouldn’t particularly increase the speed of a simple arithmetic operation like addition. However this can be used to figure out the solutions of complex mathematical problems where we have to select only one correct value from enormous number of possibilities. Integer factorization & Quantum database search are examples.
Another unintuitive quantum property which is made use of here in such computing systems is quantum entanglement. Quantum entanglement in simple words is the property of close association of two qubits. A state change in one of the pairs would affect the other one spontaneously no matter how distant they are physically. Scientists are still unsure about the reason for quantum entanglement, but that hasn’t stopped the world from researching ideas such as quantum teleportation. Any manipulation of the probability of a state of one qubit will also affect the other one in the pair due to quantum entanglement.
While it is pretty much obvious that Quantum Computing is not particularly useful in calculations which require corresponding outputs for given inputs where would they make sense? They would be an excellent choice where one valid selection has to be made from a number of possibilities. Consider a search operation. A program will have to iteratively look for the search value in an entire database to get the result in a classical computer. But guess what, the entire process can be superposed to a single step using a quantum computer and the value at the output can be measured.
Shor’s Algorithm
Shor’s algorithm is divided into two parts where there is a classical part and a quantum computing part. The calculation is done in 5 steps as follows. Out of the five steps, only in step 3 we make use of quantum computers.
Essentially what Shor’s algorithm does is splitting the factorization problem into two where one can be solved easily using a classical computer and the other can be a period finding problem which can be resolved using a Quantum Computer.
To understand the third step solved by a Quantum Computer, we need to know a bit about modular arithmetic.
a mod N is defined as the remainder obtained while performing integer division of a with N.
Modular arithmetic is also called clock arithmetic as the operation is analogous to wrapping around a thread of length a on a clock of circumference N. For example consider the following clock with circumference 13. To find 17 mod 13 we can take a thread of length 17 and wrap around the clock starting from 0. Where the thread ends would be the value of 17 mod 13 ie; 4.
Example
Step 1: Choose a number N which is not prime.
Consider a small number which is a product of 2 prime numbers, say p = 11 and q = 7
Thus, N = 77
We know that N is not a prime number.
Step 2: Select ‘a’
Select a random integer a less than 77.
a = 4
GCD (a,N) = GCD (4,77) = 1
[If GCD of a and N is not equal to 1, then gcd(N,a) is a factor of N and the whole remaining process is not required]
Step 3: Find r, the period of the function
Now we have to find the period of the function. In Shor’s algorithm this step is performed using a quantum computer.
By plotting the values of f(x) we can see that it is a periodic function. f(1) =f(16) so the period of function is 15.
r = 15 since r is odd we have to repeat the steps with another value for r. Considering f(x) where a = 8
Step 4: Evaluate the range
The range was observed to be 10 which is an even value and we can proceed to the next step.
We need to verify if
Step 5: Finding the factors
Quantum Computation for finding the range
The first step here is to identify an integer Q which is a power of 2. Q should also comply with the following conditions.
N ≤ Q < N^2 and
Q/r > N
Since Q= 2^q [Note that this q is different from the prime factor q which we are calculating. This q is effectively the size of bit reqister which can hold the value Q]
As we have mentioned earlier all the value up to integer Q can be represented by a superposition of q qubits. The superposition of Q values here will serve as x from 0 to Q-1.
Then f(x) is constructed as a quantum function which would also be in superposition of Q distinct states as x.
The Quantum part
As explained above, the Shor’s algorithm uses two q qubit registers — one with the superposed values for x and another for the superposed values of f(x)=a^x mod N. Let’s call the x- register, Register 1 and the f(x) register, Register 2. The circuit would be designed using quantum gates such that both x and f(x) registers are quantum entangled such that measuring the register with f(x) would result in the following.
- Register with f(x) will collapse to a finite value of〖 a〗^x mod N, say k
- Register with x will go into a superposition of all the possible values of x which can result in f(x)=k
So if we consider the example, f(x)=4^x mod 77 Register 1 & Register 2 will have the following values superposed on q qubits. For ease of representation we have taken Q = 30, But in actual scenario N ≤Q<N^2 is considered.
We would then measure Register 2. On measuring, Register 2 would collapse into one of the finite values listed above. Suppose the Register 2 collapsed to 43. Since 43 is the value of f(x) when x=5,15 or 25, the quantum entangled Register 1 will then go to a superposition of 5, 15 and 25. In the next step we would measure Register 1 for the value of x corresponding to f(x). Due to the same quantum mechanical principles we described initially, we would get only one value of x as Register 1 collapses to one of the three finite states — 5, 15 or 25. With a few number of attempts, considerably less than what is required in a classical computer algorithm, we would be able to reproduce the same f(x)=43 and then measure Register 1 for a different value of x. If we get two consecutive values of x forf(x)=43, the period of the function can be found out, r=x_2 - x_1
Above given is the state diagram of the Quantum Sub routine of Shor’s algorithm.
Register 1 carries the input values — x. To get right superposed values of |0> and |1>, q bit qubit register is subjected to a Hardmard gate.
Register 2 stores the output values — f(x).
The output register arrives into a different representation of f(x) using a unitary quantum Fourier transform. This discrete Fourier transform representation of f(x) is an easily measurable qubit representation and that makes the whole job a lot easier.
In the previous section we mentioned that the input and output register qubit values would be entangled. To understand how quantum entanglement is possible with operations using quantum gates, please watch the videos listed below.
References
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer — Peter W. Shor
- Introduction to Quantum Algorithms — Peter W. Shor
- An Introduction to Quantum Algorithms — Emma Strubell
- Shor, I’ll do it — Scott Aaronson
- Video: Building the Bits and Qubits — Frame Of Essence — Philip O. Duncan
- Video: You don’t know how Quantum Computers work! — Frame Of Essence — Philip O. Duncan
