Dynamical Phase Transitions in Sampling Complexity

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.

Gaussian Boson Sampling with Pseudo-Photon-Number-Resolving Detectors and Quantum Computational Advantage

We report new Gaussian boson sampling experiments with pseudo-photon-number-resolving detection, which register up to 255 photon-click events. We consider partial photon distinguishability and develop a more complete model for the characterization of the noisy Gaussian boson sampling. In the quantum computational advantage regime, we use Bayesian tests and correlation function analysis to validate the samples against all current classical spoofing mockups. Estimating with the best classical algorithms to date, generating a single ideal sample from the same distribution on the supercomputer Frontier would take ∼600  yr using exact methods, whereas our quantum computer, Jiǔzhāng 3.0, takes only 1.27  μs to produce a sample. Generating the hardest sample from the experiment using an exact algorithm would take Frontier∼3.1×10^{10}  yr.

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.

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.

Complexity Phase Diagram for Interacting and Long-Range Bosonic Hamiltonians

We classify phases of a bosonic lattice model based on the computational complexity of classically simulating the system. We show that the system transitions from being classically simulable to classically hard to simulate as it evolves in time, extending previous results to include on-site number-conserving interactions and long-range hopping. Specifically, we construct a complexity phase diagram with easy and hard "phases" and derive analytic bounds on the location of the phase boundary with respect to the evolution time and the degree of locality. We find that the location of the phase transition is intimately related to upper bounds on the spread of quantum correlations and protocols to transfer quantum information. Remarkably, although the location of the transition point is unchanged by on-site interactions, the nature of the transition point does change. Specifically, we find that there are two kinds of transitions, sharp and coarse, broadly corresponding to interacting and noninteracting bosons, respectively. Our Letter motivates future studies of complexity in many-body systems and its interplay with the associated physical phenomena.

Classical Simulation of Boson Sampling Based on Graph Structure

Boson sampling is a fundamentally and practically important task that can be used to demonstrate quantum supremacy using noisy intermediate-scale quantum devices. In this Letter, we present classical sampling algorithms for single-photon and Gaussian input states that take advantage of a graph structure of a linear-optical circuit. The algorithms' complexity grows as so-called treewidth, which is closely related to the connectivity of a given linear-optical circuit. Using the algorithms, we study approximated simulations for local Haar-random linear-optical circuits. For equally spaced initial sources, we show that, when the circuit depth is less than the quadratic in the lattice spacing, the efficient simulation is possible with an exponentially small error. Notably, right after this depth, photons start to interfere each other and the algorithms' complexity becomes subexponential in the number of sources, implying that there is a sharp transition of its complexity. Finally, when a circuit is sufficiently deep enough for photons to typically propagate to all modes, the complexity becomes exponential as generic sampling algorithms. We numerically implement a likelihood test with a recent Gaussian boson sampling experiment and show that the treewidth-based algorithm with a limited treewidth renders a larger likelihood than the experimental data.

Lieb-Robinson Light Cone for Power-Law Interactions

The Lieb-Robinson theorem states that information propagates with a finite velocity in quantum systems on a lattice with nearest-neighbor interactions. What are the speed limits on information propagation in quantum systems with power-law interactions, which decay as 1/r^{α} at distance r? Here, we present a definitive answer to this question for all exponents α>2d and all spatial dimensions d. Schematically, information takes time at least r^{min{1,α-2d}} to propagate a distance r. As recent state transfer protocols saturate this bound, our work closes a decades-long hunt for optimal Lieb-Robinson bounds on quantum information dynamics with power-law interactions.

Lieb-Robinson Bound and Almost-Linear Light Cone in Interacting Boson Systems

In this work, we investigate how quickly local perturbations propagate in interacting boson systems with Bose-Hubbard-type Hamiltonians. In general, these systems have unbounded local energies, and arbitrarily fast information propagation may occur. We focus on a specific but experimentally natural situation in which the number of bosons at any one site in the unperturbed initial state is approximately limited. We rigorously prove the existence of an almost-linear information-propagation light cone, thus establishing a Lieb-Robinson bound: the wave front grows at most as t log^{2}(t). We prove the clustering theorem for gapped ground states and study the time complexity of classically simulating one-dimensional quench dynamics, a topic of great practical interest.

Interference of Temporally Distinguishable Photons Using Frequency-Resolved Detection

We demonstrate quantum interference of three photons that are distinguishable in time by resolving them in the conjugate parameter frequency. We show that the multiphoton interference pattern in our setup can be manipulated by tuning the relative delays between the photons, without the need for reconfiguring the optical network. Furthermore, we observe that the symmetries of our optical network and the spectral amplitude of the input photons are manifested in the interference pattern. We also demonstrate time-reversed Hong-Ou-Mandel-like interference in the spectral correlations using time-bin entangled photon pairs. By adding a time-varying dispersion using a phase modulator, our setup can be used to realize dynamically reconfigurable and scalable boson sampling in the time domain as well as frequency-resolved multiboson correlation sampling.

Locality and Digital Quantum Simulation of Power-Law Interactions

The propagation of information in nonrelativistic quantum systems obeys a speed limit known as a Lieb-Robinson bound. We derive a new Lieb-Robinson bound for systems with interactions that decay with distance r as a power law, 1/r α . The bound implies an effective light cone tighter than all previous bounds. Our approach is based on a technique for approximating the time evolution of a system, which was first introduced as part of a quantum simulation algorithm by Haah et al., FOCS'18. To bound the error of the approximation, we use a known Lieb-Robinson bound that is weaker than the bound we establish. This result brings the analysis full circle, suggesting a deep connection between Lieb-Robinson bounds and digital quantum simulation. In addition to the new Lieb-Robinson bound, our analysis also gives an error bound for the Haah et al. quantum simulation algorithm when used to simulate power-law decaying interactions. In particular, we show that the gate count of the algorithm scales with the system size better than existing algorithms when α > 3D (where D is the number of dimensions).