Imperfections Lower the Simulation Cost of Quantum Computers

(Physics.aps) With a few quantum bits, an ideal quantum computer can process vast amounts of information in a coordinated way, making it significantly more powerful than a classical counterpart. This predicted power increase will be great for users but is bad for physicists trying to simulate on a classical computer how an ideal quantum computer will behave. Now, a trio of researchers has shown that they can substantially reduce the resources needed to do these simulations if the quantum computer is “imperfect”.
Yiqing Zhou, of the University of Illinois at Urbana–Champaign, and her two colleagues focused on algorithms for classically replicating “imperfect” quantum computers, which are also known as NISQ (noisy intermediate-scale quantum) devices. Today’s state-of-the-art quantum computers—including Sycamore—are NISQ devices. The algorithms the team used are based on so-called tensor network methods, specifically matrix product states (MPS), which are good for simulating noise and so are naturally suited for studying NISQ devices. MPS methods approximate low-entangled quantum states with simpler structures, so they provide a data-compression-like protocol that can make it less computationally expensive to classically simulate imperfect quantum computers.
Zhou and colleagues first consider a random 1D quantum circuit made of neighboring, interleaved two-qubit gates and single-qubit random unitary operations. The trio demonstrate that they can exactly simulate any imperfect quantum circuit if D and N are small enough and is set to a value within reach of a classical computer. They can do that because shallow quantum circuits can only create a small amount of entanglement, which is fully captured by a moderate .
How do their results relate to the quantum advantage claims by Google? As they stand, they do not weaken or refute claims.
So, what’s next? One natural question is, Can the approach here be transferred to efficiently simulate other aspects of quantum computing, such as quantum error correction? The circuits the trio considered are essentially random, whereas quantum error correction circuits are more ordered by design. That means that updates to the new algorithm are needed to study such systems.