{"id":634425,"date":"2026-08-13T05:12:32","date_gmt":"2026-08-13T05:12:32","guid":{"rendered":"https:\/\/www.europesays.com\/ie\/634425\/"},"modified":"2026-08-13T05:12:32","modified_gmt":"2026-08-13T05:12:32","slug":"3d-local-noisy-shallow-quantum-circuits-defeat-unbounded-fan-in-classical-circuits","status":"publish","type":"post","link":"https:\/\/www.europesays.com\/ie\/634425\/","title":{"rendered":"3D-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits"},"content":{"rendered":"

We show that noisy shallow 3D-local quantum circuits solve a computational task with higher probability than (ideal) unbounded fan-in classical \\({{\\mathsf{AC}}}^{0}\\)-circuits of a certain subexponential size. This can thus be seen as a fault-tolerant counterpart to the work6<\/a>. More precisely, we show the following (see\u00a0Supplementary Note<\/a>[Theorems 6.7 and 7.10]9<\/a>):<\/p>\n

Theorem 1<\/p>\n

(Fault-tolerant quantum advantage against \\({{\\mathsf{AC}}}^{0}\\), informal version) Let (\u03bc,\u00a0\u03bd)\u00a0\u2208\u00a0(0,\u00a01)2 with \u03bd\u00a0<\u00a01\u00a0\u2212\u00a0\u03bc be arbitrary. There is a computational problem with the following properties:<\/p>\n

    \n
  1. \n (i)<\/p>\n

    The problem is beyond the reach of \\({{\\mathsf{AC}}}^{0}\\)-circuits: Any \\({{\\mathsf{AC}}}^{0}\\)-circuit solving the problem with probability at least \u03bd on average over a randomly chosen instance has superpolynomial size.<\/p>\n<\/li>\n

  2. \n (ii)<\/p>\n

    The problem can be solved with average probability at least 1\u00a0\u2212\u00a0\u03bc by a 3D-local shallow quantum circuit even in the presence of local stochastic noise. That is, the quantum advantage can be observed using a shallow, noisy quantum circuit which only involves nearest-neighbor gates on qubits arranged on a regular 3D lattice.<\/p>\n<\/li>\n<\/ol>\n

    Our result thus strengthens the findings of8<\/a>: While requiring a comparable amount of (imperfect) quantum resources\/capabilities, and only local operations in 3D, it establishes a quantum advantage against \\({{\\mathsf{AC}}}^{0}\\) instead of only \\({{\\mathsf{NC}}}^{0}\\). In addition, contrary to earlier work, our result features a classical\u2013quantum gap (1\u00a0\u2212\u00a0\u03bc)\u00a0\u2212\u00a0\u03bd (difference of success probabilities) arbitrarily close to 1, a fact we establish by using Raz\u2019s parallel repetition result10<\/a>,11<\/a> for one-round two-player games.<\/p>\n

    From single-qubit gate teleportation to complexity theory<\/p>\n

    Our result is obtained by identifying a particularly simple computational problem which is motivated by what we call the single-qubit gate-teleportation circuit (see Fig.\u00a01<\/a> and ref. 12<\/a>). This circuit is a concatenation of multiple applications of the standard gate-teleportation procedure13<\/a> for single-qubit Clifford gates, except for the fact that the final \u201cPauli correction” is not applied \u2013 we are only interested in the measurement outcomes produced in the repeated gate-teleportation procedure. In more detail, the single-qubit gate-teleportation circuit is a classically controlled Clifford circuit taking n single-qubit Clifford elements C0,\u00a0\u2026,\u00a0Cn\u22121 as input, and outputting the result of n Bell measurements, i.e., a sequence of n Pauli observables P0,\u00a0\u2026,\u00a0Pn\u22121 (corrections in gate-teleportation).<\/p>\n

    Fig. 1: The gate-teleportation circuit.<\/b>\"Fig.<\/p>\n

    \\({U}_{n}^{{\\mathsf{Telep}}}\\) is a classically controlled Clifford circuit. It takes as input n single-qubit Clifford group elements (C0,\u00a0\u2026,\u00a0Cn\u22121). Each of these is applied to half of a\u00a0maximally entangled state \\(\\left\\vert \\Phi \\right\\rangle={2}^{-1\/2}(\\left\\vert 00\\right\\rangle+\\left\\vert 11\\right\\rangle )\\) (i.e., this constitutes a classically controlled single-qubit Clifford gate.) If Bell measurements are performed on pairs of qubits (shifted by one), the output (P0,\u00a0\u2026,\u00a0Pn\u22121) is an n-tuple of Paulis.<\/p>\n

    The computational problem we consider is the following: Given an input (C0,\u00a0\u2026,\u00a0Cn\u22121), output a sequence (P0,\u00a0\u2026,\u00a0Pn\u22121) of Paulis that occurs with nonzero probability in the output distribution of the gate-teleportation circuit. This can be formulated succinctly as follows: a correct output is one that satisfies <\/p>\n

    $${{\\rm{tr}}}({P}_{n-1}{C}_{n-1}\\cdots {P}_{0}{C}_{0})\\,\\ne \\,0.$$<\/p>\n

    \n (1)\n <\/p>\n

    For more details see the\u00a0Supplementary Note<\/a>[Section 2]9<\/a>.<\/p>\n

    On our route to establishing a quantum advantage of noisy shallow 3D-local quantum circuits against \\({{\\mathsf{AC}}}^{0}\\), we show the following result for (ideal) 1D-local quantum circuits (see\u00a0Supplementary Note<\/a>[Corollary 5.4]9<\/a>).<\/p>\n

    Theorem 2<\/p>\n

    (Single-qubit gate teleportation yields a quantum advantage against \\({{\\mathsf{AC}}}^{0}\\), informal version) Let \\({{\\mathcal{C}}}\\) be an \\({{\\mathsf{AC}}}^{0}\\)-circuit which, for a uniformly chosen sequence \\(C=({C}_{0},\\ldots,{C}_{n-1})\\in {{\\mathsf{Cliff}}}^{n}\\) of n single-qubit Clifford gates, produces \u2013 with probability at least 0.986 on average \u2013 a sequence \\(({P}_{0},\\ldots,{P}_{n-1})\\in {{\\mathsf{Pauli}}}^{n}\\) which occurs with non-zero probability in the output distribution of the single-qubit gate-teleportation circuit on input C. Then the size of \\({{\\mathcal{C}}}\\) is superpolynomial (in fact subexponential). On the other hand, this problem is solved with certainty by a 1D-local \\({{\\mathsf{QNC}}}^{0}\\) circuit.<\/p>\n

    This improves our result12<\/a> where we showed that the\u00a0single-qubit gate-teleportation problem cannot be solved by an \\({{\\mathsf{NC}}}^{0}\\) circuit.<\/p>\n

    Theorem 2 gives a version applicable for the proof of Theorem 6.7 with parameter \u03bd\u00a0=\u00a00.986. In Section 7 of the\u00a0Supplementary Note<\/a> (Theorem 7.10), we show that this can be replaced by an arbitrary constant \u03bd\u00a0\u2208\u00a0(0,\u00a01) by considering a relation obtained by parallel repetition. This proof relies on a variant of Raz\u2019s parallel repetition for nonlocal games10<\/a>,11<\/a>.<\/p>\n

    In the terminology of14<\/a>, Theorem 2 states that the computational problem of \u201cpossibilistically\u201d simulating the single-qubit gate-teleportation circuit is infeasible for \\({{\\mathsf{AC}}}^{0}\\)-circuits of polynomial size. The 1D-locality of the single-qubit gate-teleportation is what ultimately yields our fault-tolerant quantum advantage proposal with a 3D-local quantum circuit. In contrast, the so-called relaxed parity-halving problem considered by the authors of6<\/a>,15<\/a> does not have a simple locality structure, and is arguably more complex.<\/p>\n

    This quantum advantage demonstration based on the single-qubit gate-teleportation circuit shares a few attractive average-case hardness features with prior work such as6<\/a>,16<\/a>: The bound on the classical circuits considered here involves the average over a fully random input. In contrast, the results of5<\/a>,8<\/a> (as well as our results for the noise-tolerant setup) require restricting to a subset of inputs corresponding to valid problem instances.<\/p>\n","protected":false},"excerpt":{"rendered":"We show that noisy shallow 3D-local quantum circuits solve a computational task with higher probability than (ideal) unbounded…\n","protected":false},"author":2,"featured_media":634426,"comment_status":"","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","_share_on_mastodon":"0"},"categories":[271],"tags":[1096,18,1099,19,17,1100,452,1097,133],"class_list":["post-634425","post","type-post","status-publish","format-standard","has-post-thumbnail","category-physics","tag-computer-science","tag-eire","tag-humanities-and-social-sciences","tag-ie","tag-ireland","tag-multidisciplinary","tag-physics","tag-quantum-information","tag-science"],"share_on_mastodon":{"url":"https:\/\/pubeurope.com\/@ie\/117086490932122172","error":""},"_links":{"self":[{"href":"https:\/\/www.europesays.com\/ie\/wp-json\/wp\/v2\/posts\/634425","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.europesays.com\/ie\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.europesays.com\/ie\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.europesays.com\/ie\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.europesays.com\/ie\/wp-json\/wp\/v2\/comments?post=634425"}],"version-history":[{"count":0,"href":"https:\/\/www.europesays.com\/ie\/wp-json\/wp\/v2\/posts\/634425\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.europesays.com\/ie\/wp-json\/wp\/v2\/media\/634426"}],"wp:attachment":[{"href":"https:\/\/www.europesays.com\/ie\/wp-json\/wp\/v2\/media?parent=634425"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.europesays.com\/ie\/wp-json\/wp\/v2\/categories?post=634425"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.europesays.com\/ie\/wp-json\/wp\/v2\/tags?post=634425"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}