Measurement based quantum computation

Reference

  1. Jozsa, Richard. "An introduction to measurement based quantum computation." NATO Science Series, III: Computer and Systems Sciences. Quantum Information Processing-From Theory to Experiment 199 (2006): 137-158.
  2. Browne, Dan, and Hans Briegel. "One‐way Quantum Computation." Quantum information: From foundations to quantum technology applications (2016): 449-473.
  3. Petros Wallden, “Introduction to Quantum Computing” Lecture 16-18: Measurement-Based Quantum Computing (2018)
  4. Advanced Quantum Algorithms Lecture by Giulia Ferrini, Anton Frisk Kockum, Laura García-Álvarez, Pontus Vikstål (2020)

1. The basic idea of MBQC

In the circuit model of quantum computation, we prepare

  1. (input) initialize the qubits in the input state.
    • Quantum bits (qubits) : represent the data.
  2. (computation) Quantum gates on the qubits to manipulate the data.
  3. (output) Measurements on the qubits to read out the result.

It seems logically natural to perform operations in this order, which corresponds to our intuition about how classical computations work. While the basic strategy of Measurement based quantum computation:

  1. Initialize with a large entangled state.
  2. Make single-qubit measurements in suitably chosen bases.

Because of the presence of measurements are done before we reach the output state in MBQC, that computation cannot be reversed. For this reason, Measurement based quantum computation (MBQC) also known as one-way quantum computer).

1.1. Example

Many of the features of one-way quantum computation can be illustrated in a simple two qubit example.

1.1.1. Resource States

Consider the following simple protocol;

  • A qubit is prepared in an unknown state ∣ψ⟩=α∣0⟩+β∣1⟩|\psi\rangle=\alpha|0\rangle+\beta|1\rangle.
  • A second qubit is prepared in the state ∣+⟩=12(∣0⟩+∣1⟩)|+\rangle=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle).

Entangling the total state by apply controlled-Z gate (CZ\mathrm{CZ}) on the two qubits CZ(∣ψ⟩⊗∣+⟩)=[∣0⟩⟨0∣⊗1+∣1⟩⟨1∣⊗Z^]((α∣0⟩+β∣1⟩)⊗12(∣0⟩+∣1⟩))=[α∣0⟩⊗12(∣0⟩+∣1⟩)+β∣1⟩⊗12(∣0⟩−∣1⟩)]=α∣0⟩∣+⟩+β∣1⟩∣−⟩ \begin{aligned} C Z(|\psi\rangle \otimes|+\rangle) &=[|0\rangle\langle 0|\otimes 1+| 1\rangle\langle 1| \otimes \hat{Z}]\left((\alpha|0\rangle+\beta|1\rangle) \otimes \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\right) \\ &=\left[\alpha|0\rangle \otimes \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)+\beta|1\rangle \otimes \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\right] \\ &=\alpha|0\rangle|+\rangle+\beta|1\rangle|-\rangle \end{aligned}

1.1.2. Measurements

The next step is to measure the input qubit in some rotated basis.

  • Measuring in a rotated basis with angles (ϑ,φ)(\vartheta, \varphi) is like measuring Rz(φ+π/2)Rx(ϑ)ZRx(−ϑ)Rz(−φ−π/2)R_{z}(\varphi+\pi / 2) R_{x}(\vartheta) Z R_{x}(-\vartheta) R_{z}(-\varphi-\pi / 2).
  • Here we measure the first qubit with ϑ=π/2\vartheta=\pi / 2 and an arbitrary φ\varphi, i.e.,

we measure the observable σ^φ≡Rz(φ+π/2)Rx(π/2)ZRx(−π/2)Rz(−φ−π/2)=cos⁡φX+sin⁡φY=e−iφ∣0⟩⟨1∣+eiφ∣1⟩⟨0∣=∣φ+⟩⟨φ+∣−∣φ−⟩⟨φ−∣ \begin{aligned} \hat{\sigma}_{\varphi} & \equiv R_{z}(\varphi+\pi / 2) R_{x}(\pi / 2) Z R_{x}(-\pi / 2) R_{z}(-\varphi-\pi / 2) \\ &=\cos \varphi X+\sin \varphi Y \\ &=e^{-i \varphi}|0\rangle\left\langle 1\left|+e^{i \varphi}\right| 1\right\rangle\langle 0|\\ &=\left| \varphi_{+}\right\rangle\left\langle\varphi_{+}|-| \varphi_{-}\right\rangle\left\langle\varphi_{-}\right| \end{aligned} where

  • the rotated measurement basis ∣φ±⟩=1/2(∣0⟩±eiφ∣1⟩)\left|\varphi_{\pm}\right\rangle=1 / \sqrt{2}\left(|0\rangle \pm e^{i \varphi}|1\rangle\right).

conversely ∣φ±⟩=1/2(∣0⟩±eiφ∣1⟩)\left|\varphi_{\pm}\right\rangle=1 / \sqrt{2}\left(|0\rangle \pm e^{i \varphi}|1\rangle\right)

  • ∣0⟩=12(∣φ+⟩+∣φ−⟩)|0\rangle=\frac{1}{\sqrt{2}}\left(\left|\varphi_{+}\right\rangle+\left|\varphi_{-}\right\rangle\right)
  • ∣1⟩=12e−iφ(∣φ+⟩−∣φ−⟩)|1\rangle=\frac{1}{\sqrt{2}} e^{-i \varphi}\left(\left|\varphi_{+}\right\rangle-\left|\varphi_{-}\right\rangle\right)

and apply into the state to rewrite CZ(∣ψ⟩⊗∣+⟩)=α∣0⟩∣+⟩+β∣1⟩∣−⟩=α2(∣φ+⟩+∣φ−⟩)∣+⟩+β2e−iφ(∣φ+⟩−∣φ−⟩)∣−⟩=∣φ+⟩(α2∣+⟩+β2e−iφ∣−⟩)+∣φ−⟩(α2∣+⟩−β2e−iφ∣−⟩) \begin{aligned} C Z(|\psi\rangle \otimes|+\rangle) &=\alpha|0\rangle|+\rangle+\beta|1\rangle|-\rangle\\ &=\frac{\alpha}{\sqrt{2}}\left(\left|\varphi_{+}\right\rangle+\left|\varphi_{-}\right\rangle\right)|+\rangle+\frac{\beta}{\sqrt{2}} e^{-i \varphi}\left(\left|\varphi_{+}\right\rangle-\left|\varphi_{-}\right\rangle\right)|-\rangle \\ &=\left|\varphi_{+}\right\rangle\left(\frac{\alpha}{\sqrt{2}}|+\rangle+\frac{\beta}{\sqrt{2}} e^{-i \varphi}|-\rangle\right)+\left|\varphi_{-}\right\rangle\left(\frac{\alpha}{\sqrt{2}}|+\rangle-\frac{\beta}{\sqrt{2}} e^{-i \varphi}|-\rangle\right) \end{aligned} the measurement operator σ^φ=∣φ+⟩⟨φ+∣−∣φ−⟩⟨φ−∣ \hat{\sigma}_{\varphi} =\left|\varphi_{+}\right\rangle\left\langle\varphi_{+}|-| \varphi_{-}\right\rangle\left\langle\varphi_{-}\right| projects the second qubit into:

  • ∣ψ⟩out ∝(α∣+⟩+βe−iφ∣−⟩)|\psi\rangle_{\text {out }} \propto\left(\alpha|+\rangle+\beta e^{-i \varphi}|-\rangle\right) if the outcome is 11
  • ∣ψ⟩out ∝(α∣+⟩−βe−iφ∣−⟩)|\psi\rangle_{\text {out }} \propto\left(\alpha|+\rangle-\beta e^{-i \varphi}|-\rangle\right) if the outcome is −1-1

The state of the second qubit can then be compactly written as ∣ψ⟩out =XmHRz(−2φ)∣ψ⟩ |\psi\rangle_{\text {out }}=X^m H R_z(-2 \varphi)|\psi\rangle since ∣ψ⟩out =XmHRz(−2φ)∣ψ⟩=XmHRz(−2φ)(α∣0⟩+β∣1⟩)=XmH(αeiφ∣0⟩+βe−iφ∣1⟩)=Xm(αeiφ∣+⟩+βe−iφ∣−⟩) \begin{aligned} |\psi\rangle_{\text {out }}=& X^m H R_z(-2 \varphi)|\psi\rangle \\=& X^m H R_z(-2 \varphi)(\alpha|0\rangle+\beta|1\rangle) \\=& X^m H\left(\alpha e^{i \varphi}|0\rangle+\beta e^{-i \varphi}|1\rangle\right) \\=& X^m\left(\alpha e^{i \varphi}|+\rangle+\beta e^{-i \varphi}|-\rangle\right) \end{aligned} where the mm corresponding to

  • ∣ψ⟩out ∝(α∣+⟩+βe−iφ∣−⟩)|\psi\rangle_{\text {out }} \propto\left(\alpha|+\rangle+\beta e^{-i \varphi}|-\rangle\right) if the outcome is 1(m=0)1(m=0)
  • ∣ψ⟩out ∝(α∣+⟩−βe−iφ∣−⟩)|\psi\rangle_{\text {out }} \propto\left(\alpha|+\rangle-\beta e^{-i \varphi}|-\rangle\right) if the outcome −1(m=1)-1(m=1)

The extra Pauli operator XmX^m depends on the outcome of the measurement on qubit 1

1.2. Universal single-qubit operations

For a four qubits system

We can break the pattern of the figure to 3 steps:

  1. first consider qubit 1 and qubit 2 alone ,
  2. then using qubit 2 as input and qubit 3 as output,

  3. finally, using qubit 3 as input and qubit 4 as output

    The final output state (qubit 4) then becomes ∣ψ⟩out =Xm3HRz(φ3)Xm2HRz(φ2)Xm1HRz(φ1)∣ψ⟩=HZm3Rz(φ3)HZm2Rz(φ2)HZm1Rz(φ1)∣ψ⟩=HZm3Rz(φ3)(HZm2H)(HRz(φ2)H)Zm1Rz(φ1)∣ψ⟩=HZm3Rz(φ3)Xm2Rx(φ2)Zm1Rz(φ1)∣ψ⟩=Xm3Zm2Xm1HRz((−1)m2φ3)Rx((−1)m1φ2)Rz(φ1)∣ψ⟩ \begin{aligned} |\psi\rangle_{\text {out }} &=X^{m_{3}} H R_{z}\left(\varphi_{3}\right) X^{m_{2}} H R_{z}\left(\varphi_{2}\right) X^{m_{1}} H R_{z}\left(\varphi_{1}\right)|\psi\rangle \\ &=H Z^{m_{3}} R_{z}\left(\varphi_{3}\right) H Z^{m_{2}} R_{z}\left(\varphi_{2}\right) H Z^{m_{1}} R_{z}\left(\varphi_{1}\right)|\psi\rangle \\ &=H Z^{m_{3}} R_{z}\left(\varphi_{3}\right)\left(H Z^{m_{2}} H\right)\left(H R_{z}\left(\varphi_{2}\right) H\right) Z^{m_{1}} R_{z}\left(\varphi_{1}\right)|\psi\rangle \\ &=H Z^{m_{3}} R_{z}\left(\varphi_{3}\right) X^{m_{2}} R_{x}\left(\varphi_{2}\right) Z^{m_{1}} R_{z}\left(\varphi_{1}\right)|\psi\rangle \\ &=X^{m_{3}} Z^{m_{2}} X^{m_{1}} H R_{z}\left((-1)^{m_{2}} \varphi_{3}\right) R_{x}\left((-1)^{m_{1}} \varphi_{2}\right) R_{z}\left(\varphi_{1}\right)|\psi\rangle \end{aligned} where

  4. in the first step we used that XmH=HZmX^{m} H=H Z^{m},

  5. in the third that HZmH=XmH Z^{m} H=X^{m}
  6. and later on that XRz(φ)=Rz(−φ)XX R_{z}(\varphi)=R_{z}(-\varphi) X
  7. and ZRx(φ)=Rx(−φ)ZZ R_{x}(\varphi)=R_{x}(-\varphi) Z.

Due to Euler's rotation theorem any single-qubit SU(2)\mathrm{SU}(2) rotation can be decomposed as a product of three rotations Rz(γ)Rx(β)Rz(α) R_{z}(\gamma) R_{x}(\beta) R_{z}(\alpha) Thus, by repeating the simple two-qubit protocol three times.

  • φ1=α\varphi_{1}=\alpha
  • φ2=(−1)m1β \varphi_{2}=(-1)^{m_{1}} \beta
  • φ3=(−1)m2γ \varphi_{3}=(-1)^{m_{2}} \gamma

The above steps lets us implement any single-qubit operation

2. Entanglement as a resource for computational power

The entangled states used are called graph states. Given graph G=(V,E) G=(V, E) where

  • vertices VV
  • edges EE

Graph states are obtained by

  1. Place at each vertex VV a qubit at ∣+⟩|+\rangle
  2. For each edge EE apply CZCZ to entangle the vertices

Resulting state: ∣G⟩=∏(a,b)∈ECZ(a,b)∣+⟩⊗V |G\rangle=\prod_{(a, b) \in E} CZ^{(a, b)}|+\rangle^{\otimes V} comment

  • Graph states are highly entangled between all qubits. Entanglement remains after measuring some qubits
  • Entanglement is "consumed" during the computation ⇒\Rightarrow Entanglement are resource of the computation.

2.1. cluster states

If the graph used is subset of dd-dimensional lattice the state are also known as cluster states

results matching ""

    No results matching ""