<p>Efficiently simulating quantum mechanics.</p>

CC BY-SA 3.0
2012-02-17T16:53:06.553Z
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
CC BY-SA 3.0
2012-02-17T16:59:10.893Z
@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
CC BY-SA 3.0
2012-02-18T04:19:03.763Z
@vzn I don't have a paper reference, but Scott Aaronson says this and mentioned it in his recent [Times article](http://www.nytimes.com/2011/12/06/science/scott-aaronson-quantum-computing-promises-new-insights.html?_r=1&ref=science).
Tyson Williams
CC BY-SA 3.0
2012-02-19T01:20:27.743Z
@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 (http://www.springerlink.com/content/t2x8115127841630/), and you can also check this (http://www.wisdom.weizmann.ac.il/~naor/COURSE/feynman-simulating.pdf)
Marcos Villagra
CC BY-SA 3.0
2012-02-23T20:06:30.857Z
I know that many eminent authorities have stated something along these lines & vaguely recall feynmans original idea but imho the idea needs to be fleshed out more. marcin's idea that n-body interactions can be approximated by 2-body interactions "in most physical interactions" needs to be extended to QM which defn has laws that defy or are counter to "most [classical] physical interactions". by the way I myself am making an assumption that most QM computers seem to be based on 2-way interactions, that is not a proven situation but it seems to be case so far [incl largely in the theory].
vzn
CC BY-SA 3.0
2012-02-23T20:13:11.643Z
also, I suspect that experimentally devising/arranging arbitrary n-way interactions is going to be significantly harder than 2-way interactions which themselves are seen to be very difficult to create.
vzn
CC BY-SA 3.0
2012-02-24T10:28:07.290Z
@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
CC BY-SA 3.0
2012-12-09T20:04:43.623Z
This paper by Bravyi, DiVincenzo, Loss and Terhal (http://arxiv.org/abs/0803.2686) explains "how to map a given n-qubit target Hamiltonian with bounded-strength k-body interactions onto a simulator Hamiltonian with two-body interactions , such that the ground-state energy of the target and the simulator Hamiltonians are the same up to an extensive error O(epsilon n) for arbitrary small epsilon".
Anthony Leverrier
CC BY-SA 3.0
2017-06-22T01:04:32.013Z
It is a well-known result in quantum computing that n-wise interactions are closely simulatable using combinations of operations on 1 and 2 qubits (i.e. pairwise interactions), but more than this, they are known to be simulatable efficiently (i.e. don't need that many single or 2-qubit operations to get to an arbitrary n-qubit operation/interaction). See for example Nielsen and Chuang, chapter 4.
Sherif F.
CC BY-SA 3.0
2012-02-16T22:52:20.583Z
2012-02-16T22:52:20.583Z
Tyson Williams
<p>Simulating quantum systems! </p>

<p>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.</p>

<p>Original proposal by Feynman:</p>

<blockquote>
  <p>Feynman, R.: Simulating physics with computers. Int. J. Theor. Phys. 21(6)
  (1982) 467–488</p>
</blockquote>

<p>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.)</p>

<blockquote>
  <p>Lloyd, S.: Universal quantum simulators. Science 273(5278) (1996) 1073–1078</p>
</blockquote>

<p>Further generalization to sparse Hamiltonians, which are more general than local Hamiltonians:</p>

<blockquote>
  <p>Aharonov, D., Ta-Shma, A.: Adiabatic quantum state generation and statistical
  zero knowledge. In: Proc. 35th STOC, ACM (2003) 20–29</p>
</blockquote>

<p>Further reading:</p>

<blockquote>
  <p>Berry, D., Ahokas, G., Cleve, R., Sanders, B.: Eﬃcient quantum algorithms for
  simulating sparse Hamiltonians. Commun. Math. Phys. 270(2) (2007) 359–371</p>
  
  <p>Childs, A.M.: Quantum information processing in continuous time. PhD thesis,
  Massachusetts Institute of Technology (2004)</p>
</blockquote>

CC BY-SA 3.0
2012-12-08T00:30:11.903Z
2012-12-08T00:30:11.903Z
Robin Kothari
<p><a href="http://arxiv.org/abs/quant-ph/0005055">Brassard, Hoyer, Mosca and Tapp</a> 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.</p>

CC BY-SA 3.0
2012-02-23T18:22:31.947Z
2012-02-23T18:22:31.947Z
lamontap
<p>Visioning is both dangerous and polemic in this field, so we should be cautious with this topic. Yet some Q-algorithms with <strong>polynomial</strong> speed-ups have interesting potential applications.</p>

<p>It is known that Grover search can be used to polynomially seep-up the solution to NP-complete problems <a href="http://math.nist.gov/quantum/zoo/" rel="nofollow">[1]</a>. This is proven for 3-SAT in <a href="http://arxiv.org/abs/quant-ph/0504012" rel="nofollow">[2]</a>. Some applications of SAT, borrowed from <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4605925&amp;tag=1" rel="nofollow">[3]</a>, are: <a href="http://en.wikipedia.org/wiki/Formal_equivalence_checking" rel="nofollow">checking circuit equivalence</a>, <a href="http://en.wikipedia.org/wiki/Automatic_test_pattern_generation" rel="nofollow">automatic test-pattern generation</a>, <a href="http://en.wikipedia.org/wiki/Model_checking" rel="nofollow">model checking using  Linear Time Logic</a>,
<a href="http://en.wikipedia.org/wiki/Artificial_intelligence#Planning" rel="nofollow">planning in artificial intelligence</a> and <a href="http://en.wikipedia.org/wiki/Haplotype" rel="nofollow">haplotyping in bioinformatics</a>. Although I do not know much about these topics, this line of research looks rather practical to me.</p>

<p>Also, there is a quantum algorithm to evaluate NAND-trees with a polynomial speed-up over classical computation [<a href="http://arxiv.org/abs/quant-ph/0702144" rel="nofollow">8</a>,<a href="http://www.scottaaronson.com/blog/?p=207" rel="nofollow">10</a>,<a href="http://cacm.acm.org/magazines/2010/2/69352-recent-progress-in-quantum-algorithms/fulltext" rel="nofollow">11</a>]. 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?</p>

<p>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 [<a href="http://arxiv.org/abs/1006.4014" rel="nofollow">12</a>]. I have not seen any study considering a real-life scenario, so it is hard to say how beneficial is the speed-up from [<a href="http://arxiv.org/abs/quant-ph/0702144" rel="nofollow">8</a>] in practice. This could be a good topic for discussion.</p>

CC BY-SA 3.0
2018-04-04T02:29:11.297Z
Please accept my invitation to join: https://quantumcomputing.stackexchange.com/ .
Rob
CC BY-SA 3.0
2012-02-24T13:22:23.080Z
2012-02-24T13:22:23.080Z
Juan Bermejo Vega
<p>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 &amp; being actively pursued. some of this is related to the (open questions on) complexity of QM-related classes. </p>

<p>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).</p>

<p>something strange about current QM knowledge on <a href="http://en.wikipedia.org/wiki/Quantum_algorithm" rel="nofollow">quantum algorithms</a>
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. </p>

<p>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.</p>

<p>a stronger idea might be that eventually when the QM complexity theory is fleshed out better, NP completeness will fit "neatly" into it somehow.</p>

<p>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:</p>

<blockquote>
  <p>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.</p>
</blockquote>

CC BY-SA 3.0
2012-02-17T17:01:55.603Z
"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
CC BY-SA 3.0
2012-02-23T19:56:25.750Z
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
CC BY-SA 3.0
2012-02-24T14:03:41.267Z
What do you mean by "increasingly unstructured databases"? A database looks like something pretty ordered by definition.
Juan Bermejo Vega
CC BY-SA 3.0
2012-02-17T06:02:17.927Z
2012-02-17T06:02:17.927Z
vzn
<p>Let's assume that we have built an universal quantum computer.</p>

<p>Except for security-related issues (cryptography, privacy, ...) which current real world problems can benefit from using it?</p>

<p>I am interested in both:</p>

<ul>
<li>problems currently unsolvable for a practical entry,</li>
<li>problems which currently are being resolved, but a significant speedup would greatly improve their usability.</li>
</ul>

CC BY-SA 3.0
2012-02-09T12:25:04.907Z
Maybe [this](http://math.nist.gov/quantum/zoo/) helps.
aelguindy
CC BY-SA 3.0
2012-02-09T22:50:10.323Z
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
CC BY-SA 3.0
2012-02-13T01:37:37.790Z
Is [this](http://cstheory.stackexchange.com/questions/3888/np-intermediate-problems-with-efficient-quantum-solutions) helpful?
Kaveh
CC BY-SA 3.0
2012-02-13T11:06:15.277Z
@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
CC BY-SA 3.0
2012-02-23T20:45:57.373Z
Constructing [Optimum phylogenetic tree](http://en.wikipedia.org/wiki/Phylogenetic_tree).
Saeed
<quantum-computing><application-of-theory>
Real world applications of quantum computing (except for security)
Piotr Migdal
# Real world applications of quantum computing (except for security)

(Asked by: username_0 on 2012-02-09)

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.

**Tags:** quantum-computing, application-of-theory
> **Comments:**
> **username_1**: Maybe [this](http://math.nist.gov/quantum/zoo/) helps.  
> **username_2**: IIRC, there was a question about what quantum computers can be used to compute efficiently. You may want to have a look at it.  
> **username_2**: Is [this](http://cstheory.stackexchange.com/questions/3888/np-intermediate-problems-with-efficient-quantum-solutions) helpful?  
> **username_0**: @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).  
> **username_3**: Constructing [Optimum phylogenetic tree](http://en.wikipedia.org/wiki/Phylogenetic_tree).  

---

## 5 answers

### Answer by username_4 on 2012-02-16. Score: 17

Efficiently simulating quantum mechanics.

> **Comments:**
> **username_5**: 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.  
> **username_6**: @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.  
> **username_4**: @vzn I don't have a paper reference, but Scott Aaronson says this and mentioned it in his recent [Times article](http://www.nytimes.com/2011/12/06/science/scott-aaronson-quantum-computing-promises-new-insights.html?_r=1&ref=science).  
> **username_7**: @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 (http://www.springerlink.com/content/t2x8115127841630/), and you can also check this (http://www.wisdom.weizmann.ac.il/~naor/COURSE/feynman-simulating.pdf)  
> **username_5**: I know that many eminent authorities have stated something along these lines & vaguely recall feynmans original idea but imho the idea needs to be fleshed out more. marcin's idea that n-body interactions can be approximated by 2-body interactions "in most physical interactions" needs to be extended to QM which defn has laws that defy or are counter to "most [classical] physical interactions". by the way I myself am making an assumption that most QM computers seem to be based on 2-way interactions, that is not a proven situation but it seems to be case so far [incl largely in the theory].  
> **username_5**: also, I suspect that experimentally devising/arranging arbitrary n-way interactions is going to be significantly harder than 2-way interactions which themselves are seen to be very difficult to create.  
> **username_8**: @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.  
> **username_9**: This paper by Bravyi, DiVincenzo, Loss and Terhal (http://arxiv.org/abs/0803.2686) explains "how to map a given n-qubit target Hamiltonian with bounded-strength k-body interactions onto a simulator Hamiltonian with two-body interactions , such that the ground-state energy of the target and the simulator Hamiltonians are the same up to an extensive error O(epsilon n) for arbitrary small epsilon".  
> **username_10**: It is a well-known result in quantum computing that n-wise interactions are closely simulatable using combinations of operations on 1 and 2 qubits (i.e. pairwise interactions), but more than this, they are known to be simulatable efficiently (i.e. don't need that many single or 2-qubit operations to get to an arbitrary n-qubit operation/interaction). See for example Nielsen and Chuang, chapter 4.  

---

### Answer by username_11 on 2012-12-08. Score: 9

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.: Eﬃcient 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)


---

### Answer by username_12 on 2012-02-23. Score: 8

[Brassard, Hoyer, Mosca and Tapp](http://arxiv.org/abs/quant-ph/0005055) 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.


---

### Answer by username_8 on 2012-02-24. Score: 2

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]](http://math.nist.gov/quantum/zoo/). This is proven for 3-SAT in [[2]](http://arxiv.org/abs/quant-ph/0504012). Some applications of SAT, borrowed from [[3]](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4605925&tag=1), are: [checking circuit equivalence](http://en.wikipedia.org/wiki/Formal_equivalence_checking), [automatic test-pattern generation](http://en.wikipedia.org/wiki/Automatic_test_pattern_generation), [model checking using Linear Time Logic](http://en.wikipedia.org/wiki/Model_checking),
[planning in artificial intelligence](http://en.wikipedia.org/wiki/Artificial_intelligence#Planning) and [haplotyping in bioinformatics](http://en.wikipedia.org/wiki/Haplotype). 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](http://arxiv.org/abs/quant-ph/0702144),[10](http://www.scottaaronson.com/blog/?p=207),[11](http://cacm.acm.org/magazines/2010/2/69352-recent-progress-in-quantum-algorithms/fulltext)]. 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](http://arxiv.org/abs/1006.4014)]. 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](http://arxiv.org/abs/quant-ph/0702144)] in practice. This could be a good topic for discussion.

> **Comments:**
> **username_13**: Please accept my invitation to join: https://quantumcomputing.stackexchange.com/ .  

---

### Answer by username_5 on 2012-02-17. Score: -6

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](http://en.wikipedia.org/wiki/Quantum_algorithm)
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.

> **Comments:**
> **username_6**: "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).  
> **username_5**: 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.  
> **username_8**: What do you mean by "increasingly unstructured databases"? A database looks like something pretty ordered by definition.  

---

