Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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:

  • problems currently unsolvable for a practical entry,
  • problems which currently are being resolved, but a significant speedup would greatly improve their usability.
share|improve this question
7  
Maybe this helps. –  aelguindy Feb 9 '12 at 12:25
    
IIRC, there was a question about what quantum computers can be used to compute efficiently. You may want to have a look at it. –  Kaveh Feb 9 '12 at 22:50
    
Is this helpful? –  Kaveh Feb 13 '12 at 1:37
1  
@Kevah: Not much, to be honest. The emphasis of my question is the real world applications (so not only where 'there is a speedup for a particular algorithm' but when a speedup solves a particular practical problem). –  Piotr Migdal Feb 13 '12 at 11:06
1  
Constructing Optimum phylogenetic tree. –  Saeed Feb 23 '12 at 20:45

5 Answers 5

Efficiently simulating quantum mechanics.

share|improve this answer
    
this is the std/folklore/ironic/glib/near-joke answer & I wonder who originated it. does anyone have an actual reference? I question it as not nec trivially possible as follows. qm computing is largely focused on pairwise qubit interactions (gates). to prove that one could efficiently simulate QM in general it seems one would have to show that you can simulate all possible n-wise interactions efficiently with pairwise interactions. have not seen this proven in a paper. –  vzn Feb 17 '12 at 16:53
2  
@vzn: in most physical interactions, restricting to 2-particle interactions is a good approximation, good enough for simulations based only on local 2-body interactions to make sense (interactions including more terms usually decay very fast). So the existence of general n-body interactions does not invalidate the simulation idea. –  Marcin Kotowski Feb 17 '12 at 16:59
    
@vzn I don't have a paper reference, but Scott Aaronson says this and mentioned it in his recent Times article. –  Tyson Williams Feb 18 '12 at 4:19
2  
@vzn, this was the original application in mind when quantum computing was conceived by Richard Feynman. This is the link to the paper where he proposed the idea of quantum computers (springerlink.com/content/t2x8115127841630), and you can also check this (wisdom.weizmann.ac.il/~naor/COURSE/feynman-simulating.pdf) –  Marcos Villagra Feb 19 '12 at 1:20
1  
@vzn The answer is valid, but the literature on digital quantum simulation is quite extent to just sum it up via comments. I would recommend opening a new discussion since the topic is interesting. –  Juan Bermejo Vega Feb 24 '12 at 10:28

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.

share|improve this answer

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)

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
3  
"QM complexity theory is fleshed out better, NP completeness will fit "neatly" into it somehow." There is a well-developed theory of quantum interactive proof systems (complexity classes like QMA etc.) which generalize classical complexity classes like NP, PSPACE etc. In this sense, NP-completeness does fit neatly into quantum complexity theory. (on the other hand, I agree that field of quantum algorithms lacks cohesion, but quantum algorithms and quantum complexity are different subfields). –  Marcin Kotowski Feb 17 '12 at 17:01
    
agreed there are well defined QM classes & hierarchies that mirror non QM classes but their relation to (power relative to) "classical" non QM classes & NP in particular is largely an open question as stated. –  vzn Feb 23 '12 at 19:56
1  
What do you mean by "increasingly unstructured databases"? A database looks like something pretty ordered by definition. –  Juan Bermejo Vega Feb 24 '12 at 14:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.