Explore the vast range of titles available.

Quantum algorithms hold the promise of solving certain computational problems dramatically faster than their classical counterparts. The latest generation of quantum processors with ~50 qubits are expected to be at the brink of outperforming classical computers. However, due to the lack of fault tolerance, the qubits can be operated for only a few time steps, making the quantum circuits shallow in depth. Variational quantum algorithms are leading candidates in the effort to find shallow-depth quantum algorithms that outperform classical computers. Here we consider the task of computing the mean values of multi-qubit observables, which is a cornerstone of variational quantum algorithms for optimization, machine learning and the simulation of quantum many-body systems. We develop sub-exponential time classical algorithms for solving the quantum mean value problem for general classes of quantum observables and constant-depth quantum circuits. In the special case of geometrically local two-dimensional quantum circuits, the runtime of our algorithm scales linearly with the number of qubits. Our results demonstrate that appropriate choices of circuit parameters such as geometric locality and depth are essential to obtain quantum speed-ups based on variational quantum algorithms.Finding expectation values is a key step in variational quantum algorithms that are hoped to provide a near-term quantum advantage. Bravyi et al. show that a classical approximation is possible when the quantum circuits are limited to constant depth.

Any discrete quantum process is represented by a sequence of quantum channels. We consider ergodic quantum processes obtained by a map that takes the points along the trajectory of a discrete ergodic dynamical system to the space of quantum channels. Under a natural irreducibility condition, we obtain a theorem showing that the state under such a process converges exponentially fast to an ergodic sequence depending on the process, but independent of the initial state. As an application, we describe the thermodynamic limit of ergodic matrix product states and prove that the 2-point correlations of local observables in such states decay exponentially with their distance in the bulk.

Electrons are indivisible elementary particles, yet paradoxically a collection of them can act as a fraction of a single electron, exhibiting exotic and useful properties. One such collective excitation, known as a topological Majorana mode, is naturally stable against perturbations, such as unwanted local noise, and can thereby robustly store quantum information. As such, Majorana modes serve as the basic primitive of topological quantum computing, providing resilience to errors. However, their demonstration on quantum hardware has remained elusive. Here, we demonstrate a verifiable identification and braiding of topological Majorana modes using a superconducting quantum processor as a quantum simulator. By simulating fermions on a one-dimensional lattice subject to a periodic drive, we confirm the existence of Majorana modes localized at the edges, and distinguish them from other trivial modes. To simulate a basic logical operation of topological quantum computing known as braiding, we propose a non-adiabatic technique, whose implementation reveals correct braiding statistics in our experiments. This work could further be used to study topological models of matter using circuit-based simulations, and shows that long-sought quantum phenomena can be realized by anyone in cloud-run quantum simulations, whereby accelerating fundamental discoveries in quantum science and technology. Superconducting quantum simulators are promising platforms for simulations of quantum many-body systems. Here the authors simulate a periodically driven 1D quantum spin model hosting Majorana zero modes on a superconducting qubit processor and propose new protocols for their detection and braiding.

The generic behavior of quantum systems has long been of theoretical and practical interest. Any quantum process is represented by a sequence of quantum channels. We consider general ergodic sequences of stochastic channels with arbitrary correlations and non-negligible decoherence. Ergodicity includes and vastly generalizes random independence. We obtain a theorem which shows that the composition of such a sequence of channels converges exponentially fast to a replacement (rank-one) channel. Using this theorem, we derive the limiting behavior of translation-invariant channels and stochastically independent random channels. We then use our formalism to describe the thermodynamic limit of ergodic matrix product states. We derive formulas for the expectation value of a local observable and prove that the two-point correlations of local observables decay exponentially. We then analytically compute the entanglement spectrum across any cut, by which the bipartite entanglement entropy (i.e., Rényi or von Neumann) across an arbitrary cut can be computed exactly. Other physical implications of our results are that most Floquet phases of matter are metastable and that noisy random circuits in the large depth limit will be trivial as far as their quantum entanglement is concerned. To obtain these results, we bridge quantum information theory to dynamical systems and random matrix theory.

Interacting many-body quantum systems and their dynamics, while fundamental to modern science and technology, are formidable to simulate and understand. However, by discovering their symmetries, conservation laws, and integrability, one can unravel their intricacies. Here, using up to 124 qubits of a fully programmable quantum computer, we uncover local conservation laws and integrability in one- and two-dimensional periodically-driven spin lattices in a regime previously inaccessible to such detailed analysis. We focus on the paradigmatic example of disorder-induced ergodicity breaking, where we first benchmark the system crossover into a localized regime through anomalies in the one-particle-density-matrix spectrum and other hallmark signatures. We then demonstrate that this regime stems from hidden local integrals of motion by faithfully reconstructing their quantum operators, thus providing a more detailed portrait of the system’s integrable dynamics. Our results demonstrate a versatile strategy for extracting the hidden dynamical structure from noisy experiments on large-scale quantum computers. Local integrals of motion are useful for understanding emergent integrability in many-body localized systems. Here the authors use a large-scale superconducting quantum processor with up to 124 qubits to simulate many-body dynamics in 1D and 2D systems and demonstrate extraction of local integrals of motion.

As Moore’s law reaches its limits, quantum computers are emerging that hold promise to dramatically outperform classical computers. It is now possible to build quantum processors with over 100 qubits, which are expected to be beyond the reach of classical simulation. These developments have been accompanied by the anticipation that, at some stage, a quantum computer should be able to perform a task that is practically impossible for any classical computer. The lead candidate for reaching this threshold is random circuit sampling, which involves sampling the output of a quantum computer after implementing a sequence of random quantum operations. However, it is difficult to provide theoretical guarantees on the hardness of simulating random quantum circuits by classical computers. Here we prove that estimating the output probabilities of random quantum circuits is #P-hard for any classical computer. We also extend our results to a restricted model of quantum computation known as instantaneous quantum polynomial-time (IQP) circuits. We achieve this by a worst-case to average-case reduction for quantum-circuit simulation. The robustness of our result to the estimation error serves as a new hardness criterion for the performance of classical algorithms. Our results suggest that there is an exponential hardness barrier for the approximate classical simulation of most quantum circuits.Quantum computers are believed to exponentially outperform classical computers at some tasks, but it is hard to make guarantees about the limits of classical computers. It has now been proven that classical computers cannot efficiently simulate most quantum circuits.

Toeplitz matrices have entries that are constant along diagonals. They model directed transport, are at the heart of correlation function calculations of the two-dimensional Ising model, and have applications in quantum information science. We derive their eigenvalues and eigenvectors when the symbol is singular Fisher–Hartwig. We then add diagonal disorder and study the resulting eigenpairs. We find that there is a “bulk” behavior that is well captured by second order perturbation theory of non-Hermitian matrices. The non-perturbative behavior is classified into two classes: Runaways type I leave the complex-valued spectrum and become completely real because of eigenvalue attraction. Runaways type II leave the bulk and move very rapidly in response to perturbations. These have high condition numbers and can be predicted. Localization of the eigenvectors are then quantified using entropies and inverse participation ratios. Eigenvectors corresponding to Runaways type II are most localized (i.e., super-exponential), whereas Runaways type I are less localized than the unperturbed counterparts and have most of their probability mass in the interior with algebraic decays. The results are corroborated by applying free probability theory and various other supporting numerical studies.

Quantum entanglement is the most surprising feature of quantum mechanics. Entanglement is simultaneously responsible for the difficulty of simulating quantum matter on a classical computer and the exponential speedups afforded by quantum computers. Ground states of quantum many-body systems typically satisfy an “area law”: The amount of entanglement between a subsystem and the rest of the system is proportional to the area of the boundary. A system that obeys an area law has less entanglement and can be simulated more efficiently than a generic quantum state whose entanglement could be proportional to the total system’s size. Moreover, an area law provides useful information about the low-energy physics of the system. It is widely believed that for physically reasonable quantum systems, the area law cannot be violated by more than a logarithmic factor in the system’s size. We introduce a class of exactly solvable one-dimensional physical models which we can prove have exponentially more entanglement than suggested by the area law, and violate the area law by a square-root factor. This work suggests that simple quantum matter is richer and can provide much more quantum resources (i.e., entanglement) than expected. In addition to using recent advances in quantum information and condensed matter theory, we have drawn upon various branches of mathematics such as combinatorics of random walks, Brownian excursions, and fractional matching theory. We hope that the techniques developed herein may be useful for other problems in physics as well.

Implementing robust quantum error correction (QEC) is imperative for harnessing the promise of quantum technologies. We introduce a framework that takes ıt any classical code and explicitly constructs the corresponding QEC code. Our framework can be seen to generalize the CSS codes, and goes beyond the stabilizer formalism~(Fig.~1). A concrete advantage is that the desirable properties of a classical code are automatically incorporated in the design of the resulting quantum code. We reify the theory by various illustrations some of which outperform the best previous constructions. We then introduce a local quantum spin-chain Hamiltonian whose ground space we analytically completely characterize. We utilize our framework to demonstrate that the ground space contains explicit quantum codes with linear distance. This side-steps the Bravyi-Terhal no-go theorem.

We prove that the complex conjugate (c.c.) eigenvalues of a smoothly varying real matrix attract (Eq. 15). We offer a dynamical perspective on the motion and interaction of the eigenvalues in the complex plane, derive their governing equations and discuss applications. C.c. pairs closest to the real axis, or those that are ill-conditioned, attract most strongly and can collide to become exactly real. As an application we consider random perturbations of a fixed matrix M. If M is Normal, the total expected force on any eigenvalue is shown to be only the attraction of its c.c. (Eq. 24) and when M is circulant the strength of interaction can be related to the power spectrum of white noise. We extend this by calculating the expected force (Eq. 41) for real stochastic processes with zero-mean and independent intervals. To quantify the dominance of the c.c. attraction, we calculate the variance of other forces. We apply the results to the Hatano-Nelson model and provide other numerical illustrations. It is our hope that the simple dynamical perspective herein might help better understanding of the aggregation and low density of the eigenvalues of real random matrices on and near the real line respectively. In the appendix we provide a Matlab code for plotting the trajectories of the eigenvalues.