Patrick Hayden

Approximation based on perturbation theory is the foundation for most of the quantitative predictions of quantum mechanics, whether in quantum many-body physics, chemistry, or other domains. Quantum computing provides an alternative to the perturbation paradigm, yet current quantum processors with few noisy qubits are of limited practical utility. In this talk, we introduce perturbative quantum simulation, which combines the complementary strengths of the two approaches, enabling the solution of large quantum problems using limited intermediate-scale quantum hardware. The use of a quantum processor alleviates the need to identify a solvable unperturbed Hamiltonian, while the introduction of perturbative coupling permits a quantum processor to simulate systems with larger sizes. We present an explicit perturbative expansion that mimics the Dyson series expansion and involves only local unitary operations. We then discuss its optimality over other expansions under certain conditions. This perturbative approach is benchmarked by simulating the interacting dynamics of representative quantum systems.

Abstract It has long been known that the existence of certain superquantum nonlocal correlations would cause communication complexity to collapse. The absurdity of a world in which any function could be evaluated by two players with a constant amount of communication in turn provides a tantalizing way to distinguish quantum mechanics from incorrect theories of physics; the statement ``communication complexity is nontrivial" has even been conjectured to be a concise information-theoretic axiom for characterizing quantum mechanics. We directly address the viability of that perspective with two results. First, we exhibit a nonlocal game such that communication complexity collapses in any physical theory whose maximal winning probability exceeds the quantum value. Second, we consider the venerable CHSH game that initiated this line of inquiry. In that case, the quantum value is about 0.85 but it is known that a winning probability of approximately 0.91 would collapse communication complexity. We show that the 0.91 result is the best possible using a large class of proof strategies, suggesting that the communication complexity axiom is insufficient for characterizing CHSH correlations. Both results build on new insights about reliable classical computation. The first exploits our formalization of an equivalence between amplification and reliable computation, while the second follows from a rigorous determination of the threshold for reliable computation with formulas of noise-free XOR gates and $\epsilon$-noisy AND gates.