Pulkit Sinha

We study the problem of learning Hamiltonians H that are s-sparse in the Pauli basis, given access to their time-evolution operators. Although Hamiltonian learning has been extensively investigated, two issues recur in much of the existing literature: the absence of lower bounds establishing optimality and the use of mathematically convenient but physically opaque error measures. We address both challenges by introducing two physically motivated notions of distance between Hamiltonians and designing a nearly optimal algorithm with respect to one of these metrics. The first, the time-constrained distance, quantifies distinguishability through dynamical evolution up to a bounded time. The second, the temperature-constrained distance, captures distinguishability through thermal states at bounded inverse temperatures. We show that s-sparse Hamiltonians with bounded operator norm can be learned under both distances using only $O(s log(1/ε))$ experiments and $O(s^2/ε)$ total evolution time. For the time-constrained distance, we further establish lower bounds of $Ω((s/n) log(1/ε) + s)$ experiments and $Ω(√s/ε)$ total evolution time, demonstrating near-optimality in the number of experiments. As an intermediate result, we obtain an algorithm that learns every Pauli coefficient of s-sparse Hamiltonians up to error ε in $O(s log(1/ε))$ experiments and $O(s/ε)$ total evolution time, improving upon several recent results. The source of this improvement is a new isolation technique, inspired by the Valiant-Vazirani theorem (STOC’85), which shows that NP is as easy as detecting unique solutions. This isolation technique allows us to query the time evolution of a single Pauli coefficient of a sparse Hamiltonian—even when the Pauli support of the Hamiltonian is unknown—ultimately enabling us to recover the Pauli support itself.

Security proofs for quantum key distribution (QKD) based on the entropic uncertainty relations and the phase-error approach have the advantage of producing some of the tightest key rates against coherent attacks. We prove the security of QKD using the entropic uncertainty relations, for scenarios where Eve is allowed full control of the detection efficiency and dark rates of all detectors within some specified ranges. Thus, our work solves the practically important problem of detector side channels. Our work also removes the requirement of ``basis-independent loss'' required by these proof techniques. Thus, we render these proof techniques applicable to practical QKD scenarios. Furthermore, we prove security for variable-length QKD protocols, which do not require Alice and Bob to characterize the honest behaviour of the channel.

A basic question in the PAC model of learning is whether proper learning is harder than improper learning. In the classical case, there are examples of concept classes with VC dimension d that have sample complexity Ω(d/ϵ log(1/ϵ)) for proper learning with error ϵ, while the complexity for improper learning is O(d/ϵ). One such example arises from the Coupon Collector problem. Motivated by the efficiency of proper versus improper learning with quantum samples, Arunachalam, Belovs, Childs, Kothari, Rosmanis, and de Wolf (TQC 2020) studied an analogue, the Quantum Coupon Collector problem. Curiously, they discovered that for learning size k subsets of [n] the problem has sample complexity Θ(k log mink,n−k+1), in contrast with the complexity of Θ(k log k) for Coupon Collector. This effectively negates the possibility of a separation between the two modes of learning via the quantum problem, and Arunachalam et al. posed the possibility of such a separation as an open question. In this work, we first present an algorithm for the Quantum Coupon Collector problem with sample complexity that matches the sharper lower bound of (1−o_k(1))k ln mink,n−k+1 shown recently by Bab Hadiashar, Nayak, and Sinha (IEEE TIT 2024), for the entire range of the parameter k. Next, we devise a variant of the problem, the Quantum Padded Coupon Collector. We prove that its sample complexity matches that of the classical Coupon Collector problem for both modes of learning, thereby exhibiting the same asymptotic separation between proper and improper quantum learning as mentioned above. The techniques we develop in the process can be directly applied to any form of padded quantum data. We hope that padding can more generally lift other forms of classical learning behaviour to the quantum setting.

Although a concept class may be learnt more efficiently using quantum samples as compared with classical samples in certain scenarios, Arunachalam and de Wolf (JMLR, 2018) proved that quantum learners are asymptotically no more efficient than classical ones in the quantum PAC and Agnostic learning models. They established lower bounds on sample complexity via quantum state identification and Fourier analysis. In this paper, we derive optimal lower bounds for quantum sample complexity in both the PAC and agnostic models via an information-theoretic approach. The proofs are arguably simpler, and the same ideas can potentially be used to derive optimal bounds for other problems in quantum learning theory. We then turn to a quantum analogue of the Coupon Collector problem, a classic problem from probability theory also of importance in the study of PAC learning. Arunachalam, Belovs, Childs, Kothari, Rosmanis, and de Wolf (TQC, 2020) characterized the quantum sample complexity of this problem up to constant factors. First, we show that the information-theoretic approach mentioned above provably does not yield the optimal lower bound. As a by-product, we get a natural ensemble of pure states in arbitrarily high dimensions which are not easily (simultaneously) distinguishable, while the ensemble has close to maximal Holevo information. Second, we discover that the information-theoretic approach yields an asymptotically optimal bound for an approximation variant of the problem. Finally, we derive a sharp lower bound for the Quantum Coupon Collector problem, with the exact leading order term, via the generalized Holevo-Curlander bounds on the distinguishability of an ensemble. All the aspects of the Quantum Coupon Collector problem we study rest on properties of the spectrum of the associated Gram matrix, which may be of independent interest.