Even though Trotterized Hamiltonians have polynomial time scaling directly, the process of quantum phase estimation means that the controlled unitaries $ CU$ scale exponentially with number of precision bits. That means we need to apply our controlled Hamiltonian an exponential number of times if we increase the number of precision bits. Furthermore, because increasing the trotter step size requires greater precision, doesn't this directly imply that there is some relationship between Hamiltonian size and precision required, and thus a somewhat exponential relationship?

So, does Trotterization technically scale closer to exponential time or amortized superpolynomial time? Are there ways to get around this additional time cost incurred by QPE?

  • $\begingroup$ If you found an answer since posting this, please do share. $\endgroup$
    – shashvat
    Apr 28, 2021 at 2:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.