18
$\begingroup$

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.
$\endgroup$
5
  • 8
    $\begingroup$ Maybe this helps. $\endgroup$
    – aelguindy
    Feb 9, 2012 at 12:25
  • $\begingroup$ IIRC, there was a question about what quantum computers can be used to compute efficiently. You may want to have a look at it. $\endgroup$
    – Kaveh
    Feb 9, 2012 at 22:50
  • $\begingroup$ Is this helpful? $\endgroup$
    – Kaveh
    Feb 13, 2012 at 1:37
  • 1
    $\begingroup$ @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). $\endgroup$ Feb 13, 2012 at 11:06
  • 1
    $\begingroup$ Constructing Optimum phylogenetic tree. $\endgroup$
    – Saeed
    Feb 23, 2012 at 20:45

5 Answers 5

17
$\begingroup$

Efficiently simulating quantum mechanics.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Feb 17, 2012 at 16:53
  • 2
    $\begingroup$ @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. $\endgroup$ Feb 17, 2012 at 16:59
  • $\begingroup$ @vzn I don't have a paper reference, but Scott Aaronson says this and mentioned it in his recent Times article. $\endgroup$ Feb 18, 2012 at 4:19
  • 2
    $\begingroup$ @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) $\endgroup$ Feb 19, 2012 at 1:20
  • 1
    $\begingroup$ @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. $\endgroup$ Feb 24, 2012 at 10:28
9
$\begingroup$

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)

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
-6
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ "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). $\endgroup$ Feb 17, 2012 at 17:01
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Feb 23, 2012 at 19:56
  • 1
    $\begingroup$ What do you mean by "increasingly unstructured databases"? A database looks like something pretty ordered by definition. $\endgroup$ Feb 24, 2012 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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