Which of the following sets of gates are universal for quantum computation?
- {H, T, CPHASE}
- {H, T, SWAP}
And how do we prove it?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ 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? $\endgroup$– AHusainApr 10, 2019 at 18:34
-
2$\begingroup$ A gate set cannot be universal if it cannot create entanglement, so {H,T, SWAP} is not universal. $\endgroup$– Victory OmoleApr 10, 2019 at 18:34
-
1$\begingroup$ Related: What is the mathematical justification for the "universality" of the universal set of quantum gates (CNOT, H, Z, X and π/8)?. $\endgroup$– Sanchayan DuttaApr 10, 2019 at 19:08
-
$\begingroup$ 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. $\endgroup$– Sanchayan DuttaApr 10, 2019 at 19:10
-
$\begingroup$ 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! $\endgroup$– Mithrandir24601 ♦Apr 10, 2019 at 19:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Apr 11, 2019 at 7:21
-
1$\begingroup$ 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. $\endgroup$– Danylo YApr 11, 2019 at 8:18
-
$\begingroup$ @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". $\endgroup$ Apr 11, 2019 at 10:59