Quantum Algorithms - John Watrous - USEQIP 2012

Prof. John Watrous discusses quantum algorithms during the 2012 Undergraduate School on Experimental Quantum Information Processing (USEQIP) at the Institute for Quantum Computing.

For More:
http://iqc.uwaterloo.ca/conferences/u...
http://iqc.uwaterloo.ca
http://www.facebook.com/QuantumIQC
http://www.twitter.com/QuantumIQC
QuantumFactory Blog: http://quantumfactory.wordpress.com

• Category

  Science & Technology

[jepkofficial]

Future programming is great but it would be nice to build one larger than 5 atoms first. :/

[delerium2k]

Aaronson himself agrees that it is not known with certainty whether classical can run QC in poly time. Just like it is not *commonly* known whether P and NP are one in the same. Post-IQP collapses the poly hierarchy if it can be simulated with a log algo... Not known again whether such an algo exists but this can collapse the exp probability which makes QC so difficult for classical machines

[xknowledgeisfreex]

It is known that BQP is included in PSPACE. So we can simulate quantum algorithms by classical algorithms, just not very efficiently. :)

[delerium2k]

The truth is not told, its proven. There is no proof to show that classical Turing machines can't efficiently handle quantum computations - that is an assumption. In the obvious sense the required resources mushroom, but most of this is junk. No math is impossible for a Turing machine, as we know they are capable of all math, even quantum computations. The only problem is efficiency, therefore with a clever enough algo, it can be done.

[Ravi Mohan]

Its not a mistake. Its the truth which was told by Feynman. At classical level "nearly" all the quantum effects vanish.

[delerium2k]

the quantum people make a very large mistake in assuming classical machines can't efficiently emulate quantum systems