Quantum Chemistry
The accurate description of a molecule involves understanding the distance between the atoms and the strength of their atomic bonds (the sharing of electrons so that the atoms stick together …
Course: Understanding Quantum Computers
Linear Systems Algorithms
Machine learning involves classifying data, in order to make decisions. “Efficient” classical algorithms for finding full solutions exist, but the sheer volume of data means that computation times are high. …
Putting It All Together -Big factors that impact the performance
Today’s best classical computers and algorithm would require the lifetime of the universe to factor a number that is 2000 bits long. Even the apparently exponential gain of Moore’s law …
Putting It All Together -Summarizing the Algorithm
Shor’s algorithm is an amazing accomplishment, isn’t it? But it’s a complex algorithm involving a number of concepts that are probably new to you and it’s a combination of both …
Quantum Period Finding
Now that we understand what the quantum Fourier transform (QFT) does, and we know what the period of a function is, we can talk about how the QFT is used …
Quantum Fourier Transform
Like the classical Fourier transform, quantum Fourier transform (QFT) takes data from the original signal representation to the frequency domain representation. The QFT differs from the classical Fourier transform in …
Modular Exponentiation
The key to Shor’s algorithm is the insight that the function (f(x) = a^x bmod N) is periodic, and that we can extract that period using the quantum Fourier transform. …
Fourier Transform
We have already seen what a sine wave looks like in time and space – it’s the most basic form of wave. The Fourier transform lets us to see that …
Euclid’s Algorithm
One tool we are going to need in our toolbox is a way to find the greatest common divisor (GCD) of two numbers. You probably learned the basic idea in …
The Period of a Function
A lot of mathematical functions are periodic. That is, if you start in some place and move forward, eventually the sequence of values repeats itself. The time it takes for …
Structure of Shor’s algorithm
Let’s talk about the structure of Peter Shor’s algorithm for factoring large numbers. As we saw, a “quantum” algorithm is really a hybrid quantum-classical algorithm. It begins with some classical …
Basic Goal: Factoring
In computer science, the two most important classes of problems are P and NP. The P class stands for polynomial, that is, we can solve the problem in order of …
Diffusion and Performance
Our second major building block in Grover’s algorithm is the diffusion operator, which implements the “inversion about the mean” operation. The algorithm gives us a polynomial speedup on a broad …
Working with larger quantum registers
Working with multi-qubit registers allows the number of possible states to grow exponentially. It requires us to keep track of the weight (or amplitude) and phase of each possible state. …
Basic Algorithmic Flow
A quantum algorithm generally has five parts. The first part is the classical pre-processing. Next, we initialize the processor or qubit register to zero and create a superposition of all …