The Pauli Propagation Surrogate

Given that large parts of the Pauli path branching are determined by the observable and the types of gates in the circuit, could we do the propagation once, somehow compile the paths, and never re-compute the full problem? Especially in expectation value calculations, where a lot fewer paths than we compute end up contributing? This is what our Pauli propagation surrogate is for! With an initial investment of time and especially memory, we try to make consecutive evaluations a lot faster.

The surrogate is not the main focus of the PauliPropagation.jl package, and there are still a lot of potential improvements, but it may already be what you are looking for in some cases.

using PauliPropagation

Let's define some arbitrary small example simulation. Please know that the surrogate currently only accepts circuits with CliffordGates and PauliRotations.

nq = 8
nl = 4

topology = bricklayertopology(nq)
circuit = efficientsu2circuit(nq, nl; topology)
nparams = countparameters(circuit)

64

observable = PauliSum(nq)
add!(observable, :Z, 1)
add!(observable, :Z, nq)

PauliSum(nqubits: 8, 2 Pauli terms:
 1.0 * IIIIIIIZ
 1.0 * ZIIIIIII
)

Using the Surrogate

Our surrogation approach is based on a custom PathPropergies type called NodePathProperties. Similar to the PauliFreqTracker, we use can truncate via max_freq and max_sins, but it also carries objects instead of coefficients that build a propagation graph on the fly. This graph will later be evaluated.

Here is how you prepare the surrogate by wrapping your observable, i.e. your PauliString or PauliSum into NodePathProperties. This may become simpler in the future.

wrapped_observable = wrapcoefficients(observable, NodePathProperties)

PauliSum(nqubits: 8, 2 Pauli terms:
 NodePathProperties * IIIIIIIZ
 NodePathProperties * ZIIIIIII
)

To surrogate, simply propagate without passing any parameters thetas. Those come later. Note that for any harder simulation we should set truncation values!

@time surrogate_psum = propagate(circuit, wrapped_observable)

  2.337709 seconds (2.89 M allocations: 137.868 MiB, 1.60% gc time, 99.24% compilation time)





PauliSum(nqubits: 8, 15314 Pauli terms:
 NodePathProperties * IIYZXIXI
 NodePathProperties * ZXXYXYZY
 NodePathProperties * XXIXXYXY
 NodePathProperties * XZIZYZYZ
 NodePathProperties * ZZIZIZYZ
 NodePathProperties * IIXZZXZI
 NodePathProperties * ZXXXZXXI
 NodePathProperties * YZIXXZII
 NodePathProperties * IIXZZZYZ
 NodePathProperties * ZZZZYXZZ
 NodePathProperties * ZZXYIYZZ
 NodePathProperties * XZZXZYIZ
 NodePathProperties * IIYYZZYX
 NodePathProperties * ZZZZIYZZ
 NodePathProperties * XZZXZZYZ
 NodePathProperties * IIYXXIYI
 NodePathProperties * ZZXZZXII
 NodePathProperties * XZXZZIZX
 NodePathProperties * XXXYIYXZ
 NodePathProperties * ZZIXZXZY
  ⋮)

Done. Now we define the parameters for the Pauli rotations.

using Random
Random.seed!(42)
thetas = randn(nparams)

By calling evaluate!() on the surrogate Pauli sum, the computational graph is properly evaluated for specific parameter values.

# the surrogate_psum is evaluated in-place
evaluate!(surrogate_psum, thetas)

Now we can use the surrogate like the Pauli sums that you are used to.

overlapwithzero(surrogate_psum)

-0.2488994501782641

Now compare this with the conventional Pauli propagation simulation:

psum = propagate(circuit, observable, thetas)

PauliSum(nqubits: 8, 15314 Pauli terms:
 0.00094943 * IIYZXIXI
 0.0012401 * ZXXYXYZY
 -8.8328e-5 * XXIXXYXY
 -8.9315e-5 * XZIZYZYZ
 0.00079019 * ZZIZIZYZ
 -0.0027623 * IIXZZXZI
 2.3068e-5 * ZXXXZXXI
 0.013333 * YZIXXZII
 -0.0047358 * IIXZZZYZ
 -0.00024593 * ZZZZYXZZ
 0.00046659 * ZZXYIYZZ
 2.7781e-5 * XZZXZYIZ
 0.00014479 * IIYYZZYX
 3.3844e-5 * ZZZZIYZZ
 -9.6428e-6 * XZZXZZYZ
 -0.0016772 * IIYXXIYI
 -0.0037817 * ZZXZZXII
 2.8355e-6 * XZXZZIZX
 4.4524e-6 * XXXYIYXZ
 -0.0002194 * ZZIXZXZY
  ⋮)

# the same result
overlapwithzero(psum)

-0.2488994501782641

Benchmarking

We mentioned this approach would be faster, but is it? First addressing the elephant in the room: The initial surrogation propagation is a lot slower. It also uses drastically more memory. These are things that can be improved in the future, but you may still find this useful. Also note that these notebooks are run with 12 usable CPU threads in the Julia kernel. Results may vary with more or less.

# load Julia's benchmarking library
using BenchmarkTools

# benchmark the surrogate
@btime evaluate!($surrogate_psum, $thetas)

  11.588 ms

 (17 allocations: 479.45 KiB)

# benchmark the normal propagation
@btime propagate($circuit, $observable, $thetas)

  5.086 ms

 (518 allocations: 1.16 MiB)

Depending on whether you started started your Julia kernel with several CPU threads, this might already be faster. While we will discuss some caveats further down, this is not the surrogate's final form.

We have not yet made use of the main advantage of a surrogate: If we know at the end which Pauli strings contribute to expectation values, we can call evaluate!() only on those paths and none of the others. Let's filter the surrogate Pauli sum so that it only contains the Pauli strings relevant to overlapwithzero(), i.e. the $|0\rangle\langle0|$ state.

# zerofilter! actually changes the surrogate in-place. Copying may lead to wrong behavior.
surrogate_psum = zerofilter!(surrogate_psum);

## zerofilter!() is the same as this:
# for pstr in paulis(surrogate_psum)
#     if containsXorY(pstr)
#         delete!(surrogate_psum, pstr)
#     end
# end

@btime evaluate!($surrogate_psum, $thetas)

  433.631 μs (17 allocations: 4.01 KiB)

And this is substantially faster!

So far we covered a very small-scale problem without the need to perform any truncations. Though this is what we will now do, highlighting some of the nuances and issues of a(/our) surrogate.

Truncating the Surrogate

Set up a bigger problem on a 2D topology. Don't run this without truncations!

nx = 6
ny = 6
nq = nx * ny

nl = 4

topology = rectangletopology(nx, ny)

circuit = hardwareefficientcircuit(nq, nl; topology)

nparams = countparameters(circuit)

672

# a Pauli Z observable in the middle
pstr = PauliString(nq, :Z, 21)

PauliString(nqubits: 36, 1.0 * IIIIIIIIIIIIIIIIIIII...)

# wrap it in `NodePathProperties` again
wrapped_pstr = wrapcoefficients(pstr, NodePathProperties)

PauliString(nqubits: 36, NodePathProperties * IIIIIIIIIIIIIIIIIIII...)

Now we set the truncation values. For this demonstration, we will chose them as rather inaccurate truncations. Otherwise we might run out of memory pretty quickly.

max_freq = 26
# max_sins = 10   # another option if your rotation angles are small
max_weight = 7

@time surrogate_psum = propagate(circuit, wrapped_pstr; max_freq, max_weight)

 11.426539 seconds (46.24 M allocations: 1.721 GiB, 27.28% gc time, 9.10% compilation time)





PauliSum(nqubits: 36, 1626 Pauli terms:
 NodePathProperties * IIIIIIIIIIIIIXIIIIIZ...
 NodePathProperties * IIIIIIIIIIIIIIIIIIII...
 NodePathProperties * IIIIIIIIIIIIIIZIIIII...
 NodePathProperties * IIIIIIIIIIIIIIIIIIII...
 NodePathProperties * IIIIIIIIIIIIIIYIIIIZ...
 NodePathProperties * IIIIIIIIIIIIIIYXIIII...
 NodePathProperties * IIIIIIIIIIIIIIIYIIII...
 NodePathProperties * IIIIIIIIIIIIIIXIIIIX...
 NodePathProperties * IIIIIIIIIIIIIIXIIIIZ...
 NodePathProperties * IIIIIIIIIIIIIIYIIIIY...
 NodePathProperties * IIIIIIIIIIIIIIIIIIII...
 NodePathProperties * IIIIIIIIXIIIIIZXIIII...
 NodePathProperties * IIIIIIIIIIIIIIIZIIII...
 NodePathProperties * IIIIIIIIIIIIIIZIIIIY...
 NodePathProperties * IIIIIIIIIIIIIIIIIIIY...
 NodePathProperties * IIIIIIIIIIIIIIZIIIIZ...
 NodePathProperties * IIIIIIIIIIIIIIYIIIIY...
 NodePathProperties * IIIIIIIIIIIIIIIIIIII...
 NodePathProperties * IIIIIIIIIIIIZIIIIIXI...
 NodePathProperties * IIIIIIIIYIIIIIYZIIII...
  ⋮)

# filter against the initial state to speed up evaluation
surrogate_psum = zerofilter!(surrogate_psum)

Now we can compare against non-surrogate Pauli propagation simulation.

First, compare to the fully equivalent simulation with coefficients wrapped in PauliFreqTracker

Random.seed!(420)

for _ in 1:10
    thetas = randn(nparams)
    t1 = @timed psum = propagate(circuit, wrapcoefficients(pstr, PauliFreqTracker), thetas; max_freq, max_weight)
    t2 = @timed evaluate!(surrogate_psum, thetas)
    println("Equivalent Pauli propagation takes time: $(t1.time). Expectation: ", overlapwithzero(psum))
    println("Pauli propagation surrogate takes time:  $(t2.time). Expectation: ", overlapwithzero(surrogate_psum))
    println("") # for space
end

Equivalent Pauli propagation takes time: 4.148007759. Expectation: -0.09195551666054731


Pauli propagation surrogate takes time:  0.249509153. Expectation: -0.09195551665437668



Equivalent Pauli propagation takes time: 2.648998529. Expectation: 0.006196102025874881
Pauli propagation surrogate takes time:  0.136000766. Expectation: 0.006196102025828214



Equivalent Pauli propagation takes time: 3.159205027. Expectation: 0.26122265730227046
Pauli propagation surrogate takes time:  0.175336498. Expectation: 0.2612226572956533



Equivalent Pauli propagation takes time: 2.448908273. Expectation: 0.23681986847693884
Pauli propagation surrogate takes time:  0.145843746. Expectation: 0.23681986862949683



Equivalent Pauli propagation takes time: 3.975911512. Expectation: 0.017753943018382908
Pauli propagation surrogate takes time:  0.139397537. Expectation: 0.017753942996396717



Equivalent Pauli propagation takes time: 2.295772191. Expectation: 0.11424995928834948
Pauli propagation surrogate takes time:  0.155934525. Expectation: 0.11424995897094593



Equivalent Pauli propagation takes time: 2.562063232. Expectation: -0.02330422748624532
Pauli propagation surrogate takes time:  0.209382763. Expectation: -0.0233042274864537



Equivalent Pauli propagation takes time: 2.595612716. Expectation: -0.021730640866541515
Pauli propagation surrogate takes time:  0.264013935. Expectation: -0.02173064086670088



Equivalent Pauli propagation takes time: 3.034266337. Expectation: -0.24370682737291208
Pauli propagation surrogate takes time:  0.265193888. Expectation: -0.24370682744191186



Equivalent Pauli propagation takes time: 2.166812667. Expectation: -0.00026444458430952933
Pauli propagation surrogate takes time:  0.265802398. Expectation: -0.00026408645889508054

In some sense, this comparison is fair in that it shows the power of the fast re-evaluation of the surrogate. On the other hand, though, truncation via max_freq (as used here) is a little unnatural when the parameters are known. If the parameters are known then you can simply use coefficient truncation via min_abs_coeff which is both quicker and more accurate. So let's compare against some simulations with min_abs_coeff truncation.

min_abs_coeff = 1e-3  # this is a very inaccurate truncation for simulations of interest

Random.seed!(420)

for _ in 1:10
    thetas = randn(nparams)
    t1 = @timed psum = propagate(circuit, pstr, thetas; min_abs_coeff, max_weight)
    t2 = @timed evaluate!(surrogate_psum, thetas)
    println("Conventional Pauli propagation takes time: $(t1.time). Expectation: ", overlapwithzero(psum))
    println("Pauli propagation surrogate takes time:    $(t2.time). Expectation: ", overlapwithzero(surrogate_psum))
    println("") # for space
end

Conventional Pauli propagation takes time: 1.665167554. Expectation: -0.11957680055685284


Pauli propagation surrogate takes time:    0.136389762. Expectation: -0.09195551665437668



Conventional Pauli propagation takes time: 0.482978332. Expectation: 0.039055569410942605
Pauli propagation surrogate takes time:    0.178235112. Expectation: 0.006196102025828214



Conventional Pauli propagation takes time: 0.722367172. Expectation: 0.2592670505089841
Pauli propagation surrogate takes time:    0.200950801. Expectation: 0.2612226572956533



Conventional Pauli propagation takes time: 0.344771189. Expectation: 0.2228438487160257
Pauli propagation surrogate takes time:    0.184479998. Expectation: 0.23681986862949683



Conventional Pauli propagation takes time: 0.490818177. Expectation: 0.049819592824997774
Pauli propagation surrogate takes time:    0.16091662. Expectation: 0.017753942996396717



Conventional Pauli propagation takes time: 0.586835143. Expectation: 0.05547121704791134
Pauli propagation surrogate takes time:    0.226399897. Expectation: 0.11424995897094593



Conventional Pauli propagation takes time: 0.522788213. Expectation: 0.03410853823943496
Pauli propagation surrogate takes time:    0.173785623. Expectation: -0.0233042274864537



Conventional Pauli propagation takes time: 0.593706603. Expectation: -0.03623847105288109
Pauli propagation surrogate takes time:    0.280876283. Expectation: -0.02173064086670088



Conventional Pauli propagation takes time: 0.360614101. Expectation: -0.223124545768324
Pauli propagation surrogate takes time:    0.266771882. Expectation: -0.24370682744191186



Conventional Pauli propagation takes time: 0.489774636. Expectation: -0.08455886704434287
Pauli propagation surrogate takes time:    0.278618061. Expectation: -0.00026408645889508054

Which approach is more accurate? The precise comparison is beyond the scope of this notebook and highly implementation dependent. What we can say at this point is that there is a potential advantage of using the surrogate if you can afford the extra memory. There is also some initial time overhead, but the faster re-evaluation should quickly compensate if you are doing lots of evaluations. When you are happy with rough but rapid estimates, the surrogate might be the way to go.