6
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ There may be special classes of Hamiltonians that can be simulated by shorter time algorithms. For example, see this paper (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. $\endgroup$
    – BlackHat18
    Jul 13 at 4:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.