Showing quant-phShow all
2 papers · 1 filter
quant-ph2025
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…
quant-ph2024
Grothendieck inequalities characterize converses to the polynomial method
Jop Briët, Francisco Escudero Gutiérrez, Sander Gribling
A surprising 'converse to the polynomial method' of Aaronson et al. (CCC'16) shows that any bounded quadratic polynomial can be computed exactly in expectation by a 1-query algorit…