Pauli Propagation

Pauli propagation computes an expectation value without ever building a state. Instead of evolving the state forward, it evolves the observable backward through the circuit (the Heisenberg picture) and evaluates the result against |0…0⟩.

Capabilities

Output	Supported
Expectation value	Yes (only)
Counts	No
Statevector	No

It is enumerated only for expectation requests.

Which circuits

The operations must be Clifford gates or one of a few rotations:

Gate	Effect on one Pauli term
X Y Z H S Sdg SX SXdg CX CZ SWAP	One term becomes one term (with a sign)
RZ RX RY P	One term splits into at most 2 weighted terms
U	One term splits into at most 3 weighted terms

T, Tdg, CP, CCX and unitary operations are not supported and make the engine infeasible, naming the operation:

operation 20 (t) is not supported by Pauli propagation (Clifford gates and RZ/RX/RY/P/U only)

A region that is entirely Clifford is also refused, by the routing rule: the stabilizer engine handles those.

Cost and its limit

A Clifford gate does not change the number of terms. Each rotation can multiply it by up to 2 (by up to 3 for U), so in the worst case the count grows exponentially with the number of rotations that reach the observable. MENOS computes a worst-case bound before propagating anything and refuses a job whose bound cannot be represented, rather than truncating terms. The engine is always exact.

It shines when the observable is local and few rotations reach it.

Example

An RZ-ladder circuit on 10 qubits with a single-qubit observable, run natively. The planner considers six strategies and picks Pauli propagation:

"""An expectation value by Pauli propagation: no statevector is ever built."""

from qiskit import QuantumCircuit
from qiskit.quantum_info import SparsePauliOp, Statevector

from menos import Circuit, Opcode, RunOptions, run
from menos._core import Observable, PauliString

n = 10
native = Circuit(n, 0)
reference = QuantumCircuit(n)
for layer in range(3):
    for q in range(n):
        native.append(Opcode.H, [q])
        reference.h(q)
    native.append(Opcode.RZ, [0], [0.37])
    reference.rz(0.37, 0)
    for q in range(layer % 2, n - 1, 2):
        native.append(Opcode.CX, [q, q + 1])
        reference.cx(q, q + 1)

z0 = PauliString()
z0.num_qubits = n
z0.x_words = [0]
z0.z_words = [1]  # Z on qubit 0
observable = Observable()
observable.terms = [(z0, 1.0 + 0.0j)]

options = RunOptions()
options.expectation = observable
result = run(native, options)

report = result.explain()
print("\n".join(line for line in report.splitlines() if line.startswith(("candidate", "strategy"))))
print("expectation:", result.expectation_value.real)
print("bytes used:", result.actual_state_bytes)

expected = Statevector(reference).expectation_value(SparsePauliOp("I" * (n - 1) + "Z")).real
assert "strategy   direct_pauli" in report
assert abs(result.expectation_value.real - expected) < 1e-12

candidate strategy=direct_dense feasible=true winner=false peak_bytes=256 work_units=672
candidate strategy=direct_stabilizer feasible=false …
candidate strategy=direct_pauli feasible=true winner=true peak_bytes=256 work_units=128
candidate strategy=direct_mps feasible=true winner=false peak_bytes=384 work_units=148
candidate strategy=direct_tensor_network feasible=true winner=false peak_bytes=1024 work_units=2890
candidate strategy=cut_and_recombine feasible=true winner=false peak_bytes=256 work_units=840

Pauli propagation has 128 work units, against 672 for dense, and the value agrees with Qiskit's Statevector to about 1e-16. The report above is abridged; the real lines have no space after the label (see Plan Explanation).

Related

Observables · Light-Cone Reduction · Expectation Values