In this case, the team made a couple of key variations. The first is that it mostly performed what are called Clifford gates, which are relatively easy to simulate on classical hardware. But it sprinkled in a few non-Clifford gates (specifically T gates) of a specific type chosen in part because they are less prone to error. “Z rotations (including T gates) are special in our hardware: they are implemented by virtual frame tracking and do not add extra noise,” the paper said.
But the T gates also help ensure that this is especially hard to simulate on a classical computer. “It’s got a stronger complexity argument because of the [T gates], which you can prove on average is exponentially hard to sample for a classical computer,” Gambetta told Ars. That will make it very challenging for classical algorithms to catch up.
The work also linked in a few additional qubits around the periphery of those used for the algorithm, arranged so that gentle measurements performed during the operations could detect whether errors had occurred; if they were detected, the results were discarded. (Note that this would also throw out valid results that were flagged by an erroneous read of these additional qubits.)
The result was an algorithm that “combines the broad output statistics of hard sampling problems with circuit structure that can be exploited for error detection and fidelity certification,” the team said.
The last of the new results comes from quantum software developer Algorithmiq, which used an algorithm similar to the one in Google’s “quantum echoes” work. A set of gates first alters a quantum system, after which the process is reversed. Additional operations performed during the reversal prevent the system from returning to its original state—instead, the noise creates an imperfect “echo” of the forward process. As with one of the earlier works, attempts to simulate this on classical hardware require some simplification, and different simplification methods yield different results. By its nature, then, the problem is beyond the reach of classical hardware.