2026-07-31T15:23:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16516 2024-03-06T10:57:43Z ddc:004 open_access

Approximating Output Probabilities of Shallow Quantum Circuits Which Are Geometrically-Local in Any Fixed Dimension Dontha, Suchetan Tan, Shi Jie Samuel Smith, Stephen Choi, Sangheon Coudron, Matthew Low-Depth Quantum Circuits Matrix Product States Block-Encoding We present a classical algorithm that, for any D-dimensional geometrically-local, quantum circuit C of polylogarithmic-depth, and any bit string x ∈ {0,1}ⁿ, can compute the quantity |<x|C|0^{⊗ n}>|² to within any inverse-polynomial additive error in quasi-polynomial 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 Divide-and-Conquer framework of [Nolan J. Coble and Matthew Coudron, 2021] 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 D^{th} dimension is so small that they can effectively be regarded as (D-1)-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 block-encodings within the original classical algorithm in [Nolan J. Coble and Matthew Coudron, 2021]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Suchetan Dontha and Shi Jie Samuel Tan and Stephen Smith and Sangheon Choi and Matthew Coudron 2022 Is Part Of LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2022.9 urn:nbn:de:0030-drops-165163 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.9 eng https://creativecommons.org/licenses/by/4.0/legalcode