Humpty Dumpty sat on a wall, Humpty Dumpty had a great fall. All the king’s horses and all the king’s men Couldn’t put Humpty together again.

We refer to “query access” as the ability to perform the unitary transformation $U_t$ followed by a measurement on a quantum register consisting of $n$ qubits.

The simplified settings of this Letter correspond to a special class of $t$-doped Clifford circuits. In particular, one can always write $U_t=C_0{W}_1{W}_2\cdots W_t{C}_0^{\prime }$, where $C_0,C_0^{\prime }$ are Clifford, while $W_j$ are 1-doped Clifford circuits. The setting explored in this Letter corresponds to the special case where $[W_j,W_k]=0$ for $j,k\in 1,t/2$, and $W_{j+t/2}=C_j^{†}{W}_j{C}_j$ for $j\in 1,\dots ,t/2$, such that $[W_{j+t/2},W_j]\ne 0$, with $C_j$ being a set of commuting Clifford operators. In this manner, if $P$ is the Pauli generator not preserved by the action of $W_j$, then $C_j^{†}P{C}_j$ is also not preserved.

Note that this probability is different from the one displayed in Eq. (2). The reason is that Čebyšëv inequality allows us to say that $\mathcal{F}(V)=[1/(1+2^{2|A|-2|E|})]+O(ϵ)$ with probability $O({ϵ}^{-2}{2}^{-2|C|})$, while the more detailed analysis of [34] shows $\mathcal{F}(V)\ge [1/(1+2^{2|A|-2|E|})]$ [see Eq. (1)] with probability given by Eq. (2).