# 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


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

##### single qubit example

### 2.2 Unitary and Hermitian matrices

* ### unitary matrices


* ### orthogonal basis:



* ### Hermitian matrices


* ### diagonalizable both unitary and hermitian

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

### 2.3 Pauli decomposition

* single qubit




* multiple qubits



## 3. Defining Universality


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


* S gate


### 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


* multiple qubit gates ex. CNOT


### 4.2 Non-Clifford Gates

#### combine them with Clifford gates

### 4.3 Expanding the Gate Set

* conjugate with CNOT

* conjugate with S - X into Y

* with many qubits

## 5. Proving Universality

prove unitary :


but all we have is 

since Rx(θ) & Rz(θ) cannot commute



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.