27 citations · 183 across the 26 of their papers we have counts for
31 papers
Testing bosonic and fermionic Gaussian states with a constant number of copies
Jop Briët, Davi Castro-Silva, Michael Walter +1
Bosonic and fermionic Gaussian quantum states are families of quantum states that play a central role in quantum physics and quantum information processing. We study the problem of…
An algorithmic Polynomial Freiman-Ruzsa theorem
Davi Castro-Silva, Jop Briët, Srinivasan Arunachalam +2
We provide algorithmic versions of the Polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao (Ann. of Math., 2025). In particular, we give a polynomial-time algorithm…
Clifford testing: algorithms and lower bounds
Marcel Hinsche, Zongbo Bao, Philippe van Dordrecht +3
We consider the problem of Clifford testing, which asks whether a black-box -qubit unitary is a Clifford unitary or at least -far from every Clifford unitary. We gi…
On the threshold for Szemerédi's theorem with random differences
Jop Briët, Davi Castro-Silva
Using recent developments on the theory of locally decodable codes, we prove that the critical size for Szemerédi's theorem with random differences is bounded from above by $N^{1-\…
Noisy decoding by shallow circuits with parities: classical and quantum
Jop Briët, Harry Buhrman, Davi Castro-Silva +1
We consider the problem of decoding corrupted error correcting codes with NC circuits in the classical and quantum settings. We show that any such classical circuit can…
Random restrictions of high-rank tensors and polynomial maps
Jop Briët, Davi Castro-Silva
Motivated by a problem in computational complexity, we consider the behavior of rank functions for tensors and polynomial maps under random coordinate restrictions. We show that, f…