2
$\begingroup$

I'm interested in the question written in the title. To explain what I mean, let's take the following set of 9 Pauli terms for 3 qubits: \begin{equation} X_1X_2, X_2X_3, X_3X_1,~ Y_1Y_2, Y_2Y_3, Y_3Y_1,~ Z_1Z_2, Z_2Z_3, Z_3Z_1. \end{equation} Some of them commute, some of them anticommute. Those relations could be expressed by a "anticommutation graph" that has a vertex for each Pauli term and connects them (say,) if they anticommute.

Furthermore, some of the terms will multiply up to $1$ or $-1$ (the identity matrix). We can also put this information to the graph in some way. For example, I can just draw additional lines showing which ones add up to $\pm1$. I will call this anticommutation graph that is augmented with the $\pm1$ information, the structure of Pauli terms.

Now, my question is: given such a structure, how can we know the minimum number of qubits to realize such relations among Pauli terms? With the above example, there actually is a way to represent the exact same relation of Pauli terms only using two qubits, as I show below. This seems quite nontrivial to me.

I guess I can break down my question into the following:

  1. Given such structure, is there an easy way to tell whether there exists an actual Pauli realization? Is there an efficient algorithm?
  2. Given such structure, is there an easy way to tell the minimum number of qubits required for an actual Pauli realization? Is there an efficient algorithm?
  3. Does this type of problem known to have some name? Any good references?

Thank you!

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ This is generally called a "group presentation" (i.e. a set of generators and the relations between them). -- As for the question, my guess would be that it should be possible to do Gaussian elimination with the stabilizer tableaus (i.e. a matrix which tells you the positions of the X and Z, with each row corresponding to a stablizer), but it is not immediate that this provably leads to the shortest Pauli string (though it will lead to shorter strings as this is the point of Gaussian elimination, so it feels plausible that it will give the shortest strings if you use the right cost function). $\endgroup$
    – Norbert Schuch
    Commented Jun 21 at 6:28
  • $\begingroup$ Thank you for your comment! If I understand you correctly, I guess now I can rephrase my problem to "Given a group presentation, what is the minimal set of qubits + Paulis that realizes that?" but I have a question. The formal definition of a "presentation of a group" is to have a list of combinations of generators that give you 1. In this case, I will have distinction between plus and minus 1, and I don't think that is formally captured in a group (it needs a notion of addition). Am I missing something? $\endgroup$
    – Jun_Gitef17
    Commented Jun 21 at 19:01
  • 1
    $\begingroup$ You can add $-I$ as a generator, that should fix your issue with the minus sign. And the question is: Given a group (which is provided through a presentation), what is the smallest representation in terms of Paulis? (Which might be identical, or not, to the smallest-dimensional representation of the group as such. If I would have to guess, I would say it is, as the structure is Pauli-like, but I haven't though about it.) $\endgroup$
    – Norbert Schuch
    Commented Jun 21 at 19:06

0

Reset to default

Your Answer

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