To simulate arbitrary single-qubit rotation, we need only simulate the X-rotation and Z-rotation, then make the decomposition of $\hat U = \hat R_x(\gamma) \hat R_z(\beta) \hat R_x(\alpha)$ ..

Let us firstly introduce the single-qubit rotation unit:

$$ \begin{aligned} \ket{\psi} &\rightarrow \ket{ini} &&=\textrm{CZ}_{0,1}(\ket{\psi}_0\otimes \ket{+}_1) \\ &\rightarrow \ket{fin:s} &&= \hat P_{(\theta, \phi) = (\pi/2, \xi)}^{(\textrm{on qubit-0})}(s)\ket{ini} \\ & && = H Z^s e^{\ti Z \xi/2} \ket{\psi} \end{aligned} $$

(neglect global phase.) State $\ket{+}$ is the eigenstate of $X$ , with $1$ eigenvalue. The probabilities to find $s = 0, 1$ are both $1/2$ ,.. By circuit model we illustrate this unit as

Such single-qubit rotation unit together with single-qubit Hadamard gate and Pauli gates would offer us any single qubit rotation, by the fact that $HZH=X$ (even Hadamard gate can be implemented with $\xi =0$ )). Such unit can be viewed as the MBQC operation with graph state by $G(\{0, 1\}, \{(0,1)\})$ as the resource. We note that MBQC strategy could be different for different resource setup.

Cascading the unit, we can implement any rotation for single qubit with $5$ --qubit graph state with only single-qubit measurement. By

$$ \begin{aligned} \ket{G} = \prod_{i=3}^0\textrm{CZ}_{i,i+1}(\ket{\psi}\ket{+}^{\otimes 4}) \sim & G(\{0,1,2,3,4\}, \{ \\ & \indent (0, 1), (1, 2), (2, 3), (3, 4) \\ & \}), \end{aligned} $$

by GZ gates with $0$ as input qubit, we have (Raussendorf 2003)

$$ \begin{aligned} & \prod_{i=4}^1 \hat P_{(\theta, \phi) = (\pi/2, \xi_i)}(s_i)\ket{G} = \prod_{i=4}^1 HZ^{s_i} e^{\ti Z\xi_i / 2} \ket{\psi} \\ =& R_x(-\xi_4) X^{s_4}R_z(-\xi_3)Z^{s_3}R_x(-\xi_2)X^{s_2}Z^{s_1}R_z(-\xi_1) \ket{\psi} \\ =& X^{s_4}Z^{s_3}X^{s_2}Z^{s_1}R_x\Big((-1)^{1+s_3+s_1}\xi_4\Big)R_z\Big((-1)^{1+s_2}\xi_3\Big)R_x\Big((-1)^{1+s_1} \xi_2\Big)R_z(-\xi_1)\ket{\psi} \end{aligned} $$

By adaptively choosing $\xi_1=0, \xi_2 = (-1)^{1+s_1}\alpha, \xi_3=(-1)^{1+s_2} \beta, \xi_4=(-1)^{1+s_1+s_3} \gamma$ ,, we have any single-qubit rotation as (neglecting global phase factor)

$$ R_x(\gamma)R_z(\beta)R_x(\alpha)\ket{\psi} = X^{s_4+s_2}Z^{s_1+s_3}\prod_{i=4}^1 \hat P_{(\theta, \phi) = (\pi/2, \xi_i)}(s_i)\ket{G}. $$

The proof is as follows. The initial state reads

$$ \begin{aligned} \ket{ini} &= \textrm{CZ}_{0,1} \Big((u_0\ket{0}+u_1\ket{1})\otimes \ket{+}\Big) \\ &= \frac 1 {\sqrt{2}}\Big(u_0 \ket{0,0} + u_0\ket{0,1} + u_1\ket{1,0} - u_1\ket{1,1}\Big)\\ &= \frac 1 {\sqrt{2}} \Big(u_0 \ket{0}\ket{+} + u_1 \ket{1} \ket{-}\Big). \end{aligned} $$

We measure this state along the direction $(\pi/2, \xi)\sim (\cos \xi, \sin\xi, 0)$ on the first qubit(input), with the basis

$$ \begin{aligned} \ket{0: (\pi/2, \xi)} &= \frac 1 {\sqrt 2}\ket{0} +\frac 1 {\sqrt{2}} e^{\ti \xi} \ket{1}\\ \ket{1: (\pi/2, \xi)} &= \frac 1 {\sqrt 2}\ket{0} -\frac 1 {\sqrt{2}} e^{\ti \xi} \ket{1} \end{aligned} $$

or $\ket{s: (\pi/2, \xi)} = \frac 1 {\sqrt{2}} (\ket{0} + (-1)^s e^{\ti \xi}\ket{1})$ in short (( $s \in \{0, 1\}$ )). Then the possible outcome reads

$$ \begin{aligned} \ket{fin:s} &= \braket{s:(\pi/2,\xi)| ini} \\ &= \frac 1 2 \Big(u_0 \ket{+} + u_1(-1)^s e^{-\ti \xi}\ket{-}\Big) \\ &=\frac {e^{-\ti \xi/2}} {\sqrt{2}} H Z^s e^{\ti Z\xi /2}(u_0\ket{0}+ u_1\ket{1}). \end{aligned} $$

It is not normalized with the length as the probability to find result $s$ .. Obviously the probability of $0/1$ is the same.

The minimal implement of CNOT gate requires $4$ qubit in total(Raussendorf 2001). The graph state reads

$$ G(\{0, 1, 2, 3\}, \{(0, 2), (1, 2), (2, 3)\}). $$

The qubit $0, 1$ are input qubit, while $1, 3$ is the output qubit. Actually, we note $1$ as the controlling qubit.

Formally, the CNOT unit reads

$$ \begin{aligned} \ket{c}\otimes\ket{\psi} & \rightarrow \ket{ini} &&= \textrm{CZ}_{0,2}\textrm{CZ}_{1,2}\textrm{CZ}_{2,3} \Big(\ket{\psi}_0 \ket{c}_1 \ket{+}_2 \ket{+}_3 \Big) \\ & \rightarrow \ket{fin: s_0, s_2} && = \hat P_{(\theta,\phi) = (\pi/2, 0)}^{(\textrm{on qubit-2})}(s_2) \hat P_{(\theta,\phi) = (\pi/2, 0)}^{(\textrm{on qubit-1})}(s_0)\ket{ini} \\ & && = \Big(Z^{s_0}\otimes (X^{s_2}Z^{s_0})\Big) \textrm{CNOT} (\ket{c}\otimes \ket{\psi}) \end{aligned} $$

with $\ket{c}$ being the controlling qubit.

The proof is as follows.

Note the basis along $(\theta,\phi) = (\pi/2, 0)$ is the eigenstates of $X$ , , i.e.,

$$ \ket{s: (\pi/2, 0)} = \frac 1 {\sqrt{2}}(\ket{0} + (-1)^s \ket{1}). $$

Thus, we have

$$ \begin{aligned} \ket{fin: s_0, s_2} &= \bra{s_0, s_2:(\pi/2,0)}\textrm{CZ}_{0,2}\textrm{CZ}_{1,2}\textrm{CZ}_{2,3} \ket{\psi}_0 \ket{c}_1 \ket{+}_2 \ket{+}_3 \\ &=\bra{s_2:(\pi/2,0)} \textrm{CZ}_{1,2}\textrm{CZ}_{2,3} \ket{c}_1 (H Z^{s_0}\ket{\psi})_2 \ket{+}_3 \\ &= \sum_{s\in \{0, 1\}}\braket{s|c}\bra{s_2:(\pi/2,0)} \textrm{CZ}_{23}\ket{s}_1 (Z^s H Z^{s_0}\ket{\psi}_2)\ket{+}_3 \\ &= \sum_{s\in \{0, 1\}} \braket{s|c} \ket{s}_1 \Big(H Z^{s_2} Z^s H Z^{s_0}\ket{\psi}_3\Big) \\ &= (1\otimes HZ^{s_2}) (\textrm{CZ}_{1,3}) (1\otimes HZ^{s_0}) \ket{c}_1 \ket{\psi}_3 \\ &= (1\otimes X^{s_2}) (1\otimes H) (Z\otimes X)^{s_0} \textrm{CZ}_{1,3} (1\otimes H) \ket{c}_1 \ket{\psi}_3 \\ &=\Big(Z^{s_0}\otimes X^{s_2}Z^{s_0}\Big) \textrm{CNOT}_{1,3}(\ket{c}_1\ket{\psi}_3) \end{aligned} $$

We used the following property of (Clifford algebra):

$$ \begin{aligned} Z^s H &= H X^s \\ H Z^s &= X^s H \\ \textrm{CNOT} &= (1\otimes H)\textrm{CZ} (1\otimes H) \\ X^s Z &= (-1)^s Z X^s \\ \textrm{CZ}(1\otimes X^s) &= \begin{bmatrix} X^s & 0 \\ 0 & Z X^s \end{bmatrix} = (1\otimes X^s)\begin{bmatrix} 1 & 0 \\ 0 & (-1)^s \end{bmatrix}\begin{bmatrix} 1 & 0 \\ 0 & Z \end{bmatrix} = (Z^s \otimes X^s)\textrm{CZ} \end{aligned} $$

We need only to prove the cascading of L-MBQC unit preserve the format. Then by cascading the single-qubit rotation and CNOT any unitary can be simulated.

For this, we denote single qubit syntax $X, Z$ as $C$ ,, a general L-MBQC unit reads

$$ \hat U \ket{\psi}_O = C_O M_{V-O} E \ket{\psi}_I \otimes \ket{+}_{V-I}. $$

Then the cascading

$$ \begin{aligned} \hat U_2 \hat U_1\ket{\psi}_O &= C_{O_2} M_{V_2 - O_2} E_{V_2} \Big((\hat U_1 \ket{\psi})_{I_2} \otimes \ket{+}_{V_2 - I_2}\Big) \\ &= C_{O_2} M_{V_2-O_2}E_{V_2} \Big(C_{O_1} M_{V_1-O_1} E_{V_1} (\ket{\psi}_{I_1} \otimes \ket{+}_{V_1-I_1}) \otimes \ket{+}_{V_2-I_2} \Big) \\ &= C_{O_2}C'_{O_1} M'_{V_2-O_2} M_{V_1-O_1} E_{V_2}E_{V_1} \ket{\psi}_{I_1} \otimes \ket{+}_{V_1-I_1 + V_2-I_2}. \end{aligned} $$

We note that $V_1 \cap V_2 = O_1$ thus $(V_1-O_1) \cap V_2 = \varnothing$ .. That is why we have

$$ E_{V_2} M_{V_1-O_1} = M_{V_1-O_1} E_{V_2}. $$

By standardization we can always move $C$ , to the left side. q.e.d.

Without loss of generality, let the classical part of adjoint system is deterministic (classical non-deterministic part could be absorbed in quantum measurement). Then the procedure reads:

1. Perform proper measurement on $\Psi$ . .. This could be done adaptively.
2. Input the result of measurement of $\Psi$ . . as a bit-string into the classical part.
3. Get the classical output within polynomial time and solve the problem.

The ability of performing measurement on $\Psi$ . . is to efficiently sampling the bit-string with the distribution $p_z$ .:.. The adaptive measurement is actually the autoregressive random process based on $\Psi$ . .. All bitstrings by such distribution could used to solve the NP problem via the classical part.

The requirement of bounded success probability means

$$ \frac 1 2 \lt \sum_{z \sim p_z} |\braket{z|\Psi}|^2 \leq n_p 2^{-E_g(\Psi)} \lt n_z 2^{-n + \delta}, $$

where $\ket{z}$ is the product state generated by the given bitstring, and $n_z$ is the number of ``good’’ bitstrings, formally the size of support of $p_z$ .:.: $n_z = |\{z: p_z(z) \gt 0\}|$ .. Then we have

$$ n_z \gt 2^{n-\delta - 1} \Rightarrow \frac {n_z} {2^n} \gt 2^{-\delta - 1}. $$

This means that by the assumption that local-measurement augmented classical computer could solve NP problem with bounded probability, the probability of finding a ``good’’ bitstring pure randomly is also bounded.

Then we solve the problem on a pure classical machine. We still need to call the classical part of the adjoint system. By purely randomly generating bitstrings, the probability of hitting a ``good’’ one is greater than $2^{-1-\delta}$ .. Then we repeatedly call such generating and the classical part subroutine, the probability of failed is

$$ \mathbb{P}(\textrm{failed } k ) \lt \Big(1 - 2^{-1-\delta}\Big)^k \leq e^{-k 2 ^{-1-\delta}}. $$

It could be exponentially small. Thus, given the success probability bound $p_f$ ,, one need only call such process $k \sim 2^{1+\delta} \log 1/p_f$ .. Note that certify an answer of NP problem needs only polynomial time, such pure classical system could solve this NP problem with bounded success probability and polynomial time cost.

In MBQC, we introduce adaptive measurement and post-processing to avoid the probabilistic nature of quantum measurement. This helps us specify the distribution $p_z$ .:.. But generally, the ability to handle all possible output of measurement on $n-k$ qubits and obtain the same state on the remaining $k$ - qubits is non-trivial. In Ref. (Nest 2007), the authors introduced CQ-universality to describe such property. In Ref. (Haddadi 2019), the authors shows the geometric measure for graph states up to $7$ qubits.

Consider the input state reads

$$ \ket{\psi} = \sum_{\sigma} x_\sigma \ket{\sigma}, $$

where $\sigma$ is $k$ - -length bitstrings. Then the graph state reads

$$ \prod_{l=1}^k \textrm{CZ}_{0, l} \Big(\ket{+}_0 \otimes \ket{\psi} \Big) = \frac 1 {\sqrt{2}}\sum_{\sigma} x_\sigma \ket{0, \sigma} + x_\sigma (-1)^{\sum_{l=1}^j \sigma_l}\ket{1, \sigma}. $$

The basis of measurement reads

$$ \begin{aligned} \ket{0: (2\tau, \pi/2)} &= \cos \tau \ket{0} + \ti \sin \tau \ket{1} \\ \ket{1: (2\tau, \pi/2)} &= \sin\tau \ket{0} - \ti \cos \tau \ket{1} \end{aligned} $$

Then the projection on each branch

$$ \begin{aligned} s = 0 &\Rightarrow \frac 1 {\sqrt{2}} \sum_\sigma x_\sigma \big(\cos \tau - \ti \sin \tau (-1)^{\sum \sigma_l}\big) \ket{\sigma} \\ & = \frac 1 {\sqrt{2}} \sum_\sigma x_\sigma e^{-\ti \tau \sum \sigma_l} \ket{\sigma} \\ &= \frac 1 {\sqrt{2}} e^{-\ti \tau Z_1\cdots Z_k} \ket{\psi} \\ s = 1 &\Rightarrow \frac 1 {\sqrt{2}} \sum_\sigma x_\sigma \big(\sin \tau + \ti \cos \tau (-1)^{\sum \sigma_l}\big) \ket{\sigma} \\ &= \frac {\ti} {\sqrt{2}} \sum_\sigma x_\sigma (-1)^{\sum \sigma_l} e^{-\ti \tau \sum \sigma_l} \ket{\sigma} \\ &= \frac {\ti} {\sqrt{2}} \Big(\prod_{l=1}^k Z_l \Big)e^{-\ti \tau Z_1\cdots Z_k} \ket{\psi} \end{aligned} $$

q.e.d.