Arkin Tikku

Here we describe an approach for simulating quantum chemistry on quantum computers with significantly lower asymptotic complexity than prior work. The approach uses a real-space first-quantised representation of the molecular Hamiltonian which we propagate using high-order product formulae. Essential for this low complexity is the use of a technique similar to the fast multipole method for computing the Coulomb operator with O(eta) complexity for a simulation with eta particles. We show how to modify this algorithm so that it can be implemented on a quantum computer. We ultimately demonstrate an approach with t(eta^{4/3} N^{1/3} + eta^{1/3} N^{2/3})(eta Nt/epsilon)^o(1) gate complexity, where N is the number of grid points, epsilon is target precision, and t is the duration of time evolution. This is roughly a speedup by O(eta) over most prior algorithms. We provide lower complexity than all prior work for N<eta^7 (the regime of practical interest), with only first-quantised interaction-picture simulations providing better performance for N>eta^7. As with the classical fast multipole method, large numbers eta>10^3 would be needed to realise this advantage.

We prove a nontrivial circuit-depth lower bound for preparing a low-energy state of a locally interacting quantum many-body system in two dimensions, assuming the circuit is geometrically local. For preparing any state which has an energy density of at most ε with respect to Kitaev's toric code Hamiltonian on a two dimensional lattice Λ, we prove a lower bound of Ømegałeft(minłeft(1/epsilon^frac1-alpha2, sqrtabsŁambdaright)right) for any alpha >0. We discuss two implications. First, our bound implies that the lowest energy density obtainable from a large class of existing variational circuits (e.g., Hamiltonian variational ansatz) cannot, in general, decay exponentially with the circuit depth. Second, if long-range entanglement is present in the ground state, this can lead to a nontrivial circuit-depth lower bound even at nonzero energy density. Unlike previous approaches to prove circuit-depth lower bounds for preparing low energy states, our proof technique does not rely on the ground state to be degenerate.

Due to Csiszar and Koerner, the capacity of classical wiretap channels has a single-letter characterization in terms of the private information. For quantum wiretap channels, however, it is known that regularization of the private information is necessary to reach the capacity. Here, we study hybrid classical-quantum wiretap channels in order to resolve to what extent quantum effects are needed to witness non-additivity phenomena in quantum Shannon theory. For wiretap channels with quantum inputs but classical outputs, we prove that the characterization of the capacity in terms of the private information stays single-letter. Hence, entangled input states are of no asymptotic advantage in this setting. For wiretap channels with classical inputs, we show by means of explicit examples that the private information already becomes non-additive when either one of the two receivers becomes quantum (with the other receiver staying classical). This gives non-additivity examples that are not caused by entanglement and illustrates that quantum adversaries are strictly different from classical adversaries in the wiretap model.