publications

We study the problem of learning an unknown quantum many-body Hamiltonian H from black-box queries to its time evolution e^-\mathrmi H t. Prior proposals for solving this task either impose some assumptions on H, such as its interaction structure or locality, or otherwise use an exponential amount of computational postprocessing. In this paper, we present algorithms to learn any n-qubit Hamiltonian, which do not need to know the Hamiltonian terms in advance, nor are they restricted to local interactions. Our algorithms are efficient as long as the number of terms m is polynomially bounded in the system size n. We consider two models of control over the time evolution: the first has access to time reversal (t < 0), enabling an algorithm that outputs an ε-accurate classical description of H after querying its dynamics for a total of \widetilde\mathcalO(m/ε) evolution time. The second access model is more conventional, allowing only forward-time evolutions; our algorithm requires \widetilde\mathcalO(\|H\|^3/ε^4) evolution time in this setting. Central to our results is the recently introduced concept of a pseudo-Choi state of H. We extend the utility of this learning resource by showing how to use it to learn the Fourier spectrum of H, how to achieve nearly Heisenberg-limited scaling with it, and how to prepare it even under our more restricted access models.

Fermions are fundamental particles which obey seemingly bizarre quantum-mechanical principles, yet constitute all the ordinary matter that we inhabit. As such, their study is heavily motivated from both fundamental and practical incentives. In this dissertation, we will explore how the tools of quantum information and computation can assist us on both of these fronts. We primarily do so through the task of partial state learning: tomographic protocols for acquiring a reduced, but sufficient, classical description of a quantum system. Developing fast methods for partial tomography addresses a critical bottleneck in quantum simulation algorithms, which is a particularly pressing issue for currently available, imperfect quantum machines. At the same time, in the search for such protocols, we also refine our notion of what it means to learn quantum states. One important example is the ability to articulate, from a computational perspective, how the learning of fermions contrasts with other types of particles.
The main results of this dissertation are as follows. First, we introduce a protocol called fermionic classical shadows that efficiently learns all local properties of a many-fermion system. We furthermore show that this protocol is optimal, in the sense that information-theoretic arguments imply matching lower bounds for the fundamental complexity of this learning task. Next, we extend the theory to a noise-robust formulation called symmetry-adjusted classical shadows, which uses symmetry in the quantum system to mitigate errors that occur during the quantum computation. We establish a rigorous theory for this protocol, as well as demonstrate realistic, near-term performance with comprehensive numerical experiments. We then study unitary partitioning, an alternative strategy for easing the measurement complexity of Hamiltonians for interacting electrons. Finally, we draw surprising connections between a hard classical optimization problem, known as the noncommutative Grothendieck problem, and the simulation of fermions. We establish a natural embedding of the classical problem into a fermionic one and provide both theoretical and numerical evidence that quantum computers can provide high-quality solutions over classical approximations through this embedding.

Estimating expectation values is a key subroutine in quantum algorithms. Near-term implementations face two major challenges: a limited number of samples required to learn a large collection of observables, and the accumulation of errors in devices without quantum error correction. To address these challenges simultaneously, we develop a quantum error-mitigation strategy called symmetry-adjusted classical shadows, by adjusting classical-shadow tomography according to how symmetries are corrupted by device errors. As a concrete example, we highlight global \mathrmU(1) symmetry, which manifests in fermions as particle number and in spins as total magnetization, and illustrate their group-theoretic unification with respective classical-shadow protocols. We establish rigorous sampling bounds under readout errors obeying minimal assumptions, and perform numerical experiments with a more comprehensive model of gate-level errors derived from existing quantum processors. Our results reveal symmetry-adjusted classical shadows as a low-cost strategy to mitigate errors from noisy quantum experiments in the ubiquitous presence of symmetry.

Quadratic programming over orthogonal matrices encompasses a broad class of hard optimization problems that do not have an efficient quantum representation. Such problems are instances of the little noncommutative Grothendieck problem (LNCG), a generalization of binary quadratic programs to continuous, noncommutative variables. In this work, we establish a natural embedding for this class of LNCG problems onto a fermionic Hamiltonian, thereby enabling the study of this classical problem with the tools of quantum information. This embedding is accomplished by a new representation of orthogonal matrices as fermionic quantum states, which we achieve through the well-known double covering of the orthogonal group. Correspondingly, the embedded LNCG Hamiltonian is a two-body fermion model. Determining extremal states of this Hamiltonian provides an outer approximation to the original problem, a quantum analogue to classical semidefinite relaxations. In particular, when optimizing over the special orthogonal group our quantum relaxation obeys additional, powerful constraints based on the convex hull of rotation matrices. The classical size of this convex-hull representation is exponential in matrix dimension, whereas our quantum representation requires only a linear number of qubits. Finally, to project the relaxed solution back into the feasible space, we propose rounding procedures which return orthogonal matrices from appropriate measurements of the quantum state. Through numerical experiments we provide evidence that this rounded quantum relaxation can produce high-quality approximations.

Quantum algorithms for simulating electronic ground states are slower than popular classical mean-field algorithms such as Hartree–Fock and density functional theory but offer higher accuracy. Accordingly, quantum computers have been predominantly regarded as competitors to only the most accurate and costly classical methods for treating electron correlation. However, here we tighten bounds showing that certain first-quantized quantum algorithms enable exact time evolution of electronic systems with exponentially less space and polynomially fewer operations in basis set size than conventional real-time time-dependent Hartree–Fock and density functional theory. Although the need to sample observables in the quantum algorithm reduces the speedup, we show that one can estimate all elements of the k-particle reduced density matrix with a number of samples scaling only polylogarithmically in basis set size. We also introduce a more efficient quantum algorithm for first-quantized mean-field state preparation that is likely cheaper than the cost of time evolution. We conclude that quantum speedup is most pronounced for finite-temperature simulations and suggest several practically important electron dynamics problems with potential quantum advantage.

We propose a set of Bell-type nonlocal games that can be used to prove an unconditional quantum advantage in an objective and hardware-agnostic manner. In these games, the circuit depth needed to prepare a cyclic cluster state and measure a subset of its Pauli stabilizers on a quantum computer is compared to that of classical Boolean circuits with the same, nearest-neighboring gate connectivity. Using a circuit-based trapped-ion quantum computer, we prepare and measure a six-qubit cyclic cluster state with an overall fidelity of 60.6% and 66.4%, before and after correcting for measurement-readout errors, respectively. Our experimental results indicate that while this fidelity readily passes conventional (or depth-0) Bell bounds for local hidden-variable models, it is on the cusp of demonstrating a higher probability of success than what is possible by depth-1 classical circuits. Our games offer a practical and scalable set of quantitative benchmarks for quantum computers in the pre-fault-tolerant regime as the number of qubits available increases.

We propose a tomographic protocol for estimating any k-body reduced density matrix (k-RDM) of an n-mode fermionic state, a ubiquitous step in near-term quantum algorithms for simulating many-body physics, chemistry, and materials. Our approach extends the framework of classical shadows, a randomized approach to learning a collection of quantum-state properties, to the fermionic setting. Our sampling protocol uses randomized measurement settings generated by a discrete group of fermionic Gaussian unitaries, implementable with linear-depth circuits. We prove that estimating all k-RDM elements to additive precision \varepsilon requires on the order of \binomnk k^3/2 \log(n) / \varepsilon^2 repeated state preparations, which is optimal up to the logarithmic factor. Furthermore, numerical calculations show that our protocol offers a substantial improvement in constant overheads for k ≥2, as compared to prior deterministic strategies. We also adapt our method to particle-number symmetry, wherein the additional circuit depth may be halved at the cost of roughly 2–5 times more repetitions.

Variational quantum algorithms are promising applications of noisy intermediate-scale quantum (NISQ) computers. These algorithms consist of a number of separate prepare-and-measure experiments that estimate terms in a Hamiltonian. The number of terms can become overwhelmingly large for problems at the scale of NISQ hardware that may soon be available. We use unitary partitioning (developed independently by Izmaylov et al. [J. Chem. Theory Comput. 16, 190 (2020)]) to define variational quantum eigensolver procedures in which additional unitary operations are appended to the ansatz preparation to reduce the number of terms. This approach may be scaled to use all coherent resources available after ansatz preparation. We also study the use of asymmetric qubitization to implement the additional coherent operations with lower circuit depth. Using this technique, we find a constant factor speedup for lattice and random Pauli Hamiltonians. For electronic structure Hamiltonians, we prove that linear term reduction with respect to the number of orbitals, which has been previously observed in numerical studies, is always achievable. For systems represented on 10–30 qubits, we find that there is a reduction in the number of terms by approximately an order of magnitude. Applied to the plane-wave dual-basis representation of fermionic Hamiltonians, however, unitary partitioning offers only a constant factor reduction. Finally, we show that noncontextual Hamiltonians may be reduced to effective commuting Hamiltonians using unitary partitioning.