Amortizing or batching circuit evaluation for many different inputs?
Some further thoughts, at least for the case when batch generation is done by feeding a gray code or other simply generated sequence into a circuit with internal memory.

For an ordinary combinatorial logic circuit without memory, we can bound the size of a circuit needed to evaluate a general function on n bits in two ways: by providing a general construction with known size, or by observing that 2^2^n different functions require 2^2^n different circuits, so the size of the largest circuit encountered cannot be so small that there are less than 2^2^n different circuits of up to that size. Knuth Vol 4A section 7.1.2 Theorem L shows that these bounds are in fact very close together, and require a circuit of size O(2^n/n) for a general function on n bits. So combinatorial logic circuits without memory do not waste much complexity by having many different circuits computing the same function.

If we stick to the design of a gray code generator feeding a circuit with internal memory, the only source of variation is the choice of the circuit, which now includes memory elements. The description of such a circuit needs a few more bits per item to offer the possibility of memory elements, but this is just a constant factor. By the requirement that to be able to compute any of 2^2^n different functions we must provide 2^2^n different circuits, and by the observation that ordinary combinatorial logic circuits do not have staggering inefficiencies, I think we find that introducing internal memory into an otherwise pedestrian design will not allow all possible functions to be calculated using only circuits of size significantly smaller than their best combinatorial logic implementation.

(but if P=NP our simulator has other options, such as Valiant Approximate Counting, which allow them to estimate the fraction of input states leading to a particular outcome in a simulation, without actually simulating all possibilities).

I remain interested in any comments, pointers, or whatever, about anything that bears on this.