| dc.description.abstract | Many simulation problems can be expressed as time evolution under specific interactions,
from some simple initial state to a final state whose properties are to be investigated. In this
context, the Hamiltonian evolution problem has been extensively studied. Quantum simulations
can sum multiple evolutionary paths contributing to a quantum process in superposition at one
go, while classical simulations need to evaluate these paths one by one. Real physical systems are
governed by local Hamiltonians, i.e. where each component interacts only with a limited number
of its neighbours independent of the overall size of the system, which helps in parallelisation
of their simulations. The procedure is not simple, however. Although, in the 2n-dimensional
Hilbert space of n qubits, we can superpose 2n components evolving in parallel, we can measure
only n binary observables at the end. So the exponential gain of superposition is limited by
the restriction to extract only a small number of results at the end. This dichotomy means that
quantum algorithms will be advantageous only when the final observables are local in some
manner; no general prescription is available, and one has to look at the problems on a case by
case basis.
Early quantum evolution algorithms exploited locality of Hamiltonians for efficient use of
time and space resources during evolution [3, 4]. More recently, the error complexity of the
evolution has been reduced from power-law to logarithmic in the inverse error, using large step
discrete time algorithms [5–7]. After the Hamiltonian evolution, investigation of final state
properties requires expectation values of various observables to be measured. The problem of
how to do this efficiently has not been adequately addressed so far. Since quantum measurements
are probabilistic, determination of the expectation values needs multiple repetitions of the same
algorithm. Thereafter, importance sampling or phase estimation based results yield errors that
decrease as power-law in the number of repetitions [8, 9], e.g. Niter × *2 as per the central
limit theorem, and that is not efficient. What we want is a strategy that decreases the errors
exponentially with the number of repetitions, e.g. finding zeroes of a function by bisection
is efficient with Niter × log , and finding them by Newton’s method is super-efficient with
Niter × log log . While that may not be possible for generic observables, it can be achieved
for k-local observables that appear in evaluations of k-point Green’s functions for many-body
systems. We explicitly show how to do that.
The novel concept we introduce is a digital state representation of quantum states, which
maps non-unitary linear algebra operations to unitary operators. High precision calculations need
3 1.1. Scope of the Thesis
a digital representation instead of an analog one. Our digital representation for both the quantum
states and the operators maintains the expectation values of all physical observables. It combines
classical reversible logic with equally weighted linear superposition, and is essentially free of
the unitarity constraint for quantum states. This digital implementation can help in construction
of efficient quantum algorithms for many linear algebra problems. | en_US |
