Eric R. Anschuetz

Finding the ground state of strongly-interacting fermionic systems is often the prerequisite for fully understanding both quantum chemistry and condensed matter systems. The Sachdev–Ye–Kitaev (SYK) model is a representative example of such a system; it is particularly interesting not only due to the existence of efficient quantum algorithms preparing approximations to the ground state such as Hastings–O'Donnell (STOC 2022), but also known no-go results for many classical ansatzes in preparing low-energy states. However, this quantum-classical separation is known to not persist when the SYK model is sufficiently sparsified, i.e., when terms in the model are discarded with probability 1 − p , where p = Θ ( 1 / n 3 ) and n is the system size. This raises the question of how robust the quantum and classical complexities of the SYK model are to sparsification.In this work we initiate the study of the sparse SYK model where p ∈ [ Θ ( 1 / n 3 ) , 1 ] and show there indeed exists a certain robustness of sparsification. We prove that with high probability, Gaussian states achieve only a Θ ( 1 / n ) -factor approximation to the true ground state energy of sparse SYK for all p ≥ Ω ( log ⁡ n / n 2 ) , and that Gaussian states cannot achieve constant-factor approximations unless p ≤ O ( log 2 ⁡ n / n 3 ) . Additionally, we prove that the quantum algorithm of Hastings–O'Donnell still achieves a constant-factor approximation to the ground state energy when p ≥ Ω ( log ⁡ n / n ) . Combined, these show a provable separation between classical algorithms outputting Gaussian states and efficient quantum algorithms for the goal of finding approximate sparse SYK ground states whenever p ≥ Ω ( log ⁡ n / n ) , extending the analogous p = 1 result of Hastings–O'Donnell.

Recent theoretical results in quantum machine learning have demonstrated a general trade-off between the expressive power of quantum neural networks (QNNs) and their trainability; as a corollary of these results, practical exponential separations in expressive power over classical machine learning models are believed to be infeasible as such QNNs take a time to train that is exponential in the model size. We here circumvent these negative results by constructing a hierarchy of efficiently trainable QNNs that exhibit unconditionally provable, polynomial memory separations of arbitrary constant degree over classical neural networks—including state-of-the-art models, such as Transformers—in performing a classical sequence modeling task. This construction is also computationally efficient, as each unit cell of the introduced class of QNNs only has constant gate complexity. We show that contextuality—informally, a quantitative notion of semantic ambiguity—is the source of the expressivity separation, suggesting that other learning tasks with this property may be a natural setting for the use of quantum learning algorithms.

Combinatorial optimization problems that arise in science and industry typically have constraints. Yet the presence of constraints makes them challenging to tackle using both classical and quantum optimization algorithms. We propose a new quantum algorithm for constrained optimization, which we call quantum constrained Hamiltonian optimization (Q-CHOP). Our algorithm leverages the observation that for many problems, while the best solution is difficult to find, the worst feasible (constraint-satisfying) solution is known. The basic idea of Q-CHOP is to enforce a Hamiltonian constraint at all times, thereby restricting evolution to the subspace of feasible states, and slowly “rotate” an objective Hamiltonian to trace an adiabatic path from the worst feasible state to the best feasible state. Q-CHOP thereby assigns qualitatively distinct roles to the constraint and objective functions of a constrained optimization problem. We additionally propose a version of Q-CHOP that can start in any feasible state. Finally, we benchmark Q-CHOP against the commonly-used adiabatic algorithm of quantum annealing with an objective function that penalizes constraint violation, and find that Q-CHOP consistently performs significantly better on a wide range of problems, including textbook graph problems, knapsack problems, combinatorial auctions, and a real-world financial use case of bond exchange-traded fund basket optimization.

A large amount of effort has recently been put into understanding the barren plateau phenomenon. In this perspective article, we face the increasingly loud elephant in the room and ask a question that has been hinted at by many but not explicitly addressed: Can the structure that allows one to avoid barren plateaus also be leveraged to efficiently simulate the loss classically? We collect evidence-on a case-by-case basis-that many commonly used models whose loss landscapes avoid barren plateaus can also admit classical simulation, provided that one can collect some classical data from quantum devices during an initial data acquisition phase. This follows from the observation that barren plateaus result from a curse of dimensionality, and that current approaches for solving them end up encoding the problem into some small, classically simulable, subspaces. Thus, while stressing that quantum computers can be essential for collecting data, our analysis sheds doubt on the information processing capabilities of many parametrized quantum circuits with provably barren plateau-free landscapes. We end by discussing the (many) caveats in our arguments including the limitations of average case arguments, the role of smart initializations, models that fall outside our assumptions, the potential for provably superpolynomial advantages and the possibility that, once larger devices become available, parametrized quantum circuits could heuristically outperform our analytic expectations.

Random spin systems at low temperatures are glassy and feature computational hardness in finding low-energy states. We study the random all-to-all interacting fermionic Sachdev-Ye-Kitaev model and prove that, in contrast, the low-energy states have polynomial circuit depth, yet the annealed and quenched free energies agree to polynomially inverse low temperatures, ruling out a glassy phase transition in this sense. These results are derived by showing that fermionic and spin systems significantly differ in their “commutation index,” which quantifies the noncommutativity of Hamiltonian terms. Our results suggest that low-temperature strongly interacting fermions, unlike spins, belong in a classically nontrivial yet quantumly easy phase.

Classical machine learning models struggle with learning and prediction tasks on data sets exhibiting long-range correlations. Previously, the existence of a long-range correlational structure known as contextuality was shown to inhibit efficient classical machine learning representations of certain quantum-inspired sequential distributions. Here, we define a new quantifier of contextuality we call strong k-contextuality, and prove that any translation task exhibiting strong k-contextuality is unable to be represented to finite relative entropy by a classical streaming model with fewer than k latent states. Importantly, this correlation measure does not induce a similar resource lower bound for quantum generative models. Using this theory as motivation, we develop efficient algorithms which estimate our new measure of contextuality in sequential data, and empirically show that this estimate is a good predictor for the difference in performance of resource-constrained classical and quantum Bayesian networks in modeling the data. Strong k-contextuality thus emerges as a measure to help identify problems that are difficult for classical computers, but may not be for quantum computers.