I am wondering if there is an automated way to determine whether a given set of quantum operations is universal.

More precisely given a set of 1 and 2 qubit gates can we write a program to determine whether this constitutes a universal gateset? If so how might we do this?

EDIT: To clarify I'm interested in both approaches which allow exact replacements (as shown below) and approaches which allow approximating any unitary to some finite precision. Perhaps restricting the problem by not allowing arbitrary rotations in the input gateset could make the problem more tractable I'm not sure.

If I was given a set of quantum gates I would try to use the gates I'm given to implement a well known universal gateset.

Take this artifical example...

\begin{equation} S_0 = \{\text{H}, \text{Rx}(\alpha), \text{CZ}\} \end{equation}

I know I can write any single qubit operation with $\{\text{H}, \text{Rx}(\alpha)\}$ as I can reach any point on the Bloch sphere with 3 parameterised rotations in 2 directions (I can implement $\text{Rz}$ in terms of $\text{H}$ and $\text{Rx}$).

From here it's well known that an arbitary single qubit rotation along with a $\text{CX}$ gate is sufficent for universality and I can realise a $\text{CX}$ using a $\text{CZ}$ with Hadamards on the target qubit. Therefore the set $S_0$ is a universal gateset.

When I try to think of a way to automate this process of using the provided gates to implement a well known universal gateset I'm not sure where to start. It certainly seems like a hard problem.

  • 2
    $\begingroup$ See this question and answer -cstheory.stackexchange.com/questions/11298/… $\endgroup$ Commented May 2, 2023 at 21:39
  • $\begingroup$ Are you asking specifically about the case where you can exactly recreate any gate you want (e.g. the gate sets you've mentioned) or would finite gate sets achieving the target gate with arbitrary accuracy also fall within your interest? $\endgroup$
    – DaftWullie
    Commented May 3, 2023 at 8:28
  • $\begingroup$ Thanks @Mark S. indeed this other post is relevant. I think I’d need to read around a bit more to understand the discussion $\endgroup$
    – Callum
    Commented May 3, 2023 at 8:44
  • $\begingroup$ @DaftWullie . I suppose both cases are of interest to me. Is there a way to check if a gateset is approximately universal up to some $\epsilon$? $\endgroup$
    – Callum
    Commented May 3, 2023 at 8:49
  • 1
    $\begingroup$ It might be an incomplete analogy but - we can't square the circle with a ruler and a compass; however, Archimedes taught us that we can get arbitrarily close, by inscribing and circumscribing polygons. With that in mind, can the ruler and compass alone get arbitrarily close to any well-defined point on the plane? $\endgroup$ Commented May 3, 2023 at 13:59


Your Answer

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