The power and limitations of restricted quantum learning models

Schatzki, Louis

Permalink

https://hdl.handle.net/2142/132454 Copy

Description

Title

The power and limitations of restricted quantum learning models

Author(s)

Schatzki, Louis

Issue Date

2025-08-25

Director of Research (if dissertation) or Advisor (if thesis)

Chitambar, Eric

Doctoral Committee Chair(s)

Leditzky, Felix

Committee Member(s)

• Milenkovic, Olgica
• Arunachalam, Srinivasan

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Quantum Information Theory
• Learning Theory
• Entanglement Theory

Language

eng

Abstract

Quantum technologies have rapidly advanced over the past decade or so. However, noise and decoherence are still challenges. At the same time, quantum learning theory has quickly grown and many techniques have been developed with applications in verifying and benchmarking quantum devices. However, known generic but optimal protocols may require entangled measurements across many copies of a state, rendering experimental implementations rather difficult. With this mind, it is interesting to ask what learning tasks can and cannot be achieved with limited models of measurements, a question which has received much attention in recent years. In this thesis we answer several questions in this vein. First, we consider entangled versus separable measurements for exactly learning a function c ∈ C from a quantum example state |c⟩. We show that, if T copies suffice to learn f using entangled measurements, O(n^2) copies suffice to learn f using only separable measurements. Second, we study the Quantum Statistical Query model. We exhibit a concept class C based of degree-2 functions with an exponential separation between QSQ learning and quantum learning with entangled measurements (even in the presence of noise). This proves the “quantum analogue” of the seminal result of Blum, Kalai, & Wasserman. [1] that separates classical SQ learning from classical PAC learning with classification noise. To obtain these bounds, we introduce a quantum statistical query dimension (QSD). We prove superpolynomial QSQ lower bounds for testing purity of quantum states, reconstructing a state via shadow tomography, learning coset states for the Abelian hidden subgroup problem, approximating degree-2 functions, finding planted bi-cliques, and learning the output states of Clifford circuits of depth polylog(n). We also show that an extension of QSD characterizes the complexity of general search problems. Lastly, we give an unconditional separation between weak and strong error mitigation and prove lower bounds for learning distributions in the QSQ model. Prior works by Quek et al. [2], Hinsche et al. [3], and Nietner et al. [4] proved analogous results assuming diagonal measurements and our work removes this assumption. Next, we consider the fundamental task of distributed inner product estimation when allowed limited communication. Suppose Alice and Bob are given k copies of an unknown n-qubit quantum state |ψ⟩ and |ϕ⟩ respectively. They are allowed to send q qubits to one another with the goal of estimating |⟨ψ|ϕ⟩|^2 up to constant additive error. We show that k = Θ(√(2^(n−q)) copies are essentially necessary and sufficient for this task (extending the work of Anshu, Landau and Liu (STOC’22) who considered the case when q = 0). Additionally, we also consider the task when the goal of the players is to estimate |⟨ψ|M|ϕ⟩|^2, for arbitrary Hermitian M. For this task we show that certain norms on M determine the sample complexity of estimating |⟨ψ|M|ϕ⟩|^2 when using only classical communication. Returning to separable vs entangled measurements, we make progress on proving a hierarchy of copy complexity separations. To that end, we prove that estimating Tr[ρ^k], for k a constant, requires Ω(log d) samples with (k − 1)-copy measurements. By contrast, O(1) samples suffice with k-copy measurements. To obtain our bounds, we extend Harrow’s [5] method of PPT constraints on sums of permutations. Lastly, we consider measuring the entanglement in multipartite systems using two-copy measurements, in particular the SWAP test. Multipartite entanglement is one of the hallmarks of quantum mechanics and is central to quantum information processing. We show that the concentratable entanglement (CE), an operationally motivated measure from SWAP tests, induces a hierarchy upon pure states from which different entanglement structures can be experimentally certified. In particular, we find that nearly all genuine multipartite entangled states can be verified through the CE. Interestingly, GHZ states prove to be far from maximally entangled according to this measure. Instead we find the exact maximal value and corresponding states for up to 18 qubits and show that these correspond to extremal quantum error correcting codes. The latter allows us to unravel a deep connection between CE and coding theory. Finally, our results also offer an alternative proof, on up to 31 qubits, that absolutely maximally entangled states do not exist.

Graduation Semester

2025-12

Type of Resource

Thesis

Handle URL

https://hdl.handle.net/2142/132454

Copyright and License Information

Copyright 2025 Louis Schatzki

Owning Collections