Dorit Aharonov

Abstract Can quantum computational tools enhance the precision and efficiency of physical experiments? Promising examples are known, but a systematic treatment and comprehensive framework are missing. We introduce Quantum Algorithmic Measurements (QUALMs) to enable the study of quantum measurements and experiments from the perspective of computational complexity and communication complexity. The measurement process is described, in its utmost generality, by a many-round quantum interaction protocol between the experimental system and a full-fledged quantum computer. The QUALM complexity is quantified by the number of elementary operations performed by the quantum computer, including its coupling to the experimental system. We study how the QUALM complexity depends on the type of allowed access the quantum computer has to the experimental system: local-local, incoherent, coherent, adaptive, etc. We provide the first example of a measurement "task" for which the coherent QUALM complexity is exponentially better than the incoherent one, even if the latter is adaptive; this implies that using entanglement between different systems in experiments may lead to exponential savings in resources. We extend our results to derive a similar exponential advantage for a physically motivated measurement task which determines the symmetry class of the time evolution operator for a quantum many-body system. Many open questions are raised towards better understanding how quantum computational tools can be applied in experimental physics. A major question is whether an exponential advantage in QUALM complexity can be achieved in the NISQ era; an equally important one is to design new, efficient quantum algorithmic measurements based on our framework, perhaps relying on ideas from quantum algorithms.

Abstract A universal family of Hamiltonians can be used to simulate any local Hamiltonian by encoding its full spectrum as the low-energy subspace of a Hamiltonian from the family. Many spin-lattice model Hamiltonians---such as Heisenberg or XY interaction on the 2D square lattice---are known to be universal. However, the known encodings can be very inefficient, requiring interaction strengths that scales exponentially with system size if the original Hamiltonian have complex, possibly all-to-all connectivity. In this work, we provide an efficient construction by which these universal families are in fact ``strongly'' universal; this means that the required interaction strengths as well as all other resources scale polynomially, regardless of the connectivity of the original Hamiltonian. This exponential improvement over previous constructions based on perturbative gadgets is achieved by combining the tools of quantum phase-estimation algorithm and circuit-to-Hamiltonian transformation in a non-perturbative way that only incurs polynomial overhead. Furthermore, we show that 1D Hamiltonians with nearest-neighbor interaction of 8-dimensional particles on a line are also strongly universal Hamiltonian simulators. Our results demonstrate that analog quantum simulation of general Hamiltonians can be made efficient for all target local Hamiltonians; this has potential application for future quantum technologies.

I will describe a classical randomized simulation of noisy quantum Turing machines and noisy quantum circuits. It is shown that for quantum Turing machine with any non-zero amount of noise, the simulation is efficient. Hence noisy quantum Turing machines have no computational advantage over classical computers.