On the power of geometrically-local classical and quantum circuits

• URL: http://arxiv.org/abs/2310.01540v1
• Date: Mon, 2 Oct 2023 18:27:53 GMT
• Title: On the power of geometrically-local classical and quantum circuits
• Authors: Kishor Bharti and Rahul Jain
• Abstract summary: We show a relation, based on parallel repetition of the Magic Square game, that can be solved, with probability exponentially close to $1$. We show that the same relation cannot be solved, with an exponentially small success probability. We propose a protocol that can potentially demonstrate verifiable quantum advantage in the NISQ era.
• Score: 6.011628409537168
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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, 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.

Related papers

• Pauli path simulations of noisy quantum circuits beyond average case [0.3277163122167433]
  For random quantum circuits on $n$ qubits of depth, the task of sampling from the output state can be efficiently performed classically using a Pauli path method. We derive sufficient conditions for simulatability in terms of noise rate and the fraction of gates that are T gates, and show that if noise is introduced at a faster rate, the simulation becomes classically easy.
  arXiv  Detail & Related papers  (2024-07-22T21:58:37Z)
• The power of shallow-depth Toffoli and qudit quantum circuits [3.212381039696143]
  One of the main goals of quantum circuit complexity is to find problems that can be solved by quantum shallow circuits but require more computational resources classically. We prove new separations between classical and quantum constant-depth circuits. In the infinite-size gateset case, these quantum circuit classes for higher-dimensional Hilbert spaces do not offer any advantage to standard qubit implementations.
  arXiv  Detail & Related papers  (2024-04-28T07:44:27Z)
• On verifiable quantum advantage with peaked circuit sampling [9.551919087634522]
  We show that getting $1/textpoly(n)$ peakedness from such circuits requires $tau_p = Omega(tau_r/n)0.19)$ with overwhelming probability. We also give numerical evidence that nontrivial peakedness is possible in this model.
  arXiv  Detail & Related papers  (2024-04-22T18:00:06Z)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  We perform classical simulations of the 127-qubit kicked Ising model, which was recently emulated using a quantum circuit with error mitigation. Our approach is based on the projected entangled pair operator (PEPO) in the Heisenberg picture. We develop a Clifford expansion theory to compute exact expectation values and use them to evaluate algorithms.
  arXiv  Detail & Related papers  (2023-08-06T10:24:23Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• On the relation between completely bounded and $(1,cb)$-summing maps with applications to quantum XOR games [65.51757376525798]
  We show that given a linear map from a general operator space into the dual of a C$*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  arXiv  Detail & Related papers  (2021-12-09T21:06:52Z)
• The principle of majorization: application to random quantum circuits [68.8204255655161]
  Three classes of circuits were considered: (i) universal, (ii) classically simulatable, and (iii) neither universal nor classically simulatable. We verified that all the families of circuits satisfy on average the principle of majorization. Clear differences appear in the fluctuations of the Lorenz curves associated to states.
  arXiv  Detail & Related papers  (2021-02-19T16:07:09Z)
• Interactive quantum advantage with noisy, shallow Clifford circuits [0.0]
  We show a strategy for adding noise tolerance to the interactive protocols of Grier and Schaeffer. A key component of this reduction is showing average-case hardness for the classical simulation tasks. We show that is true even for quantum tasks which are $oplus$L-hard to simulate.
  arXiv  Detail & Related papers  (2021-02-13T00:54:45Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates [0.0]
  We prove that $poly(t)cdot n1/D$-depth local random quantum circuits with two qudit nearest-neighbor gates are approximate $t$-designs in various measures. We also prove that anti-concentration is possible in depth O(log(n) loglog(n) using a different model.
  arXiv  Detail & Related papers  (2018-09-18T22:28:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.