One of the main milestones in quantum information science is to realise quantum devices that exhibit an exponential computational advantage over classical ones without being universal quantum computers, a state of affairs dubbed quantum speedup, or sometimes "quantum computational supremacy". The known schemes heavily rely on mathematical assumptions that are plausible but unproven, prominently results on anticoncentration of random prescriptions. In this work, we aim at closing the gap by proving two anticoncentration theorems and accompanying hardness results, one for circuit-based schemes, the other for quantum quench-type schemes for quantum simulations. Compared to the few other known such results, these results give rise to a number of comparably simple, physically meaningful and resource-economical schemes showing a quantum speedup in one and two spatial dimensions. At the heart of the analysis are tools of unitary designs and random circuits that allow us to conclude that universal random circuits anticoncentrate as well as an embedding of known circuit-based schemes in a 2D translation-invariant architecture.
https://arxiv.org/abs/1706.03786https://arxiv.org/pdf/1706.03786.pdf
https://arxiv-vanity.com/papers/1706.03786
Scited by: Abel Molina, Abhinav Deshpande, Adel SOHBI, Andras Molnar, Anna Pappa, Anurag Anshu, Aram Harrow, Daniel Miller, Dave Bacon, David Elkouss, David Mesterhazy, Dawei Ding, Dominic Williamson, Earl Campbell, Eleanor Rieffel, Fabiano Andrade, Florian Speelman, Francesco Battistel, Frédéric Grosshans, HA, Ingo Roth, Ish Dhand, James Seddon, Jianxin Chen, Jizhou Wu 吴骥宙, Joe Fitzsimons, Kunal Sharma, Lorenzo Catani, Man-Hong Yung, Manoj G. Gowda, Mark Howard, Markus Kesselring, Michael Jarret, Michal Oszmaniec, mick, Murphy Yuezhen Niu, Nayeli A. Rodriguez Briones, Nicolas Delfosse, Nikolas Breuckmann, Ninnat Dangniam, Noon van der Silk, Peter Wittek, Raul Garcia-Patron, Richard Kueng, Robert Raussendorf, Rui Chao, Sirui Lu, Stephen Bartlett, Stephen Jordan, Steve Flammia, Stuart Hadfield, Vincent Russo, Vojtech Havlicek, Xiaobin Zhao, Xin Wang, You Zhou, Yupan Liu, Zak Webb, Zi-Wen Liu, Zoltán Zimborás
0 comments