- Drugs/Materials/Fuels1
- Experiments are expensive and slow, computer simulation is critical
- Theoretically, we know what to do:
$$\hat{H}\ket{\psi} = i\hbar \tfrac{d}{dt} \ket{\psi}$$ - Exponential scaling, even small molecules would require earth sized hardware!
- Protein folding
- Vaccination:
- https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.101.058701
- use graph partitioning to minimize the number of vaccine doses needed to immunize a population (or network of computers)
-
Traveling salesman problem
- Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
NP-hard- It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, many heuristics and exact algorithms are known, so that some instances with tens of thousands of cities can be solved completely and even problems with millions of cities can be approximated within a small fraction of 1%.[1]
-
Max-CutProblemNP-complete- For a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets S and T, such that the number of edges between S and T is as large as possible. Finding such a cut is known as the max-cut problem.
- One wants a subset S of the vertex set such that the number of edges between S and the complementary subset is as large as possible. Equivalently, one wants a bipartite subgraph of the graph with as many edges as possible.
-
Circuit design