3Tim Gowers - Computational Complexity and Quantum Compuation
http://sms.cam.ac.uk/collection/545358
Computational complexity is the study of what resources, such as time and memory, are needed to carry out given computational tasks, with a particular focus on lower bounds for the amount needed of these resources. Proving any result of this kind is notoriously difficult, and includes the famous problem of whether P = N P . This course will be focused on two major results in the area. The first is a lower bound, due to Razborov, for the number of steps needed to determine whether a graph contains a large clique, if only “monotone” computations are allowed. This is perhaps the strongest result in the direction of showing that P and N P are distinct (though there is unfortunately a very precise sense in which the proof cannot be developed to a proof of the whole conjecture). The second is Peter Shor’s remarkable result that a quantum computer can factorize large integers in
polynomial time. In order to present these two results, it will be necessary to spend some time discussing some of the basic concepts of computational complexity, such as the relationship between Turing machines and the more obviously mathematical notion of circuit complexity, and an introduction to what a quantum computation actually is. For the latter, no knowledge of quantum mechanics will be expected, and scarcely any will be imparted during the course: it is possible to understand quantum computation in a very “pure mathematics” way. The reason this is a graduate course rather than a Part III course is that I intend to give several lectures in an informal style that would be hard to examine. It is not because the material will be more advanced: indeed, my aim will be to make allowances for the fact that people will not be working on it with an exam in mind, and to make the course as easy to follow as I can. Having said that, the main results will be proved in full: the informal discussion will be with a view to making these proofs more comprehensible.
The collection will have 12 graduate level lectures which are currently being given during the Easter term 2009. Many thanks to Adrian Callum-Hinshaw for his help with these video lectures.14402010Mon, 25 Jan 2010 07:54:54 +0000Sun, 26 Apr 2009 22:08:00 +0100ensms-support@ucs.cam.ac.ukTim Gowers - Computational Complexity and Quantum Compuation
http://sms.cam.ac.uk/collection/545358
http://rss.sms.cam.ac.uk/itunes-image/546662.jpghttp://video.search.yahoo.com/mrssTim Gowers - Computational Complexity and Quantum CompuationComputational complexity is the study of what resources, such as time and memory, are needed to carry out given computational tasks, with a particular focus on lower bounds for the amount needed of these resources. Proving any result of this kind is notoriously difficult, and includes the famous problem of whether P = N P . This course will be focused on two major results in the area. The first is a lower bound, due to Razborov, for the number of steps needed to determine whether a graph contains a large clique, if only “monotone” computations are allowed. This is perhaps the strongest result in the direction of showing that P and N P are distinct (though there is unfortunately a very precise sense in which the proof cannot be developed to a proof of the whole conjecture). The second is Peter Shor’s remarkable result that a quantum computer can factorize large integers in
polynomial time. In order to present these two results, it will be necessary to spend some time discussing some of the basic concepts of computational complexity, such as the relationship between Turing machines and the more obviously mathematical notion of circuit complexity, and an introduction to what a quantum computation actually is. For the latter, no knowledge of quantum mechanics will be expected, and scarcely any will be imparted during the course: it is possible to understand quantum computation in a very “pure mathematics” way. The reason this is a graduate course rather than a Part III course is that I intend to give several lectures in an informal style that would be hard to examine. It is not because the material will be more advanced: indeed, my aim will be to make allowances for the fact that people will not be working on it with an exam in mind, and to make the course as easy to follow as I can. Having said that, the main results will be proved in full: the informal discussion will be with a view to making these proofs more comprehensible.
The collection will have 12 graduate level lectures which are currently being given during the Easter term 2009. Many thanks to Adrian Callum-Hinshaw for his help with these video lectures.Tim Gowers - Computational Complexity and Quantum CompuationComputational complexity is the study of what resources, such as time and memory, are needed to carry out given computational tasks, with a particular focus on lower bounds for the amount needed of these resources. Proving any result of this kind is notoriously difficult, and includes the famous problem of whether P = N P . This course will be focused on two major results in the area. The first is a lower bound, due to Razborov, for the number of steps needed to determine whether a graph contains a large clique, if only “monotone” computations are allowed. This is perhaps the strongest result in the direction of showing that P and N P are distinct (though there is unfortunately a very precise sense in which the proof cannot be developed to a proof of the whole conjecture). The second is Peter Shor’s remarkable result that a quantum computer can factorize large integers in
polynomial time. In order to present these two results, it will be necessary to spend some time discussing some of the basic concepts of computational complexity, such as the relationship between Turing machines and the more obviously mathematical notion of circuit complexity, and an introduction to what a quantum computation actually is. For the latter, no knowledge of quantum mechanics will be expected, and scarcely any will be imparted during the course: it is possible to understand quantum computation in a very “pure mathematics” way. The reason this is a graduate course rather than a Part III course is that I intend to give several lectures in an informal style that would be hard to examine. It is not because the material will be more advanced: indeed, my aim will be to make allowances for the fact that people will not be working on it with an exam in mind, and to make the course as easy to follow as I can. Having said that, the main results will be proved in full: the informal discussion will be with a view to making these proofs more comprehensible.
The collection will have 12 graduate level lectures which are currently being given during the Easter term 2009. Many thanks to Adrian Callum-Hinshaw for his help with these video lectures.Cambridge UniversityJ. Oppenheimjo270@cam.ac.ukhttp://sms.cam.ac.uk/collection/545358Tim Gowers - Computational Complexity and Quantum CompuationJ. Oppenheimjo270@cam.ac.ukhttp://sms.cam.ac.uk/person/jo2702009-04-26T22:08:00+01:00DAMTPGowers Lecture 01ucs_sms_545358_545992
http://sms.cam.ac.uk/media/545992
Gowers Lecture 10ucs_sms_545358_603689
http://sms.cam.ac.uk/media/603689
Gowers Lecture 2ucs_sms_545358_545985
http://sms.cam.ac.uk/media/545985
Gowers Lecture 3ucs_sms_545358_547720
http://sms.cam.ac.uk/media/547720
Gowers Lecture 4ucs_sms_545358_547673
http://sms.cam.ac.uk/media/547673
Gowers Lecture 5ucs_sms_545358_548183
http://sms.cam.ac.uk/media/548183
Gowers Lecture 6ucs_sms_545358_549398
http://sms.cam.ac.uk/media/549398
Gowers Lecture 7ucs_sms_545358_549440
http://sms.cam.ac.uk/media/549440
Gowers Lecture 8ucs_sms_545358_603698
http://sms.cam.ac.uk/media/603698
Gowers Lecture 9ucs_sms_545358_637312
http://sms.cam.ac.uk/media/637312
545358