PaperlayerView exact revision on arXiv

Source-linked AI summary

Toward the first quantum simulation with quantum speedup

Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, Yuan Su

arXiv:1711.10980v1quant-ph

TL;DR

The paper asks how limited quantum computers might solve practical problems beyond classical reach, using spin-system simulation as a candidate. It constructs optimized circuits for three Hamiltonian-simulation algorithms and finds segmented QSP strongest among rigorous methods, while empirical product formulas are cheaper; the estimates remain upper bounds and QSP angle computation is difficult.

  • Problem

    The paper addresses the need to identify practical quantum computations beyond classical reach while using relatively limited quantum resources.

  • Method

    The authors synthesize and optimize explicit circuits for product-formula, Taylor-series, and quantum-signal-processing Hamiltonian-simulation algorithms on a disordered Heisenberg spin model.

  • Results

    Segmented QSP outperforms rigorously bounded product formulas by about an order of magnitude in CNOT count and almost two orders of magnitude in T count.

  • Takeaways & Limitations

    Quantum signal processing appears preferred among rigorously analyzed algorithms, whereas higher-order product formulas are useful when empirical error estimates suffice.

  • Takeaways & Limitations

    The results are upper bounds, and computing QSP rotation angles prevented a full explicit implementation except for very small instances.

Abstract

from arXiv · show

With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, employing diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically-infeasible instances of factoring and quantum chemistry.

1 Introduction

The paper seeks practical quantum computations beyond classical reach by designing explicit, resource-conscious circuits, focusing on digital simulation of spin systems as an early application.

  • The work develops explicit circuits and concrete resource estimates for quantum computations intended to outperform classical computers.
  • The authors distinguish their goal of practical super-classical computation from quantum supremacy demonstrations that need only accomplish a super-classical task.
  • Spin-system simulation is selected because quantum computers naturally simulate quantum dynamics, while local interactions may impose less overhead.
  • The paper investigates whether improved Hamiltonian-simulation algorithms can benefit relatively small systems and support a first practical quantum-computing application.

2 Target system

The benchmark is a disordered one-dimensional nearest-neighbor Heisenberg model whose thermalization transition is difficult to study classically. The analysis fixes parameters to expose system-size dependence.

  • The target task is a one-dimensional nearest-neighbor Heisenberg model with a random magnetic field in the z direction.
  • The disorder strength h is defined by choosing each field value h_j uniformly from [−h, h] under periodic boundary conditions.
  • The model’s transition between thermal and localized phases remains poorly understood, while the largest cited classical study reached only 22 spins.
  • The simulations use evolution time comparable to system size because self-thermalization and information propagation require this scale.
  • The gate-count benchmarks fix h = 1, t = n, and overall accuracy ǫ = 10^-3 to emphasize system-size dependence.

3 Implementations

The paper implements product-formula, Taylor-series, and quantum-signal-processing simulation algorithms as optimized circuits, using tighter error analyses and specialized subroutines. QSP is fully implemented only in segmented form, while some alternatives rely on empirical estimates or gate-count estimates.

  • The study implements high-order product formulas, direct Taylor-series simulation, and quantum signal processing as leading candidate algorithms.
  • Circuits are written in Quipper, analyzed with tightened parameters, manually optimized, and processed by an automated circuit-optimization tool.
  • CNOT gates measure physical-level cost, while T gates represent a typically expensive resource in fault-tolerant Clifford+T circuits.
  • The commutator bound changes the (2k)th-order product-formula complexity from O(n3+1/k) to O(n3+2/(2k+1)) for t = n, while improving the leading constant.
  • Empirical error estimates reduce product-formula costs by several orders of magnitude but do not rigorously guarantee simulation error.
  • An optimized binary-tree walk for select(V) reduces Taylor-series CNOT and T counts by factors between 5 and 9 for systems with 10 to 100 spins.
  • Segmented QSP enables complete implementation by shortening evolution segments, although it has higher asymptotic complexity than single-segment QSP.

4 Results

The results compare resource requirements across PF, TS, and QSP implementations, showing QSP is strongest among rigorously bounded methods while empirically bounded PF is often preferred. Higher-order PF formulas perform best for the benchmark’s tens-to-hundreds-of-qubits regime, and spin-system simulations require far fewer resources than comparable factoring or quantum-chemistry instances.

  • QSP outperforms rigorously bounded PF, improving by about an order of magnitude in cnot count and almost two orders of magnitude in T count.
  • Empirical error bounds improve PF performance by two to three orders of magnitude, making PF preferred when rigorous guarantees are unnecessary.
  • Fourth- and sixth-order PF formulas perform best for systems with tens to hundreds of qubits; empirical bounds favor sixth order above about 30 qubits.
  • At 50 qubits, TS uses 171 qubits, QSP uses 67, and PF uses 50; segmented QSP requires about 1.8 × 10^8 cnot gates and 2.4 × 10^9 T gates.
  • Spin-system simulation estimates are significantly smaller than those for 1024-bit factoring and FeMoco quantum chemistry simulations.

5 Discussion

The discussion frames the circuits as progress toward practical quantum computation while emphasizing that the estimates remain upper bounds and omit realistic device constraints. It also identifies higher-order product formulas, stronger error analysis, and improved QSP preprocessing as key directions for future work.

  • Conclusions: The results establish concrete benchmarks for a practical quantum computation beyond classical reach, but further improvements or other algorithms may perform better.The authors characterize their results as upper bounds and expect future studies to improve the benchmarks.
  • Experimental implications: Higher-order product formulas could be useful in near-term digital quantum-simulation experiments, which might test the validity of empirical error bounds.Existing demonstrations have mainly used first-order formulas, with limited second-order applications.
  • Algorithmic improvements: Rigorous product-formula error bounds remain loose, even with the newly developed commutator bound.The authors motivate stronger rigorous bounds as a future improvement.
  • Algorithmic improvements: Computing QSP angles is difficult enough to prevent full practical use of the algorithm, motivating more efficient classical procedures.The angles require high-precision roots of a degree-2M polynomial.
  • Resource requirements: Current estimates require millions of CNOT gates for a superclassical simulation, likely placing it beyond present fault-tolerance-free experiments.Further gate-count reductions could make error-correction-free demonstrations more accessible with highly accurate gates.
  • Scope: The analysis uses an idealized system and does not incorporate architectural constraints, alternative basic operations, gate parallelization, or likely fault-tolerance requirements.The authors present incorporating these features as a path toward a practical-computation blueprint.

Appendices

The appendices motivate a localized Heisenberg spin model as a concrete benchmark and compare implementation strategies for Hamiltonian simulation. They develop tighter product-formula bounds and optimized select-gate implementations while deriving system-size costs for several algorithms.

  • Candidate system: Classical simulations of localization–thermalization transitions have generally been restricted to fewer than 25 qubits, motivating quantum simulation of spin systems.The selected Heisenberg benchmark has previously been studied with at most 22 spins.
  • Candidate system: The benchmark is a one-dimensional nearest-neighbor Heisenberg model with a random z-direction magnetic field, studied for self-thermalization and many-body localization.The simulation focuses on dynamics rather than full-spectrum calculations, partly because phase estimation introduces additional overhead.
  • Algorithm comparison: The study compares product formulas, Taylor series, and quantum signal processing, alongside broader families based on quantum walks and linear combinations of unitaries.The implemented algorithms are selected as expected efficient approaches to digital simulation.
  • Product formulas: O(n^5) gates arise for the baseline product-formula implementation, while a (2k)th-order formula has complexity O(n^3+1/k).Each segment has size O(n), and the number of segments is O(n^4) in the stated construction.
  • Product formulas: Commutation-aware analysis improves the (2k)th-order product-formula scaling from O(n^3+1/k) to O(n^3+2/(2k+1)).The bound is tighter because many Hamiltonian-term pairs commute, also improving the leading gate count.
  • Error bounds: The strongest rigorous product-formula bound may still be loose in practice, so the study supplements it with an empirical bound extrapolated from small classical simulations.The empirical approach does not provide a rigorous performance guarantee.
  • Circuit optimization: The binary-tree select(V) implementation reduces gate complexity from O(Γ log Γ) to O(Γ).This optimization is a central implementation improvement for the Taylor-series and signal-processing approaches.

C.3 Quantum signal processing algorithm

Quantum signal processing uses phased iterates and ancilla-controlled polynomial transformations to convert Hamiltonian eigenvalue phases into the desired time evolution. Its asymptotic costs are favorable, but post-selection and difficult classical angle computation constrain practical implementation.

  • Qubitization: Qubitization maps eigenvalues of H/α to paired eigenvalues of the walk operator, allowing QSP to act on each Hamiltonian eigenvalue through an ancilla-qubit rotation.Eigenvalues at ±1 are treated as degenerate cases, while unreachable eigenspaces can be neglected.
  • Signal processing: QSP uses phased iterates whose varying rotation phases implement a polynomial transformation of Hamiltonian eigenvalue phases.Only selected polynomial components are extracted by preparing and postselecting an ancilla state.
  • Polynomial approximation: QSP approximates e^-iλt by truncating a Jacobi–Anger expansion to a polynomial of degree M.The rotation angles realizing the expansion can be computed classically, in principle.
  • State evolution: The algorithm simulates an initial state by applying V and postselecting the ancilla register on |+⟩⊗|G⟩.A nonmatching measurement outcome causes failure.
  • Gate complexity: O(n^3 log n) gates are required asymptotically, reducible to O(n^3) with the improved select(V) implementation.The dominant component is select(H), whose direct implementation costs O(n log n) elementary gates.
  • Practical limitation: QSP requires substantial classical preprocessing because its degree-2M polynomial roots must be computed to high precision.This prevented explicit parameter computation except for very small instances.
  • Segmented implementation: The segmented implementation has complexity O(n^3+4/M); with M = 28, its exponent is about 3.14.Using r = O(n^2+4/M) segments ensures the target overall error in the stated instance.

D System-size dependence for other simulation algorithms

The appendix derives system-size gate complexities for quantum-walk-based simulation and details optimized oracle and select-gate implementations for the chosen sparse Heisenberg Hamiltonian. The improved implementations reduce some costs but leave quantum-walk simulation at high polynomial complexity.

  • Fractional queries: For the local Hamiltonian, fractional-query methods use a bound involving L = Θ(n) and ∥H∥max = Θ(n), yielding the stated system-size dependence.The appendix uses these parameters to specialize general complexity bounds.
  • Quantum walk: The quantum-walk procedure uses O(n^3) walk steps, which dominate the phase-estimation and phase-correction costs.The Fourier-transform cost is O(log n log log n), while sine-function correction is poly(log n).
  • Oracle implementation: Preparing the walk state costs O(n + cost(O_F) + cost(O_H)), reducing the oracle analysis to the two Hamiltonian-access procedures.The reflection about |0⟩ costs O(n).
  • Hamiltonian structure: For the Heisenberg Hamiltonian, off-diagonal nonzero entries correspond to swapping adjacent bits, with at most n+1 nonzero elements per row.This sparse structure supports the oracle constructions for row and matrix-element access.
  • Oracle implementation: The O_F oracle can be implemented with O(n) time using a reversible comparison that identifies the swapped adjacent bits.The construction first copies the input register, applies the controlled swap, and uncomputes the index.
  • Quantum walk: Quantum-walk simulation has gate complexity O(n^4 log n), reduced to O(n^4) by the improved implementation of O_F.The improvement uses a select(·) implementation whose cost is linear in n.
  • Circuit construction: The study uses Quipper’s hierarchical circuit representation and automated optimization tools to manipulate and optimize the large circuits.The implementations and sample circuits were made publicly available.

E.1 Overview of algorithm implementations

The implementations cover product formulas, Taylor series, and quantum signal processing, with explicit parameter choices, gate representations, synthesis, optimization, and correctness tests.

  • Product formulas: 18 product-formula algorithm types combine orders 1, 2, 4, 6, and 8 with analytic, minimized, empirical, and selected commutator bounds.Commutator bounds are implemented for first-, second-, and fourth-order formulas.
  • Product formulas: Product formulas exponentiate individual 1- or 2-qubit Pauli terms in carefully chosen sequences and repeat the sequence for longer evolutions.The evolution duration and repetition count are set using an error estimate.
  • Taylor series: The Taylor-series implementation uses unary-binary control encoding, state-preparation subroutines, select(V), and reflection about |0⟩.The second state-preparation routine uses controlled rotations tailored to the Taylor coefficients.
  • Quantum signal processing: Two QSP versions are implemented: a non-segmented version with placeholder random angles and a segmented version using rigorous bounds and offline high-precision parameters.The non-segmented circuit has the correct structure but its rotation-angle computation cannot handle more than very small systems.
  • Gate representation and synthesis: Circuits are represented with Clifford gates, CNOTs, and arbitrary-angle Rz rotations, then converted to Clifford+T using optimal rotation synthesis.The error budget allocates ǫ/2 to simulation and ǫ/2 to gate synthesis.
  • Future synthesis improvements: RUS and unitary-mixing decompositions could reduce fault-tolerant resource counts by a factor of 5 or more, but are left for future work.These alternatives require additional measurements, classical feedback, and CNOT gates.
  • Circuit optimization: Automated optimization applies gate commutations, mergers, cancellations, phase-polynomial rewrites, and Rz reductions, using the light optimizer for reported results.The heavy option is more computationally intensive and was not expected to change the conclusions qualitatively.
  • Validation: Correctness tests simulate complete product-formula circuits through 15 qubits and segmented QSP circuits for a 5-qubit system against ideal evolution operators.The tests use spectral-norm distance; larger Taylor-series tests are limited by the number of ancillas.

F Product formula implementation details

The product-formula analysis develops rigorous analytic, minimized, and commutator bounds, then compares them with empirical estimates for a one-dimensional spin system. Commutator structure improves asymptotic costs, while empirical fits produce smaller but non-rigorous estimates.

  • F Product formula implementation details: Rigorous analytic, minimized, and commutator bounds guarantee that the simulated evolution is ǫ-close to the ideal evolution.The commutator bound exploits Hamiltonian commutator structure, unlike the analytic and minimized bounds.
  • F.3 Empirical bounds: Empirical bounds extrapolate numerical data and yield smaller gate counts, but provide no guarantee on the distance to the ideal evolution.They are plausible estimates of actual performance rather than rigorous correctness bounds.
  • F.1 Analytic and minimized bounds: Analytic bounds are efficiently computable but pessimistic, producing unnecessarily large circuits; minimized bounds search for the smallest r satisfying the rigorous constraints.The minimized procedure gives a slight improvement over the closed-form analytic choice.
  • F.2 Commutator bounds: Commutator bounds for second- and fourth-order formulas exploit commuting Hamiltonian-term pairs, providing the first higher-order bounds of this type according to the authors.The construction can in principle be adapted to higher orders.
  • F.2.2 Concrete commutator bounds: Polynomial interpolation exploits Hamiltonian symmetries to compute commutator bounds in closed form from a constant number of numerical values.The method relies on tuple counts being low-degree polynomials in n and may apply to other Hamiltonians with suitable symmetries.
  • F.2.2 Concrete commutator bounds: For the explicit bounds, fourth-, second-, and first-order commutator formulas achieve O(n3.4), O(n11/3), and O(n4) gate complexities, improving analytic/minimized values O(n3.5), O(n4), and O(n5).The fourth-order result uses r = O(n2.4) segments, with O(n) gates per segment.
  • F.2.2 Concrete commutator bounds: For nearest-neighbor n-spin systems evolving for t = n, commutator bounds improve (2k)th-order PF complexity from O(n3+1/k) to O(n3+2/(2k+1)).The improvement also significantly reduces the leading constant.

G.1 Error analysis

The error analysis bounds Taylor-series truncation and implementation errors, then selects truncation orders through tabulation. It also accounts for probabilistic failure and reduces select(V) costs with mixed encoding.

  • G.1 Error analysis: The Taylor-series analysis derives an explicit bound quantifying how truncation order K affects overall accuracy.The bound is then used to choose K for a desired error ǫ.
  • G.1 Error analysis: The implementation bounds errors from truncating the Taylor series, approximating the isometry V(t), and normalizing the resulting state.Contraction and normalization lemmas combine these contributions into an accuracy guarantee.
  • G.1 Error analysis: Because K is integer-valued, the required truncation order is selected by tabulating error estimates for potentially relevant K values and choosing one that ensures small error.The lookup table uses s boosted to 2 in each segment.
  • G.1 Error analysis: The Taylor-series algorithm’s empirical error cannot be directly estimated because its ancilla count prevents classical simulation even for very small systems.Improving the truncated-series estimate would change K by at most an additive ln 2 under the stated bound.
  • G.1 Error analysis: The Taylor-series algorithm can fail after ancilla measurement, but with ǫ = 10^-3 its expected repetition overhead is approximately 1/0.998 ≈ 1.002 and is neglected.This permits direct gate-count comparison with product formulas, which have no failure probability.
  • G.1 Error analysis: The select(V) cost depends strongly on the control-register representation, motivating a mixed unary-binary encoding.Unary encoding labels k while binary encoding stores each ℓ_j.
  • G.1 Error analysis: The mixed encoding adds ⌈K + 1 − log2(K + 1)⌉ qubits but replaces one Θ(K log L)-bit selection with K + 1 selections on log2 L-bit registers.Each selection is controlled by a single unary-encoding qubit.

G.4 Implementation of select(V )

The paper implements select(V) by cycling through Boolean products on a binary tree, then optimizes the resulting reversible circuit to reduce expensive gates. The optimized construction approaches the lower-bound resource scale and improves substantially over multiply-controlled-Toffoli baselines.

  • Control generation: select(V) applies Vγ when a binary control register encodes γ, using an ancilla cycled through Boolean products of w literals.The construction describes all 2^w products for simplicity, although only Γ products are required.
  • Gate optimization: 2^w−w−1 Toffoli gates are necessary for select(V) control generation, establishing a lower bound for NCT circuits.The lower bound is stated for an NCT circuit implementing the control generation.
  • Binary-tree walk: The circuit walks a complete binary tree whose leaves represent all Boolean products over the w variables and their polarities.The walk starts and ends at the root and traverses each edge twice.
  • Gate optimization: 17.5·2^w+o(2^w) elementary gates are used after optimization, versus 18w^2^w+o(w^2^w) for the baseline estimate.The optimized implementation replaces Toffoli subsequences with CNOTs and other simplifications.

H.3 Phase computation and segmented algorithm

QSP phase computation is difficult for long, single-segment evolutions, so the paper introduces segmentation to make preprocessing tractable and obtain a complete implementation. Segmentation increases asymptotic complexity, but its phased-iterate overhead is modest for the studied system sizes.

  • Phase computation: For n=10, t=n, and ϵ=10^-3, the required M=1100 phased iterates make direct QSP phase computation impractical.Computing the phases requires high-precision roots of a degree-2M polynomial, and computation was prohibitive above M≈32.
  • Segmented algorithm: The segmented QSP algorithm divides the evolution into r shorter segments whose phase angles can be computed tractably.Each segment uses a fixed number M of phased iterates independent of system size.
  • Trade-off: Segmentation sacrifices the optimal single-segment asymptotic complexity but enables a complete implementation with moderate overhead.The optimal QSP approach relies on simulating the entire evolution as one segment.
  • Segmented algorithm: With fixed M, segmented QSP has gate complexity O(n^(3+4/M)), because it uses O(n^(2+4/M)) segments and O(n)-size phased iterates.The stated scaling assumes t=n and α=O(n).
  • Segmented algorithm: For the studied parameter range, segmentation uses only a factor of 2–3 more phased iterates than the optimal implementation.The comparison is reported for the range shown in Figure 7.

H.4 Empirical error bounds

The paper compares analytic and empirical error bounds for QSP resource estimation. Empirical evaluation lowers the estimated cost of the full QSP algorithm, but the resulting benchmark is optimistic and is not used for the rigorous segmented implementation.

  • Empirical bounds: The empirical Jacobi–Anger bound improves estimated QSP gate counts by a factor of 1.25–1.45 for 10≤n≤100.The estimate comes from numerical evaluation for sizes 10–20 followed by extrapolation.
  • Empirical bounds: Analytic and empirical fits give QSP complexities O(n^2.988) and O(n^2.939), respectively.Each phased iterate has gate complexity O(n) with the improved select(V) implementation.
  • Scope of estimates: The empirical bound is applied to the non-segmented QSP algorithm as its most optimistic resource benchmark.It is not applied to segmented QSP because the savings are small and rigorous guarantees are the main goal there.
  • Scope of estimates: The full empirical error analysis is challenging because QSP uses n+⌈log 4n⌉+1 qubits and requires direct classical evaluation of small instances.The paper reports preliminary numerical investigation rather than a complete overall empirical bound.

I Detailed results

The results compare product-formula orders and error bounds, then benchmark product formulas against Taylor-series and quantum-signal-processing methods. Rigorous bounds favor fourth-order product formulas or segmented QSP, while empirical bounds substantially reduce product-formula costs.

  • Product formulas: Fourth-order product formulas outperform other orders across system sizes 13–500 when rigorous bounds are required, except at very small sizes.With the minimized bound, second order is preferred only for n ≤28.
  • Product formulas: 102 to over 10^4 times more gates make first-order formulas much worse than fourth- or sixth-order formulas.The comparison spans orders and bounds in the considered simulations.
  • Limitations: The commutator bound was not evaluated above fourth order because computing it is difficult in practice.The authors expect fourth order would still outperform sixth order with an analogous commutator bound, based on analytic and minimized-bound results.
  • Error bounds: A commutator bound saves more than 10× over the minimized bound, while the empirical bound saves about 100× to over 500× further.The empirical savings range from system sizes in the 10s to sizes around 100.
  • Error bounds: Commutator and empirical bounds improve the dependence on system size n, reducing the observed slope of fourth-order product-formula gate counts.The commutator-bound lowest-order error changes from O(n4k+2/r2k+1) to O(n4k+1/r2k+1).
  • Limitations: The empirical bound applies directly only to the studied system and parameters, although extrapolations at h = 1/10 and h = 10 showed similar n exponents with slightly different prefactors.This supports qualitative similarity across those tested parameter changes, not general applicability.
  • Algorithm comparison: For n ≥30, Taylor series outperforms rigorously guaranteed fourth-order product formulas, but uses 116–171 qubits for system sizes 20–50, whereas product formulas have no space overhead.QSP outperforms Taylor series in both circuit size and qubit count.
  • Algorithm comparison: Among completely implemented algorithms with rigorous guarantees, segmented QSP has the lowest gate counts and uses at least 5× fewer cnot gates than fourth-order product formulas or Taylor series.Full QSP has lower gate complexity empirically but requires classically computing difficult rotation angles; heuristic product formulas require no ancillas.

I.3 Circuit optimization

Automated optimization reduces product-formula circuit sizes substantially, especially for higher-order formulas, and can change which algorithms are preferable at smaller system sizes. Taylor-series and QSP circuits receive much smaller cnot reductions than product formulas.

  • Optimization results: About 30% reductions in both cnot and T counts occur for fourth-order product formulas across the range of interest.The optimization improves TS and QSP circuits less significantly.
  • Optimization results: 33% cnot reductions occur for product-formula circuits, compared with about 1% for TS and QSP circuits in the Clifford+Rz estimates.The authors expect heavier optimization could improve TS and QSP reductions without qualitatively changing relative performance.
  • Relative performance: Optimization makes product formulas outperform Taylor series in cnot count for system sizes smaller than about 30.Before optimization, Taylor series outperforms the best rigorously guaranteed product formula for all shown sizes.
  • Optimization results: Higher-order product formulas retain essentially the same relative optimization improvements under different error bounds.The circuit structure is unaffected by the choice of error bound.
  • Optimization results: First-order product formulas admit no cnot or Rz reduction, while higher-order formulas achieve about 33% cnot and 29% Rz reductions.The Rz savings exploit reflection symmetry in formulas of order 2 and higher.
Loading 1711.10980v1…