**Title:** Quasi-Polynomial Time Approximation of Output Probabilities of Geometrically-Local, Shallow Quantum Circuits

**Abstract: ** We present a classical algorithm that, for any geometrically-local, constant-depth quantum circuit C, and any bit string x \in \{0,1\}^n, can compute the quantity |<0^n|C|x>|^2 to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is #P-hard to compute this same quantity to within 2^{-n^2} additive error [Mov20, KMM21]. The previous best known algorithm for this problem used O(2^{n^{1/3}}\poly(1/\epsilon)

Our algorithm has a Divide-and-Conquer structure, demonstrating how to approximate the desired quantity via several instantiations of the same problem type, each involving 3D-local circuits on at most half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from the entanglement that may exist between the different circuit ``pieces" produced this way. We believe that the division step, which makes a novel use of block-encodings, together with an Inclusion-Exclusion style argument to reduce error, may be of interest for future research on constant-depth quantum circuits. Our algorithm for 3D circuits can be extended to constant depth quantum circuits which are geometrically local in K-dimensions for any fixed constant K.

## All scheduled dates:

### Upcoming

No Upcoming activities yet