Matthias C. Caro

We study the problems of certifying and learning local quantum Hamiltonians and their associated Gibbs states. We first address Hamiltonian certification given real-time access to the dynamics of an unknown k-local Hamiltonian. Given oracle access to its time-evolution operator and a fully specified target Hamiltonian, the task is to decide whether the two Hamiltonians are identical or differ by at least a prescribed accuracy in normalized Frobenius norm, while minimizing the total evolution time. We introduce the first certification protocol that achieves optimal performance for all constant-locality Hamiltonians. For general n-qubit, k-local, traceless Hamiltonians, our algorithm succeeds with high probability using total evolution time that scales inversely with the target accuracy, and for constant locality this matches the fundamental lower bound, achieving Heisenberg-limit scaling. In contrast to prior approaches, our method requires neither inverse evolution nor controlled operations, and relies only on forward real-time dynamics. We then turn to thermal states generated by local Hamiltonians. We develop algorithms for both learning and certifying Gibbs states that are fully sample-efficient in all relevant parameters. For polynomially bounded temperature, our methods achieve exponential improvements over general quantum state tomography. While the learning algorithm is inherently time-inefficient due to covering arguments, the certification algorithm is both sample- and time-efficient, resolving a previously open question on efficient Gibbs state testing. Together, these results establish optimal or near-optimal complexity bounds for characterizing local quantum systems in both dynamical and thermal regimes.

The impossibility of simultaneously cloning non-orthogonal states lies at the foundations of quantum theory. Even when allowing for approximation errors, cloning an arbitrary unknown pure state requires as many initial copies as needed to fully learn the state. Rather than arbitrary unknown states, modern quantum learning theory often considers structured classes of states and exploits such structure to develop learning algorithms that outperform general-state tomography. This raises the question: How do the sample complexities of learning and cloning relate for such structured classes? We answer this question an important class of states. Namely, for $n$-qubit stabilizer states, we show that the optimal sample complexity of cloning is $\Theta(n)$. Thus, also for this structured class of states, cloning is as hard as learning. To prove these results, we use representation-theoretic tools in the recently proposed Abelian State Hidden Subgroup framework and a new structured version of the recently introduced random purification channel to relate stabilizer state cloning to a variant of the sample amplification problem for probability distributions that was recently introduced in classical learning theory. This allows us to obtain our cloning lower bounds by proving new sample amplification lower bounds for classes of distributions with an underlying linear structure. Our results provide a more fine-grained perspective on No-Cloning theorems, opening up connections from foundations to quantum learning theory and quantum cryptography.

Quantum data access and quantum processing can make certain classically intractable learning tasks feasible. However, quantum capabilities will only be available to a select few in the near future. Thus, reliable schemes that allow classical clients to delegate learning to untrusted quantum servers are required to facilitate widespread access to quantum learning advantages. Building on a recently introduced framework of interactive proof systems for classical machine learning by Goldwasser et al. (ITCS 2021), we develop a framework for classical verification of quantum learning. We exhibit learning problems that a classical learner cannot efficiently solve on their own, but that they can efficiently and reliably solve when interacting with an untrusted quantum prover. Concretely, we consider the problems of agnostic learning parities and Fourier-sparse functions with respect to distributions with uniform input marginal. We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples, based on which we give efficient quantum learning algorithms for these tasks. Moreover, we prove that agnostic quantum parity and Fourier-sparse learning can be efficiently verified by a classical verifier with only random example or statistical query access. Finally, we showcase two general scenarios in learning and verification in which quantum mixture-of-superpositions examples do not lead to sample complexity improvements over classical data. Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents through interaction with untrusted quantum entities.

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 in fact local were known. We investigate Hamiltonian locality testing as a property testing problem, where the task is to determine whether an unknown Hamiltonian H is k-local or epsilon-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 at least order 2^n many time evolution queries and an expected total evolution time of order 2^n/epsilon, and even coherent testers need at least order 2^(n/2) many queries and order 2^(n/2)/epsilon 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.

In this work, we prove uniform continuity bounds for entropic quantities related to the sandwiched Rényi divergences such as the sandwiched Rényi conditional entropy. We follow three different approaches: The first one is the axiomatic approach, which exploits the sub-/ superadditivity and joint concavity/ convexity of the exponential of the divergence. In our second approach, termed the "operator space approach", we express the entropic measures as norms and utilize their properties for establishing the bounds. These norms draw inspiration from interpolation space norms. We not only demonstrate the norm properties solely relying on matrix analysis tools but also extend their applicability to a context that holds relevance in resource theories. By this, we extend the strategies of Marwah and Dupuis as well as Beigi and Goodarzi employed in the sandwiched Rényi conditional entropy context. Finally, we merge the approaches into a mixed approach that has some advantageous properties and then discuss in which regimes each bound performs best. Our results improve over the previous best continuity bounds or sometimes even give the first continuity bounds available. In a separate contribution, we use the ALAAF method, developed in a previous article by some of the authors, to study the stability of approximate quantum Markov chains.

Learning tasks play an increasingly prominent role in quantum information and computation. They range from fundamental problems such as state discrimination and metrology over the framework of quantum probably approximately correct (PAC) learning, to the recently proposed shadow variants of state tomography. However, the many directions of quantum learning theory have so far evolved separately. We propose a general mathematical formalism for describing quantum learning by training on classical-quantum data and then testing how well the learned hypothesis generalizes to new data. In this framework, we prove bounds on the expected generalization error of a quantum learner in terms of classical and quantum mutual information quantities measuring how strongly the learner's hypothesis depends on the specific data seen during training. To achieve this, we use tools from quantum optimal transport and quantum concentration inequalities to establish non-commutative versions of decoupling lemmas that underlie recent information-theoretic generalization bounds for classical machine learning. Our framework encompasses and gives intuitively accessible generalization bounds for a variety of quantum learning scenarios such as quantum state discrimination, PAC learning quantum states, quantum parameter estimation, and quantumly PAC learning classical functions. Thereby, our work lays a foundation for a unifying quantum information-theoretic perspective on quantum learning.

Generalization bounds are a critical tool to assess the training data requirements of Quantum Machine Learning (QML). In this work, we prove the first out-of-distribution generalization guarantees in QML, where we require a trained model to perform well even on testing data drawn from a distribution different from the training data distribution. Namely, we establish out-of-distribution generalization for the task of learning an unknown unitary using a quantum neural network and for a broad class of training and testing distributions. In particular, we show that one can learn the action of a unitary on entangled states using only product state training data. Since product states can be prepared using only single-qubit gates, this advances the near-term prospects of QML for learning quantum dynamics, and further opens up new methods for both the classical and quantum compilation of quantum circuits. Based on these insights, we propose a QML-based algorithm for simulating quantum dynamics on near-term quantum hardware and rigorously prove its resource-efficiency in terms of qubit and training data requirements. We also demonstrate the viability of this algorithm through numerical experiments, both in classical simulations and on quantum hardware. Finally, we embed this algorithm in a broader framework for using QML methods for quantum dynamical simulation on NISQ devices.

Quantum learning from remotely accessed and a priori unknown quantum data must address two key challenges: verifying the correctness of data and ensuring the privacy of the learner’s data-collection strategies and resulting conclusions. The covert (verifiable) learning model of Canetti and Karchmer (TCC 2021) provides a framework for endowing classical learning algorithms with such guarantees, protecting against computationally bounded adversaries who observe and tamper with public oracle queries. However, their framework has two drawbacks: it relies on computational hardness assumptions and does not flexibly accommodate richer data-access models, such as quantum ones. In this work, we propose models of covert verifiable learning in quantum learning theory and realize them without computational hardness assumptions for remote data access scenarios motivated by established quantum data advantages. We consider two privacy notions: (i) strategy-covertness, where the eavesdropper does not gain information about the learner's strategy; and (ii) target-covertness, where the eavesdropper does not gain information about the unknown object being learned. We show: - Strategy-covert algorithms for making quantum statistical queries via classical shadows; - Target-covert algorithms for: - learning quadratic functions from public quantum examples and private quantum statistical queries; - Pauli shadow tomography and stabilizer state learning from public multi-copy and private single-copy quantum measurements; - solving Forrelation and Simon's problem from public quantum queries and private classical queries, where the adversary is an i.i.d. ancilla-free eavesdropper. The lattermost results in particular establish that the exponential separation between classical and quantum queries for Forrelation and Simon’s problem survives under covertness constraints. Along the way, we design covert verifiable protocols for quantum data acquisition from public quantum queries which may be of independent interest. Overall, our models and corresponding algorithms demonstrate that quantum advantages are privately and verifiably achievable even with untrusted, remote data.