Complexity test offers new perspective on small quantum computers
Chris Cesare, Joint Quantum Institute
But while the power of quantum computers remains unproven, exploring the crossover from low complexity to high complexity could offer fresh insights about the capabilities of early quantum devices, says Alexey Gorshkov, a JQI and QuICS Fellow who is a co-author of the new paper. Sampling complexity has remained an underappreciated tool, Gorshkov says, largely because small quantum devices have only recently become reliable. Deshpande, Gorshkov and their colleagues proved that there is a sharp transition between how easy and hard it is to simulate boson sampling on an ordinary computer. If you start with a few well-separated bosons and only let them hop around briefly, the sampling complexity remains low and the problem is easy to simulate. Gorshkov says that looking for changes like this in sampling complexity may help uncover physical transitions in other quantum tasks or experiments.