# How to prove universality for a set of gates?

Which of the following sets of gates are universal for quantum computation?

1. {H, T, CPHASE}
2. {H, T, SWAP}

And how do we prove it?

• Have you already covered an example of a universal set of gates? Do you have to do from scratch or can you reduce to a previous case and then use a result from class? Apr 10 '19 at 18:34
• A gate set cannot be universal if it cannot create entanglement, so {H,T, SWAP} is not universal. Apr 10 '19 at 18:34
• Apr 10 '19 at 19:08
• Hi, hey0god. Welcome to Quantum Computing SE! Please note that we're not a homework help site. I've removed the unnecessary details from v2 of the question. Anyway, I believe the edited v3 of the question is generic enough and would be useful for future visitors to the site and so I'm leaving it open. Apr 10 '19 at 19:10
• Welcome to Quantum Computing SE! If possible, in order to get better answers more directly dealing with your problem, would you be able to edit this question explaining what exactly you've tried so far and where exactly you're stuck? Thanks! Apr 10 '19 at 19:31

On the other hand, the best way to prove that a gate set is not universal is to show that you can simulate the evolution of any circuit efficiently on a classical computer. To the extent that we believe that classical and quantum computers are different is the extent to which we believe that gate set cannot be universal for quantum computation. So, how would you efficiently simulate arbitrary single qubit gates being applied to a set of $$n$$ qubits? Can you update your simulation algorithm to include SWAP without losing efficiency? (Hint: Yes)