A theorem for a Quantum Computer

  • Every unitary operator can be built from one and two qubit gates
  • Every two qubit gate can be built from CNOT and one-qubit gate

Just these gates and to the 1D nearest-neighbor connectivity and you can build anything (like how NANDs can build everything in classical computing)

{H,  eiπ8σZ,  CNOT}\{H,\; e^{i\frac{\pi}{8}\sigma^Z},\; \text{CNOT}\}