PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient classical simulation of noisy random quantum circuits in one dimension

Kyungjoo Noh, Liang Jiang, Bill Fefferman

arXiv:2003.13163v3quant-ph

TL;DR

The paper asks how gate-level noise affects the computational power of near-term quantum devices, a question not answered by noise models based only on output-distribution distance. It simulates one-dimensional noisy random circuits with MPOs and finds a size-independent bound on maximum MPO entanglement entropy, while lower error rates may still make simulation costly.

  • Problem

    How does realistic nonzero gate error affect the classical simulation cost and computational power of noisy quantum circuits as system size grows?

    Source: §1 · p. 2

  • Method

    The authors simulate mixed-state dynamics of one-dimensional noisy random circuits with matrix product operators and use MPO entanglement entropy to characterize simulation cost.

    Source: §1 · p. 3

  • Results

    Above a characteristic system size, maximum MPO entanglement entropy is bounded independently of system size, and the optimal circuit depth is independent of system size.

    Source: §1 · p. 3, §4.1 · pp. 11–12, §6 · p. 18

  • Takeaways & Limitations

    The heuristic scaling suggests MPO simulation cost increases exponentially as gate error rates decrease, potentially limiting practical classical simulation.

    Source: §1 · p. 3

    The considered gate error rates, 0.06 ≤ p ≤ 0.15, are not small enough to fit the heuristic exponent α stably.

    Source: §4.2 · p. 16

Abstract

from arXiv · show

Understanding the computational power of noisy intermediate-scale quantum (NISQ) devices is of both fundamental and practical importance to quantum information science. Here, we address the question of whether error-uncorrected noisy quantum computers can provide computational advantage over classical computers. Specifically, we study noisy random circuit sampling in one dimension (or 1D noisy RCS) as a simple model for exploring the effects of noise on the computational power of a noisy quantum device. In particular, we simulate the real-time dynamics of 1D noisy random quantum circuits via matrix product operators (MPOs) and characterize the computational power of the 1D noisy quantum system by using a metric we call MPO entanglement entropy. The latter metric is chosen because it determines the cost of classical MPO simulation. We numerically demonstrate that for the two-qubit gate error rates we considered, there exists a characteristic system size above which adding more qubits does not bring about an exponential growth of the cost of classical MPO simulation of 1D noisy systems. Specifically, we show that above the characteristic system size, there is an optimal circuit depth, independent of the system size, where the MPO entanglement entropy is maximized. Most importantly, the maximum achievable MPO entanglement entropy is bounded by a constant that depends only on the gate error rate, not on the system size. We also provide a heuristic analysis to get the scaling of the maximum achievable MPO entanglement entropy as a function of the gate error rate. The obtained scaling suggests that although the cost of MPO simulation does not increase exponentially in the system size above a certain characteristic system size, it does increase exponentially as the gate error rate decreases, possibly making classical simulation practically not feasible even with state-of-the-art supercomputers.

1 Introduction

The introduction asks how noise in realistic, error-uncorrected quantum devices affects their computational power, focusing on one-dimensional noisy random circuit sampling. It proposes MPO simulation and finds that system-size growth eventually saturates, while lower gate error rates may still make simulation costly.

1 Introduction

  • The introduction motivates studying gate-level noise because total-variation-distance noise does not capture realistic circuits in which nonzero gate error eventually depolarizes the system.The authors frame this as a question about whether adding qubits increases noisy devices’ computational power.Source: §1 · p. 2
  • The authors focus on the optimal circuit depth because shallow circuits are efficiently simulable with MPSs, while deep noisy circuits approach a depolarized state with washed-away correlations.They study whether simulating the intermediate regime of maximal non-trivial correlation is hard.Source: §1 · pp. 2–3
  • The paper directly simulates mixed-state dynamics with matrix product operators, whose entanglement entropy determines the cost of classical MPO simulation.Computing output probabilities from an MPO is more demanding than sampling alone, since it also permits marginal and conditional probabilities.Source: §1 · p. 3
  • Above a characteristic system size, the maximum MPO entanglement entropy is bounded independently of system size, so adding qubits brings only polynomial growth in classical simulation cost.The bound depends on the gate error rate; the heuristic analysis suggests cost increases exponentially as that rate decreases.Source: §1 · p. 3

2 Problem setup

The setup defines one-dimensional random circuit sampling and adopts two-qubit depolarization as its concrete gate-noise model. Circuits begin in the all-zero state, apply alternating layers of neighboring two-qubit gates, and measure in the computational basis.

2 Problem setup

  • The setup studies noisy random circuit sampling in a one-dimensional architecture using a two-qubit depolarization error model for its numerical results.The model is presented as representative; the MPO method applies to any two-qubit error model.Source: §2 · p. 3, §2.2 · p. 5

2.1 Noisy random circuit sampling in one dimension

  • Circuits start in the all-zero state, apply Haar-random neighboring two-qubit gates on alternating bonds, and measure all qubits in the computational basis.The circuit depth is the number of time steps; the setup assumes even n but allows odd depth D.Source: §2.1 · p. 4, Figure 2 · p. 4

2.2 Noise model: Two-qubit depolarization channel

  • Each two-qubit gate is followed by the depolarization channel N2[p], with p denoting the gate error rate.The channel includes the possibility of correlated two-qubit errors.Source: §2.2 · p. 5

3 Matrix product operators

The section develops an MPO representation and update procedure for simulating one-dimensional noisy random circuits, then defines MPO entanglement entropy as a measure of correlation and simulation cost. It also describes how to compute output probabilities and sample from them using the MPO.

3.1 Vectorization of density matrices and canonical form

  • A mixed state is vectorized by mapping each bra index to a ket index, then represented as an MPO whose bond dimension controls its exact representational capacity.For even n, bond dimension χ ≥ d^n can represent any n-qudit density matrix exactly.Source: §3.1 · pp. 5–6

3.2 Canonical update of MPOs

  • Two-qudit CPTP maps require a canonical MPO update because, unlike unitary updates, non-unitary local operations can change entanglement across the entire chain.Random gates initially increase correlations, while noise tends to reduce them as circuit depth grows.Source: §3.2 · pp. 6–7

3.3 MPO entanglement entropy

  • MPO entanglement entropy uses the normalized squared singular values of the vectorized density matrix to quantify correlations across a cut and estimate simulation cost.For mixed states it does not track reduced-state von Neumann entropy; a globally depolarized state has extensive von Neumann entropy but zero MPO entanglement entropy.Source: §3.3 · pp. 7–8
  • An extensive MPO entanglement entropy does not by itself establish classical hardness, because classical correlations can raise it even in states that are separable and easy to simulate.The section therefore focuses on whether the quantity is bounded independently of system size, which suggests that a small bond dimension may suffice.Source: §3.3 · p. 8

3.4 Efficient computation of the output probabilities

  • Output probabilities are computed from the MPO, and samples are generated sequentially from marginal and conditional distributions over the measured bits.The computation uses matrix multiplications involving χ-sized matrices; discarded singular values can reduce the total probability below unity, which the numerical study uses to characterize truncation error.Source: §3.4 · p. 9

4 Main results

The authors simulate the real-time density-matrix dynamics of 1D noisy random circuits with MPOs, using MPO entanglement entropy to characterize simulation cost. Their results show that beyond a gate-error-dependent system size, entropy saturates and adding qubits no longer causes exponential growth in MPO simulation cost.

4 Main results

  • The authors directly simulate noisy circuits’ density matrices in real time with MPOs, a more challenging task than sampling their output distributions.They average entropies across 24 circuit realizations and maximize over subsystem cuts at each depth.Source: §4 · p. 9, §4.1 · p. 10

4.1 Numerical results

  • For nonzero gate error, maximum MPO entanglement entropy decreases exponentially with circuit depth as the system approaches a globally depolarized state.The corresponding output distribution becomes uniform at large depth, unlike the noiseless case, whose distribution converges to a nonuniform limit.Source: §4.1 · p. 11
  • At p = 0.15, D⋆ = 4 and S⋆ max ≃ 2.75 for n ≥ 8; at p = 0.1, D⋆ = 6 and S⋆ max ≃ 4 for n ≥ 8.At p = 0.06, D⋆ = 9 or 10 for n ≥ 12 and S⋆ max ≃ 6.3.Source: §4.1 · p. 12
  • For n = 32 and p = 0.1, the bulk entropy is independent of subsystem length at D⋆ = 6, following an area law.The authors attribute this to noise-limited circuit depth and finite causal cones.Source: Figure 6 · p. 13, §4.1 · p. 13
  • MPO singular values decrease exponentially with bond index, making truncation negligible when log2 χ is much larger than S⋆ max.The required bond dimension and simulation time then increase only poly-logarithmically in 1/ϵ.Source: Figure 7 · p. 13, §4.1 · p. 13
  • Beyond a gate-error-dependent characteristic size, maximum MPO entanglement entropy saturates, and its optimal circuit depth is independent of system size.In the saturated regime, the required bond dimension does not increase exponentially with the number of qubits.Source: §4.1 · pp. 11–12, Figure 8 · p. 14, §4.2 · p. 14

4.2 Maximum achievable MPO entanglement entropy

  • For p = 0.06, entropy saturates around n = 12 at S⋆ max,∞ ≃ 6.3; for p = 0.1, it saturates around n = 8 at S⋆ max,∞ ≃ 4.The authors report sufficient bond dimensions to capture over 99.1% and 99.7% of the total probability, respectively.Source: §4.2 · p. 14
  • A heuristic model suggests MPO simulation cost grows exponentially as gate error decreases, although the authors could not numerically explore rates below p = 0.06.They note that the tested rates were not small enough for a stable fit of the model’s exponent.Source: §4.2 · pp. 15–16

5 Relation to previous results

The MPO approach directly simulates mixed states under CPTP noise, exploiting noise-induced correlation reduction; the authors contrast this with earlier methods and identify different scope and error-rate conditions.

Relation to previous results

  • Direct MPO simulation exploits CPTP noise maps’ reduction of quantum correlations, yielding an MPO entanglement entropy bounded independently of system size.The authors contrast this with methods that simulate pure-state trajectories or approximate ideal circuits.Source: §5 · pp. 16–17
  • The authors’ heuristic analysis suggests efficient MPO simulation is not forbidden below any nonzero gate-error threshold.This contrasts with the cited MPS method, which is efficient only for error rate ϵ > ϵ∞∼0.01.Source: §5 · pp. 16–17
  • The authors distinguish CPTP-noise dynamics from measurement-driven circuits, where pure states retain nonzero long-time entanglement except at measurement probability 1.In noisy circuits, CPTP maps eventually produce a globally depolarized mixed state.Source: §5 · p. 16
  • Unlike measurement-based quantum trajectories, which can have volume-law pure-state entanglement below a nonzero threshold, the combined mixed state has area-law MPO entanglement.The trajectory method’s threshold is specific to that method, not intrinsic to the 1D noisy RCS model.Source: §5 · p. 17
  • The cited MPS work simulates ideal random circuits with truncation-induced errors, whereas this work models CPTP noise and general Haar-random two-qubit gates in 1D.The authors report that constant bond dimension suffices and truncation errors are insignificant in their setting.Source: §5 · p. 17
  • Unlike prior Fourier-based noisy-RCS methods limited to large circuit depth, MPO simulation applies at any depth and targets the depth of maximum correlation.The goal is to understand simulation difficulty in that optimal regime, rather than only the large-depth limit.Source: §5 · pp. 17–18

6 Summary and open questions

The paper concludes that MPO entanglement in 1D noisy systems is bounded independently of system size, while its scale depends on gate error. It identifies numerical and dimensional limits that remain open.

6 Summary and open questions

  • Above a gate-error-dependent characteristic size, adding qubits increases classical MPO simulation cost only polynomially, not exponentially.The maximum MPO entanglement entropy is bounded by a constant independent of system size.Source: §6 · p. 18
  • In the small-p limit, the heuristic scaling is S⋆ max,∞(p) ∝p^-1/α for some α > 0, implying simulation cost grows exponentially as gate error decreases.At sufficiently large system size, lower gate error may make classical simulation practically infeasible.Source: §6 · p. 18
  • The authors could not numerically investigate gate error rates p ≤0.06.They propose exploring this low-error regime with advanced computing resources and making the heuristic analysis more rigorous.Source: §6 · p. 18
  • Whether the conclusions extend to 2D noisy RCS remains open, including whether constant-bond-dimension PEPOs faithfully represent its states.Exact observable computation from PEPOs is not feasible, though efficient approximate contraction may still be possible.Source: §6 · p. 18
  • The authors identify approximate contraction of output PEPOs as a possible route to 2D simulation despite worst- and average-case hardness of exact PEPS contraction.The passage presents approximate contraction as a possibility, not an established efficient method.Source: §6 · p. 18
  • Possible efficient simulation of typical 2D noisy random circuits would not contradict fault-tolerant computing, whose circuits are carefully structured to restrict error propagation.The efficient approximate simulability of typical 2D noisy circuits is itself future work.Source: §6 · p. 19

A Canonical update of MPOs under the action of a general two-qudit CPTP map

The canonical update applies a local two-qudit CPTP map to an MPO and updates its representation across the chain. SVD and truncation keep the bond dimension bounded.

A Canonical update of MPOs under the action of a general two-qudit CPTP map

B Time cost of MPO simulation of 1D noisy RCS

The prescribed canonical update has a global chain cost even for a local noisy gate. A depth-D circuit applies this update O(nD) times.

B Time cost of MPO simulation of 1D noisy RCS

  • Each canonical update costs O(nχ^3), because SVDs of O(χ) × O(χ) matrices are performed during a global chain update.For a unitary channel, the global update is unnecessary and the factor n is absent.Source: B Time cost of MPO simulation of 1D… · p. 27
  • A depth-D 1D noisy RCS with n qubits requires O(nD) noisy-gate updates, each with the global update cost described above.The passage refers to a total simulation-time expression but does not state it in the supplied text.Source: B Time cost of MPO simulation of 1D… · p. 27

Related papers

Loading 2003.13163v3…