PaperlayerView exact revision on arXiv

Source-linked AI summary

What limits the simulation of quantum computers?

Yiqing Zhou, E. Miles Stoudenmire, Xavier Waintal

arXiv:2002.07730v2quant-phcond-mat.str-el

TL;DR

Perfect quantum computers are exponentially hard to simulate, raising the question of whether noisy real devices remain difficult to simulate classically. This paper uses approximate MPS wavefunctions to model their finite fidelity with linear scaling in qubit number and circuit depth. It finds that experimentally relevant fidelities can be reproduced at moderate cost, while improving beyond a finite error floor becomes exponentially expensive.

  • Problem

    Determining the classical difficulty of simulating noisy quantum computers is important because perfect-state simulation is exponentially costly, while real devices have finite fidelity and competing estimates of simulation cost.

  • Method

    The authors use matrix product states to compress quantum wavefunctions with low to moderate entanglement, introducing a controlled finite error per two-qubit gate.

  • Results

    The algorithm runs with computing time linear in N and D, reproduces approximately 99% fidelity at moderate cost, and reaches a finite fidelity limit beyond which improvement is exponentially costly.

  • Takeaways & Limitations

    Fidelities in the 99% range correspond to a much smaller accessible fraction of Hilbert space than the full 2^N dimension suggests.

Abstract

from arXiv · show

It is imperative that useful quantum computers be very difficult to simulate classically; otherwise classical computers could be used for the applications envisioned for the quantum ones. Perfect quantum computers are unarguably exponentially difficult to simulate: the classical resources required grow exponentially with the number of qubits $N$ or the depth $D$ of the circuit. Real quantum computing devices, however, are characterized by an exponentially decaying fidelity $\mathcal{F} \sim (1-ε)^{ND}$ with an error rate $ε$ per operation as small as $\approx 1\%$ for current devices. In this work, we demonstrate that real quantum computers can be simulated at a tiny fraction of the cost that would be needed for a perfect quantum computer. Our algorithms compress the representations of quantum wavefunctions using matrix product states (MPS), which capture states with low to moderate entanglement very accurately. This compression introduces a finite error rate $ε$ so that the algorithms closely mimic the behavior of real quantum computing devices. The computing time of our algorithm increases only linearly with $N$ and $D$. We illustrate our algorithms with simulations of random circuits for qubits connected in both one and two dimensional lattices. We find that $ε$ can be decreased at a polynomial cost in computing power down to a minimum error $ε_\infty$. Getting below $ε_\infty$ requires computing resources that increase exponentially with $ε_\infty/ε$. For a two dimensional array of $N=54$ qubits and a circuit with Control-Z gates, error rates better than state-of-the-art devices can be obtained on a laptop in a few hours. For more complex gates such as a swap gate followed by a controlled rotation, the error rate increases by a factor three for similar computing time.

I. INTRODUCTION

Real quantum computers may be far easier to simulate than perfect ones because decoherence limits entanglement, while approximate MPS simulations trade fidelity for computational efficiency.

  • Motivation: Conflicting estimates for simulating a 53-qubit, depth-20 experiment expose uncertainty about the classical difficulty of noisy quantum computation.Reported estimates range from thousands of years to two days.
  • Motivation: Real-device imperfections limit entanglement, making approximate simulation relevant to assessing quantum-computing difficulty.The authors frame fidelity, rather than exact-state representation, as the limiting factor for their simulations.
  • Approach: The algorithms introduce a finite error per two-qubit gate while their computing time grows linearly with qubit number and circuit depth.This scaling is intended to mimic the fidelity behavior of real devices.
  • Approach: MPS compresses many-qubit states with low to moderate entanglement, extending controlled approximation beyond exact simulation methods.The representation organizes states by entanglement and truncates the basis when necessary.
  • Approach: Keeping χ largest singular values controls the approximation: when χ ≫ e^S, truncation is essentially exact, whereas increasing entanglement lowers fidelity.Here S denotes the entanglement entropy of the bipartition.

III. NOISY ALGORITHM IN ONE DIMENSION

The one-dimensional algorithm represents the wavefunction as an MPS and updates it gate by gate, truncating singular values after two-qubit operations to maintain a bounded bond dimension.

  • MPS representation: For nearest-neighbor one-dimensional circuits, the algorithm stores N tensors and supports two-qubit gates between adjacent qubits.Non-neighboring interactions require approximately N SWAP operations to bring qubits together.
  • MPS representation: MPS represents an N-qubit wavefunction through tensors whose virtual indices bound the allowed entanglement.Allowing exponentially large bond dimensions makes the representation exact; enforcing χn ≤ χ makes it approximate.
  • Gate updates: One-qubit gates update a single MPS tensor exactly, while two-qubit gates require canonicalization, contraction, gate application, and SVD-based truncation.The truncation retains only the χ largest singular values to restore the MPS form.
  • Computational cost: The dominant cost of applying a two-qubit gate scales as χ^3, while the MPS memory footprint scales as Nχ^2.Exact algorithms would allow the bond dimension to double after each two-qubit gate.
  • Capabilities: MPS simulations retain the full approximate wavefunction, enabling exact calculation of amplitudes, observables, correlations, and entanglement entropy without sampling errors.This provides more information than direct samples of a quantum wavefunction.

B. Random Quantum Circuit

The authors test the MPS method on strongly entangling random circuits designed to remove structure and approach Porter–Thomas output statistics.

  • Circuit design: The random circuit alternates one- and two-qubit layers and is designed to create strongly entangled states with few operations.Random one-qubit gates remove structure or symmetry from the circuit.
  • Distribution test: For N = 15, the output distribution P(px < ρ) is compared with the Porter–Thomas distribution at D = 24 for χ = 2, 8, and 32.The inset gives exact results for D = 2, 16, and 24.
  • Distribution test: After depth D ∼ N, the circuit state becomes totally scrambled and is well described by a Porter–Thomas distribution.This behavior is used to assess whether truncated MPS simulations reproduce random-circuit statistics.

C. Effective two-qubit gate fidelity

Effective two-qubit fidelity measures the error introduced by MPS truncation and reveals a depth-independent saturation regime, with residual error controlled by bond dimension.

  • Fidelity measure: Effective fidelity fn is the computational analogue of experimental two-qubit-gate fidelity, with fn = 1 for exact calculation and 0 < fn < 1 after truncation.It can be evaluated through MPS contraction, or directly in canonical form.
  • Depth dependence: The χ = 64 simulations achieve averaged fidelity better than 99% on a laptop, despite representing only ∼10^-13 percent of the Hilbert space.After the transient, fidelity is approximately independent of D and N up to small 1/N corrections.
  • Bond-dimension dependence: At large depth and system size, residual error per gate approaches ε∞ ≈ 10^-2 as χ increases.For one-dimensional computers with lower two-qubit-gate fidelity than f∞ = 99%, the algorithm retains linear cost in N and D.
  • Bond-dimension dependence: Increasing χ reduces residual error, but lowering it beyond ε∞ requires exponential computational effort.Finite-system edge gates create small logarithmic improvements as χ grows.

IV. LINKS BETWEEN TWO-QUBIT AND MULTI-QUBIT FIDELITY

The paper relates multi-qubit fidelity to the accumulated effective two-qubit fidelities of a truncated MPS calculation. This relation is highly accurate numerically and supports fidelity estimation when the exact state is inaccessible.

  • The N-qubit fidelity F measures the overlap between the exact perfect state and the truncated MPS state after n two-qubit gates.The perfect state is never truncated, whereas the truncated state is approximated during circuit evolution.
  • The accumulated fidelity is naturally modeled as a product of the effective two-qubit fidelities fn as truncation errors accumulate.The effective two-qubit fidelity equals one for a perfect calculation and falls below one because of MPS truncation.
  • Eq. (17) is a very accurate approximation supported by both analytical reasoning and numerical simulations.
  • For N = 20, direct fidelity calculations and the Eq. (17) prediction show an almost perfect match across the studied regimes.The comparison uses fidelity versus circuit depth D for χ = 10, 20, and 50.
  • Eq. (17) estimates the exact-state fidelity using quantities defined solely from the MPS, enabling fidelity estimates when the exact state is unavailable.The experimentally comparable average two-qubit fidelity fav is introduced because fn cannot be measured directly.
  • The exact bound in Eq. (24) is especially useful for shallow circuits, where fidelity decreases linearly with n before the exponential regime.A weaker but exact bound is established without the assumption used in the preceding argument.

B. Other fidelity metrics

The paper compares overlap fidelity with experimentally accessible cross-entropy-based metrics. Fidelity and XEB can decay consistently, but their absolute values differ substantially because of their distinct initial conditions and definitions.

  • The overlap F is a bounded measure of the likelihood that the approximate state matches the exact state, but it cannot be measured directly in experiments.Experimental devices provide sampled bitstrings rather than direct access to the full state overlap.
  • Cross entropy is sampleable from repeated output bitstrings and compares the approximate and perfect output distributions.It is not symmetric in the two distributions and can be strongly affected by particular configurations.
  • XEB is sampleable and symmetric, but its value depends on the approximate distribution and is not generally a direct likelihood measure.For Porter–Thomas circuits, exact states have B = 1, while a uniform approximate state gives B = 0.
  • Equation (28) provides a way to estimate the actual fidelity F from XEB measurements.
  • F and XEB decay exponentially with consistent decay rates across two-qubit fidelities f = 99.5%, f = 99.0%, and f = 98.0%.The comparison uses a 1D random circuit with N = 20 qubits.
  • At f = 99%, the initial-value shift typically makes fidelity about one order of magnitude lower than the XEB curve.The shift grows as the fidelity is lowered.

V. RANDOM TENSOR THEORY OF ϵ∞

The authors model highly scrambled MPS tensors with a Gaussian tensor ensemble and find a χ-independent asymptotic fidelity determined by the gate type. This ensemble provides a lower bound for large-χ, large-depth simulations, while exceeding it requires exponential resources.

  • Random tensor ensemble: The Gaussian tensor ensemble models tensors as totally random in a worst-case scenario for highly chaotic circuits.The ensemble is used to study the singular values of the tensor produced when a two-qubit gate acts on neighboring MPS tensors.
  • Scaling: The singular-value curves collapse when plotted against the rescaled index μ/χ, following μ = g(μ/χ)/χ across bond dimensions.The collapse occurs for both gate families: CX/CZ and iSWAP-related gates.
  • Scaling: This scaling already holds for relatively small χ, although its connection to the Gaussian unitary ensemble remains an empirical numerical observation.The authors note consistency with semicircular-law scaling but do not present a firm mathematical derivation.
  • Gate dependence: The asymptotic GTE fidelity is finite and χ-independent: CZ and CX give fGTE = 96.2%, while iSWAP-family gates give fGTE = 93.2%.The iSWAP-family value corresponds to roughly twice the error of CZ because these gates have four distinct singular values instead of two.
  • Simulation fidelity: MPS simulations agree closely but retain higher asymptotic fidelity than the GTE prediction because truncation does not fully rescramble the singular-value distribution.Only a single one-qubit gate separates successive truncations, which is insufficiently chaotic to restore the initial distribution.
  • Computational boundary: For sufficiently large χ and depth, fGTE acts as a lower bound; surpassing the asymptotic value requires algorithms with exponential cost.The stated practical regime is typically χ ≥ 300.

VI. ALGORITHMS FOR GETTING BEYOND ϵ∞

The one-dimensional algorithm can be extended to two-dimensional circuits by replacing distant interactions with neighboring gates and SWAP operations, but this becomes inefficient as transverse size grows. Grouping qubits into larger tensors is proposed as a strategy to surpass the fidelity limit.

  • 2D extension: Two-qubit gates between distant qubits in a 2D array can be decomposed into neighboring gates using SWAP gates.This preserves applicability of the algorithm but increases the effective simulation cost.
  • 2D extension: The SWAP-based 2D approach becomes less efficient as the transverse dimension increases because its effective fidelity decreases.The passage identifies this as a direct limitation of applying the one-dimensional ordering to two-dimensional arrays.
  • Fidelity boundary: The algorithm cannot efficiently simulate systems whose fidelity exceeds f∞.The authors therefore consider methods intended to go beyond this asymptotic boundary.
  • Beyond f∞: Grouping several qubits into each MPS tensor is presented as a simple strategy for improving simulations beyond the preceding algorithm.The paper also notes tensor-network contraction methods as potential candidates for 2D systems.

A. Grouped MPS State and Extraction Algorithm

The grouped MPS algorithm represents multiple qubits per tensor, treating intra-tensor gates exactly while truncating inter-tensor operations. This trades exponential dependence on qubits per tensor for improved circuit fidelity.

  • Grouped MPS state: Each grouped tensor addresses Nn qubits, with the total number of represented qubits satisfying ΣNn = N.The grouped chain contains P ≤ N tensors, with boundary tensors having fewer bond indices than interior tensors.
  • Grouped MPS state: The grouped tensor size scales as χ2^2Nn, so computing time grows exponentially with the number of qubits per tensor.This cost is offset by handling gates internal to a tensor exactly.
  • Fidelity trade-off: Gates within a grouped tensor are exact, increasing the circuit’s average fidelity despite the larger tensor cost.Only gates connecting different tensors require the approximate extraction and truncation procedure.
  • Extraction algorithm: A gate between neighboring grouped tensors is processed by QR extraction, gate application to the extracted factors, SVD truncation, and reconstruction.The QR step isolates the involved qubit indices, while the final contractions rebuild the updated grouped tensors.
  • Fidelity trade-off: The grouped algorithm produces 4χ singular values instead of 2χ, so retaining χ values lowers fidelity per inter-tensor gate relative to the 1D case.For CZ, the GTE fidelity falls from fGTE(β = 1) = 96.2% to fGTE(β = 2) = 87.4%.

B. Application to a two dimensional circuit

The grouped MPS method is tested on a 54-qubit, depth-20 two-dimensional circuit alternating one-qubit gates with Control-Z gates. Different qubit groupings reduce the error below 1.4% on a single-core computer, with runtimes from seconds to under 48 hours.

  • Circuit setup: The benchmark uses a 54-qubit 2D grid with alternating one-qubit gates and Control-Z gates applied across different qubit pairs.The circuit is chosen to be close to the Google supremacy experiment.
  • Grouping strategies: The tested grouping strategies partition the grid into tensors containing different numbers of columns or large qubit blocks.The [112] strategy uses 12 tensors, while uses two tensors of 27 qubits each.
  • Results: At depth D = 20, the error rate falls below 1.4%, corresponding to global fidelity F = 0.002, on a single-core computer.The reported runtimes range from a few seconds to less than 48 hours for the most expensive points.
  • Results: Grouping is effective but not maximally efficient because fidelity decreases for the noisy gates even as some intra-group gates become exact.Thus, making selected gates perfect does not fully compensate for the reduced fidelity of inter-group operations.

C. Split-and-Merge algorithm for more complex gates

For the more entangling iSθ gate, the authors switch to a Split-and-Merge strategy that improves fidelity but leaves errors roughly three times higher than for CZ at similar cost.

  • C. Split-and-Merge algorithm for more complex gates: iSθ combines iSWAP with a controlled z-axis rotation and is expected to generate more entanglement than CZ.The simulations use θ = 1, making the gate non-trivial to simulate.
  • C. Split-and-Merge algorithm for more complex gates: 92% two-qubit gate fidelity is obtained for χ = 128 with the original grouping, compared with 98% for CZ.The [2] grouping is used for this comparison.
  • C. Split-and-Merge algorithm for more complex gates: 95% fidelity is recovered by switching to a Split-and-Merge strategy that extracts a full qubit column and alternates [2] with [5] [2].Changing groupings induces truncation errors, but the modification substantially improves the iSθ result.
  • C. Split-and-Merge algorithm for more complex gates: Three times larger error rates are observed for iSθ than for CZ at similar computational cost.Figure 14 plots residual error per gate against bond dimension χ for N = 54 qubits and depth D = 20.
  • C. Split-and-Merge algorithm for more complex gates: 98.6% or higher average fidelity matches the Google experiment for CZ in hours on one core, whereas iSθ reaches 95% in similar time.The authors could not raise the iSθ fidelity above 98% with a single-core implementation; parallelization was projected to reach 98–99%.

VII. DISCUSSION

The discussion presents an approximate simulation algorithm whose cost is linear in qubit number and circuit depth, while fidelity improvements become exponentially expensive beyond a finite limit. It argues that 99% fidelity corresponds to substantially less accessible computational space than the full Hilbert space suggests.

  • VII. DISCUSSION: Linear growth with N and D is achieved by accepting finite fidelity per two-qubit operation.The fidelity can be increased polynomially up to f∞, with further improvement requiring exponential cost.
  • VII. DISCUSSION: 99% fidelities typical of state-of-the-art experiments can be reproduced at moderate computational cost.This is the paper’s main practical observation.
  • VII. DISCUSSION: The MPS ansatz estimates or upper-bounds the fraction of Hilbert space associated with a given fidelity through the entanglement it can represent.Because MPS spans only a tiny fraction of the full Hilbert space, 99% fidelity may correspond to much less computational power than 2^N suggests.
Loading 2002.07730v2…