1
$\begingroup$

A set of quantum gates is universal when it can approximate any unitary operation with arbitrary precision. These unitary operations are used in quantum algorithms, in a general sense, manipulating entanglement and superposition. Are these two features necessary and/or sufficient for a set of quantum gates to satisfy quantum universality?

$\endgroup$
4
  • 4
    $\begingroup$ $H$ + CNOT can generate both entanglement and superposition, but can be efficiently simulated, and as such can't offer quantum supremacy. It's also not a universal set of gates. As a final remark, entanglement implies superposition, so your question can be reduced to that of entanglement I think! $\endgroup$
    – Tristan Nemoz
    Jun 19, 2023 at 21:32
  • $\begingroup$ You are right - entanglement implies superposition. So the answer would be that entanglement is a necessary condition for a set of gates to be universal but not sufficient. Are there other necessary conditions other than entanglement? $\endgroup$
    – grav.field
    Jun 19, 2023 at 22:33
  • 2
    $\begingroup$ I think @TristanNemoz was hinting that non-Clifford gates are required. $H$ and CNOT generate entanglement, but are "Clifford gates" and can be efficiently simulated by the Gottesman-Knill theorem. $\endgroup$ Jun 20, 2023 at 18:24
  • $\begingroup$ I do not understand how efficient classical simulation relates to quantum universality, so I asked another question asking for clarification on this as I think it's a different question than I originally posted here. Thanks to both of you! $\endgroup$
    – grav.field
    Jun 26, 2023 at 19:03

1 Answer 1

0
$\begingroup$

To take full advantage of quantum computation, a set of gates has to be able to generate entanglement and superposition. However, this alone is not enough for this set of gates to be universal. The Hadamard and the CNOT gates are able to create entanglement (and thus superposition) but belong to the Clifford group, which, by the Gottesman-Knill theorem can be simulated in polynomial time in a classical computer. If a set of gates can be efficiently simulated in a classical computer, it cannot be quantum universal.

$\endgroup$
1
  • 1
    $\begingroup$ "If a set of gates can be efficiently simulated in a classical computer, it cannot be quantum universal": under the assumption that BQP$\neq$BPP $\endgroup$
    – DaftWullie
    Aug 24, 2023 at 5:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.