Measuring complexity of quantum experiments for classical simulation
Probing the classical complexity of quantum dynamics experiments
Computational Complexity
Summary
Quantum experiments can sometimes be simulated on regular computers even when they seem very complex. The authors introduce a new way to measure this complexity called reactivity, which looks at the entire experiment instead of just states or parts. They show that experiments with low reactivity are easier to simulate, understand, and speed up using classical computers. They also propose efficient methods called Pauli path spectroscopy to measure reactivity, even for experiments too complex to simulate directly.
What this means in practice
- •For quantum algorithm developers: Identify when quantum algorithms can be efficiently simulated classically by measuring their reactivity to avoid unnecessary quantum resource use.
- •For quantum hardware engineers: Use Pauli path spectroscopy to characterize quantum devices’ dynamic complexity beyond classical simulation limits for better hardware benchmarking.
Authors
Thomas Schuster, Andreas Elben
Abstract
A confluence of recent works has shown that many quantum circuits and dynamics are efficiently simulable by classical algorithms that track local information, even when conventional complexity measures such as the entanglement and magic are high. Here, we introduce a novel measure of complexity, the reactivity, to capture this new method of classical attack. Unlike conventional complexity measures, the reactivity does not capture a property of a quantum state or operator in isolation, but rather a quantum experiment as a whole. We provide numerical and rigorous evidence that quantum experiments with low reactivity are simple by a host of measures: they are efficient to classically simulate, learn, and fast-forward. This motivates the search for quantum experiments with high reactivity, which may evade these simplistic features. To this end, we introduce easily implementable experimental protocols---dubbed Pauli path spectroscopy---that allow one to efficiently measure the reactivity of any quantum experiment of interest. Our protocols are applicable even when the experiment itself is beyond the reach of classical simulation.