It is imperative that useful quantum computers be very difficult to simulate classically; otherwise classical computers could be used for the applications envisioned for the quantum ones. Perfect quantum computers are unarguably exponentially difficult to simulate: the classical resources required grow exponentially with the number of qubits N or the depth D of the circuit. Real quantum computing devices, however, are characterized by an exponentially decaying fidelity F∼(1−ϵ)ND with an error rate ϵ per operation as small as ≈1% for current devices. In this work, we demonstrate that real quantum computers can be simulated at a tiny fraction of the cost that would be needed for a perfect quantum computer. Our algorithms compress the representations of quantum wavefunctions using matrix product states (MPS), which capture states with low to moderate entanglement very accurately. This compression introduces a finite error rate ϵ so that the algorithms closely mimic the behavior of real quantum computing devices. The computing time of our algorithm increases only linearly with N and D. We illustrate our algorithms with simulations of random circuits for qubits connected in both one and two dimensional lattices. We find that ϵ can be decreased at a polynomial cost in computing power down to a minimum error ϵ∞. Getting below ϵ∞ requires computing resources that increase exponentially with ϵ∞/ϵ. For a two dimensional array of N=54 qubits and a circuit with Control-Z gates, error rates better than state-of-the-art devices can be obtained on a laptop in a few hours. For more complex gates such as a swap gate followed by a controlled rotation, the error rate increases by a factor three for similar computing time.
With the help of high-resolution microscopy, scientists at MPQ successfully observed the transformation of a metal of magnetic polarons into a normal Fermi liquid. Furthermore, the team was able to measure novel correlations that could serve as a basis for theoretical models of strongly-correlated electrons.