Representing a tensor product of single-qubit operations, with the capability to efficiently modify an arbitrary single-qubit operator in that product

[LEXUGE]

It seems like there is no method that allows you to compose single qubit Clifford operators. This is understandable as sX(1) * sY(2) will no longer be single-qubit and doesn't really make sense to use "symbolic" interface.

However, for graph state simulator, for VOP we would like to have a representation of single qubit Clifford group which is closed under composition so we could basically make a table for composition. Having a data structure representing that will be of great use as we don't need to use CliffordOperator etc. for computing composition.

Describe the solution you’d like

Create a new data structure for single qubit clifford group.

[Hamiltonian-Action]

I would also be interested in this concept from the GPU space, since as it stands doing sX(i) * sY(j) * Tableau would evaluate as sX(i) * (sY(j) * Tableau) which has terrible performance characteristics. I believe that we can style this interface as some union of symbolic operators acting on a disjoint sets of qubits -- no need to restrict to single qubit symbolics, which would just be a specific case of the general structure.

If I am to understand correctly, whatever comes out of this ought to satisfy the following constraints, right?
Let $C_n$ be the Clifford group on $n$ qubits for some $n \geq 1$, wherein your case would be $n = 1$, and let $\mathrm{Ind}(g)$ denote the set of qubit indices acted on by $g$. Then we would like to have a structure $S$ (treated here as a set) such that:
$\mathrm{Id} \in S$
$\forall c \in C_n , s \in S : \mathrm{Ind}(c) \cap \mathrm{Ind}(s) = \emptyset \implies c \circ s = s \circ c \in S$
$S \ni s = \prod_{k \in I} c_k \land \forall k \in I : c_k \in C_n \land \forall i, j \in I : \mathrm{Ind}(c_i) \cap \mathrm{Ind}(c_j) = \emptyset \implies \forall \alpha \in \{\alpha : \alpha \in C_n \land \exists! k \in I : \mathrm{Ind}(\alpha) = \mathrm{Ind}(c_k) \} : \alpha \circ s \in S \land s \circ \alpha \in S$

Another interesting facet is whether general $n$-qubit gates arise commonly enough in practice beyond $n = 2$ such that we could conceivably benefit from allowing user-definable sparse $n$-qubit gates in order to avoid dense Clifford operations, but that is probably better discussed elsewhere.

[LEXUGE]

If I understand correctly, the set S you are saying is basically a subgroup of C_n acting on a selection of qubits? For example n = 10, the Clifford gates acting on indices 1, 3, 5, 10 only will form a subgroup.

[Krastanov]

The two use cases you guys have in mind might require different solutions.

Here is my version of a summary:

• We already have single/two-qubit operations that are fairly fast, but inherently they can not have generic fast composition rules.
• We already have n-qubit operations as dense tableaux, but they are slow if you know your operation can be expressed as tensor products of single/two-qubit operations.
• For GPU code where launching a kernel has latency, it would be of interest to do the equivalent of composing multiple kernels of single/two-qubit operations in one object out of which a single kernel is launched.
• For Graph sim code it is instead important to be able to represent tensor products of single-qubit operations efficiently in a way in which applying other single qubit operations to the existing single-qubit operations is efficient. That requirement does not exist for the GPU application.

Let's keep this issue focused on the Graph sim application @LEXUGE is working on and have a new issue for the GPU kernel composition.

[Krastanov]

Of course, any discussion of overlapping needs for the GPU and Graph sim cases are very appropriate.

[LEXUGE]

Just a comment on the tensor product of single qubit operators: if we are sure the operator is separable as such, a vector of single qubit operator should serve the purpose?

And the real problem is still to apply single qubit ops upon single qubit op?

[Krastanov]

@LEXUGE , how about the following:

struct Rank1TensorProduct{C}
    ops::Vector{C}
end

 # let's assume that C is CliffordOperator of size 1 for now, we can do something more efficient in the future
Rank1TensorProduct(ops) = Rank1TensorProduct{CliffordOperator{...}}(...)

apply!(r1tp::Rank1TensorProduct, g::SingleQubitOperation)
    apply!(r1tp.ops[affectedqubits(g)[1]], ...)
end

#and a nice error message for all other `apply!` operations

[Krastanov]

Admittedly it is kinda silly that I am using the n-qubit dense CliffordOperator to represent just a single-qubit operation, but that way it works out of the box. We can leave the type parameterized so that we can implement something more intelligent in the future.

Pardon the repeated messages, I should not be using this as a IM thread

[Hamiltonian-Action]

If I understand correctly, the set S you are saying is basically a subgroup of C_n acting on a selection of qubits? For example n = 10, the Clifford gates acting on indices 1, 3, 5, 10 only will form a subgroup.

Not quite, since the structure's properties are dynamically modified in a manner that would require some extra elbow grease to deal with via group theory. When reading the definition, think of $\in S$ to signify isa S rather than some concrete fixed set. Taking $n = 2$, the definition I gave would allow $X_1 \circ Y_2 \in S$ as well as $\mathrm{CNOT}_{1, 2} \circ X_1 \circ Y_3 \circ X_1 = \mathrm{CNOT}_{1, 2} \circ Y_3 \in S$, but would not allow $\mathrm{CNOT}_{1, 2} \circ X_1 \notin S$.
For the sake of clarity and completeness, your description would indeed be correct if we set $n = 1$.

Let's keep this issue focused on the Graph sim application @LEXUGE is working on and have a new issue for the GPU kernel composition.

I understand the concern and will step down should need be, the point of view I am espousing is that I believe both of the goals can be achieved simultaneously via the same mechanism(s).

[Krastanov]

I understand the concern and will step down should need be, the point of view I am espousing is that I believe both of the goals can be achieved simultaneously via the same mechanism(s)

That is fair. Once a more general version exists, we can move the Graph simulator to it.