Efficient Quantum Algorithms for Linear Algebra Problems

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.