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 * ZIIIIIII
 1.0 * IIIIIIIZ
)

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 * ZIIIIIII
 NodePathProperties * IIIIIIIZ
)

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.909776 seconds (2.97 M allocations: 150.284 MiB, 2.38% gc time, 98.47% compilation time)





PauliSum(nqubits: 8, 15314 Pauli terms:
 NodePathProperties * XZZYYIYX
 NodePathProperties * XXXXXXIZ
 NodePathProperties * XXIYZIYY
 NodePathProperties * IIZYXXYX
 NodePathProperties * IZIXXXII
 NodePathProperties * XXZZXIYI
 NodePathProperties * ZXXZIZZX
 NodePathProperties * ZZXZYYYZ
 NodePathProperties * XZXIXYZZ
 NodePathProperties * ZXXZXYIY
 NodePathProperties * YYZIZYII
 NodePathProperties * XZIXZXXX
 NodePathProperties * ZZZXIXXX
 NodePathProperties * XZZYZZIY
 NodePathProperties * XXIZIIXZ
 NodePathProperties * ZXZYIIYY
 NodePathProperties * XZXZZYIX
 NodePathProperties * IIXYIZXI
 NodePathProperties * IIYYIIXZ
 NodePathProperties * XXXIIYXY
  ⋮)

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.24889945017826412

Now compare this with the conventional Pauli propagation simulation:

psum = propagate(circuit, observable, thetas)

PauliSum(nqubits: 8, 15314 Pauli terms:
 3.4893e-5 * XZZYYIYX
 -7.9442e-6 * XXXXXXIZ
 1.6572e-7 * XXIYZIYY
 0.0001293 * IIZYXXYX
 -0.013172 * IZIXXXII
 1.943e-5 * XXZZXIYI
 -1.5311e-5 * ZXXZIZZX
 -0.0001322 * ZZXZYYYZ
 2.4683e-6 * XZXIXYZZ
 2.8125e-5 * ZXXZXYIY
 0.010307 * YYZIZYII
 0.00026285 * XZIXZXXX
 -5.2965e-5 * ZZZXIXXX
 0.00018093 * XZZYZZIY
 -4.9863e-6 * XXIZIIXZ
 -0.0031117 * ZXZYIIYY
 -4.3344e-5 * XZXZZYIX
 0.00055294 * IIXYIZXI
 3.2833e-5 * IIYYIIXZ
 -9.0128e-6 * XXXIIYXY
  ⋮)

# the same result
overlapwithzero(psum)

-0.24889945017826412

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)

  9.804 ms

 (17 allocations: 479.45 KiB)

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

  3.130 ms

 (658 allocations: 1.18 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)

  253.809 μ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.574965 seconds (46.18 M allocations: 1.720 GiB, 27.35% gc time, 12.52% compilation time)





PauliSum(nqubits: 36, 1626 Pauli terms:
 NodePathProperties * IIIIIIIIIIIIIIIIIIII...
 NodePathProperties * IIIIIIIIIIIIIIXIIIIX...
 NodePathProperties * IIIIIIIIIIIIIIXIIIIY...
 NodePathProperties * IIIIIIIIIIIIIXYIIIII...
 NodePathProperties * IIIIIIIIIIIIIIIZIIII...
 NodePathProperties * IIIIIIIIIIIIIIIIIIII...
 NodePathProperties * IIIIIIIIIIIIIIZIIIIY...
 NodePathProperties * IIIIIIIIIIIIIIYIIIIZ...
 NodePathProperties * IIIIIIIIIIIIIIIIIIYY...
 NodePathProperties * IIIIIIIIIIIIIIIYIIII...
 NodePathProperties * IIIIIIIIIIIIIIZXIIII...
 NodePathProperties * IIIIIIIIIIIIIIIIIIII...
 NodePathProperties * IIIIIIIIIIIIIYIIIIXY...
 NodePathProperties * IIIIIIIIIIIIIIIIIIII...
 NodePathProperties * IIIIIIIIIIIIIIIIIIIZ...
 NodePathProperties * IIIIIIIIIIIIIIZIIIIY...
 NodePathProperties * IIIIIIIIIIIIIIYIIIIX...
 NodePathProperties * IIIIIIIIIIIIIIYIIIIX...
 NodePathProperties * IIIIIIIIIIIIIYIIIIIY...
 NodePathProperties * IIIIIIIIIIIIIIIXIIII...
  ⋮)

# 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.514689819. Expectation: -0.09195551666054726


Pauli propagation surrogate takes time:  0.302625125. Expectation: 

-0.09195551665437661



Equivalent Pauli propagation takes time: 4.665752222. Expectation: 0.006196102025874873
Pauli propagation surrogate takes time:  0.29709778. Expectation: 0.006196102025828209



Equivalent Pauli propagation takes time: 1.908404513. Expectation: 0.2612226573022704
Pauli propagation surrogate takes time:  0.243983542. Expectation: 0.2612226572956533



Equivalent Pauli propagation takes time: 3.138951371. Expectation: 0.23681986847693878
Pauli propagation surrogate takes time:  0.289315051. Expectation: 0.2368198686294968



Equivalent Pauli propagation takes time: 1.967123988. Expectation: 0.017753943018382908
Pauli propagation surrogate takes time:  0.228203773. Expectation: 0.017753942996396734



Equivalent Pauli propagation takes time: 2.43645297. Expectation: 0.1142499592883495
Pauli propagation surrogate takes time:  0.290830248. Expectation: 0.1142499589709459



Equivalent Pauli propagation takes time: 1.878974997. Expectation: -0.023304227486245326
Pauli propagation surrogate takes time:  0.27237488. Expectation: -0.02330422748645372



Equivalent Pauli propagation takes time: 1.692217587. Expectation: -0.021730640866541515
Pauli propagation surrogate takes time:  0.152948854. Expectation: -0.021730640866700884



Equivalent Pauli propagation takes time: 1.831923677. Expectation: -0.2437068273729121
Pauli propagation surrogate takes time:  0.162131835. Expectation: -0.24370682744191188



Equivalent Pauli propagation takes time: 2.634757424. Expectation: -0.0002644445843095304
Pauli propagation surrogate takes time:  0.310310002. Expectation: -0.0002640864588950827

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.661014407. Expectation: -0.11957680055685285


Pauli propagation surrogate takes time:    0.191127275. Expectation: -0.09195551665437661



Conventional Pauli propagation takes time: 0.371238344. Expectation: 0.03905556941094261
Pauli propagation surrogate takes time:    0.198918406. Expectation: 0.006196102025828209



Conventional Pauli propagation takes time: 0.630315706. Expectation: 0.2592670505089841
Pauli propagation surrogate takes time:    0.330747479. Expectation: 0.2612226572956533



Conventional Pauli propagation takes time: 0.338004269. Expectation: 0.22284384871602575
Pauli propagation surrogate takes time:    0.307827291. Expectation: 0.2368198686294968



Conventional Pauli propagation takes time: 0.581892624. Expectation: 0.0498195928249978
Pauli propagation surrogate takes time:    0.297248304. Expectation: 0.017753942996396734



Conventional Pauli propagation takes time: 0.539990413. Expectation: 0.05547121704791136
Pauli propagation surrogate takes time:    0.254604634. Expectation: 0.1142499589709459



Conventional Pauli propagation takes time: 0.565370552. Expectation: 0.034108538239434966
Pauli propagation surrogate takes time:    0.296704209. Expectation: -0.02330422748645372



Conventional Pauli propagation takes time: 0.455860654. Expectation: -0.03623847105288112
Pauli propagation surrogate takes time:    0.151578656. Expectation: -0.021730640866700884



Conventional Pauli propagation takes time: 0.134465029. Expectation: -0.22312454576832405
Pauli propagation surrogate takes time:    0.158734625. Expectation: -0.24370682744191188



Conventional Pauli propagation takes time: 0.350867883. Expectation: -0.08455886704434286
Pauli propagation surrogate takes time:    0.21442001. Expectation: -0.0002640864588950827

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.