Classical-quantum computational complexity separations are an important motivation for the long-term development of digital quantum computers, but classical-quantum complexity equivalences are just as important in our present era of noisy intermediate-scale quantum devices for framing near-term progress towards quantum supremacy. We establish one such equivalence using a noisy quantum circuit model that can be simulated efficiently on classical computers. With respect to its noise model, quantum states have a robust decomposition into a sequence of operations that each extend the state by one qubit without spreading errors between qubits. This enables universal quantum sampling of states with an efficient representation in this robust form and observables with low quantum weight that can be sampled from general measurements on a few qubits and computational basis measurements on the remaining qubits. These robust decompositions are not unique, and we construct two distinct variants, both of which are compatible with machine-learning methodology. They both enable efficiently computable lower bounds on von Neumann entropy and thus can be used as finite-temperature variational quantum Monte Carlo methods.
Classical-quantum computational complexity separations are an important motivation for the long-term development of digital quantum computers, but classical-quantum complexity equivalences are just as important in our present era of noisy intermediate-scale quantum devices for framing near-term progress towards quantum supremacy. We establish one such equivalence using a noisy quantum circuit model that can be simulated efficiently on classical computers. With respect to its noise model, quantum states have a robust decomposition into a sequence of operations that each extend the state by one qubit without spreading errors between qubits. This enables universal quantum sampling of states with an efficient representation in this robust form and observables with low quantum weight that can be sampled from general measurements on a few qubits and computational basis measurements on the remaining qubits. These robust decompositions are not unique, and we construct two distinct variants, both of which are compatible with machine-learning methodology. They both enable efficiently computable lower bounds on von Neumann entropy and thus can be used as finite-temperature variational quantum Monte Carlo methods.
Demonstrating quantum supremacy, a complexity-guaranteed quantum advantage against over the best classical algorithms by using less universal quantum devices, is an important near-term milestone for quantum information processing. Here we develop a threshold theorem for quantum supremacy with noisy quantum circuits in the pre-threshold region, where quantum error correction does not work directly. We show that, even in such a region, we can virtually simulate quantum error correction by postselection. This allows us to show that the output sampled from the noisy quantum circuits (without postselection) cannot be simulated efficiently by classical computers based on a stable complexity theoretical conjecture, i.e., non-collapse of the polynomial hierarchy. By applying this to fault-tolerant quantum computation with the surface codes, we obtain the threshold value 2.84% for quantum supremacy, which is much higher than the standard threshold 0.75% for universal fault-tolerant quantum computation with the same circuit-level noise model. Moreover, contrast to the standard noise threshold, the origin of quantum supremacy in noisy quantum circuits is quite clear; the threshold is determined purely by the threshold of magic state distillation, which is essential to gain a quantum advantage.
Extracting information efficiently from quantum systems is crucial for quantum information processing. Classical shadows enable predicting many properties of arbitrary quantum states using few measurements. While random single-qubit measurements are experimentally friendly and suitable for learning low-weight Pauli observables, they perform poorly for nonlocal observables. Introducing a shallow random quantum circuit before measurements improves sample efficiency for high-weight Pauli observables and low-rank properties. However, in practice, these circuits can be noisy and bias the measurement results. Here, we propose the robust shallow shadows, which employs Bayesian inference to learn and mitigate noise in postprocessing. We analyze noise effects on sample complexity and the optimal circuit depth. We provide theoretical guarantees for the success of error mitigation under a wide class of noise processes. Experimental validation on a superconducting quantum processor confirms the advantage of our method, even in the presence of realistic noise, over single-qubit measurements for predicting diverse state properties, such as fidelity and entanglement entropy. Our protocol thus offers a scalable, robust, and sample-efficient method for quantum state characterization on near-term quantum devices. Fast and reliable characterisation of quantum systems is a key part of quantum technologies development. Here, the authors propose and demonstrate a way to embed noise characterisation in classical shadow estimation of nonlocal properties, enabling an efficient way to extract information from noisy quantum systems.
Noise in quantum operations often negates the advantage of quantum computation. However, most classical simulations of quantum computers calculate the ideal probability amplitudes by either storing full state vectors or using sophisticated tensor-network contractions. Here we investigate sampling-based classical simulation methods for noisy quantum circuits. Specifically, we characterize the simulation costs of two major schemes, stabilizer-state sampling of magic states and Heisenberg propagation, for quantum circuits subject to stochastic Pauli noise, such as depolarizing and dephasing noise. To this end, we introduce several techniques for the stabilizer-state sampling to reduce the simulation costs under such noise. It is revealed that in the low-noise regime, stabilizer-state sampling results in a smaller sampling cost, while Heisenberg propagation is better in the high-noise regime. Furthermore, for a high depolarizing noise rate of approximately 10%, these methods provide better scaling than that given by the low-rank stabilizer decomposition. We believe that this knowledge of classical simulation costs is useful to achieve possible quantum advantage on near-term noisy quantum devices as well as efficient classical simulation methods.
The preparation of an equilibrium thermal state of a quantum many-body system on noisy intermediate-scale quantum (NISQ) devices is an important task in order to extend the range of applications of quantum computation. Faithful Gibbs state preparation would pave the way to investigate protocols such as thermalization and out-of-equilibrium thermodynamics and provide useful resources for quantum algorithms, where sampling from Gibbs states constitutes a key subroutine. We propose a variational quantum algorithm (VQA) to prepare Gibbs states of a quantum many-body system. The novelty of our VQA consists of implementing a parameterized quantum circuit acting on two distinct, yet connected (via cnot gates), quantum registers. The VQA evaluates the Helmholtz free energy, where the von Neumann entropy is obtained via postprocessing of computational-basis measurements on one register, while the Gibbs state is prepared on the other register via a unitary rotation in the energy basis. Finally, we benchmark our VQA by preparing Gibbs states of the transverse-field Ising and Heisenberg XXZ models and achieve remarkably high fidelities across a broad range of temperatures in state-vector simulations. We also assess the performance of the VQA on IBM quantum computers, showcasing its feasibility on current NISQ devices.
Although the emergence of a fully-functional quantum computer may still be far away from today, in the near future, it is possible to have medium-size, special-purpose, quantum devices that can perform computational tasks not efficiently simulable with any classical computer. This status is known as quantum supremacy (or quantum advantage), where one of the promising approaches is through the sampling of chaotic quantum circuits. Sampling of ideal chaotic quantum circuits has been argued to require an exponential time for classical devices. A major question is whether quantum supremacy can be maintained under noise without error correction, as the implementation of fault-tolerance would cost lots of extra qubits and quantum gates. Here we show that, for a family of chaotic quantum circuits subject to Pauli errors, there exists an non-exponential classical algorithm capable of simulating the noisy chaotic quantum circuits with bounded errors. This result represents a serious challenge to a previous result in the literature suggesting the failure of classical devices in simulating noisy chaotic circuits with about 48 qubits and depth 25. Moreover, even though our model does not cover all types of experimental errors, from a practical point view, our result describes a well-defined setting where quantum supremacy can be tested against the challenges of classical rivals, in the context of chaotic quantum circuits.
Understanding the computational power of noisy intermediate-scale quantum (NISQ) devices is of both fundamental and practical importance to quantum information science. Here, we address the question of whether error-uncorrected noisy quantum computers can provide computational advantage over classical computers. Specifically, we study noisy random circuit sampling in one dimension (or 1D noisy RCS) as a simple model for exploring the effects of noise on the computational power of a noisy quantum device. In particular, we simulate the real-time dynamics of 1D noisy random quantum circuits via matrix product operators (MPOs) and characterize the computational power of the 1D noisy quantum system by using a metric we call MPO entanglement entropy. The latter metric is chosen because it determines the cost of classical MPO simulation. We numerically demonstrate that for the two-qubit gate error rates we considered, there exists a characteristic system size above which adding more qubits does not bring about an exponential growth of the cost of classical MPO simulation of 1D noisy systems. Specifically, we show that above the characteristic system size, there is an optimal circuit depth, independent of the system size, where the MPO entanglement entropy is maximized. Most importantly, the maximum achievable MPO entanglement entropy is bounded by a constant that depends only on the gate error rate, not on the system size. We also provide a heuristic analysis to get the scaling of the maximum achievable MPO entanglement entropy as a function of the gate error rate. The obtained scaling suggests that although the cost of MPO simulation does not increase exponentially in the system size above a certain characteristic system size, it does increase exponentially as the gate error rate decreases, possibly making classical simulation practically not feasible even with state-of-the-art supercomputers.