Incorrect formula to calculate required Trotter steps

[kapawlak]

The function circuits.trotter_steps_required incorrectly calculates the number of Trotter steps required, if I understand the function correctly.

For a second-order product formula, the error on a simulation of $H$ over time $t$ with $r$ steps is given by:

$$ \mathcal E_2^r(t) = \frac{t^3}{r^2} \mathcal E_{bound}(H) $$

This scaling can be found in this reference or derived by ordinary error-propagation formulas. Inverting this to find $r$ for a desired total error $\mathcal E_2(t)$:

$$ r = \text{ceil} \Big(t^{3/2} \sqrt{\mathcal E_{bound}(H)/\mathcal E_2(t)}\Big) $$

The formula given in the source code of circuits.trotter_steps_required is missing a factor of $t^{1/2}$:

def trotter_steps_required(trotter_error_bound, time, energy_precision):
    """Determine the number of Trotter steps for accurate simulation.

    Args:
        trotter_error_bound (float): Upper bound on Trotter error in the
                                     state of interest.
        time (float): The total simulation time.
        energy_precision (float): Acceptable shift in state energy.

    Returns:
        The integer minimum number of Trotter steps required for
        simulation to the desired precision.

    Notes:
        The number of Trotter steps required is an upper bound on the
        true requirement, which may be lower.
    """
    return int(ceil(time * sqrt(trotter_error_bound / energy_precision)))

E.g.

$$ r = \text{ceil} \Big(t \sqrt{\mathcal E_{bound}(H)/\mathcal E_2(t)}\Big) $$

This dramatically underestimates the number of steps required for very large simulation times.

[ncrubin]

Thanks for flagging this @kapawlak and the detailed description of the issue. It'll take me a couple of days to look into this.