Efficient quantum pseudorandomness with simple graph states

Measurement based (MB) quantum computation allows for universal quantum computing by measuring individual qubits prepared in entangled multipartite states, known as graph states. Unless corrected for, the randomness of the measurements leads to the generation of ensembles of random unitaries, where each random unitary is identified with a string of possible measurement results. We show that repeating an MB scheme an efficient number of times, on a simple graph state, with measurements at fixed angles and no feedforward corrections, produces a random unitary ensemble that is an $\varepsilon$-approximate $t$ design on $n$ qubits. Unlike previous constructions, the graph is regular and is also a universal resource for measurement based quantum computing, closely related to the brickwork state.

Figure 1

MB scheme on a two-qubit cluster state; the input (squared) qubit when measured at an angle $\alpha$ in the $XY$ plane results in propagation of the input state to output along with application of a random unitary $U=H{Z}^{m}Z\left(\alpha \right)$.

Figure 2

Example of a four spins 1D system. The local Hamiltonians $h_{i,i+1}$ have a range of 2 (i.e., act on nearest-neighbor spins). For example, $h_{1,2}$ acts on spins 1 and 2. Translational invariance means that any $h_{i,i+1}$ has the same form on all two-qubit systems ($i$, $i+1$). In this case the total Hamiltonian of the system of four spins can be written as a sum of local Hamiltonians, i.e., $\mathrm{H}=h_{1,2}+h_{2,3}+h_{3,4}$.

Figure 3

Two-row, five-column brickwork state gadget giving rise to $S_{I_1}$.

Figure 4

Two-row, five-column brickwork state gadget giving rise to $S_{I_2}$.

Figure 5

Graph gadget $G_n$ pictured here for even $n$ (the odd $n$ case follows straightforwardly).