Quantum Information

We give the first instance-optimal sample complexity bounds for shadow tomography using few-copy measurements in the high-precision regime. More concretely, we study the problem of learning expectation values of a given set of observables of an unknown quantum state to precision $\epsilon$ in $L_p$-norm, using (possibly adaptive) measurements that act on one or a few copies at a time, and we are interested in the regime that $\epsilon$ is below some concrete and potentially dimension-dependent threshold. In this setup, we prove the necessary and sufficient number of copies, for any given set of observables, is characterized by a simple optimization formula involving a quadratic form of the inverse Fisher information matrix up to a logarithmic factor. Our results establish a rigorous correspondence between quantum learning and quantum metrology. 

I will discuss some surprising examples of quantum circuits that can be realized in constant T-depth. Some of these constructions, such as single-qubit rotation and its programmable variants, as well as  quantum part of Shor's factoring algorithm, require a catalyst state. But there are also other constructions that do not, such as reversible encoded addition.

The Generalized Quantum Stein's Lemma is a theorem in quantum hypothesis testing that provides an operational meaning to the relative entropy within the context of quantum resource theories. Its original proof was found to have a gap, which led to a search for a corrected proof. We formalize the proof presented in [Hayashi and Yamasaki (2024)] in the Lean interactive theorem prover. This is the most technically demanding theorem in physics with a computer-verified proof to date, building with a variety of intermediate results from topology, analysis, and operator algebra. In the process, we rectified minor imprecisions in [HY24]'s proof that formalization forces us to confront, and refine a more precise definition of quantum resource theory. Formalizing this theorem has ensured that our Lean-QuantumInfo library, which otherwise has begun to encompass a variety of topics from quantum information, includes a robust foundation suitable for a larger collaborative program of formalizing quantum theory more broadly.

Decoded Quantum Interferometry (DQI) has been recently proposed as a new quantum algorithm for optimization. Hamiltonian Decoded Quantum Interferometry (HDQI), an extension of DQI, adapts this paradigm to Hamiltonian optimization and Gibbs state preparation. In this work, I will introduce HDQI for general Pauli Hamiltonians and discuss its application to the approximation of Gibbs states.

Non-local quantum computation studies the complexity of implementing quantum channels non-locally and has fascinating connections to cryptography, complexity theory and quantum gravity. In this talk, I will survey some of these connections, with an emphasis on circuit and communication complexity. Building on ideas, I will present new lower bounds on the magic cost of quantum gates, quantum speedups in communication, and approaches to position verification with privacy guarantees.

As a class of generative artificial intelligence frameworks inspired by statistical physics, diffusion models have shown extraordinary performance in synthesizing complicated data distributions through a denoising process gradually guided by score functions. Real-life data, like images, is often spatially structured in low-dimensional spaces. However, ordinary diffusion models ignore this local structure and learn spatially global score functions, which are often computationally expensive. In this work, motivated by recent advances in statistical physics, we develop a generic framework for defining phases of data distributions and use it to analyze the locality requirements of denoisers in diffusion models. We define two distributions as belonging to the same data distribution phase if they can be mutually connected via spatially local operations such as local denoisers. We demonstrate that the reverse denoising process consists of an early trivial phase and a late data phase, sandwiching a rapid phase transition where local denoisers must fail. We further demonstrate that the performance of local denoisers is closely tied to spatial Markovianity, which provides an operational criterion for diagnosing such phase transitions. We validate this criterion through numerical experiments on real-world datasets. Our work suggests guidance for simpler and more efficient architectures of diffusion models: far from the phase transition point, we can use small local neural networks to compute the score function; global neural networks are only necessary around the narrow time interval of phase transitions. This result also opens up new directions for studying phases of data distributions, the broader science of generative artificial intelligence, and guiding the design of neural networks inspired by physics concepts.