Boundaries of classical simulability of quantum systems

6 problems

• Does absence of barren plateaus imply classical simulability?

  Open

  Variational quantum algorithms tune circuit settings to lower a cost, but most become untrainable because the cost changes exponentially little as the settings vary (a barren plateau). It is conjectured that every circuit family provably free of this flatness can also be imitated by a classical computer, which would remove the point of using it.

• Efficient contraction of PEPS for gapped two-dimensional ground states

  Partially resolved

  Two-dimensional quantum states can be written compactly as networks of small tensors (PEPS, projected entangled pair states), but extracting numbers from these networks is in general very hard. Whether it becomes easy for physically relevant states with an energy gap is open.

• Photon-loss threshold for classical simulability of Gaussian boson sampling

  Partially resolved

  Gaussian boson sampling sends squeezed light through a large optical network and records where photons arrive; it was used to claim quantum advantage. Losing photons makes the task easier for classical computers, and the loss level at which it becomes easy is not known exactly.

• Finite-size boundary of classical hardness for noisy random circuit sampling

  Contested

  At a fixed error rate per gate, very large random circuits become easy for classical computers, yet the experiments done so far are believed to be hard. Where the crossover lies, in qubit number, depth and noise rate, is not known.

• Classical sampling of random circuits with non-unital noise

  Open

  Noise that scrambles qubits toward randomness makes deep quantum circuits easy to imitate classically. Noise that pushes qubits toward a fixed state, as energy loss does, behaves differently, and whether such noisy circuits can be imitated is open.

• Exponential lower bound on the stabilizer rank of magic states

  Open

  Circuits built from one special gate family can be simulated fast classically; adding extra 'magic' states makes them universal. The best classical simulators run in time set by a number called the stabilizer rank, and no one has proven that it must grow exponentially.