PaperlayerView exact revision on arXiv

Source-linked AI summary

Fault-Tolerant Quantum Simulations of Chemistry in First Quantization

Yuan Su, Dominic W. Berry, Nathan Wiebe, Nicholas Rubin, Ryan Babbush

arXiv:2105.12767v3quant-phphysics.chem-ph

TL;DR

First-quantized chemistry algorithms had not been fully costed with constant factors, limiting resource comparisons with second-quantized methods. The paper compiles and optimizes two such algorithms, finding qubitization often more practical and sometimes far less resource-intensive than second quantization.

  • Problem

    First-quantized chemistry methods lacked rigorous constant-factor estimates, while many chemistry simulations become impractical near the continuum limit as their qubit requirements scale with basis size.

    Source: §I · p. 2

  • Method

    The authors compile and optimize first-quantized qubitization and interaction-picture algorithms for chemistry in an error-correctable gate set.

    Source: B. Overview of the Hamiltonian… · p. 8

  • Results

    The qubitization algorithm is usually more practical, and first-quantized methods often use much less surface-code spacetime volume for millions of plane waves than second-quantized methods use for hundreds of Gaussian orbitals.

    Source: B. Conclusion and outlook · p. 51

  • Takeaways & Limitations

    The authors conclude that first-quantized methods are promising for realistic materials and highly competitive for single molecules, often requiring fewer surface-code resources.

    Source: B. Conclusion and outlook · p. 50

    The reciprocal lattice defined for a cubic plane-wave mesh cannot be used for non-cubic conventional cells, such as hexagonal systems, which require non-orthogonal Bravais vectors.

    Source: B. Conclusion and outlook · p. 52

Abstract

from arXiv · show

Quantum simulations of chemistry in first quantization offer important advantages over approaches in second quantization including faster convergence to the continuum limit and the opportunity for practical simulations outside the Born-Oppenheimer approximation. However, as all prior work on quantum simulation in first quantization has been limited to asymptotic analysis, it has been impossible to compare the resources required for these approaches to those for more commonly studied algorithms in second quantization. Here, we analyze and optimize the resources required to implement two first quantized quantum algorithms for chemistry from Babbush et al that realize block encodings for the qubitization and interaction picture frameworks of Low et al. The two algorithms we study enable simulation with gate complexities $\tilde{\cal O}(\eta^{8/3}N^{1/3}t+\eta^{4/3}N^{2/3}t)$ and $\tilde{\cal O}(\eta^{8/3} N^{1/3} t)$ where $\eta$ is the number of electrons, $N$ is the number of plane wave basis functions, and $t$ is the duration of time-evolution ($t$ is inverse to target precision when the goal is to estimate energies). In addition to providing the first explicit circuits and constant factors for any first quantized simulation and introducing improvements which reduce circuit complexity by about a thousandfold over naive implementations for modest sized systems, we also describe new algorithms that asymptotically achieve the same scaling in a real space representation. We assess the resources required to simulate various molecules and materials and conclude that the qubitized algorithm will often be more practical than the interaction picture algorithm. We demonstrate that our qubitized algorithm often requires much less surface code spacetime volume for simulating millions of plane waves than the best second quantized algorithms require for simulating hundreds of Gaussian orbitals.

I. INTRODUCTION

The paper develops and optimizes concrete fault-tolerant circuits for first-quantized chemistry simulation, enabling resource comparisons with second-quantized methods.

I. INTRODUCTION

  • The optimized qubitization algorithm often proves more practical than the interaction-picture method and is highly competitive with second-quantized approaches, while reducing naive circuit complexity by about three orders of magnitude.The resource analysis finds that both approaches can require significantly fewer resources than second-quantized approaches for comparable accuracy.Source: §I · p. 3

A. Background on representing molecular Hamiltonians in a first quantized plane wave basis

  • First quantization uses O(η log N) qubits and can achieve sublinear gate scaling in N; plane waves suit this approach, though they often require many more basis functions than Gaussian orbitals.The plane-wave algorithm has e O(η^8/3 N^1/3) Toffoli complexity, while its systematic continuum convergence and applicability beyond the Born-Oppenheimer approximation are advantages for high-precision and nuclear-dynamics simulations.Source: A. Background on representing… · pp. 6–7

B. Overview of the Hamiltonian simulation frameworks deployed in this work

  • The paper focuses on Born-Oppenheimer eigenstate preparation via phase estimation, studying qubitization and interaction-picture algorithms adapted to first-quantized chemistry; both extend to non-Born-Oppenheimer dynamics with minor modifications.The non-Born-Oppenheimer Hamiltonian adds nuclear kinetic and potential terms analogous to the electronic terms.Source: B. Overview of the Hamiltonian… · p. 8

H · SELH · PREPH . (18)

  • Qubitization encodes Hamiltonian energies in quantum-walk eigenphases, enabling phase estimation to project onto an eigenstate and estimate its energy; precision ϵ requires O(λ/ϵ) controlled-Q uses.Multiplexed qubitization can halve phase-estimation complexity, and the quantum-walk framework also supports time evolution under the non-Born-Oppenheimer Hamiltonian with trivial modifications and marginal additional cost.Source: H · SELH · PREPH . (18) · pp. 8–9

Introduction

  • For qubitization, the authors detail circuits for the operators and achieve an eO(η) gate complexity for Q, using controlled momentum-register swaps and kinetic-term handling after failed potential-state preparation.They also eliminate amplitude amplification in some state-preparation cases and decompose kinetic energy into bit products to reduce Toffoli cost.Source: H · SELH · PREPH . (18) · pp. 10, 12
  • At η = 100 and N = 10^6, first quantization requires about 2 × 10^3 system qubits, while second quantization requires at least 10^6 logical qubits.The large plane-wave basis motivates first quantization, while its qubitized gate complexity scaling as eO(N^(2/3)) motivates the interaction-picture algorithm, which avoids polynomial scaling in λT.Source: H · SELH · PREPH . (18) · pp. 10–11
  • For interaction-picture simulation, the authors provide concrete Dyson-series circuits and Toffoli-cost bounds, with a kinetic-energy register, a new Dyson-series qubitization, and higher-order time-integral discretization.The approach builds on the interaction-picture technique of Low et al. [3]; its new Dyson-series qubitization avoids amplitude amplification for eigenvalue measurement.Source: H · SELH · PREPH . (18) · pp. 11–12
  • First-quantized methods often require much less surface-code spacetime volume for millions of plane waves than second-quantized methods require for hundreds of Gaussian orbitals, and qubitization is usually more practical.The comparisons assess realistic material Hamiltonians and non-periodic molecules; the paper focuses on Toffoli complexity and ancilla counts, noting that the reported algorithms have matching asymptotic Clifford complexity.Source: H · SELH · PREPH . (18) · pp. 11–12
  • The work provides explicit, optimized circuits and the first constant factors for first-quantized chemistry algorithms, reducing those constants by more than a thousandfold.The circuits support resource comparisons with second-quantized approaches and between qubitization and interaction-picture simulation.Source: H · SELH · PREPH . (18) · p. 12

II. THE QUBITIZATION BASED ALGORITHM

The algorithm block-encodes the first-quantized chemistry Hamiltonian using state-preparation and selection circuits, then uses phase estimation to estimate its spectrum. Its implementation addresses the potential-term preparation failure while controlling the block-encoding normalization.

II. THE QUBITIZATION BASED ALGORITHM

  • Phase estimation on the qubitization operator estimates the spectrum because its eigenvalues encode the Hamiltonian energies.The Hamiltonian is represented as a linear combination of unitaries, using state preparation and selection subroutines.Source: §II · p. 12
  • The potential-state preparation succeeds with probability close to 1/4, so using it directly raises the normalization toward λT + 4(λU + λV).A single oblivious amplitude-amplification step can raise success close to unity, but triples the state-preparation cost and may add gate overhead.Source: §II · p. 13
  • The new selection operator applies the kinetic selection after U + V preparation fails, and in the special case λT = 3(λU + λV) achieves normalization λT + λU + λV.This proceeds rather than discarding the failure branch.Source: §II · p. 13
  • An ancilla adjusts relative amplitudes across parameter regimes: for λT < 3(λU + λV), normalization is 4(λU + λV), while for λT > 3(λU + λV), it is λT + λU + λV.The amplitudes are tuned so the encoded operator remains proportional to T + U + V.Source: §II · pp. 13–14

A. Circuit implementation of qubitization

The circuit implementation combines state preparation and selection for the kinetic and potential terms, sharing particle-index registers and controlling momentum operations according to the selected term. It also specifies the block-encoding ancillas and analyzes preparation success and circuit costs.

A. Circuit implementation of qubitization

  • The circuit combines state preparation and selection for T, U, and V, reusing particle-index registers i and j to control term-specific momentum operations.The implementation swaps selected momenta into temporary ancillas for arithmetic.Source: A. Circuit implementation of… · p. 15
  • Selection implements the potential terms with controlled momentum addition or subtraction and boundary checks, while an ancilla makes the U and V selection self-inverse.The kinetic selection applies a phase determined by momentum bits.Source: A. Circuit implementation of… · p. 16
  • For the Born-Oppenheimer Hamiltonian, the stated lemma gives an exact block encoding with Na = 10 + 2nη + 3np + 2⌈log(np −1)⌉ + ⌈log(L)⌉ ancilla qubits.The lemma treats SEL as a defined operator and does not cost its implementation.Source: A. Circuit implementation of… · p. 16
  • For br = 7, the equal-superposition preparation success is usually above 0.999; in the charge-neutral case, the U/V selection ratio is 2 and needs a superposition over only three values.The paper also bounds the preparation error by (3/2)2(π/2br)2 with a slight adjustment to the rotation angle.Source: A. Circuit implementation of… · p. 18

B. Block-encoding the kinetic operator

The kinetic block encoding prepares bit-based momentum superpositions and routes selected momenta through temporary ancillas. The U and V preparation uses nested boxes and success flags to prepare momentum weights, with failure probability and inverse-circuit costs explicitly addressed.

B. Block-encoding the kinetic operator

  • The kinetic encoding prepares superpositions over momentum-bit indices w, r, and s, using unary preparation for r and s and CNOTs to convert the encoding.The w superposition costs 13 Toffolis, and the r,s preparation costs np −2 Toffolis.Source: B. Block-encoding the kinetic operator · pp. 19–20
  • Momentum registers i and j are swapped into ancillas so term-specific operations act on selected momenta rather than being controlled across every register.The passage gives a swap-control cost of 12ηnp plus 4η −8 Toffolis.Source: B. Block-encoding the kinetic operator · p. 20

C. State preparation for U and V

  • The U and V operators require state preparation weighted by 1/∥kν∥2, built from nested momentum boxes and flagged tests for preparation failures.The passage identifies four failure sources, including box membership and the inequality test.Source: C. State preparation for U and V · pp. 21–22
  • The U + V state preparation succeeds with probability around 1/4, while retaining arithmetic ancillas lets much of its inverse be implemented with Clifford gates.A single amplitude-amplification step raises success close to 1; only the controlled Hadamards retain non-Clifford cost in the inverse preparation.Source: C. State preparation for U and V · pp. 21, 23

D. The SEL operations for U and V

This section specifies the SEL implementation for U and V and analyzes the Toffoli cost of constructing the qubitization operator. It refines finite-precision parameter choices and error bounds, accounting for error sources separately and treating catalytic-state preparation as negligible relative to the algorithm.

D. The SEL operations for U and V

  • SEL swaps momenta into ancillae, conditionally adds or subtracts ν, and uses overflow qubits to exclude out-of-box terms through block-encoding selection, without an extra phase gate.The operations also swap the ancillae back into the momentum registers.Source: D. The SEL operations for U and V · pp. 24–25
  • Converting signed momenta to two’s complement and controlling component-wise addition or subtraction yields costs of 12(np − 2) conversion Toffolis and 12(np + 1) controlled-addition Toffolis.The controlled swaps cost 12ηnp.Source: D. The SEL operations for U and V · p. 24
  • The nuclear phase is computed by multiplying signed components and adding or subtracting their products into a phase-gradient register, with Toffoli cost 3[2npnR − np(np + 1) − 1] for nR > np or 3nR(nR − 1) for nR ≤ np.The maximum ancilla use is 2nR − 4 qubits; the paper also gives 6npnR as a convenient approximate Toffoli cost.Source: D. The SEL operations for U and V · pp. 25–26

E. Total cost of constructing the qubitization operator

  • Numerical testing finds the finite-M state-preparation error sum is about 50% of its upper bound, reducible to about 30% by choosing α in the stated range.The phase-estimation RMS energy error after m steps is πλ/(2m).Source: E. Total cost of constructing the… · p. 29
  • Theorem 4 gives the Toffoli count for estimating a Hamiltonian eigenvalue to RMS error ϵ, with amplitude amplification setting a = 3 rather than 1.The count includes the block-encoding costs, reflection overhead, and O(log(1/ϵ)) phase-estimation processing; it assumes phase-gradient and |T⟩ resources are available.Source: E. Total cost of constructing the… · p. 30
  • The total RMS error is bounded by combining phase-estimation error and other errors in quadrature, with bounds assigned to finite M, nuclear positions, and the T versus U + V rotation.The nuclear-position bound uses δR = Ω^(1/3)/2^(nR+1).Source: E. Total cost of constructing the… · p. 31
  • The phase-gradient and |T⟩ states are used catalytically for phase rotations and controlled Hadamards, and their initial preparation has negligible complexity.Source: E. Total cost of constructing the… · p. 31
  • The parameter-selection procedure sets initial error allowances, derives minimum bit counts, updates the error bounds, then searches nearby bit counts for the lowest Toffoli cost.The described search tests four bit counts below and above the initial values for nM, nR, and nT.Source: E. Total cost of constructing the… · p. 31
  • Computing the exact state-preparation error bound is identified as an improvement over using the bound from Lemma 3.Source: E. Total cost of constructing the… · p. 31
  • Choosing nT so α lies between 1 − 3/(2M) and 1 − 1/M makes εM about 30% of the Lemma 3 bound, with no additional finite-nT error.The required nT is typically nM plus 4 to 8 bits.Source: E. Total cost of constructing the… · p. 31

III. THE INTERACTION PICTURE BASED ALGORITHM

The interaction-picture algorithm splits H=A+B, with ||B|| much smaller than ||A||, and implements the Dyson-series evolution using an efficiently implementable evolution under A and a block encoding of B. For phase estimation, the paper qubitizes the pre-amplified interaction-picture subroutine to reduce implementation cost.

III. THE INTERACTION PICTURE BASED ALGORITHM

  • The method assumes H=A+B with ||B|| much smaller than ||A||, an efficiently implementable e^−isA, and a block encoding of B with normalization λB ≥ ∥B∥.For the plane-wave basis, the kinetic operator T satisfies the stated efficient-exponentiation condition.Source: §III · pp. 31–32
  • The selection operations, state preparation, and unpreparation implement the Dyson-series expansion as a linear combination of unitaries up to normalization β.The selection operators act on distinct ancilla registers and the same target register.Source: §III · pp. 32–33
  • Preparing and unpreparing each SELB successively avoids the higher qubit cost of holding all preparation registers at once.The coefficient state uses unary-encoded k, and the proposed inequality-test approach can significantly reduce its preparation cost.Source: §III · pp. 32–33
  • Sorted time indices and midpoint discretization approximate the Dyson-series integrals, with the truncation at K and integral discretization supplying the approximation.The selected time differences control the matrix exponentials in the expansion.Source: §III · pp. 32–33
  • For phase estimation, qubitizing the pre-amplified interaction-picture subroutine significantly reduces implementation cost compared with the original repeated-step approach.The original scheme chooses τ ≈ ln(2)/λB so β ≈ 1/2, then repeats the ideal evolution λBt/ln(2) times.Source: §III · p. 33

A. Implementation choices for the interaction picture algorithm

The interaction-picture implementation choices favor sorting time registers and qubitizing sin(Hτ); kinetic-energy arithmetic is reduced by retaining and updating momentum-square sums.

A. Implementation choices for the interaction picture algorithm

  • For 16 items, sorting costs 7.5 times the number of time-register qubits, versus a log(1/ϵ) factor for compressed encoding, so the algorithm uses sorting.Each comparator uses an inequality test and controlled swap.Source: A. Implementation choices for the… · pp. 33–34
  • Method [3] removes sorting but requires τ about 72% of method 's value, making its overall complexity about 39% larger.The saved sorting cost is trivial compared with other algorithm costs.Source: A. Implementation choices for the… · p. 34
  • At τ=1/λB, the effective time is approximately 1/(eλB), and the method’s complexity is 63% of time evolution or 45% of method [3], a greater-than-twofold improvement over [3].Source: A. Implementation choices for the… · p. 35
  • With energy offset E0, nonlinear phase-estimation error scales as O((Ej−E0)^2τ^2), and its O(1/N) increase can be covered by O(1) extra steps.An initial energy estimate can place Ej−E0 near zero for linearization.Source: A. Implementation choices for the… · p. 35

B. Exponentiating the kinetic operator

  • Updating a stored sum of momentum squares costs only logarithmically in η, although momentum-register selection retains linear η dependence.The stored sum avoids recomputing the squares at each update.Source: B. Exponentiating the kinetic operator · pp. 36, 38

C. Implementing SEL and PREP

The section details the interaction-picture block encoding and its cost, culminating in a Toffoli-gate bound for estimating an eigenvalue to RMS error ϵ.

C. Implementing SEL and PREP

  • The interaction-picture block encoding updates the stored sum of momentum squares and omits the kinetic-energy components used in the earlier T+U+V costing.The updated sum is used in the U+V block encoding.Source: C. Implementing SEL and PREP · p. 38
  • Qubitizing one Dyson-series step uses effective time about 1/(eλB), with phase-estimation RMS energy error πeλB/(2N) for N steps.For the electronic-structure application, λB = λU + λV.Source: C. Implementing SEL and PREP · p. 38

D. Total cost of the interaction picture simulation

  • With τ=1/λB, the Dyson-series truncation error is approximately 1/(K+1)! at cutoff K.Here λB = λU + λV.Source: D. Total cost of the interaction… · p. 39
  • The time-discretization error bound uses the Hamiltonian's second derivative, tightening the prior bound based on its first derivative.The derivation is relegated to Appendix H.Source: D. Total cost of the interaction… · p. 40
  • Theorem 5 gives a Toffoli-gate cost for estimating a Hamiltonian eigenvalue to RMS error ϵ, assuming an initial estimate with accuracy ΔE.The expression includes the single-step and state-preparation costs and requires appropriately chosen phase-gradient states.Source: D. Total cost of the interaction… · pp. 42–43

IV. RESULTS AND DISCUSSION

The section assesses the resources and practical tradeoffs of first-quantized chemistry simulation, including comparisons with second-quantized and interaction-picture methods and the optimizations and conditions shaping resource differences. It also outlines potential advantages and future directions in representations, state preparation, applications, non-periodic systems, and time evolution.

A. The resources required to simulate real systems

  • The costs have no leading-order dependence on nuclear-charge locations, magnitudes, or number, unlike Gaussian-orbital algorithms whose basis and costs depend strongly on system details.Nuclear-charge count enters only in subdominant terms; at fixed spatial resolution, changing the simulation-box size does not substantially change complexity.Source: A. The resources required to simulate… · pp. 44–45
  • Although the interaction-picture algorithm has slightly better scaling in Δ, qubitization has lower cost in almost all regimes of interest; interaction picture is cheaper at η = 20 and Δ = 10^-3 a0.Source: A. The resources required to simulate… · p. 45
  • For condensed-phase materials, qubitization was most practical across the plotted regimes, with estimated costs of 10^10 to 10^12 Toffoli gates and, under stated assumptions, a few million physical qubits and a few days of runtime.The runtime estimate assumes a 1 µs surface-code cycle time; the analysis covers η = 20–200, N = 2^12–2^21, and r_s = 0.1–100.Source: A. The resources required to simulate… · p. 46, Figure 3 · p. 47
  • For N = 2.6 × 10^5 plane waves versus a triple-zeta Gaussian basis with N between 236 and 244 orbitals, qubitization used several dozen times fewer logical qubits, about 100 times fewer Toffoli gates, and approximately three orders of magnitude less surface-code spacetime volume.The table compares ethylene carbonate and LiPF6.Source: A. The resources required to simulate… · p. 50, Table VII · p. 50

B. Conclusion and outlook

  • Implementation improvements reduce arithmetic and state-preparation overheads, including replacing kinetic-energy arithmetic with controlled momentum selection and a single Toffoli multiplication.For qubitization, kinetic operations are placed in branches that would otherwise fail state preparation, avoiding amplitude amplification; for interaction picture, total kinetic energy is computed once and updated incrementally. The algorithms also reuse selected momentum registers in ancillas and use interval-center time discretization to reduce required time bits.Source: B. Conclusion and outlook · p. 51
  • Interaction-picture gains require a kinetic-to-potential energy ratio at least as large as the Dyson-series order; only a minor advantage was found for η = 20 and N = 2^21, and it diminishes as η grows.The state-preparation cost can dominate at low electron counts, while qubitization avoids amplitude amplification for that preparation.Source: B. Conclusion and outlook · p. 51
  • Pseudopotentials could remove core electrons, reducing η, and smooth the potential to accelerate plane-wave convergence, though adapting block encodings for higher-angular-momentum non-local forms is more involved.They would also make comparisons with Gaussian-basis active spaces more straightforward.Source: B. Conclusion and outlook · p. 52
  • For non-cubic symmetry, non-orthogonal Bravais vectors could generalize the reciprocal lattice, but would make computing ∥k_p∥2 more costly and require optimization.The authors also note possible convergence advantages from representing non-cubic primitive cells, even for systems with cubic conventional cells.Source: B. Conclusion and outlook · p. 52
  • The study covers only Γ-point calculations; future work could assess k-point sampling over the Brillouin zone to represent arbitrary symmetries and approach the thermodynamic limit.The authors describe supporting sampling outside the Γ-point as a relatively simple algorithm modification.Source: B. Conclusion and outlook · p. 52
  • For isolated molecules, truncating the Coulomb interaction at distance D and simulating in a box of volume (2D)3 can eliminate interactions between periodic images up to exponentially small density-tail terms.The authors propose adapting the block encoding coefficients for this truncated kernel when simulating systems with reduced periodicity [79–81, 98].Source: B. Conclusion and outlook · pp. 52–53
  • First-quantized state preparation remains under-developed, and preparing arbitrary Slater determinants may require gate complexity linear in N, making complex initial states a potentially non-negligible cost.The authors estimate that restricting preparation to fewer plane waves can make its cost negligible relative to qubitization, but the straightforward translated approach has worse scaling and warrants further study.Source: B. Conclusion and outlook · p. 53
  • Qubitization can support time evolution with minimal quantum signal processing overhead, while non-Born–Oppenheimer dynamics could aid reaction-rate calculations.Simulating nuclear kinetic and explicit nuclear-interaction terms requires block-encoding modifications; the interaction-picture technique is also compatible with adiabatic state preparation.Source: B. Conclusion and outlook · p. 53
  • Real-space algorithms using a grid-like representation achieve asymptotically the same complexity as the paper’s qubitization and interaction-picture algorithms, though their constant factors differ.Their non-periodic representation may benefit non-periodic systems, motivating further comparison of constant factors.Source: B. Conclusion and outlook · p. 53
  • The authors expect first-quantized methods to become increasingly important for chemistry, citing easier removal of the Born–Oppenheimer approximation, more efficient accuracy refinement, and favorable scaling with reasonable constant factors.They expect Gaussian-orbital second-quantized methods to remain competitive for small non-periodic molecules, while arguing that first quantization avoids costly classical active-space and molecular-orbital precomputation.Source: B. Conclusion and outlook · p. 53

Appendix A: Variable and function names

This appendix defines notation used for the algorithms and contrasts first- and second-quantized Galerkin representations. It specifies how particle configurations are encoded in each representation.

Appendix A: Variable and function names

  • The glossary uses η for electron count, N for reciprocal-lattice vectors per electron, and Ω for computational-cell volume.It also defines T as kinetic energy and U and V as potential-energy operators.Source: Appendix A · p. 58

1. Galerkin basis representations in first quantization

  • First-quantized states encode each particle’s basis-function index, adding explicit nuclear registers beyond the Born-Oppenheimer case.The Galerkin weak formulation tests within the finite basis subspace, whose discretization overestimates eigenstate energies; the Hamiltonians assume the same basis for all particles for simplicity.Source: §1 · pp. 60–61

2. Galerkin basis representations in second quantization

  • Second quantization stores symmetrized configurations, encoding particle symmetries in operators rather than wavefunctions; fermionic mappings use O(JN) qubits.Here J is the number of distinguishable fermionic species.Source: §2 · pp. 61–62

Appendix C: Qubit costings

This appendix itemizes qubit requirements for the qubitization and interaction-picture algorithms, detailing ancilla use and how temporary ancillas are counted. It also identifies the kinetic-energy update as the dominant ancilla cost among the interaction-picture update steps.

1. Qubit costings for qubitization approach

  • For qubitization, the phase-estimation step reflects on selected state-preparation qubits, while rezeroed flags and ancillas erased by reversing the implicit ζℓ-state QROM need no additional reflection.The reflected subset includes nηζ + 1 qubits for the U/V superposition and 2nη + 2 for the i and j preparations.Source: §1 · pp. 62, 64

2. Qubit costings for interaction picture approach

  • In the interaction-picture algorithm, checking and rezeroing ancillas after each U + V block encoding allows reuse across K encodings, with K − 1 success flags retained for reflection.Arithmetic ancillas cannot be reused this way because measurement-based inversion of arithmetic Toffolis requires ancillas guaranteed to be rezeroed.Source: §2 · p. 64
  • Within interaction-picture kinetic-energy updates, the ancilla cost in (C4) is dominant; controlled addition of ||ν|| uses fewer ancillas than the preceding step when np ≥ 3.The update steps include computing a component of q · ν or p · ν and adding it into the kinetic-energy register, as well as controlled addition of ||ν||.Source: §2 · p. 65
  • The implementation omits explicit ℓ output and superposition preparation for w, r, and s, outputting Rℓ instead, which requires 3nR qubits.The passage also states that block encoding T is no longer performed.Source: §2 · p. 66
  • The zero-check register has nηζ + 2nη + 4np + nM + 12 qubits, and checking whether they are all zero costs one fewer Toffoli, repeated K −1 times.The register count is the sum of costs from items 6, 8, 9(a)–(c), and 14.Source: §2 · p. 67
  • Complete qubitization reflects over nηζ + 2nη + 4np + nM + 12 + nk + 2 + Knt + K −1 + 1 qubits, with Toffoli cost K(nηζ + 2nη + 4np + nM + nt + 12) + nk + 3.The reflection count includes the phase-estimation control and iteration-register costs.Source: §2 · p. 67
  • Temporary ancillas are counted by overlap: the part 9 cost and parts 8 and 7 are added to max(parts 13, 15), then compared with the separate zero-check ancilla count.Parts 13 and 15 are not simultaneous; the resulting temporary-ancilla total is the maximum of three counts, and these ancillas are not needed during phasing by T.Source: §2 · p. 67

Appendix D: Selection between T, U, and V

The section constructs the selection among T, U, and V by conditioning on selector, state-preparation, and inequality-test flags. It balances the resulting weights against the Hamiltonian coefficients and bounds the effect of finite-precision rotations.

Appendix D: Selection between T, U, and V

  • The selection circuit distributes weight among T, U, and V using selector, preparation-success, and i ≠ j flags.The relative weights arise from the amplitudes of the cases in which each SEL operation is applied.Source: Appendix D · pp. 67–68
  • For OR, T is selected when T is chosen or preparation or inequality testing fails; the AND alternative also assigns identity weight in specified cases.The AND implementation changes the U and V weights, and its total λ includes λI.Source: Appendix D · pp. 68–69
  • The i ≠ j test adjusts the U-to-V weight ratio to match λU/λV; in the OR case, the net λ is λT + λU + λV.For the AND case, the net λ can be larger because of the identity contribution.Source: Appendix D · pp. 68–70
  • Choose OR or AND according to the relative weights, then select θ so the T weight matches its required share.The section states that θ can be chosen in either case, with the alternative depending on the relative values of the preparation probability and λT/(λT + λU + λV).Source: Appendix D · pp. 69–70
  • Rotation error Δθ causes energy error no greater than λΔθ, so nT is chosen to meet the allowable rotation-error budget.The section bounds the rotation-angle error by π/2^nT and relates it to the allowable error εT.Source: Appendix D · p. 71
  • The best α values are typically around 1 − 3/(2M) to 1 − 1/M, with nM bits usually sufficient for its rotation.The reported error varies by only a few percent across that α range.Source: Appendix D · p. 71

Appendix E: Detailed costing of preparation of k state

The preparation of k builds its unary representation directly through successive constant-threshold inequality tests. The section also accounts for reversible test circuits, time-difference registers, and preparation failure.

Appendix E: Detailed costing of preparation of k state

  • Successive inequality tests with thresholds Σ(2), Σ(3), and onward generate the unary representation of k directly, without binary-to-unary conversion.Each test result and the preceding unary qubits determine the next unary qubit.Source: Appendix E · pp. 71–72
  • An inequality test on n qubits uses a Toffoli cost and ancilla cost each one less than the number of qubits.In the described circuit, one temporary ancilla can be erased using Clifford gates.Source: Appendix E · p. 72
  • The workspace includes nk qubits for w and registers for inequality tests and unary k; the first test uses nk − 1 qubits including its output.The passage also gives a total ancilla count in terms of the subsequent threshold registers.Source: Appendix E · pp. 72–73
  • The constant-threshold test produces its inequality flag while restoring the input registers, allowing SEL operations at the dotted line before reversing the preparation.The constant is classical and need not be stored in qubits.Source: Appendix E · p. 72, Figure 6 · p. 73
  • For reverse-order time differences, taking absolute values adds nt − 1 Toffolis per difference, for a total of 2(K − 1)(nt − 1) Toffolis with subtraction.The final time difference in the forward/reverse control case can be handled with CNOTs at no Toffoli cost.Source: Appendix E · pp. 73–74
  • If equal-superposition preparation fails, its failure flag is left flipped; block-encoding postselection on zero removes that failure branch.Source: Appendix E · p. 74

Appendix F: The modified phase gradient state

This appendix bounds the costs of modifying the phase-gradient state and of arithmetic operations including squaring, summing squares, and multiplication, with general Toffoli-cost bounds and tighter squaring estimates.

Appendix F: The modified phase gradient state

  • Choosing bgrad from bT bounds the effective-λ increase caused by adjusting τ, while adding into the phase-gradient register costs bgrad−2.The precision choice uses bT bits to approximate σ.Source: Appendix F · p. 75

Appendix G: Complexity of binary squaring

  • Binary squaring improves from n^2−2 Toffolis with repeated addition to n(n−1) by grouping bit-products and summing carries by level.The improved count is established for both even and odd n.Source: Appendix G · pp. 75, 76, 78
  • Summing three n-bit squares takes 3n^2−n−1 Toffolis, and summing them together is more efficient than separately squaring and adding.The appendix notes that this task is used repeatedly to calculate vector norms.Source: Appendix G · pp. 78–79
  • For k n-bit inputs, summing their squares has an upper bound of kn^2 Toffolis, while numerical tests indicate actual costs can be slightly lower.The bound is more efficient than computing the squares and then summing them.Source: Appendix G · p. 80
  • The proven Toffoli complexity for binary squaring is upper bounded by kn^2 for both even and odd n.The bound includes kn(n - 1)/2 Toffolis for computing bit products.Source: Appendix G · p. 81
  • Numerically, squaring uses kn^2 - n Toffolis, or kn^2 - n - 1 when k is a multiple of 3, according to numerical tests.These numerical costs are n and n + 1 below the proven upper bound, respectively.Source: Appendix G · p. 81
  • Multiplying n-bit and m-bit numbers costs 2nm - n Toffolis when n ≥ m.The count combines nm Toffolis for bit products with the cost of summing them.Source: Appendix G · p. 81

Appendix H: Bound on time-discretization error

The section bounds time-discretization error for interaction-picture evolution and derives a centered-difference estimate for the time-ordered exponential. It also discusses how midpoint sampling, derivative bounds, and the relative sizes of the interaction-picture operators affect the estimate.

Appendix H: Bound on time-discretization error

  • The block-encoded operator’s time-discretization error translates into eigenvalue error for H/(λU + λV), with nt chosen from the allowable error εt.Source: Appendix H · p. 83
  • Midpoint sampling reduces the number of time bits by one in this analysis, while a second-order correction gives a higher-order error bound.Source: Appendix H · p. 83
  • The error analysis can use an upper bound on the first or second derivative of H to bound the discretization error.Source: Appendix H · p. 84
  • The centered-difference analysis gives an error bound for approximating the time-ordered exponential across the full interval.The section derives a per-step bound and then accumulates it over the interval.Source: Appendix H · p. 85
  • When ∥A∥ ≪ ∥B∥ in the interaction picture, the section expects the second term in its error expression to dominate.Source: Appendix H · p. 85

Appendix I: Interaction picture algorithm for simulating generic Hamiltonians

The appendix costs an interaction-picture simulation of H = A + B by combining a truncated Dyson series with block-encoded B and controlled evolution under A. It gives circuit costs, error sources, and conditions for selecting the time step.

Appendix I: Interaction picture algorithm for simulating generic Hamiltonians

  • The method assumes H = A + B with ∥B∥ much smaller than ∥A∥ and represents short-time evolution using a Dyson series.A is exponentiated directly, while PREPB and SELB implement the block encoding of B.Source: Appendix I · p. 86
  • The circuit prepares Dyson-series coefficients and unary |k⟩ states, initializes time registers, sorts them, computes time differences, and applies controlled evolution under A.The described state preparation and its inverse cost Knt Toffoli gates; sorting costs 2ntSt(K).Source: Appendix I · pp. 86–87
  • A single step of oblivious amplitude amplification boosts the success amplitude close to unity, using a pre-amplified truncated series and two reflections.The reflection cost depends on nk + K(nt + nB) + 2 qubits.Source: Appendix I · p. 87
  • The error budget includes Dyson-series truncation, finite time discretization, and finite precision in the ancilla rotation.The theorem’s error bound accounts for these contributions.Source: Appendix I · pp. 88–89
  • Theorem 12 specifies 3[N(K + 1)nt + 2] controlled-eisA, 6NK PREPB, 3NK SELB, and a Toffoli-gate cost for simulating H = A + B.The Toffoli expression continues in (I17); the theorem also constrains the simulation error.Source: Appendix I · p. 88
  • Choosing the time step as a rational multiple of 1/λB constrains c/d; the algorithm is most efficient when c/d closely approximates ln 2.The appendix gives 9/13 as an example of a rational approximation below ln 2.Source: Appendix I · pp. 88–89

Appendix J: Bound on the success probability for preparing equal superposition

The appendix bounds the success probability of preparing an equal superposition state. For br = 8, it guarantees probability at least 0.999661, supporting a rational time-step choice of 9/13 in the generic interaction-picture setting.

Appendix J: Bound on the success probability for preparing equal superposition

  • The resulting lower bound on preparation success probability is stated as a function of br and supports choosing simulation parameters.The appendix notes the result is trivial for br = 1 or 2 because the lower bound is negative.Source: Appendix J · pp. 90–91
  • The bound is derived by expressing success probability in terms of x = n/2⌈log n⌉ and bounding it over x ∈ (1/2, 1).The proof considers ∆θ in [−0.7, 0.7] and uses bounds at the interval’s extremal points.Source: Appendix J · pp. 91–92
  • For br = 8, the success probability is at least 0.999661, allowing c/d = 9/13 while satisfying the stated condition.The appendix states that ln[2Ps(Σ(0), 8)] > 0.6928, which exceeds 9/13.Source: Appendix J · p. 92

Appendix K: Simulating first quantized real space grid representations

The appendix describes real-space grid block encodings for first-quantized chemistry and argues that they attain the main approaches’ asymptotic complexity. It also identifies finite-grid and representation trade-offs that qualify this alternative.

Appendix K: Simulating first quantized real space grid representations

  • On finite grids, the QFT does not exactly diagonalize the momentum operator, so treating it as doing so is an approximation.The appendix also describes a finite-difference stencil as an alternative kinetic-operator approach.Source: Appendix K · pp. 93–94
  • Real-space grids may be less reliable for continuum extrapolation because basis errors are not variationally bounded away from Galerkin discretizations.The passage also notes that potential softening and core-electron removal are less developed for grids.Source: Appendix K · p. 93
  • The real-space qubitization approach block-encodes T, U, and V, with the kinetic operator’s selection circuit applying a QFT, a phase, and an inverse QFT.The QFT costs O~(η log^2 N) Toffoli gates.Source: Appendix K · p. 94
  • For the potential block encoding, testing a squared 2-norm avoids directly computing a reciprocal square root, which the authors say can reduce constant factors.The comparison test costs O(log^2(1/ϵ)) gates.Source: Appendix K · p. 95
  • The real-space block encoding of T + U + V has gate complexity O~(η), and the qubitization approach is reported to have the same overall asymptotic scaling as the main approach.The λV and λU values have different constant factors but the same asymptotic scaling.Source: Appendix K · p. 96
  • In the real-space interaction-picture scheme, QFT and kinetic-energy recomputation costs are nearly as large as each other, yielding the main algorithm’s asymptotic scaling up to a logarithmic factor.The kinetic energy must be recomputed at each step when block-encoding U and V.Source: Appendix K · p. 96
Loading 2105.12767v3…