What can you do with a quantum computer?

What are the most promising applications of quantum computing in the next 5-10 years? In my opinion, a task is likely to be amenable to quantum computing if it has the following characteristics:

1. The task is linear, or nearly so,
2. It requires limited input and output, and
3. Approximate solutions are useful.

Linearity

When I say that a task is nearly linear, I mean that important parts of the task can be expressed concisely using matrix operations. Quantum computers excel at linear calculations, because quantum gate operations are in reality matrix operations. They are ill-suited for problems that require many if-then statements and other control structures.

Limited input and output

Current quantum computers have very limited capacity, with less than 100 qubits (quantum bits). The D-Wave computer has 2000 qubits, but this is a specialized device, and not a general-purpose quantum computer. In contrast, modern computers have billions of bits of memory.

There is a theoretical concept called "quantum RAM" which would allow us to store 2^N classical bits of information in an N-qubit register. However, quantum RAM has not been achieved in practice. Also, this would only solve the input problem. One cannot read more than N classical bits from an N-qubit register.

This does not mean that quantum computers cannot be used to process large data sets. But the input and output would have to be split into small chunks and processed independently.

Approximate solutions

In most computing tasks, we are looking for an exact answer. But current quantum computers are prone to error, so they can only deliver approximate solutions. Sometimes an approximate solution is good enough. For example, if you are planning a schedule for a fleet of trucks, you would like to find an optimal schedule, but you may be willing to settle for a schedule that is within 1% of the optimal schedule.

Potential applications

Here are some kinds of problems that might be suitable for quantum computers in the near future. (But I make no promises!)

1. Linear algebra: solving systems of linear equations, inverting matrices, finding eigenvectors and eigenvalues of matrices.
2. Chemistry: Developing new chemical compounds, materials, and processes.
3. Medicine: Drug discovery.
4. Logistics: Traffic management, scheduling, resource allocation.
5. Finance: Portfolio optimization, arbitrage.
6. Quantum machine learning: Image and speech recognition, virtual assistants, maybe self-driving cars?

Note: The silly cover image is meant to remind you that I am not an expert on quantum computing. This post reflects my current understanding, which is still evolving, and I hope that it will serve as a starting point for deeper discussion.