Calculating number of CNOT gates in Pauli evolution gate

Question

How to calculate the number of CNOT gates for a Pauli exponentiation for given time?

I am performing Trotterization which involves performing Pauli evolution sequentially for all the terms in the Hamiltonian. I would like to benchmark this against other methods based on the number of CNOT gates it requires. Currently I have been doing the following:

• Using PauliEvolutionGate that would exponentiate the Pauli and give me the gate
• Use inbuilt transpiler with u3 and cx as the set of gates on the circuit
• Count the number of cx gates

The issue with this approach is that for Hamiltonians of about 28 qubits and 15,000 terms the transpilation is very slow and would take too long even when done for one repetition.

Is there a shorter way of calculating the number of CNOT gates required for PauliEvolutionGate of given time and Pauli string? Perhaps an analytical formula that looks at the number of non-trivial Pauli positions and calculates it directly

Answer 1

First of all, when you say inbuilt, inbuilt to what?

I assume you are talking about a particular compiler, like cirq or qiskit's (maybe you meant to ask this on Qiskit.SE?) The number of CNOT gates would very much depend on the architecture and the connectivity that you are compiling to, and the output you would get for a "high-level" circuit that you describe would only be a ball-park number, depending on the compiler you are using, it's implementation and the level of optimisation that you set.

Having said that, the way I approached a similar problem recently was to fix the underlying assumptions, like architecture and a cost metric for our optimisation and then write a script where I can describe low level building blocks of my circuits, and describe how they compose. Then use that script to simulate a larger circuit that I would need at the end. The idea is that if you just want gate counts, you don't need to store the entire circuit description; you just need to know what your elementary building blocks are, and how to compose resources they require.

Answer 2

Using @Aditya's answer and reference, I got an analytical upper bound on the cx count of exponentiation of a Pauli operator. Note that this method is for a circuit that has full connectivity, i.e. you can apply a two-qubit gate between any two qubits without SWAP gates. This is only an upper bound as a sequence of PauliEvolutionGate could have canceling cx gates.

By looking at the decomposition of the exponentiation of any general $n$-qubit Pauli operator, you can see that there is a cx gate between each of the qubit where a non-trivial operator is present and the last qubit with non-trivial operator. Here is the code I am using:

def cx_count(pauli: Pauli) -> int:
    """
    Counts the number of non-Identity operators in the multi-qubit Pauli
    operator and provide an upper bound for cx gate count
    """
    count = 0
    for p in pauli:
        if str(p) == "I":
            continue
        count += 1

    return 2 * (count - 1)

Example

For the Pauli operator XIXXIZI, there are 3 X and 1 Z operators. The decomposition will have 3 H gates at the beginning to transform X to Z. This will be followed by exponentiation of ZIZZIZI that will have cx gates to -2nd qubit from 0th, 2nd, and 3rd qubit. This sequence of cx and H will be reversed with a rz gate sandwiched in between.

q_0: ───────────────────────────────────────────────────
          ┌───┐┌───┐┌───┐┌─────────┐┌───┐┌───┐┌───┐     
q_1: ─────┤ X ├┤ X ├┤ X ├┤ Rz(200) ├┤ X ├┤ X ├┤ X ├─────
          └─┬─┘└─┬─┘└─┬─┘└─────────┘└─┬─┘└─┬─┘└─┬─┘     
q_2: ───────┼────┼────┼───────────────┼────┼────┼───────
     ┌───┐  │    │    │               │    │    │  ┌───┐
q_3: ┤ H ├──■────┼────┼───────────────┼────┼────■──┤ H ├
     ├───┤       │    │               │    │  ┌───┐└───┘
q_4: ┤ H ├───────■────┼───────────────┼────■──┤ H ├─────
     └───┘            │               │       └───┘     
q_5: ─────────────────┼───────────────┼─────────────────
     ┌───┐            │               │  ┌───┐          
q_6: ┤ H ├────────────■───────────────■──┤ H ├──────────
     └───┘                               └───┘          

Sidenote: It could also be decomposed as a chain of cx, refer to this answer, this matters when your connectivity isn't full.