{"id":7643,"date":"2024-02-19T15:33:47","date_gmt":"2024-02-19T10:03:47","guid":{"rendered":"https:\/\/www.isical.ac.in\/~pamu\/?post_type=event&#038;p=7643"},"modified":"2024-03-28T16:36:33","modified_gmt":"2024-03-28T11:06:33","slug":"on-the-power-of-geometrically-local-classical-and-quantum-circuits","status":"publish","type":"event","link":"https:\/\/oldweb.isical.ac.in\/~pamu\/event\/on-the-power-of-geometrically-local-classical-and-quantum-circuits\/","title":{"rendered":"On the power of geometrically-local classical and quantum circuits"},"content":{"rendered":"<p>We show a relation, based on parallel repetition of the Magic Square game, that can be solved, with probability exponentially close to 1 (worst-case input), by 1D (uniform) depth 2, geometrically-local, noisy (noise below a threshold), fan-in 4, quantum circuits. We show that the same relation cannot be solved, with an exponentially small success probability (averaged over inputs drawn uniformly), by 1D (non-uniform) geometrically-local, sub-linear depth, sub-quadratic size, classical circuits consisting of fan-in 2 NAND gates. Quantum and classical circuits are allowed to use input-independent (geometrically-non-local) resource states, that is entanglement and randomness respectively. To the best of our knowledge, previous best (analogous) depth separation for a task between quantum and classical circuits was constant v\/s sub-logarithmic, although for general (geometrically non-local) circuits. Our hardness result for classical circuits is based on a direct product theorem about classical communication protocols from Jain and Kundu [JK22]. As an application, we propose a protocol that can potentially demonstrate verifiable quantum advantage in the NISQ era. We also provide generalizations of our result for higher dimensional circuits as well as a wider class of Bell games.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We show a relation, based on parallel repetition of the Magic Square game, that can be solved, with probability exponentially close to 1 (worst-case input), by 1D (uniform) depth 2, geometrically-local, noisy (noise below a threshold), fan-in 4, quantum circuits&#8230;<\/p>\n","protected":false},"featured_media":7646,"template":"","categories":[107],"tags":[],"acf":[],"_links":{"self":[{"href":"https:\/\/oldweb.isical.ac.in\/~pamu\/wp-json\/wp\/v2\/event\/7643"}],"collection":[{"href":"https:\/\/oldweb.isical.ac.in\/~pamu\/wp-json\/wp\/v2\/event"}],"about":[{"href":"https:\/\/oldweb.isical.ac.in\/~pamu\/wp-json\/wp\/v2\/types\/event"}],"version-history":[{"count":1,"href":"https:\/\/oldweb.isical.ac.in\/~pamu\/wp-json\/wp\/v2\/event\/7643\/revisions"}],"predecessor-version":[{"id":7651,"href":"https:\/\/oldweb.isical.ac.in\/~pamu\/wp-json\/wp\/v2\/event\/7643\/revisions\/7651"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/oldweb.isical.ac.in\/~pamu\/wp-json\/wp\/v2\/media\/7646"}],"wp:attachment":[{"href":"https:\/\/oldweb.isical.ac.in\/~pamu\/wp-json\/wp\/v2\/media?parent=7643"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/oldweb.isical.ac.in\/~pamu\/wp-json\/wp\/v2\/categories?post=7643"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/oldweb.isical.ac.in\/~pamu\/wp-json\/wp\/v2\/tags?post=7643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}