Hamiltonian Property Testing

Quantum, vol. 10, pp. 1979

Abstract

Locality is a fundamental feature of many physical time evolutions. Assumptions on locality and related structural properties also underlie recently proposed procedures for learning an unknown Hamiltonian from access to the induced time evolution. However, no protocols to rigorously test whether an unknown Hamiltonian is local were known. We investigate Hamiltonian locality testing as a property testing problem, where the task is to determine whether an unknown n -qubit Hamiltonian H is k -local or ε -far from all k -local Hamiltonians, given access to the time evolution along H . First, we emphasize the importance of the chosen distance measure: With respect to the operator norm, a worst-case distance measure, incoherent quantum locality testers require Ω ~ ( 2 n ) many time evolution queries and an expected total evolution time of Ω ~ ( 2 n / ε ) , and even coherent testers need Ω ( 2 n / 2 ) many queries and Ω ( 2 n / 2 / ε ) total evolution time. In contrast, when distances are measured according to the normalized Frobenius norm, corresponding to an average-case distance, we give a sample-, time-, and computationally efficient incoherent Hamiltonian locality testing algorithm based on randomized measurements. In fact, our procedure can be used to simultaneously test a wide class of Hamiltonian properties beyond locality. Finally, we prove that learning a general Hamiltonian remains exponentially hard with this average-case distance, thereby establishing an exponential separation between Hamiltonian testing and learning. Our work initiates the study of property testing for quantum Hamiltonians, demonstrating that a broad class of Hamiltonian properties is efficiently testable even with limited quantum capabilities, and positioning Hamiltonian testing as an independent area of research alongside Hamiltonian learning.

Authors 3

1. Andreas Blühm

   Centre National de la Recherche Scientifique · Institut polytechnique de Grenoble · Laboratoire d'Informatique de Grenoble

   Affiliation as printed

   Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG, 38000 Grenoble, France

   CAPP - Calculs algorithmes programmes et preuves (Laboratoire LIG - Bâtiment IMAG - 700 avenue Centrale, CS 40700 - 38058 Grenoble cedex 9 - France)

2. Matthias C. Caro

   University of Warwick · Freie Universität Berlin

   Affiliation as printed

   Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, Berlin, Germany

   Department of Computer Science, University of Warwick, Coventry, UK

   Freie Universität Berlin (Kaiserswerther Str. 16-18, 14195 Berlin - Germany)

3. Aadil Oufkir Aachen Institute for Quantum Information

   RWTH Aachen University · Lyon 1 Université · Institut national de recherche en sciences et technologies du numérique · École Normale Supérieure de Lyon · Université Mohammed VI Polytechnique · Laboratoire de l'Informatique du Parallélisme

   Affiliation as printed

   Institute for Quantum Information, RWTH Aachen University, Aachen, Germany

   Mohammed VI Polytechnic University, Rocade Rabat-Salé, Technopolis, Morocco

   Univ Lyon, Inria, ENS Lyon, UCBL, LIP, Lyon, France

   ENS de Lyon - École normale supérieure de Lyon (15 parvis René Descartes - BP 7000 - 69342 Lyon Cedex 07 - France)

   RWTH - Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH Aachen Templergraben 55 52062 Aachen (Hausanschrift) 52056 Aachen (Postanschrift) - Germany)