Complexity Phase Diagram for Interacting and Long-Range Bosonic Hamiltonians

An atomic boson sampler

A boson sampler implements a restricted model of quantum computing. It is defined by the ability to sample from the distribution resulting from the interference of identical bosons propagating according to programmable, non-interacting dynamics1. An efficient exact classical simulation of boson sampling is not believed to exist, which has motivated ground-breaking boson sampling experiments in photonics with increasingly many photons2-12. However, it is difficult to generate and reliably evolve specific numbers of photons with low loss, and thus probabilistic techniques for postselection7 or marked changes to standard boson sampling10-12 are generally used. Here, we address the above challenges by implementing boson sampling using ultracold atoms13,14 in a two-dimensional, tunnel-coupled optical lattice. This demonstration is enabled by a previously unrealized combination of tools involving high-fidelity optical cooling and imaging of atoms in a lattice, as well as programmable control of those atoms using optical tweezers. When extended to interacting systems, our work demonstrates the core abilities required to directly assemble ground and excited states in simulations of various Hubbard models15,16.

Effective light cone and digital quantum simulation of interacting bosons

The speed limit of information propagation is one of the most fundamental features in non-equilibrium physics. The region of information propagation by finite-time dynamics is approximately restricted inside the effective light cone that is formulated by the Lieb-Robinson bound. To date, extensive studies have been conducted to identify the shape of effective light cones in most experimentally relevant many-body systems. However, the Lieb-Robinson bound in the interacting boson systems, one of the most ubiquitous quantum systems in nature, has remained a critical open problem for a long time. This study reveals a tight effective light cone to limit the information propagation in interacting bosons, where the shape of the effective light cone depends on the spatial dimension. To achieve it, we prove that the speed for bosons to clump together is finite, which in turn leads to the error guarantee of the boson number truncation at each site. Furthermore, we applied the method to provide a provably efficient algorithm for simulating the interacting boson systems. The results of this study settle the notoriously challenging problem and provide the foundation for elucidating the complexity of many-body boson systems.

Finite-Time Teleportation Phase Transition in Random Quantum Circuits

How long does it take to entangle two distant qubits in a quantum circuit evolved by generic unitary dynamics? We show that if the time evolution is followed by measurements of all but two infinitely separated test qubits, then the entanglement between them can undergo a phase transition and become nonzero at a finite critical time t_{c}. The fidelity of teleporting a quantum state from an input qubit to an infinitely distant output qubit shows the same critical onset. Specifically, these finite-time transitions occur in short-range interacting two-dimensional random unitary circuits and in sufficiently long-range interacting one-dimensional circuits. The phase transition is understood by mapping the random continuous-time evolution to a finite-temperature thermal state of an effective spin Hamiltonian, where the inverse temperature equals the evolution time in the circuit. In this framework, the entanglement between two distant qubits at times t>t_{c} corresponds to the emergence of long-range ferromagnetic spin correlations below the critical temperature. We verify these predictions using numerical simulation of Clifford circuits and propose potential realizations in existing platforms for quantum simulation.

Programmable Quantum Simulations of Bosonic Systems with Trapped Ions

Trapped atomic ion crystals are a leading platform for quantum simulations of spin systems, with programmable and long-range spin-spin interactions mediated by excitations of phonons in the crystal. We describe a complementary approach for quantum simulations of bosonic systems using phonons in trapped-ion crystals, here mediated by excitations of the trapped-ion spins. The scheme enables a high degree of programability across a dense graph of bosonic couplings, utilizing long-lived collective phonon modes in a trapped-ion chain. As such, it is well suited for tackling hard problems such as boson sampling and simulations of long-range bosonic and spin-boson Hamiltonians.

Complexity Phase Transitions Generated by Entanglement

Entanglement is one of the physical properties of quantum systems responsible for the computational hardness of simulating quantum systems. But while the runtime of specific algorithms, notably tensor network algorithms, explicitly depends on the amount of entanglement in the system, it is unknown whether this connection runs deeper and entanglement can also cause inherent, algorithm-independent complexity. In this Letter, we quantitatively connect the entanglement present in certain quantum systems to the computational complexity of simulating those systems. Moreover, we completely characterize the entanglement and complexity as a function of a system parameter. Specifically, we consider the task of simulating single-qubit measurements of k-regular graph states on n qubits. We show that, as the regularity parameter is increased from 1 to n-1, there is a sharp transition from an easy regime with low entanglement to a hard regime with high entanglement at k=3, and a transition back to easy and low entanglement at k=n-3. As a key technical result, we prove a duality for the simulation complexity of regular graph states between low and high regularity.

Transitions in Computational Complexity of Continuous-Time Local Open Quantum Dynamics

We analyze the complexity of classically simulating continuous-time dynamics of locally interacting quantum spin systems with a constant rate of entanglement breaking noise. We prove that a polynomial time classical algorithm can be used to sample from the state of the spins when the rate of noise is higher than a threshold determined by the strength of the local interactions. Furthermore, by encoding a 1D fault tolerant quantum computation into the dynamics of spin systems arranged on two or higher dimensional grids, we show that for several noise channels, the problem of weakly simulating the output state of both purely Hamiltonian and purely dissipative dynamics is expected to be hard in the low-noise regime.