291 citations · 664 across the 28 of their papers we have counts for
Showing 2018Show all
2 papers · 1 filter
quant-ph2018★ 2 cited
Classical lower bounds from quantum upper bounds
Shalev Ben-David, Adam Bouland, Ankit Garg +1
We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove t…
quant-ph2018★ 291 cited
Quantum Supremacy and the Complexity of Random Circuit Sampling
Adam Bouland, Bill Fefferman, Chinmay Nirkhe +1
A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A l…