Nolan Coble

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 $|\bra{0^{\otimes n}}C \ket{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 \cite{Mov19}. The previous best known algorithm for this problem used $O(2^{n^{1/3}}\poly(1/\epsilon))$ time to compute probabilities to within additive error $\epsilon$ \cite{BGM19}. Notably, the \cite{BGM19} paper included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: Constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings.

Neutral atom quantum computers and to a lesser extent trapped ions may suffer from atom loss. In this work, we investigate the impact of atom loss in long chains of trapped ions. Even though this is a relatively rare event, ion loss in long chains must be addressed because it destabilizes the entire chain resulting in the loss of all the qubits of the chain. We propose a solution to the chain loss problem based on (1) a quantum error correction code distributed over multiple long chains, (2) beacon qubits within each long chain to detect the loss of a chain, and (3) a decoder adapted to correct a combination of circuit faults and erasures after beacon qubits convert chain losses into erasures. We verify the chain loss correction capability of our scheme through circuit level simulations with a distributed $[[72,12,6]]$ BB code with beacon qubits.