Introduction to MBQC

Here, we provide an introduction to the measurement-based quantum computing (MBQC), more specifically the one-way model of MBQC.

If you already know the basics of MBQC and would like to read about LC-MBQC (MBQC on local-Clifford decorated graph state), go to Introduction to LC-MBQC. We assume basic understnding of quantum mechanics.

For those new to quantum mechanics and quantum information, qiskit provides a nice introduction (chapters 0-2 of the their textbook would be sufficient to understand our introduction here).

Introduction

Quantum computing utilizes entanglment to accelerate the computation of some class of problems, such as the prime factorization.

Quantum algorithms are very often expressed in the gate network model, which is a direct analog of the classical computers expressed in the network of logical bit operations (AND, OR, XOR, …).

The familiar quantum circuits thus express the time evolution of quantum bits (qubits) as they ‘pass through’ the quantum version of the logical operation.

Here, the entanglement, which is arguably the source of the power of quantum computing, is created and destroyed continuously - in a very crude way, this means that we don’t intuitively know where the quantum comes in 1.

Measurement-based (one-way) quantum computing, introduced by Raussendorf 2, has a different approach which can be called consumption of initially entangled resource state; first you create a large entangled quantum state (graph state \(|g\rangle\)), and the computation goes by measurements of qubits which drives the evolution of the quantum state. Entanglement is only required at the start, and all subsequent operations only reduce entanglement.

MBQC has several remarkable advantages that may motivate us to study further:

• Only single-qubit measurements are needed to perform the computation on the resource state.

• The resource state can be prepared in a depth of one using CZ gates which commute with each other. Further, they can be prepared offline, and/or can be based on probabilistic entangling operations.

• The depth of the computation is usually significantly smaller than the equivalent quantum circuit, which means computation might be less affected by finite coherence time.

One-way quantum computing

In one-way model, we perform quantum computation on the resource state, or equivalently the graph state, defined on methematical graph \(G = (N, E)\) where \(N\) is the set of nodes (qubits) and \(E\) is a set of pairs of node indices, specifying graph edges, by

\[\begin{equation} |g\rangle = \prod_{(i,j) \in E} CZ_{i,j} \bigotimes_{i\in N} |+\rangle_i, \label{1} \tag{1} \end{equation}\]

where \(\bigotimes_{i\in N} = |+\rangle_{i_1}\otimes|+\rangle_{i_2} \otimes ... \) states. A simplest example is the graph state with two qubits, \(|g'\rangle = CZ_{0,1}|+\rangle_1 \otimes |+\rangle_0\), which is local-unitary equivalent to the Bell state.

Measurement of a qubit in Pauli X basis is expressed by the application of one of projection operators corresponding to measurement outcome \((-1)^s = -1\) or \(1\) for \(s=0, 1\) ,

\[\begin{equation} P_{X, s=0} = |+\rangle \langle+|, \ \ P_{X, s=1} = |-\rangle \langle-|. \label{2} \tag{2} \end{equation}\]

Since measurements can be considered destructive, we can trace out (partial trace) the measured qubits and the application of bras (\(\langle+|, \langle-|\)) is sufficient. For our simplest graph state \(|g'\rangle\), measurement of qubit 0 in the X bases gives

\[\begin{split}\begin{align} |g_{s=0}\rangle &= \langle+|_0 CZ_{0,1}|+\rangle_1 \otimes |+\rangle_0 = H|+\rangle_1,\ \ s = 0, \label{3} \tag{3} \\ |g_{s=1}\rangle &= \langle-|_0 CZ_{0,1}|+\rangle_1 \otimes |+\rangle_0 = XH|+\rangle_1, \ \ s = 1. \label{4} \tag{4} \end{align}\end{split}\]

If the measurement outcome was \(s=0\), the output state is the initial \(|+\rangle\) state with a Hadamard gate applied. If \(s=1\), there is additional \(X\) gate applied. In fact, this process of entangling with another qubit and then measuring with X basis the original qubit (qubit 0) is the MBQC version of Hadamard gate, and we treat the randomness of the measurement outcome with feedforward operations, as we describe below.

In MBQC, measurements with \(s=0\) is to be considered default outcome, and the additional \(X\) term is called byproduct of the measurement steming from the other result \(s=1\). The simplest construction of MBQC would be to apply adaptive \(X\) gate to correct for this byproduct, which we can express as follows

\[\begin{equation} H|+\rangle_1 = X^{s_0} \langle\pm|_0 CZ_{0,1}|+\rangle_1 \otimes |+\rangle_0, \label{5} \tag{5} \end{equation}\]

where \(X^{s_0}\) is applied if the measurement outcome of qubit 0 is \(s_0=1\). Another way to treat the byproduct is by rotating the subsequent measurements. In quantum hardware, we always end the quantum algorithm with computational (\(Z\)) basis measurements - so for output qubits with \(X\) byproduct applied (for this case, if \(s_0=1\)), we can simply swap the measurement result between 0 and 1 (recall that Pauli \(X\) gate can be considered analogue of classical NOT for computational bases).

This works also for arbitrary input state in qubit 0, \(|\psi\rangle = \alpha|0\rangle + \beta|1\rangle\). In this case,

\[\begin{equation} H|\psi_{in}\rangle_1 = X^{s_0} \langle\pm|_0 CZ_{0,1}|+\rangle_1 \otimes |\psi_{in}\rangle_0, \label{6} \tag{6} \end{equation}\]

which can be easily checked. notice that the input quantum state in qubit 0 has teleported to qubit 1 while being rotatetd by Hadamard gate.

Most basic quantum gates (unitary operations) have corresponding graph state and a sequence of measurements and byproduct corrections, as we show below.

\[\begin{split}\begin{align} CNOT_{0,3}|\psi_{in}\rangle_{03} = X_3^{s_2} Z_3^{s_1} Z_0^{s_1} \langle\pm|_2 \langle\pm|_1 CZ_{0,2} CZ_{2,3} CZ_{1,2} |+\rangle_3 |+\rangle_2 |\psi_{in}\rangle_{01}, \label{7} \tag{7} \\ R_x(\theta)|\psi_{in}\rangle_2 = Z_2^{s_0} X_2^{s_1} \langle\pm_{(-1)^{1+s_0} \theta}|_1 \langle\pm|_0 CZ_{1,2} CZ_{0,1}|+\rangle_2 |+\rangle_1 |\psi_{in}\rangle_0, \label{8} \tag{8} \\ R_z(\theta)|\psi_{in}\rangle_2 = Z_2^{s_0} X_2^{s_1} \langle\pm|_1 \langle\pm_{- \theta}|_0 CZ_{1,2} CZ_{0,1}|+\rangle_2 |+\rangle_1 |\psi_{in}\rangle_0, \label{9} \tag{9} \\ \end{align}\end{split}\]

where \(|\pm_{\theta}\rangle\) are the bases for measurements along the axis rotated on XY plane by angle \(\theta\) and \(\langle\pm_{(-1)^{1+s_0} \theta}|_1\) is called feedforward measurement whose angle \((-1)^{1+s_0} \theta\) is dependent on the measurement outcome of qubit \(0\). Because these building blocks include the single-qubit rotation and CNOT gate, MBQC is universal (i.e. with MBQC, we can determinisitically realize any multi-qubit unitary operations). Particularly, note that Clifford gates can be translated into MBQC with no non-Pauli measurements (see eqs (\(\ref{6}\), \(\ref{7}\)) for \(H\), \(S\) and \(CNOT\) gates, which generate any multi-qubit Clifford operations).

We can concatenate them to create a larger graph state that realizes a more complex unitary evolution we show below,

which we can express by a long sequence,

\[\begin{split}\begin{align} H_7 \ CNOT_{6,7} \ H_6 \ R_z(\eta)_7 \ |\psi_{in}\rangle_{74} =& X_7^{s_3} \langle\pm|_3 CZ_{37} |+\rangle_7 \otimes \big( \\ & X_6^{s_5} Z_6^{s_4} Z_3^{s_4} \langle\pm|_5 \langle\pm|_4 CZ_{56 } CZ_{45} CZ_{35} |+\rangle_5 |+\rangle_6 \otimes \big( \\ & X_4^{s_1} \langle\pm|_1 CZ_{14} |+\rangle_4 \otimes \big( \\ & Z_3^{s_0} X_3^{s_2} \langle\pm|_2 \langle\pm_{-\eta}|_0 CZ_{23} CZ_{02} |+\rangle_3 |+\rangle_2 \otimes |\psi_{in}\rangle_{01} \big)\big)\big). \label{10} \tag{10} \end{align}\end{split}\]

Note that the input state has teleported to qubits 4 and 7 after the computation.

Measurement Calculus

It is quite tedious to treat the MBQC by bras and kets as we show in eqs (\(\ref{6}\) - \(\ref{10}\)) - it is impossible to track all the feedforwards and ancillas by hand if the number of operations grow as we try larger quantum algorithms. Instead, we can resort to the Measurement Calculus 3 by Danos et al., a mathematical formulation of MBQC, to treat them as a linear sequence of commands consisting of

\(N_i\)	Node (qubit) preparation command with node index \(i\)
\(E_{ij}\)	Entanglement command which apply \(CZ\) gate to nodes \((i,j)\)
\({}^t[M_i^{ \lambda, \alpha}]^s\)	Measurement command which perform measurement of node \(i\) with measurement plane \(\lambda =\) XY, YZ or XZ, measurement angle \(\alpha\) defined on the plane \(\lambda\), \(s\) and \(t\) feedforward domains that adaptively changes the measurement angles to \(\alpha' = (-1)^{q_s} \alpha + \pi q_t\), where \(q_s, q_t\) are the sum of all measurement outcomes in the \(s\) and \(t\) domains.
\(X_i^{s}\)	byproduct command applied to qubit \(i\) with signal domain \(s\)
\(Z_i^{s}\)	byproduct command applied to qubit \(i\) with signal domain \(s\)
\(C_i^{k}\)	Clifford command applied to qubit \(i\) with signle-qubit Clifford operator \(k\)

where the Clifford command was added by us to treat the optimization routine we describe later in Introduction to LC-MBQC.

We can now express the MBQC in eq (\(\ref{10}\)) with these commands, which we read from the right:

\[X_7^{3} M_3^{0} E_{37} N_7 X_6^5 Z_6^4 Z_3^4 M_5^0 M_4^0 E_{56} E_{45} E_{35} N_6 N_5 X_4^1 M_1^0 E_{14} N_4 Z_3^0 X_3^2 M_2^0 M_0^{-\theta} E_{23} E_{02} N_3 N_2\]

This is an example of measurerment patttern that realize MBQC. while this still looks long, this can now be treated programmatically, to efficiently handle with code and to optimize following well-defined rules.

The first optimization is the standardization which turns arbitray measurement pattern into standard form which is sorted in the order of \(N\), \(E\), \(M\) and then followed by a mix of \(X,Z,C\). This can be done by following the command commutations rules described in the original paper 3. This removes intermediate byproduct commands to create

\[\begin{split}\begin{align} X_6^5 X_7^3 Z_6^4 Z_7^2 {}^{[0,4]}[M_3^0]^2 \ \ {}^{[1,2]}[M_5^0] \ [M_4^0]^1 \ \ M_1^0 M_2^0 M_0^{-\theta} \\ E_{02} E_{23} E_{14} E_{35} E_{45} E_{56} E_{37} N_7 N_6 N_5 N_4 N_3 N_2 \end{align}\end{split}\]

Further, signal shifting procedure 3 simplifies the measurement dependence, which removes all \(t\) signals:

\[\begin{split}\begin{align} X_6^{1,2,5} X_7^{0,3,4} Z_6^{4} Z_7^{2} [M_3^0]^2 \ M_5^0 \ [M_4^0]^1 \ M_1^0 M_2^0 M_0^{-\theta} \\ E_{02} E_{23} E_{14} E_{35} E_{45} E_{56} E_{37} N_7 N_6 N_5 N_4 N_3 N_2 \end{align}\end{split}\]

In the following page (Introduction to LC-MBQC), we will further optimize the measurement pattern using efficient graph state simulator, to classically preprocess all Pauli measurements (all \(M\) commands except qubit 0). This produce the following pattern:

\[\begin{align} X_7^0 C_6^6 M_0^{-\theta} E_{07} E_{06} N_7 \end{align}\]

References and footnotes

1

For example, we know that a certain type of quantum gates are not so essential for quantum computations (efficiently simulatable on classical computers). However, in gate sequences these ‘classical’ parts are interleaved with ‘quantum’ parts of the algorithm. In fact, by translating the problem into MBQC, one can classically preprocess such a part - see Introduction to LC-MBQC.

2

Raussendorf et al., PRL 86, 5188 (2001) and PRA 68, 022312 (2003). Here, by MBQC we refer to one-way quantum computing by Raussendorf among several measurement-based schemes.

3(1,2,3)

Danos et al., J. ACM 54.2 8 (2007) and Chapter 7, “Semantic Techniques in Quantum Computation”