Speaker
Prof.
Apoorva Patel
(Indian Institute of Science, Bangalore, India)
Description
A specific unitary evolution operator can be constructed in many
different ways, corresponding to different Hamiltonian trajectories
between the desired end-points. An optimal trajectory can then be
selected to make the evolution have the best computational complexity
and control over errors. Using Grover's quantum search algorithm as
an explicit example, it is shown that the complexity has a power-law
dependence on error when a straightforward Lie-Trotter formula is
used, and it becomes logarithmic in error when reflection operators
are used. The exponential change in error control is surprising, and
can be used to improve importance sampling methods. The key concept
is to make the evolution steps as large as possible while obeying the
constraints of the problem. In particular, we can understand why
overrelaxation algorithms are superior to small step size algorithms.
Primary author
Prof.
Apoorva Patel
(Indian Institute of Science, Bangalore, India)
