[Quantum Information] Universality of quantum gates

 Universality of quantum gates

Notes from RWTH Aachen University course 
“Quantum Information” Summer semester 2020
professor: Müller, Markus

Universality

• Entanglement
  
  
  
  
  
  • $|00\rangle\xrightarrow[]{C_1NOT_2, H_1} \frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)=|\Phi^+\rangle$
  • $|01\rangle\xrightarrow[]{C_1NOT_2, H_1} \frac{1}{\sqrt{2}}(|01\rangle+|10\rangle)=|\Psi^+\rangle$
  • $|10\rangle\xrightarrow[]{C_1NOT_2, H_1} \frac{1}{\sqrt{2}}(|00\rangle-|11\rangle)=|\Phi^-\rangle$
  • $|11\rangle\xrightarrow[]{C_1NOT_2, H_1} \frac{1}{\sqrt{2}}(|01\rangle-|10\rangle)=|\Psi^-\rangle$
• Bell state are equivalent up to local unitary operations
  • $|\Psi^+\rangle=X_1|\Phi^+\rangle=X_2|\Phi^+\rangle$
  • $|\Phi^-\rangle=Z_1|\Phi^+\rangle=Z_2|\Phi^+\rangle$

general property: Entanglement don’t change under local unitary operations.

• $\frac{1}{\sqrt{2}}(|00\rangle+i|10\rangle)$ also called Bell state: Local unitary equivalent
  with $S_1=\begin{pmatrix}1 & 0 \\ 0 & i\end{pmatrix}$

Universality of quantum gates

• Classical:
  • $\{AND, NOT\}$ and $\{NAND\}$ are sets of classical logic gate universal for irreversible computing
  • $\{TOFFELI\}$ is a universal 3-bit logic gate for reversible computing
• Quantum computing: what are the minimal sets for n-qubit computation $U$?
  • $T^4=S^2=Z$
  • $HZH=X$
  • $Y=iXZ$

  $H$-gate and $T$-gate can generate $X,Y,Z$

• Two-qubit
  • CNOT + arbitrary single rotation = universal gate set
  • example: $\{CNOT,H,T\}$
  • Proof:
    1. Arbitrary $n$-qubit gates can be decomposed into products of $n$-qubit unitary operations that act in a 2-dim subspace only.
       • decompose $U$ into a product of $\{V_k\}$
         $$V_k=\begin{pmatrix}1 &  & & & & & & & & & \\& \ddots & & & & & & & & &  \\&  & 1 & & & & & & & & \\&  & & a & & & & b & & & \\&  & &  & 1 & & & & & &\\&  & &  &  & \ddots & & & & & \\&  & &  &  &  & 1 & & & & \\&  & & c &  &  &  & d & & & \\&  & &  &  &  &  &  & 1 & &\\&  & &  &  &  &  &  & & \ddots & & \\&  & &  &  &  &  &  & & & 1 \end{pmatrix}$$
       • example: $d=3$
         $$U=\begin{pmatrix} a&d&g\\ b&e&h\\ c&f&i\end{pmatrix}, U^\dagger U=\mathbb{I}$$
         we will find $V_1,V_2,V_3$ such that $V_3V_2V_1U=\mathbb{I}$
         (until decompose of $U$ into $2$-level unitary $V_k$)
         thus $U^\dagger =V_3V_2V_1$
       • if $b=0$, set $V_1=\begin{pmatrix} 1&0&0\\ 0&1&0\\ 0&0&1\end{pmatrix}$
       • if $b\neq 0$, set  $$V_1=\begin{pmatrix} \frac{a^*}{\sqrt{|a|^2+|b|^2}}&\frac{b^*}{\sqrt{|a|^2+|b|^2}}&0\\ \frac{b}{\sqrt{|a|^2+|b|^2}}&\frac{-a}{\sqrt{|a|^2+|b|^2}}&0\\ 0&0&1\end{pmatrix}$$
         $V_1$ is a valid $2$-level unitary.
       • for $d=2^n$, we need to construct
         $(d-1)$ $2$-level unitaries for the first column
         $(d-2)$ for the second column
       • $U=V_1V_2...V_k$
         $$k\leq\frac{d(d-1)}{2}$$

       This is inefficient
       There exists matrices for which $2$-level unitaries is needed

    2. arbitrary $2$-level unitaries can be realized by $CNOT$-gate and single qubit rotations.
       • if
         $$V_k=\begin{pmatrix}a & 0 & \dots & b \\ 0 & 1 & \dots & 0 \\ \vdots & & \ddots & \vdots\\ c & 0 & \dots & d\end{pmatrix}$$
       • Problem: $V_k$ acts on the state, not a single qubit
       • Solution: Gray code that connects state $|000\rangle$ and $|111\rangle$
         • $000\rightarrow 001\rightarrow 011 \rightarrow 111$
           all differs in one qubit only
         • different controlled-controlled-$U$ ($3$-qubit):
           • applies $U$ iff the first qubit is $|0\rangle$ and the second qubit is $|1\rangle$
           • applies $X_1$ before and after controlled-controlled-$U$ (flips $|0\rangle$ to $|1\rangle$)
    3. Arbitrary single-qubit rotation can be approximated by a finite set of single qubit gates, e.g. $H$ and $T$ gates
       • arbitrary single-qubit rotation can be built up from rotations about 2-axis
       • $U=e^{i\alpha} R_n(\beta) R_m(\gamma) R_n(\delta)$
         (can be built from $R_y,R_z$)
       • 
         
         
         
         
       • 
         
         
       • Solovay–Kitaev theorem
         A single-qubit gate $U$ can be approximately to accuracy $\varepsilon$ using $O(\log^2(1/\varepsilon))$ gates from the discrete gate set.
         Poly-logarithmic increase $\Rightarrow$ growing very slow (not exponential increase in $1/\varepsilon$)
• overall resource count
  • for one $2$-level unitary $(d=2^n)$, we need at most $2(n-1)$ controlled operations $C^{n-1}(X)$ to implement a swap according to the gray code.
  • $O(n)$ toffeli-gate
  • This amounts to $O(n)$ single-qubit gates and CNOT gates.
  • We need $O(4^n)$ $2$-level unitaries $V_k$ to compose the $n$-qubit unitary $U$

Result: Implementation of an arbitrary $n$-qubit unitary $U$ can be realized by a quantum circuit containing $O(n^24^n)$ single qubit gates and CNOT operations.

$n$-qubit Pauli group

• $$P_n=\{e^{i\pi\cdot k/2}\sigma_{j_1}...\sigma_{j_n}|n=0,1,2,3\text{ and }j_k=0,1,2,3\}\\\text{where }\sigma_0=\mathbb{I},\sigma_1=X,\sigma_2=Y,\sigma_3=Z$$

$n$-qubit Clifford group

• $$C_n=\{V P_n V^\dagger=P_n\}$$
• $n=1$ example:
  • Hadamard gate $\in C_1$
    • $HXH^\dagger=Z,HXH^\dagger=Z,HZH^\dagger=X,HYH^\dagger=-Y$
      $\Rightarrow$ the 16 elements of $P_1$ are mapped onto $P_1$
  • T gate $\notin C_1$
    • $TXT^\dagger=1/\sqrt{2}(X+Y)\notin P_1$
• $n=2$ example:
  • CNOT gate $\in C_2$
    • $(C_1NOT_2)X_1(C_1NOT_2)=X_1X_2$
• gottesman-knill theorem
• Quantum circiuts of only Clifford gates can be perfectly simulated efficiently, i.e. in polynomial time, on classical computers.

Readings

Nielsen and Chuang

    4.3 Controlled operations