Derandomizing Quantum Circuits with Measurement-Based Unitary Designs

Entangled multipartite states are resources for universal quantum computation, but they can also give rise to ensembles of unitary transformations, a topic usually studied in the context of random quantum circuits. Using several graph state techniques, we show that these resources can “derandomize” circuit results by sampling the same kinds of ensembles quantum mechanically, analogously to a quantum random number generator. Furthermore, we find simple examples that give rise to new ensembles whose statistical moments exactly match those of the uniformly random distribution over all unitaries up to order $t$, while foregoing adaptive feedforward entirely. Such ensembles—known as $t$ designs—often cannot be distinguished from the “truly” random ensemble, and so they find use in many applications that require this implied notion of pseudorandomness.

Figure 1

One step in the random circuit construction of an approximate $t$ design over $n$ qubits. The shift gate $U_S$ and its inverse are together either randomly applied or not applied, with the two-qubit unitaries in between randomly sampled from the universal set $\mathcal{U}$. Polynomially many iterations of this random circuit will implement an approximate $t$ design [10].

Figure 2

The fundamental random unitary transformation induced by measurement on a graph state. Nodes are qubits initially prepared in the $+1$ eigenstate $|+⟩$ of the Pauli $X$ operator, and edges indicate entanglement via the controlled-z (cz) operation. Angles $\varphi$ indicate projective measurement direction in the Pauli $XY$ plane, with the random outcome bit $m$; output nodes are unmeasured and therefore blank. Here we explicitly include an arbitrary input (square node) state $|\psi ⟩$ and the output; $U_m(\varphi )$ is given by Eq. (3).

Figure 3

By measuring the qubits as indicated, (a) implements randomly $Z^{m_1\oplus m_3}{X}^{m_2\oplus m_4}Z(\theta {)}^{m_2\oplus 1}$ while (b) implements randomly $Z^{m_3}{X}^{m_2\oplus m_4}X(\theta {)}^{m_3\oplus 1}{Z}^{m_1}$, where $\oplus$ denotes bitwise sum (ignoring unimportant global phases).

Figure 4

Graph and measurement pattern implementing the two-qubit gate $U_{ij}=(Z_i{Z}_j{)}^M(Z(\pi /2{)}_{i}Z(\pi /2{)}_{j}C{Z}_{ij}{)}^{m_6\oplus 1}\times X_i^{m_4}{X}_j^{m_2}{Z}_i^{m_3}{Z}_j^{m_1}$, where $M$ is a random bit which is a function of measurement results $m_{5,7,8,9}$.

Figure 5

Measurement gadgets combined in this way sample from a universal set of two-qubit unitaries, given in Eq. (4).

Figure 6

From bottom to top the $t=1,2,\dots ,7$ frame potentials, given by the difference $\mathrm{\Delta }F$ from the exact bound (logarithmic scale) versus linear cluster length $L$ (interpolated). For each we consider three measurement patterns: dotted lines for those consisting entirely of the angle $\pi /4$; dashed lines for those consisting of a single measurement angle ${\varphi }_{\min }$ that minimizes the frame potential; and solid lines for a full multiangle minimization (performed in Matlab). One sees that the former approach the bound exponentially, albeit with a decreasing rate, as predicted by random quantum circuit results [32]. The latter can be seen to drop much more quickly beyond $L=4$. Other than the trivial $t=1$ case, only the $t=2$, 3 curves reach $\mathrm{\Delta }F=0$ (inset), e.g., the exact design for $L=5$. Despite the $t=4$, 5 curves coming very close to zero, an analytic solution at $L=9$ has not been found [33].