It is a major challenge in quantum fault-tolerance to obtain low-overhead protocols for performing non-Clifford gates. In this vein, we construct quantum codes with low-weight stabilizers that support transversal (i.e. low-depth) implementations of the non-Clifford $C^{r-1}Z$ gate, for every constant $r\geq 3$. In particular, we obtain length-$n$ quantum LDPC ... more >>>

Consider the following problem of learning an unknown linear order on $n$ items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample:
a pair of items in the wrong order. The goal is to identify ... more >>>

We prove exponential lower bounds for $k$-DNF resolution on random $3$-CNF formulas throughout the range $k=O(\sqrt{\log n})$ at every constant clause density above the elementary first-moment bound for unsatisfiability. For random $3$-CNFs this improves Alekhnovich's range $k=O(\sqrt{\log n/\log\log n})$, and matches the $O(\sqrt{\log n})$ range obtained by Sofronova and Sokolov ... more >>>