Suguru Tamaki

Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics. In this Letter, we give quantum algorithms which, given any k-body Hamiltonian H, compute an estimate for the ground state energy and prepare a quantum state achieving said energy, respectively. Specifically, for any ϵ>0, our algorithms return, with high probability, an estimate of the ground state energy of H within additive error ϵM, or a quantum state with the corresponding energy. Here, M is the total strength of all interaction terms, which in general is extensive in the system size. Our approach makes no assumptions about the geometry or spatial locality of interaction terms of the input Hamiltonian and thus handles even long-range or all-to-all interactions, such as in quantum chemistry, where lattice-based techniques break down. In this fully general setting, the run-time of our algorithms scales as 2cn/2 for c<1, yielding the first quantum algorithms for low-energy estimation breaking a standard square root Grover speedup for unstructured search. The core of our approach is remarkably simple, and relies on showing that an extensive fraction of the interactions can be neglected with a controlled error. What this ultimately implies is that even arbitrary k-local Hamiltonians have structure in their low energy space, in the form of an exponential-dimensional low energy subspace. Published by the American Physical Society 2025

It is known that several sub-universal quantum computing models, such as the IQP model, the Boson sampling model, the one-clean qubit model, and the random circuit model, cannot be classically simulated in polynomial time under certain conjectures in classical complexity theory. Recently, these results have been improved to ``fine-grained" versions where even exponential-time classical simulations are excluded assuming certain classical fine-grained complexity conjectures. All these fine-grained results are, however, about the hardness of strong simulations or multiplicative-error sampling. It was open whether any fine-grained quantum supremacy result can be shown for a more realistic setup, namely, additive-error sampling. In this paper, we show the additive-error fine-grained quantum supremacy (under certain complexity assumptions). As examples, we consider the IQP model, a mixture of the IQP model and log-depth Boolean circuits, and Clifford+<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math> circuits. Similar results should hold for other sub-universal models.

A two-prover one-round game is a fundamental combinatorial optimization problem arising from such areas as interactive proof systems, hardness of approximation, cryptography and quantum mechanics. The parallel repetition theorem states that for any two-prover one-round game with value smaller than 1, k-fold parallel repetition reduces the value of the game exponentially in k. The theorem was originally proved by Raz (SICOMP 1998) and later simplified and improved by Holenstein (Theory of Computing 2009) and Rao (SICOMP 2011). All the known proofs are based on information theoretic arguments. Very recently, Dinur and Steurer (STOC 2014) obtained a new proof of the parallel repetition theorem based on a matrix analysis argument. In this paper, we describe a special case of Dinur and Steurer's proof. We also describe an application of the parallel repetition theorem to inapproximability results of two-prover one-round games. Our presentation is almost self-contained in the sense that we only assume the PCP theorem. To do so, we also present proofs for the necessary results related to algebraic graph theory and hardness of approximation.