Let's assume that we have built an universal quantum computer.
Except for security-related issues (cryptography, privacy, ...) which current real world problems can benefit from using it?
I am interested in both:
Efficiently simulating quantum mechanics.
Simulating quantum systems!
I noticed that in the other answer that mentioned this there were several comments about whether this was true since it is a non-obvious claim. And people requested references. Here are some references.
Original proposal by Feynman:
Feynman, R.: Simulating physics with computers. Int. J. Theor. Phys. 21(6) (1982) 467–488
Efficient algorithms for all quantum systems defined by "local" Hamiltonians. (Lloyd also explains that any system consistent with special and general relativity evolves according to local interactions.)
Lloyd, S.: Universal quantum simulators. Science 273(5278) (1996) 1073–1078
Further generalization to sparse Hamiltonians, which are more general than local Hamiltonians:
Aharonov, D., Ta-Shma, A.: Adiabatic quantum state generation and statistical zero knowledge. In: Proc. 35th STOC, ACM (2003) 20–29
Further reading:
Berry, D., Ahokas, G., Cleve, R., Sanders, B.: Efficient quantum algorithms for simulating sparse Hamiltonians. Commun. Math. Phys. 270(2) (2007) 359–371
Childs, A.M.: Quantum information processing in continuous time. PhD thesis, Massachusetts Institute of Technology (2004)
Brassard, Hoyer, Mosca and Tapp showed that the generalized Grover search, called amplitude amplification, can be used to obtain a quadratic speed-up on a large class of classical heuristics. The intuition behind their idea is that classical heuristics use randomness to search for a solution to a given problem, so we can use amplitude amplification to search the set of random strings for one that will make the heuristic find a good solution. This yields a quadratic speed-up in the running time of the algorithm. See section 3 of the paper linked above for more details.
Visioning is both dangerous and polemic in this field, so we should be cautious with this topic. Yet some Q-algorithms with polynomial speed-ups have interesting potential applications.
It is known that Grover search can be used to polynomially seep-up the solution to NP-complete problems [1]. This is proven for 3-SAT in [2]. Some applications of SAT, borrowed from [3], are: checking circuit equivalence, automatic test-pattern generation, model checking using Linear Time Logic, planning in artificial intelligence and haplotyping in bioinformatics. Although I do not know much about these topics, this line of research looks rather practical to me.
Also, there is a quantum algorithm to evaluate NAND-trees with a polynomial speed-up over classical computation [8,10,11]. The NAND tree is an example of a game tree, a more general data-structure used to study matches of board games such as Chess and Go. It sounds plausible that this kind of speed-ups could be used to design more powerful software game-players. Could this interest some quantum-video-games developers?
Unfortunately, playing games in reality is not exactly the same thing as evaluating trees: there are complications, e.g., if your players are not using optimal strategies [12]. I have not seen any study considering a real-life scenario, so it is hard to say how beneficial is the speed-up from [8] in practice. This could be a good topic for discussion.
think you've raised an excellent question at the frontiers of QM research (partially indicated by your lack of answers so far), but it hasnt been entirely formally defined or captured as a problem. the question is along the lines of "what exactly can QM algorithms compute efficiently anyway?" and a complete answer is not known & being actively pursued. some of this is related to the (open questions on) complexity of QM-related classes.
this would be the case that there is a somewhat formal question defined. if the QM classes can be shown to be equivalent to "significantly powerful" non-QM classes, then there's your answer. the general theme of this type of result would be a "not-so-hard-in-QM" class is equivalent to a "hard-in-non-QM" class. there are various open complexity class separations of this type (maybe someone else can suggest them in more detail).
something strange about current QM knowledge on quantum algorithms is that theres a kind of weird grab bag of algorithms that are known to work in QM but theres seemingly not a lot of coherence/cohesion to them. they seem odd and disconnected in some ways. theres no apparent "rule of thumb" for "problems that are computable in QM are generally in this form" despite a reasonable expectation that one could be there.
e.g. contrast this to the theory of NP completeness which is much more cohesive in comparison. it seems like maybe if the QM theory is better developed it would obtain this greater sense of cohesion reminiscent of NP completeness theory.
a stronger idea might be that eventually when the QM complexity theory is fleshed out better, NP completeness will fit "neatly" into it somehow.
to me the most general QM speedup or widely applicable strategy Ive seen seems to be Grovers algorithm because so much practical software is related to db queries. and in some ways increasingly "unstructured" ones:
Grover's algorithm searches an unstructured database (or an unordered list) with N entries, for a marked entry, using only $O(\sqrt{N})$ queries instead of the $Ω(N)$ queries required classically.
