tag:blogger.com,1999:blog-3722233.post7228447394720113608..comments2023-03-20T21:49:52.361-05:00Comments on Computational Complexity: Quantum WorkshopLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-19244632499058695132012-10-03T15:40:54.812-05:002012-10-03T15:40:54.812-05:00We all know that Prof. Mulmuley's seminal work...We all know that Prof. Mulmuley's seminal works on using GCT to deduce some relations on the P-NP conjecture( specifically to prove P not equal to NP in characteristic zero) from the perspective of non-standard Riemann hypothesis is having a profound effect on both the fields of pure mathematics and theoretical computer science. <br /><br />But, does there exist any deep analysis to relate a hypothetical quantum version of the PCP theorem with both Church-Turing thesis and quantum computation,so that the two fields may have some powerful yet subtle connections?<br />Arka Bhattacharyahttps://www.blogger.com/profile/00801802507777720869noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58088852515551958402012-10-03T11:29:34.827-05:002012-10-03T11:29:34.827-05:00Was there any QIS Workshop discussion of the recen...Was there any QIS Workshop discussion of the recent work by Harvard's Alán Aspuru-Guzik, in collaboration with D-WAVE, that is described in the recent articles <i>"Solving quantum ground-state problems with nuclear magnetic resonance"</i> (2011) and <i>"Finding low-energy conformations of lattice protein models by quantum annealing"</i> (2012)? <br /><br />These articles introduce to QC/QIT/FTQC an ensemble of dynamical elements and mathematical idioms that, in recent decades, have proved to be spectacularly successful (both theoretically and experimentally) in improving our understanding of (classical) molecular dynamics and (quantum) chemistry … and so it is surprising to see (apparently) no talks relating to this fast-developing frontier in the QIS Workshop's program.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56532908482171605072012-10-02T14:32:44.352-05:002012-10-02T14:32:44.352-05:00The concept has existed for a long time (40 years,...The concept has existed for a long time (40 years, maybe? I don't know) under the name of "no sign problem", or rather, no sign problem for certain quantum Monte Carlo schemes.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36987244648133691572012-10-02T12:04:58.772-05:002012-10-02T12:04:58.772-05:00Stoquastic refers to a Hamiltonian that has real a...Stoquastic refers to a Hamiltonian that has real and nonpositive off-diagonal elements in the computational basis. It also refers to the corresponding ground states and Gibbs states, the latter having the property that all the elements of the density matrix are positive. Natural problems for states and Hamiltonians in this class, such as finding the ground state energy, are thought to be intermediate in complexity between their quantum and classical probabilistic counterparts, hence the name. <br /><br />I believe that resolving some complexity questions about stoquastic Hamiltonians is thought to be a key step in proving a quantum analog of the PCP theorem, although I might be confused about this since IANACS. All I know for sure is that a lot of people have become excited about proving complexity results for stoquastic Hamiltonians in the past few years. I believe the term was introduced in this paper http://arxiv.org/abs/quant-ph/0606140Anonymousnoreply@blogger.com