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.614859 seconds (3.18 M allocations: 152.106 MiB, 1.17% gc time, 99.30% 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)

  4.668 ms

 (17 allocations: 479.45 KiB)

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

  4.143 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)

  249.956 μ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)

  7.608360 seconds (46.48 M allocations: 1.732 GiB, 30.38% gc time, 11.28% 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 * IIIIIIIIIIIIZIIIIIXI...
 NodePathProperties * IIIIIIIIYIIIIIYZIIII...
 NodePathProperties * IIIIIIIIIIIIIIIIIIIX...
  ⋮)

# 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: 3.343454621. Expectation: -0.09195551666054731


Pauli propagation surrogate takes time:  0.174205398. Expectation: 

-0.09195551665437665



Equivalent Pauli propagation takes time: 4.944444748. Expectation: 0.0061961020258748875
Pauli propagation surrogate takes time:  0.403720862. Expectation: 

0.006196102025828212



Equivalent Pauli propagation takes time: 3.099213081. Expectation: 0.26122265730227046
Pauli propagation surrogate takes time:  0.288964578. Expectation: 0.2612226572956533



Equivalent Pauli propagation takes time: 2.432317732. Expectation: 0.23681986847693884
Pauli propagation surrogate takes time:  0.139839785. Expectation: 0.23681986862949678



Equivalent Pauli propagation takes time: 2.044817844. Expectation: 0.017753943018382894
Pauli propagation surrogate takes time:  0.275164324. Expectation: 0.017753942996396717



Equivalent Pauli propagation takes time: 3.036897136. Expectation: 0.11424995928834947
Pauli propagation surrogate takes time:  0.248735336. Expectation: 0.1142499589709459



Equivalent Pauli propagation takes time: 2.274554762. Expectation: -0.023304227486245332
Pauli propagation surrogate takes time:  0.153299393. Expectation: -0.023304227486453687



Equivalent Pauli propagation takes time: 1.876766191. Expectation: -0.021730640866541518
Pauli propagation surrogate takes time:  0.217780628. Expectation: -0.021730640866700873



Equivalent Pauli propagation takes time: 2.057652974. Expectation: -0.2437068273729121
Pauli propagation surrogate takes time:  0.192336326. Expectation: -0.2437068274419119



Equivalent Pauli propagation takes time: 3.310488137. Expectation: -0.00026444458430953627
Pauli propagation surrogate takes time:  0.325382592. Expectation: -0.000264086458895084

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: 2.110223081. Expectation: -0.11957680055685282


Pauli propagation surrogate takes time:    0.172926642. Expectation: -0.09195551665437665



Conventional Pauli propagation takes time: 0.514384587. Expectation: 0.0390555694109426
Pauli propagation surrogate takes time:    0.165447671. Expectation: 0.006196102025828212



Conventional Pauli propagation takes time: 0.440913281. Expectation: 0.2592670505089839
Pauli propagation surrogate takes time:    0.154315946. Expectation: 0.2612226572956533



Conventional Pauli propagation takes time: 0.245334218. Expectation: 0.22284384871602575
Pauli propagation surrogate takes time:    0.152129556. Expectation: 0.23681986862949678



Conventional Pauli propagation takes time: 0.384337305. Expectation: 0.04981959282499783
Pauli propagation surrogate takes time:    0.149253993. Expectation: 0.017753942996396717



Conventional Pauli propagation takes time: 0.408845421. Expectation: 0.05547121704791136
Pauli propagation surrogate takes time:    0.153065145. Expectation: 0.1142499589709459



Conventional Pauli propagation takes time: 0.578177159. Expectation: 0.034108538239434966
Pauli propagation surrogate takes time:    0.294904987. Expectation: -0.023304227486453687



Conventional Pauli propagation takes time: 0.460671122. Expectation: -0.0362384710528811
Pauli propagation surrogate takes time:    0.177082212. Expectation: -0.021730640866700873



Conventional Pauli propagation takes time: 0.307204134. Expectation: -0.22312454576832402
Pauli propagation surrogate takes time:    0.159444455. Expectation: -0.2437068274419119



Conventional Pauli propagation takes time: 0.892434083. Expectation: -0.08455886704434287
Pauli propagation surrogate takes time:    0.149267704. Expectation: -0.000264086458895084

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.