7

As a newbie to Quantum, I was reading some of the articles and ran into a no-fast-forwarding theorem, which is described "Simulating the dynamics of a quantum system for time T typically requires Ω(T) gates so that a generic Hamiltonian evolution cannot be achieved in sublinear time. This result is known as the “no fast-forwarding theorem”, and holds both for a typical unknown Hamiltonian and for the query model setting"

Does this mean that "there won't be any shorter-time algorithm than the required T? I don't think I fully appreciate the implication or practical meaning of this.

Any help would be appreciated

glS
  • 24,708
  • 5
  • 34
  • 108
John Parker
  • 1,081
  • 3
  • 11
  • 4
    There may be special classes of Hamiltonians that can be simulated by shorter time algorithms. For example, see this paper (https://arxiv.org/abs/1610.09619). But, as this paper proves, if all generic physically realizable Hamiltonians can be fast-forwarded, then BQP=PSPACE, which is thought to be highly unlikely. – BlackHat18 Jul 13 '21 at 04:54

1 Answers1

5

In simple words, it means you can't simulate a quantum system faster than time evolves it. However, if you have an analytical solution to the system, you can get the answer faster in theory. As an example consider a simple pendulum that you want to simulate for $t= 5$ sec. If you do it physically with an actual pendulum you have to wait for $5$ sec to get the results. But we already know its analytical solution and can predict its evolution with certainty using mathematical equations. So we can simulate the same on a computer in less than a sec. However, for most natural processes this is not the case, specifically complicated Hamiltonians.

Condo
  • 2,008
  • 6
  • 31
Shashi2 Kumar
  • 76
  • 1
  • 3