# 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? – AHusain Apr 10 '19 at 18:34
• A gate set cannot be universal if it cannot create entanglement, so {H,T, SWAP} is not universal. – Victory Omole Apr 10 '19 at 18:34
• – Sanchayan Dutta 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. – Sanchayan Dutta 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! – Mithrandir24601 Apr 10 '19 at 19:31

## 1 Answer

You can prove that one gate set is universal by showing how to construct another universal gate set out of it. For example, we know that {H, T, cNOT} is universal, so can you find a way of making cNOT out of {H, T, CPHASE}? (Hint: Yes)

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)

I just wanted to clarify the reasoning behind choosing a particular route for disproving universality. You could try to make the argument that a universal gate set has to be capable of producing any unitary, which means it has to be capable of producing any state starting from the all zeros state. However, the concept of universality is a bit more subtle than that. For example, the gate set {H,Toffoli} is universal, and yet it can not produce states with complex phases because both gates are real valued. The reason is that it produces arbitrary unitaries within a large enough subspace of the system. But due to this possibility, it makes universality much harder to disprove through this sort of reasoning.

• I think to prove that some gate set is not universal you need to show that some unitary matrix can't be decomposed into the product of gates from the set. This is not directly related to the efficient classical simulation. – Danylo Y Apr 11 '19 at 8:18
• @DanyloY True, if you want to rigorously disprove universality. But would you normally do this when presented with a set of single qubit unitaries? Personally, I'd say "I can simulate these gates, so they can't give me an exponential speedup over classical, so they can't be universal, assuming there is such a thing as an exponential speedup". – DaftWullie Apr 11 '19 at 10:59