Propagation

propagate(circ, pstr::PauliString, thetas=nothing; min_abs_coeff=1e-10, max_weight=Inf, max_freq=Inf, max_sins=Inf, customtruncfunc=nothing, heisenberg=true, thread=true, kwargs...)

Propagate a PauliString through the circuit circ. By default this is done in the Heisenberg picture, as indicated by heisenberg=true. This means that the circuit is applied to the Pauli string in reverse order, and the action of each gate is its conjugate action. Parameters for the parametrized gates in circ are given by thetas, and need to be passed as if the circuit was applied as written in the Schrödinger picture. If thetas are not passed, the circuit must contain only non-parametrized StaticGates. Default truncations are min_abs_coeff, max_weight, max_freq, and max_sins. max_freq, and max_sins will lead to automatic conversion if the coefficients are not already wrapped in suitable PathProperties objects. A custom truncation function can be passed as customtruncfunc with the signature customtruncfunc(pstr::PauliStringType, coefficient)::Bool. thread=false disables multithreading in every function on the VectorPauliSum backend that can multithread. It's safe to call from inside your own threaded loop (e.g. Threads.@threads for _ in 1:10; propagate(...; thread=false); end), since it won't spawn extra threads competing with yours. Further kwargs are passed to the lower-level functions applymergetruncate!, applytoall!, and apply.

propagate(circuit, psum::AbstractPauliSum, thetas=nothing; min_abs_coeff=1e-10, max_weight=Inf, max_freq=Inf, max_sins=Inf, customtruncfunc=nothing, heisenberg=true, thread=true, kwargs...)
propagate!(circuit, psum::AbstractPauliSum, thetas=nothing; min_abs_coeff=1e-10, max_weight=Inf, max_freq=Inf, max_sins=Inf, customtruncfunc=nothing, heisenberg=true, thread=true, kwargs...)

Propagate a Pauli sum psum through the circuit circ. By default this is done in the Heisenberg picture, as indicated by heisenberg=true. This means that the circuit is applied to the Pauli sum in reverse order, and the action of each gate is its conjugate action. In propagate() the Pauli sum psum is deepcopied and passed into the in-place propagation function propagate!(). Parameters for the parametrized gates in circ are given by thetas, and need to be passed as if the circuit was applied as written in the Schrödinger picture. If thetas are not passed, the circuit must contain only non-parametrized StaticGates. Default truncations are min_abs_coeff, max_weight, max_freq, and max_sins. max_freq, and max_sins are only supported for a PauliSum and will lead to automatic conversion if the coefficients are not already wrapped in suitable PathProperties objects. A custom truncation function can be passed as customtruncfunc with the signature customtruncfunc(pstr::PauliStringType, coefficient)::Bool. thread=false disables multithreading in every function on the VectorPauliSum backend that can multithread, allowing efficient multi-threading on a higher level (e.g. Threads.@threads for _ in 1:10; propagate(...; thread=false); end). Further kwargs are passed to the lower-level functions applymergetruncate!, applytoall!, and apply.

propagate!(circuit, prop_cache::AbstractPauliPropagationCache, thetas=nothing; min_abs_coeff=1e-10, max_weight=Inf, max_freq=Inf, max_sins=Inf, customtruncfunc=nothing, heisenberg=true, thread=true, kwargs...)

In-place propagation of an AbstractPauliPropagationCache through the circuit circ in the Heisenberg picture.

truncate!(psum::AbstractPauliSum; minabscoeff=1e-10, maxweight=Inf, maxfreq=Inf, maxsins=Inf, minrelcoeff=nothing, customtruncfunc=nothing, thread=true, kwargs...) truncate!(propcache::AbstractPauliPropagationCache; minabscoeff=1e-10, maxweight=Inf, maxfreq=Inf, maxsins=Inf, minrel_coeff=nothing, customtruncfunc=nothing, thread=true, kwargs...)

Truncation function for AbstractPauliPropagationCaches that combines multiple truncation criteria. The default truncation criteria are:

• min_abs_coeff: Truncates Pauli strings with absolute coefficient below this value.
• max_weight: Truncates Pauli strings with weight (number of non-identity Paulis) above this value.
• max_freq: Truncates Pauli strings with frequency (number of cosine factors in coefficient) above this value.
• max_sins: Truncates Pauli strings with number of sine factors in coefficient above this value.

A custom truncation function can be passed as customtruncfunc with the signature customtruncfunc(pstr, coeff)::Bool.

This function combines all truncation criteria into a single truncation function truncfunc() calls PropagationBase.truncate!(truncfunc, prop_cache).

buildtruncfunc(pobj; min_abs_coeff=1e-10, max_weight=Inf, max_freq=Inf,
               max_sins=Inf, min_rel_coeff=nothing, customtruncfunc=nothing,
               thread=true)

Build a predicate that combines the supported truncation criteria. When min_rel_coeff is specified, its absolute threshold is calculated from the largest coefficient currently in pobj and captured by the returned function.

apply(gate::TransferMapGate, pstr, coeff)

Apply a TransferMapGate to an integer Pauli string and its coefficient. The outcomes are determined by the transfer_map of the gate.

applymergetruncate!(gate::AmplitudeDampingNoise, prop_cache::AbstractPauliPropagationCache, gamma; thread=true, kwargs...)

Overload of applymergetruncate! for AmplitudeDampingNoise gates. Branches, merges and truncates in one call through xorbranchmergeandtruncate!.

applymergetruncate!(gate::CliffordGate, prop_cache::AbstractPauliPropagationCache; kwargs...)

Apply a Clifford gate and truncate in the same walk. The gate never creates duplicate terms, so no merge is needed. It changes only the signs of the coefficients, so min_abs_coeff, min_rel_coeff, max_freq and max_sins would drop nothing that the truncation after the previous gate kept. The terms are therefore truncated only when max_weight or customtruncfunc is given, and min_rel_coeff is never applied.

applymergetruncate!(gate::FrozenGate, prop_cache::AbstractPauliPropagationCache; kwargs...)

Apply a FrozenGate through the top-level implementation of its wrapped gate, with its frozen parameter.

applymergetruncate!(gate::ImaginaryPauliRotation, prop_cache::AbstractPauliPropagationCache, tau; normalize_coeffs=true, kwargs...)

Overload of applymergetruncate! for ImaginaryPauliRotation gates and a propagating PauliSum. Applies the gate, merges the resulting Pauli sum, and truncates it. If normalize_coeffs=true, the resulting Pauli sum is normalized by the coefficient of the identity Pauli string after merging. This is useful for numerical stability when evolving states in the Schrödinger picture.

applymergetruncate!(gate::PauliNoise, prop_cache::AbstractPauliPropagationCache, lambda; kwargs...)

Apply PauliNoise and truncate in one walk whenever the truncation threshold does not depend on the post-gate maximum coefficient. The gate never creates duplicate terms, so no merge is needed.

applymergetruncate!(gate::PauliRotation, prop_cache::AbstractPauliPropagationCache, theta; thread=true, kwargs...)

Overload of applymergetruncate! for PauliRotation gates. Branches, merges and truncates in one call through xorbranchmergeandtruncate!.

applymergetruncate!(gate::TGate, prop_cache::AbstractPauliPropagationCache; kwargs...)

Apply a TGate(qind) through the top-level implementation of a PauliRotation(:Z, qind) with angle π/4.

applytoall!(gate::AmplitudeDampingNoise, prop_cache::AbstractPauliPropagationCache, gamma; thread=true, kwargs...)

Overload of applytoall! for AmplitudeDampingNoise gates with noise strength gamma. On the damped qubit, X and Y are damped by a factor of sqrt(1 - gamma), and Z keeps a factor of 1 - gamma and branches into the identity with a factor of gamma.

applytoall!(gate::CliffordGate, prop_cache::AbstractPauliPropagationCache; thread=true, kwargs...)

Apply a Clifford gate in place to a propagation cache. Clifford gates have exactly one output per input, so the pair transformation is handled by map!.

applytoall!(gate::FrozenGate, prop_cache::AbstractPauliPropagationCache; kwargs...)

Apply a FrozenGate through the applytoall! implementation of its wrapped gate, with its frozen parameter.

applytoall!(gate::ImaginaryPauliRotation, prop_cache::AbstractPauliPropagationCache, tau; thread=true, kwargs...)

Like the PauliRotation method, except that an imaginary Pauli rotation branches the Pauli strings that commute with its generator, with factors of cosh(τ) and sinh(τ).

applytoall!(gate::PauliNoise, prop_cache::AbstractPauliPropagationCache, lambda; thread=true, kwargs...)

Overload of applytoall! for PauliNoise gates with noise strength lambda. The Pauli strings that isdamped selects are damped by a factor of 1 - lambda.

applytoall!(gate::PauliRotation, prop_cache::AbstractPauliPropagationCache, theta; thread=true, kwargs...)

Overload of applytoall! for PauliRotation gates. A Pauli string that anticommutes with the generator keeps a factor of cos(θ) and branches into its product with the generator, which gets a factor of sin(θ).

applytoall!(gate::TGate, prop_cache::AbstractPauliPropagationCache; kwargs...)

Apply a TGate(qind) as a PauliRotation(:Z, qind) with angle π/4.

merge!(term_sum::AbstractTermSum; thread=true)
merge!(prop_cache::AbstractPropagationCache; thread=true)

Merge the terms the last gate left in the auxiliary sum, or appended past the sorted prefix, into the main sum, combining equal terms with mergefunc. A term sum combines its own equal terms the same way, through a propagation cache of its own where it needs one.

merge(term_sum::AbstractTermSum; thread=true)
merge(prop_cache::AbstractPropagationCache; thread=true)

merge! on a copy.

mergeandtruncate!(truncfunc, term_sum::AbstractTermSum; thread=true)
mergeandtruncate!(truncfunc, prop_cache::AbstractPropagationCache; thread=true)

Merge all equal active terms, then drop every (term, coefficient) pair for which truncfunc(term, coefficient) returns true. A truncfunc of nothing drops nothing, which is merge!; every storage merges the two the same way. truncfunc sees the merged coefficient, so contributions can still cancel before a term is judged, and it is applied even when nothing needs merging, since a gate may have rescaled the terms without creating any. An array on the CPU truncates as it writes the merged terms, every other storage merges and then truncates. Several tasks on an array call truncfunc once to count the terms and once to write them, so it must return the same for the same pair each time.

Branch(kept, created)

The outcome of a rule for xorbranch! that keeps the term with the coefficient kept and creates the term term ⊻ mask with the coefficient created.

Kept(coefficient)

The outcome of a rule for xorbranch! that keeps the term with coefficient.

Unchanged()

The outcome of a rule for xorbranch! that leaves a term as it is. A rule that returns it need not read the coefficient.

ruleat(rule, terms, coefficients, ii)

rule(terms[ii], coefficients[ii]), as the array kernels of xorbranch! call a rule. A rule that can decide from a part of the term overloads this to read only that part, and the coefficient only once it needs it. The kernels keep terms alive for the whole walk, so a rule may read it through a pointer.

xorbranch!(rule, prop_cache::AbstractPropagationCache, mask; thread=true)

Branch every active term by rule. rule(term, coefficient) returns Unchanged() to leave the term alone, Kept(coefficient) to keep it with a new coefficient, or Branch(kept, created) to keep it with kept and create the term term ⊻ mask with created. The terms it creates are left for xormerge! or xormergeandtruncate! to merge: a dictionary holds them in the auxiliary sum, an array appends them past its sorted prefix in the order of their parents, a multi sum leaves them in the outboxes, each zone's in the one box of the zone that owns them, and any other storage adds them through flatmap!. Every new term is the same ⊻ mask away from its parent, which is what lets those merges sort the new terms in without comparing them. merge! and mergeandtruncate! merge them too, only by comparison. A dictionary or multi sum therefore finds its auxiliary sum or outboxes empty, and throws an ArgumentError otherwise, since a branch would write over what they hold; an array branches an unmerged tail like any other terms. Several tasks on an array call rule once to count the terms and once to write them, so it must return the same for the same pair each time.

xorbranch(rule, prop_cache::AbstractPropagationCache, mask; thread=true)

Branch every active term by rule on a copy, see xorbranch!.

xorbranchmergeandtruncate!(rule, truncfunc, prop_cache::AbstractPropagationCache, mask; thread=true)

xorbranch! by rule followed by xormergeandtruncate! by truncfunc, as one call. The merge then knows what the branch left: an array whose active terms were all in its sorted prefix sorts the new terms in by XOR passes without checking them first, a multi sum of arrays does the same zone by zone, and an array or multi sum in which the rule touched no term is left as it is, without a merge or a truncation pass. A dictionary truncates after every branch, so that a term the rule leaves alone still goes through truncfunc. A zone of a multi sum parks its new terms in the first box of its outbox, whatever zone owns them, so that one box per outbox grows instead of one per pair of zones. A truncfunc of nothing truncates nothing.

xormerge!(prop_cache::AbstractPropagationCache, mask; thread=true)

merge! for a cache that xorbranch! has branched by mask. An array sorts the tail past its sorted prefix in by XOR passes instead of by comparison when the tail is term ⊻ mask of an ascending run of terms, which one pass over the tail checks, and merges it generically otherwise. A multi sum takes delivery of the outboxes xorbranch! filled, sorting each in from where it is.

xormergeandtruncate!(truncfunc, prop_cache::AbstractPropagationCache, mask; thread=true)

mergeandtruncate! for a cache that xorbranch! has branched by mask, see xormerge!. Several tasks on an array call truncfunc once to count the terms and once to write them, so it must return the same for the same pair each time.

Truncated()

The internal outcome of mapandtruncate! and mapcoeffsandtruncate! for an input term whose mapped pair is truncated.

mapandtruncate!(mapfunc, truncfunc, prop_cache::AbstractPropagationCache; thread=true)

Replace every active (term, coefficient) pair by the pair mapfunc(term, coefficient) returns, as map! does, and discard the new pair when truncfunc(new_term, new_coefficient) returns true. This is a propagation-cache primitive: it may use the cache's auxiliary storage to compact the active terms.

It is intended for a gate that deterministically maps every term to one term and can decide, from the new pair, that it is truncated. Array storage performs the mapping and compaction in one walk, and any other storage writes the new pairs through flatmap!.

On a multithreaded CPU array, both functions are called once to count retained terms and again to write them. They must therefore be deterministic, replayable, and safe to call concurrently.

mapcoeffsandtruncate!(mapfunc, truncfunc, prop_cache::AbstractPropagationCache; thread=true)

Map every active coefficient with mapfunc(term, coefficient) and discard the mapped pair when truncfunc(term, new_coefficient) returns true. This is a propagation-cache primitive: unlike mapcoeffsbypair!, it may use the cache's auxiliary storage to compact the active terms. mapcoeffsandtruncate! itself constructs the Kept(new_coefficient) and Truncated() outcomes, so its callers only supply the mapping and truncation functions.

It is intended for a gate that deterministically rescales terms and can decide, from the new coefficient, that a term is truncated. Array storage performs the mapping and compaction in one walk; other storage types use their corresponding direct or cache-aware implementation.

On a multithreaded CPU array, both functions are called once to count retained terms and again to write them. They must therefore be deterministic, replayable, and safe to call concurrently.

onlimbs(buildrule, mask, args...)

The rule buildrule(mask, args...) of xorbranch!, which has to read a term only through mask. Where the terms span more 64-bit limbs than mask acts on, the rule is built for those limbs of mask instead, and an OnLimbs asks it about the same limbs of every term. Called once per gate, never per term.

@countpaulis expr
@countpaulis lhs = expr

Return the number of Pauli strings after every gate applied inside expr, as a Vector{Int}.

Counts are taken after merging and truncating, and are ordered as the gates are applied, which for the default Heisenberg picture is the reverse of the circuit as written. Every propagation inside expr contributes, including mcpropagate, mcsample and rewindgradient. An assignment is instrumented by prefixing it, and still assigns.

counts = @countpaulis propagate(circuit, psum, thetas)
counts = @countpaulis psum = propagate(circuit, psum, thetas)

@peakpaulis expr
@peakpaulis lhs = expr

Return the largest number of Pauli strings held after any gate applied inside expr, or 0 if nothing was propagated.

expr is typically a call to a function that propagates internally, possibly several times, in which case the peak is taken over all of those propagations. See @countpaulis for what is counted and when.

peak = @peakpaulis myexpectationvalue(circuit, thetas)
peak = @peakpaulis psum, base = headandtails(circuit, obs, thetas, nlayers)