Towards near-term quantum simulation of materials.

Determining the ground and excited state properties of materials is considered one of the most promising applications of quantum computers. On near-term hardware, the limiting constraint on such simulations is the requisite circuit depths and qubit numbers, which currently lie well beyond near-term capabilities. Here we develop a quantum algorithm which reduces the estimated cost of material simulations.

Uncomputably complex renormalisation group flows.

Renormalisation group methods are among the most important techniques for analysing the physics of many-body systems: by iterating a renormalisation group map, which coarse-grains the description of a system and generates a flow in the parameter space, physical properties of interest can be extracted. However, recent work has shown that important physical features, such as the spectral gap and phase diagram, may be impossible to determine, even in principle. Following these insights, we construct a rigorous renormalisation group map for the original undecidable many-body system that appeared in the literature, which reveals a renormalisation group flow so complex that it cannot be predicted.

Hamiltonian simulation algorithms for near-term quantum hardware.

The quantum circuit model is the de-facto way of designing quantum algorithms. Yet any level of abstraction away from the underlying hardware incurs overhead. In this work, we develop quantum algorithms for Hamiltonian simulation "one level below" the circuit model, exploiting the underlying control over qubit interactions available in most quantum hardware and deriving analytic circuit identities for synthesising multi-qubit evolutions from two-qubit interactions.

Uncomputability of phase diagrams.

The phase diagram of a material is of central importance in describing the properties and behaviour of a condensed matter system. In this work, we prove that the task of determining the phase diagram of a many-body Hamiltonian is in general uncomputable, by explicitly constructing a continuous one-parameter family of Hamiltonians H(φ), where [Formula: see text], for which this is the case. The H(φ) are translationally-invariant, with nearest-neighbour couplings on a 2D spin lattice.

Universal quantum Hamiltonians.

Quantum many-body systems exhibit an extremely diverse range of phases and physical phenomena. However, we prove that the entire physics of any quantum many-body system can be replicated by certain simple, "universal" spin-lattice models. We first characterize precisely what it means for one quantum system to simulate the entire physics of another.

Size-driven quantum phase transitions.

Can the properties of the thermodynamic limit of a many-body quantum system be extrapolated by analyzing a sequence of finite-size cases? We present models for which such an approach gives completely misleading results: translationally invariant, local Hamiltonians on a square lattice with open boundary conditions and constant spectral gap, which have a classical product ground state for all system sizes smaller than a particular threshold size, but a ground state with topological degeneracy for all system sizes larger than this threshold. Starting from a minimal case with spins of dimension 6 and threshold lattice size [Formula: see text], we show that the latter grows faster than any computable function with increasing local spin dimension. The resulting effect may be viewed as a unique type of quantum phase transition that is driven by the size of the system rather than by an external field or coupling strength.

The complexity of divisibility.

We address two sets of long-standing open questions in linear algebra and probability theory, from a computational complexity perspective: stochastic matrix divisibility, and divisibility and decomposability of probability distributions. We prove that finite divisibility of stochastic matrices is an NP-complete problem, and extend this result to nonnegative matrices, and completely-positive trace-preserving maps, i.e.

Simple universal models capture all classical spin physics.

Spin models are used in many studies of complex systems because they exhibit rich macroscopic behavior despite their microscopic simplicity. Here, we prove that all the physics of every classical spin model is reproduced in the low-energy sector of certain "universal models," with at most polynomial overhead. This holds for classical models with discrete or continuous degrees of freedom.

Undecidability of the spectral gap.

The spectral gap--the energy difference between the ground state and first excited state of a system--is central to quantum many-body physics. Many challenging open problems, such as the Haldane conjecture, the question of the existence of gapped topological spin liquid phases, and the Yang-Mills gap conjecture, concern spectral gaps. These and other problems are particular cases of the general spectral gap problem: given the Hamiltonian of a quantum many-body system, is it gapped or gapless? Here we prove that this is an undecidable problem.

Unbounded number of channel uses may be required to detect quantum capacity.

Transmitting data reliably over noisy communication channels is one of the most important applications of information theory, and is well understood for channels modelled by classical physics. However, when quantum effects are involved, we do not know how to compute channel capacities. This is because the formula for the quantum capacity involves maximizing the coherent information over an unbounded number of channel uses.

Extracting dynamical equations from experimental data is NP hard.

The behavior of any physical system is governed by its underlying dynamical equations. Much of physics is concerned with discovering these dynamical equations and understanding their consequences. In this Letter, we show that, remarkably, identifying the underlying dynamical equation from any amount of experimental data, however precise, is a provably computationally hard problem (it is NP hard), both for classical and quantum mechanical systems.

Entanglement can completely defeat quantum noise.

We describe two quantum channels that individually cannot send any classical information without some chance of decoding error. But together a single use of each channel can send quantum information perfectly reliably. This proves that the zero-error classical capacity exhibits superactivation, the extreme form of the superadditivity phenomenon in which entangled inputs allow communication over zero-capacity channels.

Improving zero-error classical communication with entanglement.

Given one or more uses of a classical channel, only a certain number of messages can be transmitted with zero probability of error. The study of this number and its asymptotic behavior constitutes the field of classical zero-error information theory. We show that, given a single use of certain classical channels, entangled states of a system shared by the sender and receiver can be used to increase the number of (classical) messages which can be sent without error.