Quantum Information

We consider the optimization problem (ground energy search) for fermionic Hamiltonians with classical interactions. This QMA-hard problem is motivated by the Coulomb electron-electron interaction being diagonal in the position basis, a fundamental fact that underpins electronic-structure Hamiltonians in quantum chemistry and condensed matter. We prove that fermionic Gaussian states achieve an approximation ratio of at least 1/3 for such Hamiltonians, independent of sparsity. This shows that classical interactions are sufficient to prevent the vanishing Gaussian approximation ratio observed in SYK-type models. We also give efficient semi-definite programming algorithms for Gaussian approximations to several families of traceless and positive-semidefinite classically interacting Hamiltonians, with the ability to enforce a fixed particle number. The technical core of our results is the concept of a Gaussian blend, a construction for Gaussian states via mixtures of covariance matrices.

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.