A Fourier analysis framework for approximate classical simulations of quantum circuits

• URL: http://arxiv.org/abs/2410.13856v1
• Date: Thu, 17 Oct 2024 17:59:34 GMT
• Title: A Fourier analysis framework for approximate classical simulations of quantum circuits
• Authors: Cristina Cirstoiu,
• Abstract summary: I present a framework that applies harmonic analysis of groups to circuits with a structure encoded by group parameters. I also discuss generalisations to homogeneous spaces, qudit systems and a way to analyse random circuits via matrix coefficients of irreducible representations.
• Score: 0.0
• License:
• Abstract: What makes a class of quantum circuits efficiently classically simulable on average? I present a framework that applies harmonic analysis of groups to circuits with a structure encoded by group parameters. Expanding the circuits in a suitable truncated multi-path operator basis gives algorithms to evaluate the Fourier coefficients of output distributions or expectation values that are viewed as functions on the group. Under certain conditions, a truncated Fourier series can be efficiently estimated with guaranteed mean-square convergence. For classes of noisy circuits, it leads to algorithms for sampling and mean value estimation under error models with a spectral gap, where the complexity increases exponentially with the gap's inverse and polynomially with the circuit's size. This approach unifies and extends existing algorithms for noisy parametrised or random circuits using Pauli basis paths. For classes of noiseless circuits, mean values satisfying Lipschitz continuity can be on average approximated using efficient sparse Fourier decompositions. I also discuss generalisations to homogeneous spaces, qudit systems and a way to analyse random circuits via matrix coefficients of irreducible representations.

Related papers

• Variance-Reducing Couplings for Random Features [57.73648780299374]
  Random features (RFs) are a popular technique to scale up kernel methods in machine learning. We find couplings to improve RFs defined on both Euclidean and discrete input spaces. We reach surprising conclusions about the benefits and limitations of variance reduction as a paradigm.
  arXiv  Detail & Related papers  (2024-05-26T12:25:09Z)
• Unified framework for efficiently computable quantum circuits [0.0]
  Quantum circuits consisting of Clifford and matchgates are two classes of circuits that are known to be efficiently simulatable on a classical computer. We introduce a unified framework that shows in a transparent way the special structure that allows these circuits can be efficiently simulatable.
  arXiv  Detail & Related papers  (2024-01-16T08:04:28Z)
• Randomized semi-quantum matrix processing [0.0]
  We present a hybrid quantum-classical framework for simulating generic matrix functions. The method is based on randomization over the Chebyshev approximation of the target function. We prove advantages on average depths, including quadratic speed-ups on costly parameters.
  arXiv  Detail & Related papers  (2023-07-21T18:00:28Z)
• Fourier expansion in variational quantum algorithms [1.4732811715354455]
  We focus on the class of variational circuits, where constant gates are Clifford gates and parameterized gates are generated by Pauli operators. We give a classical algorithm that computes coefficients of all trigonometric monomials up to a degree $m$ in time bounded by $mathcalO(N2m)$.
  arXiv  Detail & Related papers  (2023-04-07T18:00:01Z)
• Approximating outcome probabilities of linear optical circuits [0.0]
  We propose classical algorithms for approximating outcome probabilities of a linear optical circuit. Our scheme renders an efficient estimation of outcome probabilities with precision depending on the classicality of the circuit. Our study sheds light on the power of linear optics, providing plenty of quantum-inspired algorithms for problems in computational complexity.
  arXiv  Detail & Related papers  (2022-11-14T08:21:51Z)
• Efficient simulation of Gottesman-Kitaev-Preskill states with Gaussian circuits [68.8204255655161]
  We study the classical simulatability of Gottesman-Kitaev-Preskill (GKP) states in combination with arbitrary displacements, a large set of symplectic operations and homodyne measurements. For these types of circuits, neither continuous-variable theorems based on the non-negativity of quasi-probability distributions nor discrete-variable theorems can be employed to assess the simulatability.
  arXiv  Detail & Related papers  (2022-03-21T17:57:02Z)
• Faster Born probability estimation via gate merging and frame optimisation [3.9198548406564604]
  Outcome probabilities of any quantum circuit can be estimated using Monte Carlo sampling. We propose two classical sub-routines: circuit gate optimisation and frame optimisation. We numerically demonstrate that our methods provide improved scaling in the negativity overhead for all tested cases of random circuits.
  arXiv  Detail & Related papers  (2022-02-24T14:18:34Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  We show that discretizations yielding consistent estimators have the property of invariance under coarse-graining' This result explains why combining differencing schemes for derivatives reconstruction and local-in-time inference approaches does not work for time series analysis of second or higher order differential equations.
  arXiv  Detail & Related papers  (2021-01-16T17:11:02Z)
• 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)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19:00:00Z)

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.