2026-10-11T04:24:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25314 2026-03-19T12:03:23Z ddc:004 open_access

Identity Check Problem for Shallow Quantum Circuits Bravyi, Sergey Parham, Natalie Tran, Minh Quantum computing Identity check problem quantum circuits classical simulation of quantum computation shallow circuits Verifying that a quantum circuit correctly implements a desired transformation is essential for validating quantum algorithms. We consider the closely related identity check problem: given a quantum circuit U, estimate the diamond-norm distance between U and the identity channel. Ji and Wu showed that estimating this distance to within an additive 1/poly error is QMA-hard, even when U is constant-depth and 1D local - ruling out efficient algorithms in this regime. We show that this hardness barrier disappears if one seeks a constant multiplicative-approximation instead. We present a classical algorithm that, for shallow geometrically local D-dimensional circuits, approximates the distance to the identity within a factor α = D+1, provided that the circuit is sufficiently close to the identity. The runtime of the algorithm scales linearly with the number of qubits for any constant circuit depth and spatial dimension. We also show that the operator-norm distance to the identity ‖U-I‖ can be efficiently approximated within a factor α = 5 for shallow 1D circuits and, under a certain technical condition, within a factor α = 2D+3 for shallow D-dimensional circuits. A numerical implementation of the identity check algorithm is reported for 1D Trotter circuits with up to 100 qubits. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sergey Bravyi and Natalie Parham and Minh Tran 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.27 urn:nbn:de:0030-drops-253147 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.27 eng https://creativecommons.org/licenses/by/4.0/legalcode