Resource estimator execution time scales with number of samples

[guenp]

Describe the bug

The resource estimator's execution time scales with the number of samples passed to nSamples.

Execution times (for 1 run with 1 loop):	nSamples	execution time
1	37.1 ms
10	133 ms
100	995 ms
1000	9.03 s
10000	2min 37s

However, the results for any number N samples can be achieved by running estimation for 1 sample and then simply multiplying the result by N.

To Reproduce

Run the following using the iqsharp kernel:

%estimate Microsoft.Quantum.Chemistry.JordanWigner.VQE.EstimateEnergy {"jwHamiltonian": {"@type": "tuple", "Item1": 4, "Item2": {"@type": "tuple", "Item1": [{"@type": "tuple", "Item1": [0], "Item2": [0.17120128499999998]}, {"@type": "tuple", "Item1": [1], "Item2": [0.17120128499999998]}, {"@type": "tuple", "Item1": [2], "Item2": [-0.222796536]}, {"@type": "tuple", "Item1": [3], "Item2": [-0.222796536]}], "Item2": [{"@type": "tuple", "Item1": [0, 1], "Item2": [0.1686232915]}, {"@type": "tuple", "Item1": [0, 2], "Item2": [0.12054614575]}, {"@type": "tuple", "Item1": [0, 3], "Item2": [0.16586802525]}, {"@type": "tuple", "Item1": [1, 2], "Item2": [0.16586802525]}, {"@type": "tuple", "Item1": [1, 3], "Item2": [0.12054614575]}, {"@type": "tuple", "Item1": [2, 3], "Item2": [0.1743495025]}], "Item3": [], "Item4": [{"@type": "tuple", "Item1": [0, 1, 2, 3], "Item2": [0.0, -0.0453218795, 0.0, 0.0453218795]}]}, "Item3": {"@type": "tuple", "Item1": 3, "Item2": [{"@type": "tuple", "Item1": {"@type": "tuple", "Item1": 0.001, "Item2": 0.0}, "Item2": [2, 0]}, {"@type": "tuple", "Item1": {"@type": "tuple", "Item1": -0.001, "Item2": 0.0}, "Item2": [3, 1]}, {"@type": "tuple", "Item1": {"@type": "tuple", "Item1": 0.001, "Item2": 0.0}, "Item2": [2, 3, 1, 0]}, {"@type": "tuple", "Item1": {"@type": "tuple", "Item1": 1.0, "Item2": 0.0}, "Item2": [0, 1]}]}, "Item4": -0.09883444600000002}, "nSamples": 1000}

Expected behavior

Same execution time for nSamples = 1 as nSamples = 10000 or arbitrary N.

Actual behavior

See execution table above, it looks like the execution time scales with nSamples.

System information

Running in iqsharp-based docker container.

[guenp]

I investigated further, and it looks like the operation is implemented in a for loop (see EstimateFrequency.qs)

operation EstimateFrequency (preparation : (Qubit[] => Unit), measurement : (Qubit[] => Result), nQubits : Int, nMeasurements : Int) : Double
    {
        mutable nUp = 0;

        for (idxMeasurement in 0 .. nMeasurements - 1) {
            using (register = Qubit[nQubits]) {
                preparation(register);
                let result = measurement(register);

                if (result == Zero) {
                    set nUp = nUp + 1;
                }

                ApplyToEach(Reset, register);
            }
        }

        return IntAsDouble(nUp) / IntAsDouble(nMeasurements);
    }

This for-loop is avoided by the simulator but not by the resource estimator, via a workaround in a C# implementation: EstimateFrequency.cs

        ///  Provides a native emulation of the EstimateFrequency operation for adjointable operations when
        ///  the operation is executed using the full-state QuantumSimulator and the given
        ///  state preparation function does not contain any captured qubits via partial application.
        ///  
        /// The way the emulation works is to invoke the state-preparation only once, and then look 
        /// into the resulting QuantumSimulator's state to get the JointProbability and then
        /// use a classical binomial sampling to get a sample for the resulting probability.
        /// This is typically faster compared to run the state-preparation operation n-times and
        /// calculate the binomial estimation from it.

How can we make sure this is also picked up by the resource estimator such that it can be executed in O(1) time for nSamples > 1?

[cgranade]

How can we make sure this is also picked up by the resource estimator such that it can be executed in O(1) time for nSamples > 1?

The emulation functionality in EstimateFrequency.cs checks for supported simulators and provides a fast path for any simulators that it recognizes; at the moment, that's just QuantumSimulator, but adding ResourcesEstimator would be a reasonable feature request for that emulation fast-path.