---
# System prepended metadata

title: 2.5 Proving Universality

---

# 2.5 Proving Universality

## 1. Introduction 
If a device can perform any such conversion, taking any arbitrary set of inputs and converting them to an arbitrarily chosen set of corresponding outputs, we call it universal.

## 2. Fun With Matrices

### 2.1 Matrices as outer products

![](https://i.imgur.com/YcAfKQY.png)

we can write any matrix purely in terms of outer products.

##### single qubit example
![](https://i.imgur.com/hN8TB9W.png)

### 2.2 Unitary and Hermitian matrices

* ### unitary matrices

![](https://i.imgur.com/IaBUB2Q.png)

![](https://i.imgur.com/fitcfl8.png)
* ### orthogonal basis: 
 ![](https://i.imgur.com/xwMSpCw.png)
 
 ![](https://i.imgur.com/SLPkJci.png)

![](https://i.imgur.com/bveRqIq.png)


* ### Hermitian matrices

![](https://i.imgur.com/LqrC2pY.png)

* ###  diagonalizable both unitary and hermitian
![](https://i.imgur.com/ib4ghQh.png)

* **unitary - complex numbers of magnitude 1**
* **Hermitian - real eigenvalues** 

### 2.3 Pauli decomposition

* single qubit 
![](https://i.imgur.com/yItluv1.png)

![](https://i.imgur.com/RBx2ayU.png)

![](https://i.imgur.com/7PEAFGT.png)

![](https://i.imgur.com/JlUm2nd.png)

* multiple qubits

![](https://i.imgur.com/dcagbk4.png)

![](https://i.imgur.com/Xo2Le2i.png)

## 3. Defining Universality

![](https://i.imgur.com/VVQBefS.png)

If we were able to implement any possible unitary, it would therefore mean we could achieve universality in the sense of standard digital computers.


## 4. Basic Gate Sets

### 4.1 Clifford Gates

* the Hadamard

![](https://i.imgur.com/10EMgcw.png)

![](https://i.imgur.com/kekF2HZ.png)
* S gate 

![](https://i.imgur.com/9JI9Q6G.png)

### This property of transforming Paulis into other Paulis is the defining feature of Clifford gates.

* when single-qubit Clifford gates are the Paulis themselves - assign a phase of -1

![](https://i.imgur.com/QcaYBJl.png)

* multiple qubit gates ex. CNOT

![](https://i.imgur.com/0hJXwMi.png)

### 4.2 Non-Clifford Gates

![](https://i.imgur.com/19NvLwd.png)
![](https://i.imgur.com/lfQpniB.png)
![](https://i.imgur.com/dGsKkWp.png)
#### combine them with Clifford gates

### 4.3 Expanding the Gate Set 

* conjugate with CNOT
![](https://i.imgur.com/FZ1Sone.png)

* conjugate with S - X into Y
![](https://i.imgur.com/emLATyD.png)

* with many qubits 
![](https://i.imgur.com/akccSeL.png)

## 5. Proving Universality

prove unitary : 

![](https://i.imgur.com/chyrs2q.png)

but all we  have is ![](https://i.imgur.com/Rwll54n.png)



![](https://i.imgur.com/oWUgvim.png)
since Rx(θ) & Rz(θ) cannot commute

![](https://i.imgur.com/PcQnkCy.png)

![](https://i.imgur.com/6Tv5tVf.png)

The error in this approximation scales as 1/n^2. When we combine the n slices, we get an approximation of our target unitary whose error scales as 1/n. So by simply increasing the number of slices, to get U.

![](https://i.imgur.com/DE4d8Ep.png)

![](https://i.imgur.com/APTEzjQ.png)



