75 citations · 188 across the 17 of their papers we have counts for
22 papers
Beatty Sequences for a Quadratic Irrational: Decidability and Applications
Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic
Let and belong to the same quadratic field. We show that the inhomogeneous Beatty sequence is synchronized, in the sense that there is…
Sample-optimal classical shadows for pure states
Daniel Grier, Hakop Pashayan, Luke Schaeffer
We consider the classical shadows task for pure states in the setting of both joint and independent measurements. The task is to measure few copies of an unknown pure state in…
Decidability for Sturmian words
Philipp Hieronymi, Dun Ma, Reed Oei +3
We show that the first-order theory of Sturmian words over Presburger arithmetic is decidable. Using a general adder recognizing addition in Ostrowski numeration systems by Baranwa…
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…
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…
String Attractors for Automatic Sequences
Luke Schaeffer, Jeffrey Shallit
We show that it is decidable, given an automatic sequence and a constant , whether all prefixes of have a string attractor of size . Using a decision pro…