The complexity of simulating local measurements on quantum systems

Understand

An important task in quantum physics is the estimation of local quantities for ground states of local Hamiltonians.

• Recently, [Ambainis, CCC 2014] defined the complexity class P^QMA[log], and motivated its study by showing that the physical task of estimating the expectation value of a local observable against the ground state of a local Hamiltonian is P^QMA[log]-complete.
• In this paper, we continue the study of P^QMA[log], obtaining the following lower and upper bounds.
• Lower bounds (hardness results): (1) The P^QMA[log]-completeness result of [Ambainis, CCC 2014] requires O(log n)-local observables and Hamiltonians.