Will quantum computing help us create a better world, or destroy it?
Quantum computers don’t work by trying every possibility at once.
Quantum computers don’t speed up every problem.
They are faster for a certain set of problems.
There are only a few dozen or so quantum algorithms. In traditional terminology, algorithm means just a set of instructions. But when we refer to quantum algorithms, we mean instructions that actually harness quantum properties and potentially can solve these mathematical problems faster than a classical computer.
Even though there are a limited number of quantum algorithms, the ones that do exist can have a large impact on very important, broad-reaching problems.
Variational Quantum Eigensolver (VQE) and chemical simulations
The Variational Quantum Eigensolver is the foundation algorithm that could simulate molecules and chemical reactions.
In chemistry, the properties of atoms and molecules can be found by solving the Schrödinger equation. The problem gets harder the more atoms you add, so exact calculations are very time consuming above just a few atoms. Approximate solutions exist, but once you get up to just a few dozen atoms, classical computers just can’t do these problems efficiently anymore.
What VQE does is calculate the eigenvalues of a matrix. And it does so efficiently for large matrices, which means we can actually calculate these properties of large molecules in a way that a classical computer can’t.
So what is an eigenvalue anyway?
An eigenvalue of M (a matrix) is a scalar λ lambda such that the equation Mv=λv the matrix m multiplied by eigenvector has a non-trivial solution.
The matrix that we use in this calculation is the matrix that represents the Hamiltonian. A Hamiltonian describes the total energy of the system of atoms and molecules, meaning all the atoms and their interactions with each other.
The quantum subroutine has two steps:
- Prepare the quantum state ansatz
- Measure the expectation value — which, if you’re familiar with machine learning, can be thought of as the “cost function”
We start with an Ansatz — which means an educated guess or assumption. For us, in the problem of simulating molecules and finding the ground state energy, we start with a guess of that quantum state.
The trick is preparing this Ansatz — the guess needs to be pretty good. This VQE algorithm is hybrid, so it has a quantum step inside of a classical optimization loop to help prepare the quantum state. The classical step then loops until we find the minimum eigenvalue of the Hamiltonian, or state of the system, which is the lowest ground state energy.
And now you see why it’s called “Variational”. It’s a mathematical analysis that uses variations, which are small changes in functions, to find maxima and minima. This is just as we are doing here with our minimization of the expectation values.
It also means, because of the variational principle, the expectation value is larger than the smallest eigenvalue of the Hamiltonian H. The quantum subroutine measures that expectation value, and gets it closer to the smallest eigenvalue of the Hamiltonian, which is the ground state energy that we are looking for.
We can then use this minimum energy in other calculations, like modeling the evolution of the wavefunction (the wavefunction representing the molecule) over time.
Beyond chemistry, the solution of large eigenvalue problems would have even more applications that would really affect our day to day life, like designing new materials, whether that could be discovering new materials that stand up to higher heat and strain for airplanes, so maybe we could fly faster, or how we can make more effective batteries.
We are coming into the Noisy Intermediate Scale Quantum Device (NISQ) era. Our chips have dozens to a few hundred physical qubits, but have a high error rate, low coherence time, and may need a lot of error correction.
However, algorithms like VQE only need a handful of qubits to work. It’s also a “shallow” circuit, which means that it does not have a lot of sequential gates.
That matters because quantum information can only be stored for a short amount of time, called the “coherence time”. We need to apply all the gates and read out the data before the quantum bits decohere (or lose their quantum states). The deeper the circuit, the longer the coherence time. VQE works by calculating some part of the data using a quantum computer, feeding that information back to a regular computer, and looping back. It’s what we call a hybrid classical-quantum algorithm.
So if we don’t have a lot of gates that have to go in order, then we need a shorter coherence time!
Other example of variational algorithms include Variational quantum factoring (VQF) — factoring numbers for factoring RSA encryption in a new way. There’s also Quantum approximate optimization algorithm (QAOA), which can be applied to scheduling problems.
Quantum unconstrained binary optimization (QUBO)
Quantum annealers are built for translating QUBO and Ising problems effectively onto quantum hardware. Traveling salesman, scheduling problems, optimal placement problems, graph coloring problems, and even game optimization can be solved efficiently on these quantum systems.
This is extremely useful, because efficiency is an everyday problem.
Binary objective functions, the ones that QUBO can efficiently solve, can be looked at as graphs. This graph can be translated to the topology of the quantum chip. So you can take this optimization problem, and you construct the Hamiltonian equation that we need to minimize.
𝐻(𝑎,𝑏)=5𝑎+7𝑎𝑏−3𝑏
And you can represent it with a graph, where the nodes are a and b, the time they spend in each city to make the sale, with the weights corresponding to the equation, and the edge between them is a-b with the weight 7.
The minimization of that function is the “lowest energy state” of the system.
Practically, how does this work on a quantum annealer? We apply a magnetic field to control the superposition of the qubit, changing the probability of it being a one or a zero. The weights are controlled by the qubit superposition. You can adjust the coupler, and that correlates the two qubits , and that corresponds to the distance between the cities in traveling salesman.
For the optimizing solution, you can think of this as looking over a landscape and finding where the low point is. The lowest energy configuration is the “optimal” solution to these QUBO problems.
Quantum Machine Learning Algorithms
Quantum machine learning, and the research, can take different forms:
- quantum machine learning algorithms on quantum computers
- classical algorithms, inspired by quantum mechanics
- classical machine learning on quantum data
All of these fall under the “quantum machine learning” umbrella.
One major research push in quantum machine learning has been developing quantum versions of known classical machine learning algorithms. However another direction has been to make new quantum algorithms — all entirely quantum steps.
But you can also have quantum subroutines in machine learning. One idea is to have the quantum subroutine prepare data in a way that a classical computer can more efficiently process, or speeding up a bottleneck in the training. Research is going into finding the quantum versions of k-nearest neighbor methods, support vector machines, and other classical ML algorithms.
Another interested path is “quantum learning”. How would quantum tech process input-outputs and either optimize parameters, and find a new effective strategy for learning? How do we even represent the data in a quantum way?
There are proposal for quantum versions of neural networks. Most of them work Hopfield networks, which are powerful for the related task of associative memory that is derived from neuroscience rather than machine learning.
Other approaches use quantum fuzzy feed forward networks, or pattern recognition with adiabatic computing.
The impact here is similar to any machine learning algorithms, and we’ve seen the huge impact machine learning has had. Google PageRank was one of the first examples of Machine learning and Google rules our lives today.
Now anybody can train a neural net pretty easily with just a few lines of code. But there’s a lot of data in the world, and it’s only increasing. We hope that quantum can help with processing or making more efficient algorithms.
Grover’s algorithm for efficient search
Search complexity for unsorted databases is O(n), using Big O notation.
Grover’s algorithm, which takes sqrt(N) time, is the fastest possible quantum algorithm for searching an unsorted database.
When you talk about Grover’s algorithm searching faster, sometimes that is translated to “oh! It’s just parallelizing!”, but that is not the case. The better way to think about that is that Grover’s algorithm doesn’t search faster, but it inverts a function.
Grover’s algorithm applies when you have a function which returns True for one of its possible inputs, and False for all the others. The job of the algorithm is to find the one that returns True. What it really does is searches through input of the function, until it finds that single input that causes the function to return true.
Inverting a function is related to the searching of a database because we could come up with function that produces one particular value of (“true”, for instance) if matches a desired entry in a database, and another value of (“false”) for other values.
So even though Grover can search faster, ask — does your application have a way to map it onto the quantum systems? Molecules are more clear to map on quantum states, but how do you do it, for example, for actually searching words? How do you map a word onto a qubit state?
So even though Grover’s could work for searching, it does not mean we can speed up every search. The power of Grover’s algorithm will come in where search can’t scale well classically.
Examples of these problems where Grover’s can be useful and quickly gets much more difficult classically are traveling salesman and graph coloring problems (where you have to color a map, for example, with three colors, and make sure the same color isn’t touching). While Grover’s algorithm won’t apply to every search function, there is research going into implementing Grover’s algorithm to solve NP-complete problems.
Shor’s Algorithm for fast number factoring
Two common cryptosystems are Rivest–Shamir–Adleman (RSA) and elliptic curve cryptography (ECC). When you are online, any information that you exchange will be encrypted, often with these. Both of these are vulnerable to attacks by quantum computers.
For example, RSA relies on the hard problem of factoring numbers. Multiplying two prime numbers together is easy, but taking a large number and factoring it to get those two prime numbers is difficult. It would take longer than the age of the universe to factor one 4096-bit key with a classical computer.
Shor’s algorithm can find the prime factors of a number and can ”undo” this factoring problem much more easily than a classical computer. And this algorithm was created in 1994! How Shor’s algorithm works is by finding the “period” of a function.
The period of the function is when you apply some operation and the results go up and back down, like a frequency wave.
We can find the factors quickly if we have a fast way of finding the period of a known periodic function
f(x) = m^x (mod N)
There are 5 steps to Shor’s algorithm, but only this one step is “quantum”.
There is a known classical function do we have that relates to frequency and time, called the Fourier transform. We have a quantum version, called the Quantum Fourier transform. A Fourier Transform maps from the time domain to the frequency (Fourier) domain. Frequency is exactly what we want to know here.
Breaking encryption is a pretty big problem. We have to find new encryption techniques that stand up to quantum computing attacks.
It would take about 4000 qubits to break an RSA key. However, these are perfect, “logical” qubits. Because of error correction, we need many more physical qubits. John Preskill noted in his lecture on quantum information that 10 million physical and 10,000 logical qubit quantum computer would be needed. We are still pretty far away from that milestone, but it’s something we have to consider.
That makes quantum computing a technology with a lot of potential future impact, not even looking at the use cases in cybersecurity and telecommunications. So even though we only have dozens of quantum algorithms, the impact they can have is broad reaching, since optimization and search problems are really everywhere.
You can also read quantumalgorithmzoo.org to see a list of quantum algorithms!
Even just being able to simulate quantum states has a lot of applications in chemistry, materials, and energy. As we look into more algorithms, they can help with optimization and scheduling problems, and later, even search. And this is really the key to any quantum algorithm and the impacts — how do we map the problem to a Hamiltonian?
See my YouTube video talking about these quantum algorithms here: