|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)|
|Type of Article||17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)|
|Keywords||Computational Complexity (cs.CC), FOS: Computer and information sciences, FOS: Physical sciences, Quantum Physics (quant-ph)|
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.