What kind of real-world problems (excluding cryptography) can be solved efficiently by a quantum algorithm?

Question

This question is very similar as Is there any general statement about what kinds of problems can be solved more efficiently using a quantum computer?

But the answers provided to that questions mainly looked at it from a theoretical/mathematical point of view.

For this question, I am more interested in the practical/engineering point of view. So I would like to understand what kind of problems can be more efficiently solved by a quantum algorithm than you would currently be able to do with a classical algorithm. So I am really assuming that you do not have all knowledge about all possible classical algorithms that could optimally solve the same problem!

I am aware that the quantum zoo expresses a whole collection of problems for which there exists a quantum algorithm that runs more efficiently than a classical algorithm but I fail to link these algorithms to real-world problems.

I understand that Shor's factoring algorithm is very important in the world of cryptography but I have deliberately excluded cryptography from the scope of this question as the world of cryptography is a very specific world which deserves his own questions.

In efficient quantum algorithms, I mean that there must at least be one step in the algorithm that must be translated to a quantum circuit on a n-qubit quantum computer. So basically this quantum circuit is creating a $2^n$ x $2^n$ matrix and its execution will give one of the $2^n$ possibilities with a certain possibility (so different runs might give different results - where the likely hood of each of the $2^n$ possibilities is determined by the constructed $2^n$ x $2^n$ Hermitian matrix.)

So I think to answer my question there must be some aspect/characteristic of the real world problem that can be mapped to a $2^n \times 2^n$ Hermitian matrix. So what kind of aspects/characteristics of a real-world problem can be mapped to such a matrix?

With real-world problem I mean an actual problem that might be solved by a quantum algorithm, I don't mean a domain where there might be a potential use of the quantum algorithm.

Answer 1

I won't be giving any precise statements about which problems can be solved more efficiently using quantum algorithms (compared to existing classical algorithms) but rather some examples:

• Discrete Fourier transform (DFT) is used in pretty much all modern day music systems, for example in iPods. That algorithm single-handedly changed the world of digital music. See this for a summary. However, Quantum Fourier transform can further improve upon the complexity of DFT i.e. from $\mathcal{O}(N\log(N))$ to $\mathcal{O}(\log^2 N)$. I've written an answer regarding this here.

• The Quantum algorithm for linear systems of equations provides an exponential speedup over the classical methods like Gaussian elimination.

The quantum algorithm for linear systems of equations, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd is a quantum algorithm formulated in 2009 for solving linear systems. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.

The algorithm is one of the main fundamental algorithms expected to provide a speedup over their classical counterparts, along with Shor's factoring algorithm, Grover's search algorithm and quantum simulation. Provided the linear system is a sparse and has a low condition number ${\displaystyle \kappa }$ , and that the user is interested in the result of a scalar measurement on the solution vector, instead of the values of the solution vector itself, then the algorithm has a runtime of $O(\log(N)\kappa ^{2})$, where ${\displaystyle N}$ is the number of variables in the linear system. This offers an exponential speedup over the fastest classical algorithm, which runs in ${\displaystyle O(N\kappa )}$or $O(N{\sqrt {\kappa }})$ for positive semidefinite matrices).

• Hamiltonian simulation:

One of the earliest – and most important – applications of a quantum computer is likely to be the simulation of quantum mechanical systems. There are quantum systems for which no efficient classical simulation is known, but which we can simulate on a universal quantum computer. What does it mean to “simulate” a physical system? According to the OED, simulation is “the technique of imitating the behaviour of some situation or process (whether economic, military, mechanical, etc.) by means of a suitably analogous situation or apparatus”. What we will take simulation to mean here is approximating the dynamics of a physical system. Rather than tailoring our simulator to simulate only one type of physical system (which is sometimes called analogue simulation), we seek a general simulation algorithm which can simulate many different types of system (sometimes called digital simulation)

For the details, check chapter 7 of the lecture notes by Ashley Montaro.

• Hybrid Quantum/Classical Algorithms:

Hybrid Quantum/Classical Algorithms combine quantum state preparation and measurement with classical optimization. These algorithms generally aim to determine the ground state eigenvector and eigenvalue of a Hermitian Operator.

QAOA:

The quantum approximate optimization algorithm^[1] is a toy model of quantum annealing which can be used to solve problems in graph theory. The algorithm makes use of classical optimization of quantum operations to maximize an objective function.

Variational Quantum Eigensolver

The VQE algorithm applies classical optimization to minimize the energy expectation of an ansatz state to find the ground state energy of a molecule ^[2]. This can also be extended to find excited energies of molecules.^[3].

You can find many more such examples on Wikipedia itself. Apart from those, there are lots of recent algorithms which can be used in machine learning and data science. This answer will get a bit too long if I add the details of all those. However, see this and this and the references therein.

[1]: A Quantum Approximate Optimization Algorithm Farhi et al. (2014)

[2]: A variational eigenvalue solver on a quantum processor Peruzzo et al. (2013)

[3]: Variational Quantum Computation of Excited States Brierley et al. (2018)

Answer 2

The travelling salesman problem (TSP) is a very well studied real world problem which is highly suitable for qc.

Also quantum annealing and protein folding are qc suitable real world problems.

For references use google => wikipedia has nice reference sections of new and old papers.