Certifying and learning quantum Ising Hamiltonians

HAL

Abstract

In this work, we study the problems of certifying and learning quantum Ising Hamiltonians. Our main contributions are as follows: Certification of Ising Hamiltonians. We show that certifying an Ising Hamiltonian in normalized Frobenius norm via access to its time-evolution operator requires only $\widetilde O(1/\varepsilon)$ time evolution. This matches the Heisenberg-scaling lower bound of $Ω(1/\varepsilon)$ up to logarithmic factors. To our knowledge, this is the first nearly-optimal algorithm for testing a Hamiltonian property. A key ingredient in our analysis is the Bonami Lemma from Fourier analysis. Learning Ising Gibbs states. We design an algorithm for learning Ising Gibbs states in trace norm that is sample-efficient in all parameters. In contrast, previous approaches learned the underlying Hamiltonian (which implies learning the Gibbs state) but suffered from exponential sample complexity in the inverse temperature. Certification of Ising Gibbs states. We give an algorithm for certifying Ising Gibbs states in trace norm that is both sample and time-efficient, thereby solving a question posed by Anshu (Harvard Data Science Review, 2022). Finally, we extend our results on learning and certification of Gibbs states to general $k$-local Hamiltonians for any constant $k$.

Authors 4

1. Andreas Blühm

   Institut polytechnique de Grenoble · Centre National de la Recherche Scientifique · 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. Francisco Escudero Gutiérrez

   Centrum Wiskunde & Informatica

   Affiliation as printed

   Centrum Wiskunde & Informatica , CWI 1098 XG , Amsterdam , The Netherlands

   CWI - Centrum Wiskunde & Informatica (Science Park 123, 1098 XG Amsterdam - Netherlands)

3. Aadil Oufkir Aachen Institute for Quantum Information

   Laboratoire de l'Informatique du Parallélisme · QINFO: Traitement optimal de l'information avec des dispositifs quantiques · RWTH Aachen University

   Affiliation as printed

   Institute for Quantum Information RWTH Aachen University Aachen , Germany

   LIP - Laboratoire de l'Informatique du Parallélisme (46 Allée d'Italie 69364 LYON CEDEX 07 - France)

   QINFO - Traitement optimal de l'information avec des dispositifs quantiques (655 avenue de l'Europe 38334 Saint Ismier Cedex - France)

4. Cambyse Rouzé

   Télécom Paris · Institut Polytechnique de Paris · Laboratoire Traitement et Communication de l’Information · QURIOSITY: Communication et Traitement Quantiques de l'Information

   Affiliation as printed

   Inria , Télécom Paris -LTCI Institut Polytechnique de Paris 91120 Palaiseau , France

   QURIOSITY - Communications et Traitement Quantiques de l’Information (19 Place Marguerite Perey 91123 Palaiseau Cedex. Anciennement IQA, Information Quantique et Applications jusqu'en 2022-12-31 - France)