Use 'upper-triangular' structure to speed up search for symmetric circuits

[aaronszasz]

Imagine a circuit (e.g. SWAP) that is symmetric between 2 (or more) qudits. Then if the candidate circuit Rz_1, CNOT 1->2 has already been checked, there is no need to test Rz_2, CNOT 2->1, etc.

If the user can specify that a circuit should be symmetric (or if it can be automatically checked on an input unitary) between (some subset of) qudits, the above idea could be used to prune the search tree for improved speed.

[edyounis]

This is an awesome suggestion! After double-checking the code, I think we already do this. We only add two-qubit gates in one direction when building circuits with the provided layer generators. So CNOTs will never be from 2->1. This is because they are usually surrounded by single-qubit rotations, which can virtually flip the direction under instantiation. I am pretty sure this would capture your suggestion for 2-qudits, but would this do it for multi-qudits?

[aaronszasz]

No, it's not equivalent. A minimal example is a three-qubit unitary that is symmetric under permutations of the three qubits. e.g. take H = X1X2 + X2X3 + X1X3. Then e^{i H} is such a unitary.

In that case, CNOT(1->2) @ CNOT(2->3) will have the exact same cost as CNOT(2->1) @ CNOT(1->3) and 4 other circuits, namely all the circuits of the form CNOT(a->b) @ CNOT(b->c) where (a,b,c) is one of the 6 permutations of (1,2,3).

So your convention captures this effect for two qubits, but not for more than two.

[edyounis]

Our default layer generator will only build CNOT(a->b) where a < b, so for 3-qubits and all-to-all topology: CNOT(1->2), CNOT(2->3), and CNOT(1->3). So, I think this matches that pattern only one way: CNOT(a->b) @ CNOT(b->c) with a=1, b=2, and c=3. I think this generally works too, but only because CNOT is asymmetric.

If we instead used a gate like RZZ, which is symmetric, then I think we would definitely have a lot of redundancies. We could capture this in a LayerGenerator. For the initial layer, we probably would use the same single-qudit gate on every qudit, but how would we write the gen_successors function such that it would not create redundancies?

Also, you mention automatically detecting symmetries. Are you aware of how to do this? If it is computationally feasible to check for symmetries, we can add this to the core pipeline easily. I am also willing to bet that most blocks that we form during partitioning+resynthesis strategies have implicit symmetries.

[WolfLink]

CNOT by itself is asymmetric but CNOT surrounded by parameterized single qubit gates is symmetric because you can flip a CNOT by surrounding it with H gates.

[WolfLink]

You could definitely implement this feature by keeping a record of what circuit structures have been tried and pruning circuits that match the record by some function to compare circuit structures when adding a new circuit structure to the search queue.

This could also be used to prune in other situations e.g. when you have more than 3 CNOTs between the same pair of qubits in a row.

[edyounis]

That is an expensive data structure to maintain. Is there not a simple analytic method for building symmetry-aware circuits?

In the example where you have CNOT+U3(1->2) @ CNOT+U3(2->3), what circuit templates are equivalent given a target with symmetries? Consider only the alphabet {CNOT+U3(1->2), CNOT+U3(2->3), CNOT+U3(1->3)}

[aaronszasz]

One example: CNOT(2->3) @ CNOT(1->2) would be equivalent to CNOT(1->2) @ CNOT(2->3)

(With the exact same U3 gates as well, since the symmetry is equivalent to just relabeling the qubits)

[aaronszasz]

This probably won't help as much as I initially thought, but it also is pretty easy to implement. As I discussed with Ed last week, the symmetry between qubits can be handled in the following way:

For each layer of the circuit: (1) Make a list of lists of qudits symmetric under permutation. E.g. if there are 5 qubits, and the unitary you want to make is invariant under (1 <--> 2) and any permutation of (3, 4, 5), you would have [[1,2],[3,4,5]]. E.g. 2: if (1,2) are symmetric and (3,4) are symmetric, you would have [[1,2],[3,4],[5]]

(2) If a two-qudit gate would involve one qudit from one list and one from a different list, you can only use the first qudit of each list. If it would involve two in the same list, you can only use the first two from the list.

E.g. for [[1,2],[3,4],[5]], allowed CNOT locations are (1->2), (3->4) [two qudits in same list], (1->3), (1->5),(3->5) [one qudit from each of two lists]

E.g. 2: for [[1],[2],[3],[4],[5]], where no qubits are symmetry-related, all possible pairs are allowed

E.g. 3: for [[1,2,3,4,5]] where all qudits are related by symmetry, the only allowed two-qudit gate is (1->2)

(3) Once we apply a gate, the symmetry is (partially) broken. After each layer, the intersection of [two qudits used] and [list of symmetric qubits] should be moved to a separate list for future steps.

E.g. If for [[1,2,3,4,5]] we apply a CNOT on [1,2], the new list of lists would be [[1,2],[3,4,5]].

E.g. 2: If for [[1,2],[3,4,5]] we apply CNOT on [1,2], afterwards we still have [[1,2],[3,4,5]]

E.g. 3: If for [[1,2],[3,4,5]] we apply CNOT on [3,4], afterwards we have [[1,2],[3,4],[5]]

E.g. 4: If for [[1,2],[3,4,5]] we apply CNOT on [1,3], afterwards we have [[1],[2],[3],[4,5]]

The reasoning for this step is that the gate we applied breaks the symmetry, so if e.g. U was symmetric under permutation of qubits 1,2,3, and we put CNOT(1->2) at the start of the circuit, the rest of the circuit is supposed to represent CNOT(1->2) @ U, which has (1,2) still interchangeable (by choice of 1-qubit gates) but 3 is now distinct from them (no longer symmetry-related).

[aaronszasz]

Here's a concrete example: consider a 3-qubit unitary, which is symmetric under any permutation.

• The first layer is always CNOT (1->2). Our symmetry list then looks like [[1,2],[3]]

• The second layer is either CNOT (1->2), giving still [[1,2],[3]], or CNOT (1->3) giving [[1],[2],[3]]

• If the second layer was (1->2), the third layer could again by either of the possibilities above. If the second layer was (1->3), all the symmetry in the problem has now been removed, so in the third layer and onward any pair of sites is allowed as all pairs are symmetry-distinct.

Since we know that a two-qubit unitary cannot have more than 3 CNOTs, the most generic circuits look like:

• At least 1 and no more than 3 CNOT gates from (1->2)
• One CNOT gate from (1->3)
• After that, anything goes

So the speedup is mostly that you don't need to check many possibilities in the first few layers

[Note: you don't need to know/program in the 3 CNOT limit for two-qubit gates, so if you leave that out the possibilities that will be considered given the procedure described in the previous comment will be:

• Some number of layers (at least 1) of CNOT (1->2)
• One layer of CNOT (1->3)
• Then anything goes ]

[aaronszasz]

As an extra note, this approach should be compatible with connectivity graphs. For example, if the unitary is symmetric under any permutation of (1,2,3), but the connectivity is linear, 1--2--3, then effectively 1 and 3 are symmetric, so your list would be [[1,3],[2]]