activity
20112024
most citedExponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

37 citations · 39 across the 6 of their papers we have counts for

collaborators
Showing 2021Show all

2 papers · 1 filter

quant-ph2021

Classical algorithms for Forrelation

Sergey Bravyi, David Gosset, Daniel Grier +1

We study the forrelation problem: given a pair of -bit Boolean functions and , estimate the correlation between and the Fourier transform of . This problem is know…

quant-ph2021

Interactive quantum advantage with noisy, shallow Clifford circuits

Daniel Grier, Nathan Ju, Luke Schaeffer

Recent work by Bravyi et al. constructs a relation problem that a noisy constant-depth quantum circuit (QNC) can solve with near certainty (probability ), but that an…