Introduction
Contents
Introduction¶
Welcome¶
This is an introduction to Quantum Programming using Qiskit. It is targeted at high level undergraduate CS students and first year graduate CS students.
I am just doing this for fun to learn the material. Hopefully, it will probably be unfinished for a while.
Why Quantum?¶
Quantum Computer are very popular in the news right now. There is a lot of talk about them in the media and in popular fiction. They are a real thing, but the technology is still growing. We can learn about them now and be better prepared for the future.
Is Quantum Computing Placing Bitcoin’s Future in Jeopardy? [Sta21]
A student’s physics project could make quantum computers twice as reliable [Pap21]
Cryptographers are Racing Against Quantum Computers [Xu21]
IBM promises 1000-qubit quantum computer - a milestone - by 2023 [Cho20]
The future is bright for Quantum Computers. There are many hardware limitations right now. As a student studying Computer Science, you are likely to still be programming when these hardware limitations are resolved. By learning about quantum programming now, you will be really when the hardware catchs up with theory.
In the News we read that factoring Large integers will destroy cryptography as we know it. In reality, Python can factor much larger integers much faster than any current general purpose Quantum Computer.
Shor’s Algorithm is one of the most famous quantum algorithms. Can factor integers! Largest Number Ever Factored: 21 in 2012 [MLLL+11]. A failed attempt was made to factor 35 in 2019 [ASK19].
There are also quantum computers built on quantum annealing. These use special hardware that is not designed universal computation. It is designed to only solve certain types of problems. Annealing computers have been shown to be able to factor 15, 143, 59989, and 376289 [JBM+18]. This Hardware is designed for optimization problems. This limits its use for general purpose programming.
It probably isn’t worth your effort to factor 21, 35, or even 376289 on a quantum computer.
In Python, we can write a very simple loop to find a prime factor of a number. It either finds a prime factor or returns the number because it is prime.
#findFactor either finds a prime
#factor or returns the number if
#it is prime
def findFactor(num):
k=2
while k*k <= num:
if num%k==0:
return k
k=k+1
#Number is Prime
return num
We can factor a number by repeatedly running this function.
#factor takes a number and
#repeatedly finds factors
#until all are found
def factor(num):
factors=[]
while num > 1:
k = findFactor(num)
num=num//k
factors.append(k)
return factors
These are pure brute force solutions. They just try every number until they find the answer. There are many more efficient ways to compute factors even on classical computers.
We can try to factor the numbers that have been tested on quantum computers. We will see how long it takes.
#Main function runs tests
def main():
#Example Numbers to Factor
values=[15,21,35,143, 59989, 376289]
for target in values:
before=time.time()
primeFactors = factor(target)
after=time.time()
print("The Factors of {:d} are".format(target))
print(primeFactors)
print("Finding them took {:0.5f} seconds".format(after-before))
#Run the Script
if __name__=="__main__":
main()
When we run the program we get the right factors for every number.
The Factors of 15 are
[3, 5]
Finding them took 0.00001 seconds
The Factors of 21 are
[3, 7]
Finding them took 0.00000 seconds
The Factors of 35 are
[5, 7]
Finding them took 0.00000 seconds
The Factors of 143 are
[11, 13]
Finding them took 0.00000 seconds
The Factors of 59989 are
[239, 251]
Finding them took 0.00004 seconds
The Factors of 376289 are
[571, 659]
Finding them took 0.00009 seconds
Each of the numbers takes barely any time. They appear almost instantly. It would not be worth the investment to use a quantum computer to solve these in practice.
Right now, hardware might not be great but it exists. We can design, analyze, and test algorithms at small scales. We can be sure that our theory works. We also know quantum computers have amazing potential. There are significant hardware and software limitations right now. These will be solved. You can think of yourself in the 1950s of Quantum Computing. Learn the basics and you will be prepared for the near future. We are advancing much faster this time around!