Fast Stabiliser Simulation with Quadratic Form Expansions

• URL: http://arxiv.org/abs/2109.08629v3
• Date: Tue, 13 Sep 2022 12:17:28 GMT
• Title: Fast Stabiliser Simulation with Quadratic Form Expansions
• Authors: Niel de Beaudrap and Steven Herbert
• Abstract summary: This is a representation of a quantum state which specifies a formula for the expansion in the standard basis. We show how, with deft management of the quadratic form expansion representation, we may simulate individual stabiliser operations in $O(n2)$ time.
• Score: 0.8122270502556371
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper builds on the idea of simulating stabiliser circuits through transformations of quadratic form expansions. This is a representation of a quantum state which specifies a formula for the expansion in the standard basis, describing real and imaginary relative phases using a degree-2 polynomial over the integers. We show how, with deft management of the quadratic form expansion representation, we may simulate individual stabiliser operations in $O(n^2)$ time matching the overall complexity of other simulation techniques [arXiv:quant-ph/0406196, arXiv:quant-ph/0504117, arXiv:1808.00128]. Our techniques provide economies of scale in the time to simulate simultaneous measurements of all (or nearly all) qubits in the standard basis. Our techniques also allow single-qubit measurements with deterministic outcomes to be simulated in constant time. We also describe throughout how these bounds may be tightened when the expansion of the state in the standard basis has relatively few terms (has low 'rank'), or can be specified by sparse matrices. Specifically, this allows us to simulate a 'local' stabiliser syndrome measurement in time $O(n)$, for a stabiliser code subject to Pauli noise -- matching what is possible using techniques developed by Gidney [arXiv:2103.02202] without the need to store which operations have thus far been simulated.

Related papers

• Quantum Calculation for Two-Stream Instability and Advection Test of Vlasov-Maxwell Equations: Numerical Evaluation of Hamiltonian Simulation [0.0]
  We develop a quantum-classical hybrid Vlasov-Maxwell solver. We perform numerical simulation of a 1D advection test and a 1D1V two-stream instability test. Our quantum algorithm is robust under larger time steps compared with classical algorithms.
  arXiv  Detail & Related papers  (2024-08-21T11:56:55Z)
• Simulation of quantum optics by coherent state decomposition [0.0]
  We introduce a framework for simulating quantum optics by decomposing the system into a finite rank (number of terms) superposition of coherent states. We demonstrate that linear optical simulations with the $n$ photons initially in the same mode scales efficiently, as $O(m2 n)$.
  arXiv  Detail & Related papers  (2023-05-26T17:14:27Z)
• The vacuum provides quantum advantage to otherwise simulatable architectures [49.1574468325115]
  We consider a computational model composed of ideal Gottesman-Kitaev-Preskill stabilizer states. We provide an algorithm to calculate the probability density function of the measurement outcomes.
  arXiv  Detail & Related papers  (2022-05-19T18:03:17Z)
• 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)
• Classical simulation of quantum circuits with partial and graphical stabiliser decompositions [0.0]
  We show how, by considering certain non-stabiliser entangled states which have more favourable decompositions, we can speed up simulations. We additionally find a new technique of partial stabiliser decompositions that allow us to trade magic states for stabiliser terms. With our techniques we manage to reliably simulate 50-qubit 1400 T-count hidden shift circuits in a couple of minutes on a consumer laptop.
  arXiv  Detail & Related papers  (2022-02-18T14:04:30Z)
• Quantum dynamics simulations beyond the coherence time on NISQ hardware by variational Trotter compression [0.0]
  We demonstrate a post-quench dynamics simulation of a Heisenberg model on present-day IBM quantum hardware. We show how to measure the required cost function, the overlap between the time-evolved and variational states, on present-day hardware. In addition to carrying out simulations on real hardware, we investigate the performance and scaling behavior of the algorithm with noiseless and noisy classical simulations.
  arXiv  Detail & Related papers  (2021-12-23T15:44:47Z)
• Improved Graph Formalism for Quantum Circuit Simulation [77.34726150561087]
  We show how to efficiently simplify stabilizer states to canonical form. We characterize all linearly dependent triplets, revealing symmetries in the inner products. Using our novel controlled-Pauli $Z$ algorithm, we improve runtime for inner product computation from $O(n3)$ to $O(nd2)$ where $d$ is the maximum degree of the graph.
  arXiv  Detail & Related papers  (2021-09-20T05:56:25Z)
• Hybridized Methods for Quantum Simulation in the Interaction Picture [69.02115180674885]
  We provide a framework that allows different simulation methods to be hybridized and thereby improve performance for interaction picture simulations. Physical applications of these hybridized methods yield a gate complexity scaling as $log2 Lambda$ in the electric cutoff. For the general problem of Hamiltonian simulation subject to dynamical constraints, these methods yield a query complexity independent of the penalty parameter $lambda$ used to impose an energy cost.
  arXiv  Detail & Related papers  (2021-09-07T20:01:22Z)
• Constant-Depth Circuits for Dynamic Simulations of Materials on Quantum Computers [0.0]
  We present a method for generating circuits that are constant in depth with increasing simulation time for a subset of one-dimensional materials Hamiltonians. By removing the effective limit on the number of feasibly simulatable time-steps, the constant-depth circuits enable Trotter error to be made negligibly small. This paves the way for simulations of long-time dynamics for scientifically and technologically relevant quantum materials.
  arXiv  Detail & Related papers  (2021-03-12T17:47:02Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)
• 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.