PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization

Ian D. Kivlichan, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut Neven, Ryan Babbush

arXiv:1902.10673v4quant-phphysics.chem-ph

TL;DR

Fault-tolerant simulation of condensed-phase correlated electrons remains costly, especially when prior analyses target fixed additive energy error. This paper combines optimized low-order Trotter formulas with phase estimation and finds favorable scaling for extensive-error targets, while estimating surface-code resources for classically intractable instances.

  • Problem

    Prior quantum-simulation analyses often target fixed additive energy error, whereas condensed-phase applications commonly seek relative precision such as energy per unit cell.

  • Method

    The paper combines second-order Trotter formulas, optimized split-operator and fermionic swap-network circuits, Hamming weight phasing, and phase estimation.

  • Results

    Hubbard and plane-wave simulations achieve roughly O(1) and O(N^2) T complexities, respectively, for extensive-error targets, with classically intractable instances requiring a few hundred thousand physical qubits.

  • Takeaways & Limitations

    Optimized low-order Trotter methods can provide practical fault-tolerant simulation costs for condensed-phase correlated-electron models in the analyzed regime.

  • Takeaways & Limitations

    The analysis excludes some asymptotically better techniques because their large constant factors are unfavorable for the system sizes considered, and operator-norm Trotter bounds can be extremely loose.

Abstract

from arXiv · show

Recent work has deployed linear combinations of unitaries techniques to reduce the cost of fault-tolerant quantum simulations of correlated electron models. Here, we show that one can sometimes improve upon those results with optimized implementations of Trotter-Suzuki-based product formulas. We show that low-order Trotter methods perform surprisingly well when used with phase estimation to compute relative precision quantities (e.g. energies per unit cell), as is often the goal for condensed-phase systems. In this context, simulations of the Hubbard and plane-wave electronic structure models with $N < 10^5$ fermionic modes can be performed with roughly $O(1)$ and $O(N^2)$ T complexities. We perform numerics revealing tradeoffs between the error and gate complexity of a Trotter step; e.g., we show that split-operator techniques have less Trotter error than popular alternatives. By compiling to surface code fault-tolerant gates and assuming error rates of one part per thousand, we show that one can error-correct quantum simulations of interesting, classically intractable instances with a few hundred thousand physical qubits.

1 Introduction

The paper argues that condensed-phase simulations often target extensive energy errors, making low-order Trotter methods effective with phase estimation. It develops optimized fault-tolerant implementations and estimates practical costs for Hubbard and plane-wave models.

  • Scope: The study targets classically difficult condensed-phase problems, including the uniform electron gas and Hubbard model, using surface-code fault tolerance.The resource analysis focuses on T and Toffoli gates and logical-qubit requirements.
  • Approach: The work combines second-order Trotter formulas, optimized Trotter-step circuits, Hamming weight phasing, and phase estimation.The studied steps include fermionic swap networks and split-operator formulas, with numerical Trotter-error bounds used to estimate costs.
  • Motivation: Extensive energy errors are relevant for condensed-phase quantities such as energy per unit cell and response properties.Absolute energies become meaningless in the thermodynamic limit, while allowable errors for response properties can grow with system size.
  • Main result: Low-order Trotter methods perform especially well with phase estimation when targeting extensive energy errors.Allowing the target error to grow with system size ameliorates the poor time and precision scaling of low-order formulas.
  • Main result: Hubbard and plane-wave electronic structure simulations require roughly O(1) and O(N^2) T complexities, respectively, within the analyzed regime.The estimates apply until models become so large that only one Trotter step is needed or other assumptions break down.

2 Hamiltonians and Trotter Steps

The paper analyzes fermionic Hamiltonians for plane-wave electronic structure and Hubbard models, then compares optimized swap-network and split-operator Trotter steps. Hamming weight phasing reduces selected rotation costs, while numerical gate counting evaluates fault-tolerant implementations.

  • Hamiltonians: Plane-wave Hamiltonians describe periodic materials and the uniform electron gas through coefficients determined by orbital positions and momentum modes.The analysis uses N spin-orbitals and includes materials such as lithium hydride, diamond, graphite, and crystalline silicon.
  • Hamiltonians: The Hubbard model captures nearest-neighbor hopping, on-site interactions, and chemical potential, while exhibiting correlated-electron phases.Its studied interaction is U for opposite-spin electrons occupying the same orbital.
  • Trotter steps: The split-operator method alternates kinetic evolution in the momentum basis with potential evolution in the position basis.Basis changes use Givens rotations or the fermionic fast Fourier transform.
  • Trotter steps: Hamming weight phasing reduces split-operator potential simulation from O(N^2 log(1/epsilon)) to O(N^2 + N log N log(1/epsilon)).The reduction exploits translation invariance of the interaction for jellium and materials.
  • Scope: The analysis omits several asymptotically improving techniques because their large constant factors make them unhelpful for the considered system sizes.Alternative basis discretizations may also provide better molecular accuracy while remaining compatible with the Hamiltonian form.
  • Cost analysis: Gate costs are computed numerically by combining compatible rotations while counting arbitrary rotations, T gates, and Toffoli gates.The procedure depends on the ordering and structure of each Trotter step, including Hamming weight phasing ancillas.

3 Resource Analysis for Fault-Tolerant Phase Estimation

The resource analysis bounds Trotterization, phase-estimation, and synthesis errors, then optimizes second-order split-operator and fermionic-swap circuits for fault-tolerant ground-state energy estimation. Relative precision can make Hubbard costs nearly constant over studied sizes, while resource estimates reach classically intractable instances with substantial but finite surface-code resources.

  • Trotter and error analysis: Second-order Trotter formulas are implemented by evolving forward for t/2 and then in reverse, using split-operator and fermionic swap network circuits.The study computes optimized T, Toffoli, and arbitrary-rotation costs for these steps.
  • Trotter and error analysis: The improved Trotter error bound is tighter, non-perturbative, and valid for all values of t.The bound defines the Trotter error norm W from sums of nested Hamiltonian commutators.
  • Fault-tolerant cost model: Phase estimation converts bounds on W and eigenphase shifts into the number of Trotter-step applications required for a target energy precision.The analysis separately accounts for Trotter-Suzuki, phase-estimation, and circuit-synthesis errors.
  • Resource estimates: For jellium and Hubbard models, the reported T-cost scaling ranges from O(1) to O(N^1/2) for relative precision and from O(N^3/2) to O(N^2) for absolute precision.The Hubbard estimates use U/τ = 4 and 8, with separate split-operator and fermionic-swap implementations.
  • Fault-tolerant cost model: For Hubbard U/τ = 4, (∆E_TS)^3/W remains below unity until hundreds of thousands of spin-orbitals, beyond the systems studied.This condition supports the small-error approximation used in the cost analysis over the reported range.
  • Resource estimates: Surface-code estimates use selected Trotter implementations and show that adding Hamming-weight-phasing ancillae can reduce execution time by as much as an order of magnitude.The additional physical-qubit requirement is typically about 25% of the original requirement.

4 Discussion

The paper finds that optimized low-order Trotter methods can outperform prior approaches in extensive-error regimes and support surface-code simulations of classically intractable instances. It also identifies resource tradeoffs and open opportunities for reducing estimates further.

  • Asymptotic comparisons: O(1) T complexity for Hubbard simulations with extensive error, compared with O(N) for prior linear-combinations-of-unitaries methods, until N exceeds 10^5.For jellium, the paper reports O(N^2) scaling in this regime.
  • Asymptotic comparisons: The methods match the extensive-error scaling of another Trotter-based approach, while providing a concrete circuit implementation applicable to electronic structure Hamiltonians.The comparison concerns Hubbard and jellium simulations under extensive error.
  • Fault-tolerant feasibility: 10^-3 physical error rates still permit error-corrected simulations of classically intractable instances using only a few hundred thousand physical qubits.The resource reduction combines low asymptotic scaling, Hamming weight phasing, and lattice-surgery compilation.
  • Fault-tolerant feasibility: Table 2 varies logical ancillae, logical system qubits, Toffoli gates, T gates, physical qubits, and execution time across Hubbard and uniform-electron-gas cases.It assumes physical operation error rates p = 10^-3 and p = 10^-4 and varies ancilla allocation for Hamming weight phasing.
  • Open directions: More accurate Trotter-error estimates, higher-order formulas, and direct circuit simulations could reduce the reported T-count estimates by orders of magnitude.These are presented as open research directions rather than established improvements.

A.1 Combining arbitrary parallelizable rotations by Hamming weight phasing

Hamming weight phasing replaces many parallel equal-angle rotations with rotations controlled by the binary digits of their Hamming weight. The technique reduces synthesized rotations but trades that savings against Toffoli gates, T gates, and ancilla qubits.

  • Core construction: The transformed circuit preserves the phases of all logical states while reducing the number of costly arbitrary rotations that require T-gate synthesis.For three input qubits, the construction applies Rz(θ) to the 1s bit and Rz(2θ) to the 2s bit.
  • Core construction: n parallel Rz(θ) rotations can be replaced by ⌊log2 n + 1⌋ rotations on the binary Hamming-weight register.The replacement uses Rz(θ), Rz(2θ), Rz(4θ), and higher powers as needed.
  • Resource tradeoffs: n −1 Toffoli gates, equivalently 4n −4 T gates, and n−1 ancilla qubits suffice to form the Hamming-weight register.Uncomputing the register requires no further T gates or ancillae.
  • Resource tradeoffs: When θ = mπ/2^k, addition can stop at weight 2^(k−2) because further adders save one T gate while costing four.This special case applies when the rotation angle has the stated dyadic form.
  • Resource tradeoffs: Tsynth ≳ 10 is the break-even point at which Hamming weight phasing improves T-gate cost even for small n.Repeat-until-success synthesis gives Tsynth ≈ 1.15 log2(1/ϵsynth) + 9.2.
  • Resource tradeoffs: The method’s savings must be balanced against allocating n−1 ancilla qubits that could otherwise support T-gate distillation.Lower-ancilla variants increase the T-gate requirement.

A.2 Hamming weight phasing with limited ancilla

Limited-ancilla variants preserve Hamming weight phasing when the full register cannot be formed at once. They reduce space by processing rotation groups, but incur additional T or Toffoli costs.

  • Tradeoff: Reducing ancillae is achieved at the cost of requiring more Toffoli or T gates.The paper allows different schemes to be used within the same circuit according to local rotation counts and available ancillae.
  • Constant-ancilla scheme: With r < n−1 ancillae, groups of r+1 rotations are combined repeatedly into ⌊log2(r+1)+1⌋ rotations.The procedure repeats until all n original rotations have been processed.
  • Square-root grouping: The grouping scheme divides n rotations into groups of size ⌊√n⌋, accumulates their Hamming weights, and phases the total register.Each group uses ⌊√n−1⌋ ancillae, while the total register uses ⌊log2 n + 1⌋ qubits.
  • Square-root grouping: The square-root grouping method uses ⌊√n⌋+⌊log2 n⌋ ancilla qubits instead of n−1, while requiring slightly more than twice the baseline 4n−4 T gates.The additional cost comes from recomputing and subtracting group Hamming weights.
  • Hybrid use: For n = 500 rotations, 30 ancilla qubits support combining the rotations through Hamming weight phasing.For a separate set of 50 rotations, the same ancillae require 192 T gates and reduce the synthesized rotations from 50 to 10.

A.3 Catalyzing two

The paper applies Hamming weight phasing to catalyze two T gates from a reusable seed state. The catalysis circuit is equivalent to an adder-based construction but changes when the T-gate resource is consumed.

  • Catalysis construction: One ancilla seed state enables catalyzing T gates on two other qubits using one Toffoli and one T gate, or five T gates given the seed state.The seed state is synthesized once at the beginning and is not consumed during later generation.
  • Catalysis construction: The catalysis circuit is obtained by moving a T gate from the standard adder-based Hamming-weight circuit to the computation’s beginning.This moved gate prepares the seed state used by the catalysis circuit.
  • Resource accounting: The seed state can be reused anywhere after its initial synthesis because it is not consumed as T gates are generated.The initial synthesis must be performed at full cost before the rest of the computation.
  • Circuit comparison: Figure 4 compares the five-T-gate catalysis circuit with its equivalent adder-based circuit.The left circuit uses the seed-state formulation, while the right circuit is the adder-based counterpart.

B Trotter steps by fermionic swap network

The fermionic swap network simulates Hamiltonian terms as qubits become adjacent while reversing the Jordan–Wigner ordering. A symmetric second-order step restores the original ordering, and split-operator costs are governed mainly by Trotter-error-dependent step counts.

  • Fermionic swap network: The fermionic swap network alternates odd-even swap layers, simulating Hamiltonian terms whenever their spin-orbitals become neighboring qubits.The combined fermionic simulation gate evolves kinetic and potential terms before fermionically swapping the qubits.
  • Fermionic simulation gate: A fermionic simulation gate combines kinetic evolution, potential evolution, and a fermionic swap for each neighboring spin-orbital pair.The kinetic term uses X and Y operators, while the potential term uses Z operators in the Jordan–Wigner ordering.
  • First-order step: A complete first-order Trotter step is represented by the canonical-ordering boxes in Table 3, with external-potential rotations appended when needed.The table contains five swap layers for the five spin-orbital example.
  • Second-order step: The second-order symmetric step runs the network forward and backward, restoring the spin-orbitals to their original ordering.The reverse pass symmetrizes the first-order construction.
  • Split-operator comparison: For large r, merging identical beginnings and endings makes the two split-operator orderings nearly equal in circuit cost; required Trotter-step counts instead dominate.The lower-error ordering is selected for each system, with V followed by T favored for the uniform electron gas at rs ≳1.

C.2 Reducing the cost of simulating the potential energy operator using Hamming weight phasing

Translation-invariant potential interactions are grouped into equal-angle layers so Hamming weight phasing replaces many arbitrary rotations with logarithmically many per layer.

  • Cost reduction: Potential-energy evolution generally requires O(N^2) arbitrary rotations, but translation invariance reduces this to O(N log N) rotations.The reduction applies to the electronic-structure basis considered and incurs additional Toffoli or T gates.
  • Hamming weight phasing: Hamming weight phasing combines M parallel equal-angle rotations into ⌊log2 M + 1⌋ rotations using M −1 ancilla qubits.The construction adds 4M −4 T gates or M −1 Toffoli gates.
  • Layer construction: Interactions sharing an index vector s are placed in layers so every coefficient within a layer is equal, enabling full Hamming weight phasing.The layers use pairs of qubits (p, p+s).
  • Layer construction: For even N, each layer contains N/2 equal-strength interactions, while odd N requires additional layers containing lone rotations.The even case uses two layers per nonzero index vector; the odd case uses three.
  • Asymptotic cost: For both parity cases, arbitrary-rotation cost becomes O(N log N log(1/ϵ)), versus O(N^2 log(1/ϵ)) without Hamming weight phasing.The stated overhead is at most 4(N −1)^2 additional T gates or (N −1)^2 Toffoli gates.

C.3 The fast fermionic Fourier transform

The FFFT recursively changes fermionic modes between position and momentum representations using nearest-neighbor fermionic swaps and structured two-qubit gates. Its radix-2 construction supports power-of-two system sizes and has explicitly counted fault-tolerant costs.

  • Recursive construction: The FFFT implements a fermionic basis change recursively in depth O(n log n) using fermionic swaps and Fk,n gates.The recursive construction parallels the classical fast Fourier transform and requires n to be a power of two.
  • Circuit stages: Its four stages apply recursive transforms, interleave qubits into bit-reversed order, phase paired qubits, and de-interleave them.The reordering separates qubit groups by index parity before the pairwise phase gates.
  • Gate structure: The FFFT uses (n log2 n)/2 Fk,n gates and fermionic swaps in the interleave and de-interleave structure.Fermionic swaps are Clifford-only in the stated fault-tolerant model.
  • Fault-tolerant cost: For 16 qubits, the FFFT contains 70 T gates before accounting for seed-state preparation.The construction exploits pairwise T-gate synthesis in the fault-tolerant circuit.
  • 2D cost: A 2D 16 × 16 position–momentum conversion requires 2304 T and 64 Toffoli gates without spin, or 4608 T and 128 Toffoli gates with spin.For side lengths that are not powers of two, the paper uses Givens rotations instead of this FFFT construction.

C.4 Diagonalizing the kinetic energy operator using Givens rotations

Givens rotations provide a general single-particle basis-change circuit for diagonalizing number-conserving quadratic Hamiltonians. They support arbitrary transformations but require rotation counts that scale quadratically with orbital number.

  • Role of Givens rotations: Givens rotations implement arbitrary unitary transformations of fermionic mode operators, unlike the Fourier-specific FFFT.Each rotation acts by angle θ in the single-particle subspace.
  • Diagonalization: A sequence of Givens rotations can implement a basis change that diagonalizes any number-conserving quadratic Hamiltonian.The resulting diagonal phases are applied to the corresponding spin-orbital qubits, followed by the rotations in reverse.
  • Scope comparison: The FFFT is restricted to radix-2, power-of-two sizes, whereas Givens rotations use mostly arbitrary angles and handle more general transformations.The FFFT’s structured rotations are less general than the arbitrary-angle rotations in the Givens construction.
  • Rotation count: The spinless case uses exactly n(n −1)/2 Givens rotations, while the spinful case uses n(n −1).Each neighboring Givens rotation requires two arbitrary rotations in the displayed circuit construction.
  • Fault-tolerant cost: The resulting basis change requires n(n −1) arbitrary rotations without spin and 2n(n −1) with spin, plus diagonal phases.The diagonal phases add n arbitrary rotations without spin or 2n with spin.

D.1 The fermionic swap network

The section counts arbitrary rotations for fermionic-swap and split-operator Trotter steps, including spin, basis changes, and Hamming-weight-phasing optimizations.

  • Fermionic swap network: 4(N −1)² arbitrary rotations are required for the spinless uniform electron gas fermionic-swap Trotter step.Merging the first and final layers reduces the naive count by 4(N −1) rotations.
  • Fermionic swap network: (N −1)(3N −4) arbitrary rotations are required at most for the spinful fermionic-swap step.This count uses the fact that kinetic-energy terms act only within the same spin sector.
  • Fermionic swap network: 9N arbitrary rotations are required at most for the spinful Hubbard-model fermionic-swap step.The count includes on-site interactions, hopping terms, and second-order symmetrization.
  • Split-operator step: The split-operator step requires 3N arbitrary rotations for the uniform electron gas and 7N/2 for the Hubbard model.The split-operator cost combines kinetic and potential contributions, with the Hubbard potential requiring 3N/2 rotations.
  • Basis changes: A 16 × 16 FFFT costs 2304 T and 64 Toffoli gates without spin, or 4608 T and 128 Toffoli gates with spin.Basis changes are applied in both directions and twice in the symmetric split-operator step.

E Improved second-order Trotter-Suzuki error bounds

The paper derives a tighter second-order Trotter error bound that does not require small evolution time and improves prior bounds by constant factors.

  • Bound improvement: The improved second-order Trotter error bound does not require the evolution time t to be small.This extends the usual setting of Trotter-error bounds, which typically assume small t.
  • Bound improvement: The new bound is tighter than the bound in by a factor of 1/12.The factor matches the Baker-Campbell-Hausdorff expansion.
  • Derivation: The second-order Trotter formula approximates e−iHt using a symmetric product of exponentials of the Hamiltonian terms.The paper uses this formula as the basis for the subsequent energy-error analysis.
  • Derivation: For two Hamiltonian terms, the derivation writes Ht = A + B and introduces H(x) = B + (1 −x)A.The error is analyzed through derivatives and nested commutators of the interpolating Hamiltonian.

F Phase estimation circuit primitives from a Trotter step

The phase-estimation primitives use directionally controlled Trotter evolution, exploiting symmetric decompositions to reverse time evolution without controlled-unitary rotations.

  • Directional control: Directionally controlled evolution maps |c⟩|ψ⟩ to |c⟩e−iHt(−1)^c|ψ⟩.The control selects forward or inverse time evolution.
  • Directional control: Symmetric Trotter formulas permit inverse evolution by reversing the direction of each Hamiltonian-term evolution.This decomposition property does not hold for nonsymmetric lowest-order splittings.
  • Interaction terms: Potential-term directional control is implemented with controlled-NOT gates on the phase-estimation ancilla and target qubits.The resulting interaction circuit is shown in Figure 10.
  • Cost: The directionally controlled circuit uses the same number of arbitrary rotations and T gates as the bare Trotter step.The fermionic-swap construction is more challenging because it integrates kinetic terms within a constant-spin manifold.

G Trotter error numerics

The numerical analysis computes second-order Trotter error norms from ordered Hamiltonian decompositions and compares fermionic-swap with split-operator schemes across electron models.

  • Error-norm computation: W is computed by summing L³ double commutators for a Hamiltonian with L terms.For the uniform electron gas, L scales quadratically with N, giving up to O(N⁶) double commutators.
  • Error-norm computation: The split-operator error norm has only two terms because kinetic and potential terms are grouped separately.The ordering can place either kinetic or potential energy first.
  • Error tradeoff: The smaller split-operator error bound can be selected by choosing whether kinetic or potential energy is simulated first.For sufficiently many Trotter steps, this choice does not significantly change the gate count.
  • Numerical scale: A 12 × 12 spinful uniform electron gas instance contains 47,952 Hamiltonian terms and 44,496 fermionic-swap Trotter-order terms.Computing its error norm can require evaluating as many as 10^14 double commutators and more than 100 GB of memory.
  • Numerical results: The study reports Trotter-error norms for 2D and 3D uniform electron gases, 2D and 3D Hubbard models, and several materials.The uniform-electron-gas norms are reported in Ha³ and plotted with power-law fits.

H T-count minimization

The T-count minimization balances Trotter, phase-estimation, and synthesis errors while targeting either relative or absolute energy precision. The analysis uses error norms and gate-cost models to optimize phase-estimation simulations across Hubbard and uniform-electron-gas systems.

  • Cost model: The objective minimizes total T and Toffoli gates subject to a precision budget combining Trotter-Suzuki, phase-estimation, and circuit-synthesis errors.The Trotter error norm, arbitrary-rotation counts, and direct T/Toffoli gates enter the cost model.
  • Error numerics: The Hubbard Trotter-error data compare fermionic-swap and split-operator steps across system sizes and interactions, with Figure 13 fitting the error norms to power laws.The error norm is denoted W_X for algorithm X and is measured in cubed Hartree.
  • Precision targets: Two precision targets are optimized: relative precision sets ΔE as a fraction of total system energy, while absolute precision fixes ΔE for each model class.For jellium and materials, the absolute target is ΔE = 0.0016 Hartree; for the Hubbard model, it is ΔE = τ/100.
  • Cost numerics: Figure 14 bounds T-gate counts for 3D uniform-electron-gas phase estimation across Wigner-Seitz radii, using both relative and absolute energy-precision targets.The relative target is within 0.5% of total system energy, the absolute target is ΔE = 0.0016 Hartree, and 14 ancillas support Hamming-weight phasing.
  • Precision targets: 1.02 and 0.74 are the Hubbard energy-per-site magnitude bounds used for relative targets at U/τ = 4 and U/τ = 8, respectively.These bounds ensure the precision tolerance remains below 0.5% of the total ground-state energy.
  • Scaling boundary: The relative-precision Hubbard scaling is finite-range because the required number of Trotter steps decreases with system size and eventually reaches one only at hundreds of thousands of spin-orbitals.Figure 15 shows the corresponding power-law fit, whose extrapolated intercept is far above the system sizes considered.
Loading 1902.10673v4…