8 problems

Let $n$ be the number of qubits in the brickwork model, let $t$ denote the circuit depth or number of layers, and let…

Let $K_n$ be the complete graph on $n$ vertices, and consider a gadget associated with a family of 2-local gates having parameter $a=\frac{5}{9}$ in the notation of the paper. Let…

Let $n\geq 3$, let $\mathcal{G}$ be a fixed connected graph, and let $\mathcal{E}$ be a 2-local unitary circuit ensemble. Write…

Let $U$ be a quantum circuit drawn from a distribution $\mathcal{D}$, and let … A classical algorithm is polynomial-time if it runs in time polynomial in the circuit description an…

Small incremental magic conjecture. One should have

For $n$ qubits, let $\mathsf{sequ}(L)$ denote the layout consisting of $L$ CNOT units in sequence, and let $\mathsf{spin}(L)$ denote the alternating spin layout. Write…

Let $\mathcal M'_T$ be the commutant of the algebra generated by the operators $M_a$ and $M_{ab,\iota}+R_{2t}M_{ab,\iota}R_{2t}$ on the periodic chain of $2t$ spins, where $R_{2t}$…

Toffoli-gate bound conjecture. To synthesize the circuit for $S_p$, one needs at most $n$ Toffoli gates: