Skip main navigation

Machine Learning and Other Algorithms

Read a short description of some of othe other uses for quantum computers.

In quantum chemistry, factoring, and generalized search we have seen three of the four important classic (so to speak) algorithms of quantum computing, all developed in the 1990s. (The fourth, the Deutsch-Jozsa algorithm, was actually the first quantum algorithm developed in detail and showing a potential scaling improvement for quantum computers, but it is of limited practical use, so we will not discuss it in this course.) Shor is fairly cut and dried, but variants of search continue to evolve, and quantum chemistry has developed substantially in the last ten years or so. But these are far from the only uses for a quantum computer.

Let us briefly introduce a few of the other potential uses. The details of these algorithms, including the set of use cases where they are faster on a quantum computer than a classical one, are complex, so deeper study of them is left for a more advanced course. In Week 3, when we cover algorithms in detail, we will introduce one important algorithm from this group, discussing the problems it solves rather than how it operates.

Linear Algebra

Operations involving matrices and vectors of numbers are called linear algebra or linear systems. They are used in many important calculations, from rotating an object in a video game to calculating characteristics of the economy to almost every physics and engineering problem. They are even used in describing quantum computers.

Quantum computers can achieve a significant speedup on a number of linear problems: checking the result of multiplying two matrices, or finding some property of a matrix by calculating (f(A)vec{b}) for some function (f), some matrix (A), and some vector (vec{b}), for example. They can also calculate approximate values of exponents of matrices, (A^m).

For some specialized variants of these problems, quantum computers can offer superpolynomial speedups. For others, the speedup is polynomial.

Machine Learning

Machine learning is one popular subfield of artificial intelligence, especially the form known as deep learning, which is revolutionizing many real-world online services such as image recognition, voice recognition and automated language translation. In fact, it builds on subroutines for linear algebra, and so can benefit from some of the algorithms alluded to above. This area is considered particularly attractive due to the obvious economic value of solving real-world problems.

For some specialized variants of these problems, quantum computers can offer superpolynomial speedups.

Graph Algorithms

Many problems can be phrased as graph problems. A graph consists of vertices and edges (also often called nodes and links). The figure below is a simple graph consisting of nine vertices and fourteen links.

A simple graph consisting of nine vertices and fourteen links

If the letters a to i are cities, and the number above or next to each line is the number of kilometers between the pair of cities, what is the best way to get from a to e? This is the shortest path problem.

Is it actually possible to get all the way from a to e? In this simple example it is easy to see that the graph is connected, that is possible to get from any vertex to any other, but in larger graphs it can become a harder problem.

On the left, a is connected to b and h, and b and h are also connected to each other, forming a triangle. How many triangles are there in this graph? Sometimes, it is important to know.

Efficient classical algorithms exist for many of these questions, but quantum algorithms that offer a polynomial speedup have been developed.


More generally, one of the most important uses of classical computers is to solve problems in optimization. The field known as operations research involves optimizing some value, often for business purposes: reducing the amount of material used in a factory, or maximizing profit based on some set of assumptions.

Organizations considering purchasing a (hypothetical) quantum computer will, in general, not care much about whether a particular algorithm is polynomial or exponential in running time. Instead, they care about how well it works for their particular problem, given the size of the problem and perhaps some of the characteristics of the input data.

Quantum algorithms for a variety of specialized optimization problems already exist, but how well they work for different problems in the real world is not yet well understood. Researchers are probing this area actively, and it is considered to be one of the most compelling reasons for building quantum computers.






量子コンピュータを用いることで、多数の線形問題をより高速に処理し、解を得ることができます。 例えば、ある関数 (f)に行列(A)を代入した式に、ベクトル(b)をかけ合わせることや、2つの行列の掛け算などといった問題がそれに値します。 また、ある行列Aのm乗、(A^m)の近似解を素早く計算することもできます。






世の中に存在する多くの問題は頂点(ノード)辺(リンク)からなるグラフ問題に置き換えることができます。 下の図は9個の頂点と、14本の辺からなるグラフの例です。

A simple graph consisting of nine vertices and fourteen links

もし a から i が都市で、線の隣にある数字が、その距離を表しているとしたとき、a から e へ行く最善のルートはどれでしょうか?こういった問題を一般に最短経路問題と呼びます。

では、a からe へ行く全ての道順を確認することはできるでしょうか?この例のような簡単なグラフの問題であれば、どの頂点からの経路も容易に確認することができますが、都市(ノード)と道(リンク)が増えれば増えるほど、最短経路の計算が困難になってくることは容易に想像が付きます。

図の左側において、a は b と h とつながっており、 b と h はお互い同士もまたつながっているため、 a と b と h は三角形を形成しています。ではどれだけの数の三角形がこのグラフの中にあるでしょうか?一見すると、三角形を探しても得があるようには思えませんが、グラフ問題においては、それを知ることは時として重要なこととなるのです。






© Keio University
This article is from the free online

Understanding Quantum Computers

Created by
FutureLearn - Learning For Life

Reach your personal and professional goals

Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.

Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.

Start Learning now