In the recently published Nature Physics research paper, we, along with our colleague Dr. David Gosset, associate professor at the University of Waterloo's Institute of Quantum Computing, show that certain properties of shallow quantum circuits on a two-dimensional grid of qubits can be simulated classically in time that grows only linearly with the number of qubits.
When we began our current line of investigation, the goal was to study the structural property of the Clifford group, describing a set of transformations that generate entanglement, play an important role in quantum computing error correction, and are used in (randomized) benchmarking. In a series of one-thing-leads-to-another findings, however, we ended up discovering a new mathematical proof of quantum advantage – the elusive threshold at which quantum computers outperform classical machines in certain use cases.
Can the full computational power of noisy near-term quantum devices be unleashed, without paying the full price of quantum error correction? In the new paper, "Quantum advantage with noisy shallow circuits," an international team of researchers including myself seek to answer that question by proving a separation between the power of noisy quantum and that of noiseless classical computations, which obey certain technical restrictions.