[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