



02622nas a2200253   4500008004100000020002200041022001400063245012000077210006900197260001300266300001400279490000800293520178700301653003702088653004302125653002702168653003102195100002102226700002502247700001902272700001902291700002102310856003702331       2022                        eng d  a978-3-95977-237-2  a1868-896900aApproximating Output Probabilities of Shallow Quantum Circuits which are Geometrically-local in any Fixed Dimension0 aApproximating Output Probabilities of Shallow Quantum Circuits w  c4/7/2022  a9:1--9:170 v2323 a<p>We present a classical algorithm that, for any D-dimensional geometrically-local, quantum circuit C of polylogarithmic-depth, and any bit string x&isin;0,1n, can compute the quantity |&lt;x|C|0&otimes;n&gt;|2 to within any inverse-polynomial additive error in quasi-polynomial time, for any fixed dimension D. This is an extension of the result [CC21], 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 standard use of Matrix Product States, known for decades, the D=2 case required novel and interesting techniques introduced in [BGM19]. Extending to the case D=3 was even more laborious and required further new techniques introduced in [CC21]. 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&le;3, we can now handle any fixed dimension D&gt;3.<br />Our algorithm uses the Divide-and-Conquer framework of [CC21] to approximate the desired quantity via several instantiations of the same problem type, each involving D-dimensional 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 Dth dimension is so small that they can effectively be regarded as (D&minus;1)-dimensional problems by absorbing the small width in the Dth 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 [CC21] still hold in higher dimensions, which requires small modifications to the analysis in some places.</p>10aComputational Complexity (cs.CC)10aFOS: Computer and information sciences10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aDontha, Suchetan1 aTan, Shi, Jie Samuel1 aSmith, Stephen1 aChoi, Sangheon1 aCoudron, Matthew  uhttps://arxiv.org/abs/2202.08349