Title | Approximating Output Probabilities of Shallow Quantum Circuits which are Geometrically-local in any Fixed Dimension |

Publication Type | Journal Article |

Year of Publication | 2022 |

Authors | Dontha, S, Tan, SJie Samuel, Smith, S, Choi, S, Coudron, M |

Journal | Leibniz International Proceedings in Informatics (LIPIcs) |

Volume | 232 |

Pages | 9:1--9:17 |

Date Published | 4/7/2022 |

Type of Article | 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022) |

ISSN | 1868-8969 |

ISBN Number | 978-3-95977-237-2 |

Keywords | Computational Complexity (cs.CC), FOS: Computer and information sciences, FOS: Physical sciences, Quantum Physics (quant-ph) |

Abstract | We present a classical algorithm that, for any D-dimensional geometrically-local, quantum circuit C of polylogarithmic-depth, and any bit string x∈0,1n, can compute the quantity |<x|C|0⊗n>|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≤3, we can now handle any fixed dimension D>3. |

URL | https://arxiv.org/abs/2202.08349 |

DOI | 10.48550/ARXIV.2202.08349 |