Structure and symmetry in quantum verification

Main Question

Under what conditions can classical verification of quantum computation be done more efficiently than solving the problem on a quantum computer?

Vision

To bring together breakthrough classical techniques, new developments in classical simulation algorithms, and advances in the theory of classical computation and verification to attack this question.

Idea

To take advantage of the structural features of quantum circuits.

We will work on three different structural levels:

Methods that exploit the patterns or inhomogeneity of gate application in
quantum circuits

Algorithms that depend on the symmetries of the circuit

General circuits which are not known to have local symmetries but possess
general algebraic constraints.

Methodology

Start with basic structural features and move to more general cases:

Tensor Network algorithms and Separator theorems [Strelchuk]
Symmetric computation [Dawar]
Quantum proofs of proximity [Gur]