AQC 2016 - Simulated Quantum Annealing Can Be Exponentially Faster Than Classical
A Google TechTalk, June 27, 2016, presented by Elizabeth Crosson (Caltech)
ABSTRACT: Simulated Quantum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing: Cost functions with thin, high energy barriers can exhibit exponential separations between the run-time of classical simulated annealing, for which thermal fluctuations take exponential time to climb these barriers, and quantum annealing which can in some cases pass through such barriers efficiently, arguably by taking advantage of quantum tunneling.
In this talk we will describe a proof which demonstrates that the Markov chain underlying SQA can efficiently sample its target distribution and find the global minimum of such a spike cost function in polynomial time. This result provides evidence for the growing consensus that SQA inherits at least some of the advantages that arise from tunneling in QA, and we will emphasize techniques in the proof which contribute to a further understanding of both the equilibrium distribution and the nonequilibrium dynamics of SQA.
Presented at the Adiabatic Quantum Computing Conference, June 26-29, 2016, at Google's Los Angeles office.
Видео AQC 2016 - Simulated Quantum Annealing Can Be Exponentially Faster Than Classical канала Google TechTalks
ABSTRACT: Simulated Quantum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing: Cost functions with thin, high energy barriers can exhibit exponential separations between the run-time of classical simulated annealing, for which thermal fluctuations take exponential time to climb these barriers, and quantum annealing which can in some cases pass through such barriers efficiently, arguably by taking advantage of quantum tunneling.
In this talk we will describe a proof which demonstrates that the Markov chain underlying SQA can efficiently sample its target distribution and find the global minimum of such a spike cost function in polynomial time. This result provides evidence for the growing consensus that SQA inherits at least some of the advantages that arise from tunneling in QA, and we will emphasize techniques in the proof which contribute to a further understanding of both the equilibrium distribution and the nonequilibrium dynamics of SQA.
Presented at the Adiabatic Quantum Computing Conference, June 26-29, 2016, at Google's Los Angeles office.
Видео AQC 2016 - Simulated Quantum Annealing Can Be Exponentially Faster Than Classical канала Google TechTalks
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
![GTAC 2011: Automating Hadoop Stack Deployment and Testing](https://i.ytimg.com/vi/eUcej07dGu4/default.jpg)
![OpenMRS](https://i.ytimg.com/vi/tou-Ei_AKAw/default.jpg)
![Electrodynamic Signaling by the Dendritic Cytoskeleton (Google Workshop on Quantum Biology)](https://i.ytimg.com/vi/0OO8E1_GJ4o/default.jpg)
![Return to the RNAi World: Rethinking Gene Expression and...](https://i.ytimg.com/vi/81iN7zzlIPM/default.jpg)
![Visual 3D modeling of real-world objects and scenes from...](https://i.ytimg.com/vi/v-d0CQUQlAs/default.jpg)
![Improvement of Web Accessibility in Japan](https://i.ytimg.com/vi/OIDynkrTmN0/default.jpg)
![Analyzing the Privacy of Android Apps](https://i.ytimg.com/vi/hYSkpjndBjE/default.jpg)
![Knowledge Connectivity vs. Synchrony Requirements for Fault-Tolerant Agreeme...](https://i.ytimg.com/vi/_K-4mVXWfdc/default.jpg)
![PhotoTechEDU Day 6: Digital Camera Image Processing...](https://i.ytimg.com/vi/8ZTVal7ofZ8/default.jpg)
![Sparse codes for natural sounds](https://i.ytimg.com/vi/uvrIfb9_qzQ/default.jpg)
![GTAC 2016: OpenHTF - The Open-Source Hardware Testing Framework](https://i.ytimg.com/vi/bC5YhAo1kHc/default.jpg)
![Modeling Science: Dynamic Topic Models of Scholarly...](https://i.ytimg.com/vi/8nBE5Qm8y6I/default.jpg)
![GTAC 2013: Web Performance Testing with WebDriver](https://i.ytimg.com/vi/0_kAPWSZNY4/default.jpg)
![Google Production Environment](https://i.ytimg.com/vi/dhTVVWzpc4Q/default.jpg)
![Building Brains to Understand the World's Data](https://i.ytimg.com/vi/4y43qwS8fl4/default.jpg)
![Complexities of Capacity Management for Distributed Services](https://i.ytimg.com/vi/pOo0oKNM9I8/default.jpg)
![GTAC 2013: Espresso: Fresh Start to Android UI Testing](https://i.ytimg.com/vi/T7ugmCuNxDU/default.jpg)
![GTAC 2013: AddressSanitizer, ThreadSanitizer and MemorySanitizer -- Dynamic Testing Tools for C++](https://i.ytimg.com/vi/Q2C2lP8_tNE/default.jpg)
![The Paxos Algorithm](https://i.ytimg.com/vi/d7nAGI_NZPk/default.jpg)
![Sensor Fusion on Android Devices: A Revolution in Motion Processing](https://i.ytimg.com/vi/C7JQ7Rpwn2k/default.jpg)
![Flower: A Friendly Federated Learning Framework](https://i.ytimg.com/vi/NaOVX-lp5Fo/default.jpg)