CoChat

Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance

Open access

The DOI matches its Crossref record; 56 of the 56 references it cites were found in a registry or an index.

Abstract

A recent quantum simulation of observables of the kicked Ising model on 127 qubits implemented circuits that exceed the capabilities of exact classical simulation. We show that several approximate classical methods, based on sparse Pauli dynamics and tensor network algorithms, can simulate these observables orders of magnitude faster than the quantum experiment and can also be systematically converged beyond the experimental accuracy. Our most accurate technique combines a mixed Schrödinger and Heisenberg tensor network representation with the Bethe free entropy relation of belief propagation to compute expectation values with an effective wave function–operator sandwich bond dimension >16,000,000, achieving an absolute accuracy, without extrapolation, in the observables of <0.01, which is converged for many practical purposes. We thereby identify inaccuracies in the experimental extrapolations and suggest how future experiments can be implemented to increase the classical hardness.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1126/sciadv.adk4321

Cites

56 of 56 references verified0 citation errors · 0 not checkable

Statistics

Figures

Fig. 1. Schematic overview of the simulation. (A) Qubit layout of the quantum device used in (8). (B) Visualization of the full TN representation of the quantum circuit expectation value for 20 steps. Green tensors are entangling RZZ gates; orange tensors are RX rotations.
Fig. 1. Schematic overview of the simulation. (A) Qubit layout of the quantum device used in (8). (B) Visualization of the full TN representation of the quantum circuit expectation value for 20 steps. Green tensors are entangling RZZ gates; orange tensors are RX rotations.CC BY-NC · PubMed Central
Fig. 2. TN simulation overview. Full discussion in main text and Methods. (A) schematic of mixed PEPS/PEPO evolution on toy hexagonal lattice. The PEPS (red) is evolved using the next unitary layer and then compressed using L2BP. The PEPO (pink) is evolved and compressed similarly. Green bonds, “physical” indices connecting a single site. Once all unitary layers have been incorporated, the remaining PEPS/PEPO/PEPS sandwich is contracted using L1BP. (B) BP on the lattice. Blue circles, tensors on sites (which represent lazy contraction of tensors from multiple layers, represented by internal dots). Each bond has left and right tensor messages (yellow/red pairs of dots). We run BP algorithms on three types of TNs that differ in the definition of the site tensors (shown in insets). (i) Site tensor when compressing the PEPS and its unitary update, minimizing the 2-norm error (L2BP method). (ii) Site tensor when compressing the PEPO and its unitary update, minimizing the 2-norm error (L2BP method). (iii) Site tensor when using the Bethe free entropy formula to evaluate the PEPS-PEPO-PEPS expectation value (L1BP method). (C) Lazy BP contraction for updating a single message. (D) Lazy 2-norm belief propagation (L2BP) compression of a local site. From converged messages, pairs of projectors (purple rectangles), from the top right approximation, are found for each bond. Projectors adjacent to each site are then contracted in, yielding single tensors with maximum dimension χ. (E) Lazy 1-norm belief propagation (L1BP) TN contraction. Given converged messages, the global contracted value is estimated from contractions of tensors and messages.
Fig. 2. TN simulation overview. Full discussion in main text and Methods. (A) schematic of mixed PEPS/PEPO evolution on toy hexagonal lattice. The PEPS (red) is evolved using the next unitary layer and then compressed using L2BP. The PEPO (pink) is evolved and compressed similarly. Green bonds, “physical” indices connecting a single site. Once all unitary layers have been incorporated, the remaining PEPS/PEPO/PEPS sandwich is contracted using L1BP. (B) BP on the lattice. Blue circles, tensors on sites (which represent lazy contraction of tensors from multiple layers, represented by internal dots). Each bond has left and right tensor messages (yellow/red pairs of dots). We run BP algorithms on three types of TNs that differ in the definition of the site tensors (shown in insets). (i) Site tensor when compressing the PEPS and its unitary update, minimizing the 2-norm error (L2BP method). (ii) Site tensor when compressing the PEPO and its unitary update, minimizing the 2-norm error (L2BP method). (iii) Site tensor when using the Bethe free entropy formula to evaluate the PEPS-PEPO-PEPS expectation value (L1BP method). (C) Lazy BP contraction for updating a single message. (D) Lazy 2-norm belief propagation (L2BP) compression of a local site. From converged messages, pairs of projectors (purple rectangles), from the top right approximation, are found for each bond. Projectors adjacent to each site are then contracted in, yielding single tensors with maximum dimension χ. (E) Lazy 1-norm belief propagation (L1BP) TN contraction. Given converged messages, the global contracted value is estimated from contractions of tensors and messages.CC BY-NC · PubMed Central
Fig. 3. Expectation values of the quantum circuit in Eq. 1. (A) Magnetization; (B) X{3}Y{2}Z{5} ≡ X13,29,31Y9,30Z8,12,17,28,32; (C) X{8}Y{1}Z{8} ≡ X37,41,52,56,57,58,62,79Y75Z38,40,42,63,72,80,90,91, all after five steps; (D) X{8}Y{8}Z{1} ≡ X37,41,52,56,57,58,62,79Y38,40,42,63,72,80,90,91Z75 for a five-step circuit with an additional X-rotation layer, and (E) 〈Z62〉 after 20 steps. The results presented include the exact benchmarks calculated using TN contraction [“Exact,” (A) to (D)], SPD results obtained within on average 10 s per point on a single core of a laptop computer (“SPD 10s”), MIX TN results on a single GPU under 3 min (“MIX 3 min”), and the zero-noise extrapolated quantum experiment (“Quantum”) of (8). All data apart from the quantum simulations were computed at θh between zero and π/2 in increments of π/32. Thresholds used for the SPD simulations are reported in table S1.
Fig. 3. Expectation values of the quantum circuit in Eq. 1. (A) Magnetization; (B) X{3}Y{2}Z{5} ≡ X13,29,31Y9,30Z8,12,17,28,32; (C) X{8}Y{1}Z{8} ≡ X37,41,52,56,57,58,62,79Y75Z38,40,42,63,72,80,90,91, all after five steps; (D) X{8}Y{8}Z{1} ≡ X37,41,52,56,57,58,62,79Y38,40,42,63,72,80,90,91Z75 for a five-step circuit with an additional X-rotation layer, and (E) 〈Z62〉 after 20 steps. The results presented include the exact benchmarks calculated using TN contraction [“Exact,” (A) to (D)], SPD results obtained within on average 10 s per point on a single core of a laptop computer (“SPD 10s”), MIX TN results on a single GPU under 3 min (“MIX 3 min”), and the zero-noise extrapolated quantum experiment (“Quantum”) of (8). All data apart from the quantum simulations were computed at θh between zero and π/2 in increments of π/32. Thresholds used for the SPD simulations are reported in table S1.CC BY-NC · PubMed Central
Fig. 4. Absolute errors of approximate methods for the observables presented in Fig. 3. (A) Magnetization; (B) X{3}Y{2}Z{5} ≡ X13,29,31Y9,30Z8,12,17,28,32; (C) X{8}Y{1}Z{8} ≡ X37,41,52,56,57,58,62,79Y75Z38,40,42,63,72,80,90,91, all after five steps; (D) X{8}Y{8}Z{1} ≡ X37,41,52,56,57,58,62,79Y38,40,42,63,72,80,90,91Z75 for a five-step circuit with an additional X-rotation layer. We show the SPD results obtained within on average 10 s per point (SPD 10 s), converged SPD results (“SPD”), and the three TN methods (B to D): PEPS, PEPO, and MIX. Thresholds used for the converged SPD simulations are reported in table S1.
Fig. 4. Absolute errors of approximate methods for the observables presented in Fig. 3. (A) Magnetization; (B) X{3}Y{2}Z{5} ≡ X13,29,31Y9,30Z8,12,17,28,32; (C) X{8}Y{1}Z{8} ≡ X37,41,52,56,57,58,62,79Y75Z38,40,42,63,72,80,90,91, all after five steps; (D) X{8}Y{8}Z{1} ≡ X37,41,52,56,57,58,62,79Y38,40,42,63,72,80,90,91Z75 for a five-step circuit with an additional X-rotation layer. We show the SPD results obtained within on average 10 s per point (SPD 10 s), converged SPD results (“SPD”), and the three TN methods (B to D): PEPS, PEPO, and MIX. Thresholds used for the converged SPD simulations are reported in table S1.CC BY-NC · PubMed Central
Fig. 5. Expectation value of 〈Z62〉. (A) After 9 steps; (B) after 20 steps of the circuit in Eq. 1, as calculated with SPD and PEPS, PEPO, and MIX TN methods. For the 9-step result, we compare these to the exact benchmark; for the 20-step result, we compare the spread of these classically simulated expectation values with the confidence intervals (CI) of the extrapolation procedure used in the quantum simulation experiment (8). All data were computed at θh between zero and π/2 in increments of π/32. Thresholds used for SPD are reported in table S3, and bond dimensions used for TN simulations are in table S4.
Fig. 5. Expectation value of 〈Z62〉. (A) After 9 steps; (B) after 20 steps of the circuit in Eq. 1, as calculated with SPD and PEPS, PEPO, and MIX TN methods. For the 9-step result, we compare these to the exact benchmark; for the 20-step result, we compare the spread of these classically simulated expectation values with the confidence intervals (CI) of the extrapolation procedure used in the quantum simulation experiment (8). All data were computed at θh between zero and π/2 in increments of π/32. Thresholds used for SPD are reported in table S3, and bond dimensions used for TN simulations are in table S4.CC BY-NC · PubMed Central
Fig. 6. Convergence of 〈Z62〉 after 20 steps. (A) SPD with respect to the threshold; (B) the PEPS, PEPO, and MIX methods with respect to bond dimension χ. The results are presented for a range of θh values indicated by different markers. (C) Zoom-in on the convergence of the MIX method at θh = 6π/32, 8π/32, and 10π/32 (see fig. S1 for other values of θh).
Fig. 6. Convergence of 〈Z62〉 after 20 steps. (A) SPD with respect to the threshold; (B) the PEPS, PEPO, and MIX methods with respect to bond dimension χ. The results are presented for a range of θh values indicated by different markers. (C) Zoom-in on the convergence of the MIX method at θh = 6π/32, 8π/32, and 10π/32 (see fig. S1 for other values of θh).CC BY-NC · PubMed Central
Fig. 7. Convergence analysis of norm and 〈Z62〉 after 20 steps. Norm as a function of angle θh (A) and the convergence of 〈Z62〉 after 20 steps for SPD and PEPO (B), and PEPS and MIX (C) methods with respect to the norm. θh values are indicated by different markers. Horizontal lines in (B) correspond to the highest-χ MIX results at respective θh.
Fig. 7. Convergence analysis of norm and 〈Z62〉 after 20 steps. Norm as a function of angle θh (A) and the convergence of 〈Z62〉 after 20 steps for SPD and PEPO (B), and PEPS and MIX (C) methods with respect to the norm. θh values are indicated by different markers. Horizontal lines in (B) correspond to the highest-χ MIX results at respective θh.CC BY-NC · PubMed Central
Fig. 8. Verifying L1BP contraction for PEPS and PEPO evolution. (A) Comparison of 〈Z62〉 computed by L1BP contraction (lines) and via Monte Carlo sampling (markers with error bars) for the PEPS method at 20 steps at a range of χ and θh. The sampled points are computed from 10,000 shots each. (B) Expectation values 〈Z62〉 for a 20-step circuit computed with L1BP contraction (y axis) and exact (x axis) contraction at different values of θh and for different bond dimensions χ. (C) histogram of the absolute errors of all points shown. Note that, to enable exact contraction, we evolve the PEPO all the way to time 0, and the final layer is not compressed leading to a contribution of ×4 to χ. This is slightly different to the PEPO method elsewhere in the text.
Fig. 8. Verifying L1BP contraction for PEPS and PEPO evolution. (A) Comparison of 〈Z62〉 computed by L1BP contraction (lines) and via Monte Carlo sampling (markers with error bars) for the PEPS method at 20 steps at a range of χ and θh. The sampled points are computed from 10,000 shots each. (B) Expectation values 〈Z62〉 for a 20-step circuit computed with L1BP contraction (y axis) and exact (x axis) contraction at different values of θh and for different bond dimensions χ. (C) histogram of the absolute errors of all points shown. Note that, to enable exact contraction, we evolve the PEPO all the way to time 0, and the final layer is not compressed leading to a contribution of ×4 to χ. This is slightly different to the PEPO method elsewhere in the text.CC BY-NC · PubMed Central
Fig. 9. Comparison of various simulation results for 〈Z62〉. Expectation values 〈Z62〉 for a 20-step circuit computed with the reference, MIX method (shown in all panels, labeled “This work”); (A) the zero-noise extrapolated quantum simulation (“Quantum”); (B) MPS and MPO approaches (8, 17); (C) BP-TN method of (12) with χ = 500 and the extrapolated χ → ∞ result, the inset compares convergence at θh = 0.7 with our MIX and PEPS methods; (D) exact state-vector simulation on a reduced 31-qubit model (13); (E) OBPPP approach of (14) (data used with permission from Z. Liu); (F) PEPO method of (15) with χ = 256 and the extrapolated result, the inset compares convergence at θh = 7π/32 with that of our MIX and PEPO methods. The estimated error bars of the MIX method (less than 0.01) are smaller than the plot markers. Horizontal black lines in the insets of (C) and (F) correspond to the MIX results at highest available χ, while the dotted cyan (C) and green (F) lines correspond to the extrapolation fits of (12) and (15), respectively.
Fig. 9. Comparison of various simulation results for 〈Z62〉. Expectation values 〈Z62〉 for a 20-step circuit computed with the reference, MIX method (shown in all panels, labeled “This work”); (A) the zero-noise extrapolated quantum simulation (“Quantum”); (B) MPS and MPO approaches (8, 17); (C) BP-TN method of (12) with χ = 500 and the extrapolated χ → ∞ result, the inset compares convergence at θh = 0.7 with our MIX and PEPS methods; (D) exact state-vector simulation on a reduced 31-qubit model (13); (E) OBPPP approach of (14) (data used with permission from Z. Liu); (F) PEPO method of (15) with χ = 256 and the extrapolated result, the inset compares convergence at θh = 7π/32 with that of our MIX and PEPO methods. The estimated error bars of the MIX method (less than 0.01) are smaller than the plot markers. Horizontal black lines in the insets of (C) and (F) correspond to the MIX results at highest available χ, while the dotted cyan (C) and green (F) lines correspond to the extrapolation fits of (12) and (15), respectively.CC BY-NC · PubMed Central
Fig. 10. Scheme representing the computation of Uσ^(†)(∑P‍aPP)Uσ within SPD. (A) The observable is represented by an array of Pauli operators P with corresponding coefficients aP. (B) In SPD, we identify which P commute with σ (white) and which do not (gray). For P that anticommute with σ, we compute σ · P (orange). (C) Coefficients are updated according to Eq. 8. This requires that we find Pauli operators σ · P that existed in the initial observable, which is accomplished by keeping the Pauli arrays ordered and performing a binary search. New Pauli operators that were not in the representation of the initial observable are shown in orange and not crossed out. (D) After all coefficients have been updated, we find Pauli operators whose coefficients are below threshold (additional two crossed out elements in the scheme). (E) Last, the remaining Pauli operators are merged into a new array representing the updated observable.
Fig. 10. Scheme representing the computation of Uσ^(†)(∑P‍aPP)Uσ within SPD. (A) The observable is represented by an array of Pauli operators P with corresponding coefficients aP. (B) In SPD, we identify which P commute with σ (white) and which do not (gray). For P that anticommute with σ, we compute σ · P (orange). (C) Coefficients are updated according to Eq. 8. This requires that we find Pauli operators σ · P that existed in the initial observable, which is accomplished by keeping the Pauli arrays ordered and performing a binary search. New Pauli operators that were not in the representation of the initial observable are shown in orange and not crossed out. (D) After all coefficients have been updated, we find Pauli operators whose coefficients are below threshold (additional two crossed out elements in the scheme). (E) Last, the remaining Pauli operators are merged into a new array representing the updated observable.CC BY-NC · PubMed Central

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Research works printed but not linked: 1

  1. 10.22331/q-2021-03-15-410 · DOI · Paper page

Cited by

See all 89

Metadata

Authors
Begušić, T., Gray, J., & Chan, G. K.-L.
Affiliations
California Institute of Technology (US)
Corresponding author
  • Begušić, Tomislav
  • Gray, Johnnie
  • Chan, Garnet Kin-Lic
Venue
Science Advances
Published
2024-01-19
Volume
10
Issue
3
Pages
eadk4321-eadk4321
ISSN
2375-2548 (ISSN-L)
OpenAlex
W4390959369
Cited by
89
References
38
Citations by year
2026: 28 · 2025: 36 · 2024: 20
FWCI
12.37
Type
journal article
Language
en
Open access
Licence
cc-by-nc
Locations
  • Science Advances (publishedVersion, cc-by-nc)
  • PubMed Central (publishedVersion, cc-by-nc)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion, cc-by-nc-sa)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (DEAC02-05CH11231)
  • U.S. Department of Energy (DESC0022088, -AC02-05CH11231, 05CH11231, DE AC02 05CH11231, DE-AC02-)
  • California Institute of Technology
  • Resnick Sustainability Institute for Science, Energy and Sustainability, California Institute of Technology
  • National Energy Research Scientific Computing Center (DE–AC02–05CH11231, 05CH11231, AC02-05CH11231)
  • Flatiron Health
  • Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung (214214)
  • Office of Science (DEAC02–05CH11231, AC02-05CH11231, DE-AC02, DESC0022088)
  • Basic Energy Sciences (DE-AC02, SC0022088, DE-AC02-05CH11231., DESC0022088, AC02–05CH11231)
  • Advanced Scientific Computing Research (DE-AC02-05CH11231, DESC0022088)
  • Lawrence Berkeley National Laboratory (AC02‐05CH11231, DE-AC02-05CH11231, 05CH11231)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
Keywords
classical simulation of quantum circuits, tensor networks, belief propagation, bond dimension, expectation value estimation, quantum advantage

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.