Abstract
We present a classical algorithm that, for any Ddimensional geometricallylocal, quantum circuit C of polylogarithmicdepth, and any bit string x ∈ {0,1}ⁿ, can compute the quantity <xC0^{⊗ n}>² to within any inversepolynomial additive error in quasipolynomial time, for any fixed dimension D. This is an extension of the result [Nolan J. Coble and Matthew Coudron, 2021], which originally proved this result for D = 3. To see why this is interesting, note that, while the D = 1 case of this result follows from a standard use of Matrix Product States, known for decades, the D = 2 case required novel and interesting techniques introduced in [Sergy Bravyi et al., 2020]. Extending to the case D = 3 was even more laborious, and required further new techniques introduced in [Nolan J. Coble and Matthew Coudron, 2021]. Our work here shows that, while handling each new dimension has historically required a new insight, and fixed algorithmic primitive, based on known techniques for D ≤ 3, we can now handle any fixed dimension D > 3.
Our algorithm uses the DivideandConquer framework of [Nolan J. Coble and Matthew Coudron, 2021] to approximate the desired quantity via several instantiations of the same problem type, each involving Ddimensional circuits on about half the number of qubits as the original. This division step is then applied recursively, until the width of the recursively decomposed circuits in the D^{th} dimension is so small that they can effectively be regarded as (D1)dimensional problems by absorbing the small width in the D^{th} dimension into the qudit structure at the cost of a moderate increase in runtime. The main technical challenge lies in ensuring that the more involved portions of the recursive circuit decomposition and error analysis from [Nolan J. Coble and Matthew Coudron, 2021] still hold in higher dimensions, which requires small modifications to the analysis in some places. Our work also includes some simplifications, corrections and clarifications of the use of blockencodings within the original classical algorithm in [Nolan J. Coble and Matthew Coudron, 2021].
BibTeX  Entry
@InProceedings{dontha_et_al:LIPIcs.TQC.2022.9,
author = {Dontha, Suchetan and Tan, Shi Jie Samuel and Smith, Stephen and Choi, Sangheon and Coudron, Matthew},
title = {{Approximating Output Probabilities of Shallow Quantum Circuits Which Are GeometricallyLocal in Any Fixed Dimension}},
booktitle = {17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
pages = {9:19:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772372},
ISSN = {18688969},
year = {2022},
volume = {232},
editor = {Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16516},
URN = {urn:nbn:de:0030drops165163},
doi = {10.4230/LIPIcs.TQC.2022.9},
annote = {Keywords: LowDepth Quantum Circuits, Matrix Product States, BlockEncoding}
}
Keywords: 

LowDepth Quantum Circuits, Matrix Product States, BlockEncoding 
Collection: 

17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022) 
Issue Date: 

2022 
Date of publication: 

04.07.2022 