Abstract Demonstrating quantum advantage on noisy quantum devices is one of the most important tasks of quantum computing research in the near future. Random quantum circuit sampling is proposed as the most promising approach to the task and has been implemented in experiments for achieving quantum advantage. A series of encouraging computational complexity results, based on some plausible assumptions, show that this task is impossible to complete efficiently by classical computers. However, in practical experiments on noisy quantum devices, the approximate average‐case hardness and the effects of the noise need to be further checked. The competition between the classical simulation algorithm (mainly based on tensor network algorithms) and noisy quantum devices is the explicit way to understand quantum advantage in practice. This review briefly overviews the computational complexity arguments for the hardness of classical simulation of random quantum circuits sampling, then focus on various methods of classical simulation of quantum circuits based on tensor network method.
Abstract Demonstrating quantum advantage on noisy quantum devices is one of the most important tasks of quantum computing research in the near future. Random quantum circuit sampling is proposed as the most promising approach to the task and has been implemented in experiments for achieving quantum advantage. A series of encouraging computational complexity results, based on some plausible assumptions, show that this task is impossible to complete efficiently by classical computers. However, in practical experiments on noisy quantum devices, the approximate average‐case hardness and the effects of the noise need to be further checked. The competition between the classical simulation algorithm (mainly based on tensor network algorithms) and noisy quantum devices is the explicit way to understand quantum advantage in practice. This review briefly overviews the computational complexity arguments for the hardness of classical simulation of random quantum circuits sampling, then focus on various methods of classical simulation of quantum circuits based on tensor network method.
Simulating noisy quantum circuits is vital in de-signing and verifying quantum algorithms in the current NISQ (Noisy Intermediate-Scale Quantum) era, where quantum noise is unavoidable. However, it is much more inefficient than the classical counterpart because of the quantum state explosion problem (the dimension of state space is exponential in the number of qubits) and the complex (non-unitary) representation of noises. Consequently, only noisy circuits with up to about 50 qubits can be simulated approximately well. To improve the scalability of the circuits that can be simulated, this paper introduces a novel approximation algorithm for simulating noisy quantum circuits when the noisy effectiveness is insignificant. The algorithm is based on a new tensor network diagram for the noisy simulation and uses the singular value decomposition to approximate the tensors of quantum noises in the diagram. The contraction of the tensor network diagram is implemented on Google's TensorNetwork. The effectiveness and utility of the algorithm are demonstrated by experimenting on a series of practical quantum circuits with realistic superconducting noise models. As a result, our algorithm can approximately simulate quantum circuits with up to 225 qubits and 20 noises (within about 1.8 hours). In particular, our method offers a speedup over the commonly-used approximation (sampling) algorithm - quantum trajectories method [1]. Furthermore, our approach can significantly reduce the number of samples in the quantum trajectories method when the noise rate is small enough,
Noise is the defining feature of the NISQ era, but it remains unclear if noisy quantum devices are capable of quantum speedups. Quantum supremacy experiments have been a major step forward, but gaps remain between the theory behind these experiments and their actual implementations. In this work we initiate the study of the complexity of quantum random circuit sampling experiments with realistic amounts of noise. Actual quantum supremacy experiments have high levels of uncorrected noise and exponentially decaying fidelities. It is natural to ask if there is any signal of exponential complexity in these highly noisy devices. Surprisingly, we show that it remains hard to compute the output probabilities of noisy random quantum circuits without error correction. More formally, so long as the noise rate of the device is below the error detection threshold, we show it is #P-hard to compute the output probabilities of random circuits with a constant rate of noise per gate. This hardness persists even though these probabilities are exponentially close to uniform. Therefore the small deviations away from uniformity are hard to compute, formalizing an important intuition behind Google's supremacy claim. Interestingly these hardness results also have implications for the complexity of experiments in a low-noise setting. The issue here is that prior hardness results for computing output proba-bilities of random circuits are not robust enough to imprecision to connect with the Stockmeyer argument for hardness of sampling from circuits with constant fidelity. We exponentially improve the robustness of prior results to imprecision, both in the cases of Random Circuit Sampling and BosonSampling. In the latter case we bring the proven hardness within a constant factor in the exponent of the robustness required for hardness of sampling for the first time. We then show that our results are in tension with one another - the high-noise result implies the low-noise result is essentially optimal, even with generalizations of our techniques.
The present era of quantum processors with hundreds to thousands of noisy qubits has sparked interest in understanding the computational power of these devices and how to leverage it to solve practically relevant problems. For applications that require estimating expectation values of observables the community developed a good understanding of how to simulate them classically and denoise them. Certain applications, like combinatorial optimization, however demand more than expectation values: the bit-strings themselves encode the candidate solutions. While recent impossibility and threshold results indicate that noisy samples alone rarely beat classical heuristics, we still lack classical methods to replicate those noisy samples beyond the setting of random quantum circuits.Focusing on problems whose objective depends only on two-body correlations such as Max-Cut, we show that Gaussian randomized rounding in the spirit of Goemans-Williamson applied to the circuit's two-qubit marginals produces a distribution whose expected cost is provably close to that of the noisy quantum device. For instance, for Max-Cut problems we show that for any depth-D circuit affected by local depolarizing noise p, our sampler achieves a recovery ratio 1 − O [ ( 1 − p ) D ] , giving ways to efficiently sample from a distribution that behaves similarly to the noisy circuit for the problem at hand. Beyond theory we run large-scale simulations and experiments on IBMQ hardware, confirming that the rounded samples faithfully reproduce the full energy distribution, and we show similar behaviour under other various noise models. Our results supply a simple classical surrogate for sampling noisy optimization circuits, clarify the realistic power of near-term hardware for combinatorial tasks, and provide a quantitative benchmark for future error-mitigated or fault-tolerant demonstrations of quantum advantage.
While quantum computing can accomplish tasks that are classically intractable, the presence of noise may destroy this advantage in the absence of fault tolerance. In this work, we present a classical algorithm that runs in npolylog(n) time for simulating quantum circuits under local depolarizing noise, thereby ruling out their quantum advantage in these settings. Our algorithm leverages a property called approximate Markovianity to sequentially sample from the measurement outcome distribution of noisy circuits. We establish approximate Markovianity in a broad range of circuits: (1) we prove that it holds for any circuit when the noise rate exceeds a constant threshold, and (2) we provide strong analytical and numerical evidence that it holds for random quantum circuits subject to any constant noise rate. These regimes include previously known classically simulable cases as well as new ones, such as shallow random circuits without anticoncentration, where prior algorithms fail. Taken together, our results significantly extend the boundary of classical simulability and suggest that noise generically enforces approximate Markovianity and classical simulability, thereby highlighting the limitation of noisy quantum circuits in demonstrating quantum advantage.
In the effort to develop useful quantum computers, simulating quantum machines with conventional classical computing resources is a key capability. Such simulations will always face limits, preventing the emulation of quantum computers at substantial scale; however, by pushing the envelope through optimal choices of algorithms and hardware, the value of simulator tools can be maximized. This work reviews state-of-the-art numerical simulation methods, i.e., classical algorithms that emulate quantum computer evolution under specific operations. We focus on the mainstream state-vector and tensor-network paradigms, while briefly mentioning alternative methods. Moreover, we review the diverse applications of simulation across different facets of quantum computer development, including understanding the fundamental differences between quantum and classical computations, exploring algorithmic design for quantum advantage, predicting quantum processor performance at the design stage, and efficiently characterizing fabricated devices for rapid iterations. This review complements recent surveys of current tools and implementations; here, we aim to provide readers with an essential understanding of the theoretical basis of classical simulation methods, a detailed discussion of their advantages and limitations, and an overview of the demands and challenges arising from practical use cases.
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.