PaperlayerView exact revision on arXiv

Source-linked AI summary

Even more efficient quantum computations of chemistry through tensor hypercontraction

Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, Ryan Babbush

arXiv:2011.03494v3quant-phphysics.chem-ph

TL;DR

Efficient quantum chemistry simulation in arbitrary orbital bases remains challenging because prior methods either incur high costs or require specialized Coulomb-diagonalizing bases. This paper combines tensor hypercontraction with qubitization to achieve favorable arbitrary-basis scaling and estimates practical surface-code resources for FeMoCo.

  • Problem

    Efficient quantum algorithms are needed for chemistry in arbitrary bases, which can reduce basis-size requirements but are costly with prior approaches.

  • Method

    The paper combines tensor hypercontraction with qubitization and uses a non-orthogonal basis that diagonalizes the Coulomb operator.

  • Results

    The approach achieves Toffoli complexity e~O(Nλ/ε), space complexity e~O(N), and estimates FeMoCo at about four million physical qubits and under four days under stated assumptions.

  • Takeaways & Limitations

    The method provides the paper’s lowest reported arbitrary-basis complexity and lower finite-resource costs than prior approaches for the studied molecules.

  • Takeaways & Limitations

    The resource estimates assume a sufficiently good initial eigenstate guess, and circuit-level metrics can misrepresent physical costs dominated by routing and distillation.

Abstract

from arXiv · show

We describe quantum circuits with only $\widetilde{\cal O}(N)$ Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of $N$ arbitrary (e.g., molecular) orbitals. With ${\cal O}(λ/ ε)$ repetitions of these circuits one can use phase estimation to sample in the molecular eigenbasis, where $λ$ is the 1-norm of Hamiltonian coefficients and $ε$ is the target precision. This is the lowest complexity that has been shown for quantum computations of chemistry within an arbitrary basis. Furthermore, up to logarithmic factors, this matches the scaling of the most efficient prior block encodings that can only work with orthogonal basis functions diagonalizing the Coloumb operator (e.g., the plane wave dual basis). Our key insight is to factorize the Hamiltonian using a method known as tensor hypercontraction (THC) and then to transform the Coulomb operator into an isospectral diagonal form with a non-orthogonal basis defined by the THC factors. We then use qubitization to simulate the non-orthogonal THC Hamiltonian, in a fashion that avoids most complications of the non-orthogonal basis. We also reanalyze and reduce the cost of several of the best prior algorithms for these simulations in order to facilitate a clear comparison to the present work. In addition to having lower asymptotic scaling spacetime volume, compilation of our algorithm for challenging finite-sized molecules such as FeMoCo reveals that our method requires the least fault-tolerant resources of any known approach. By laying out and optimizing the surface code resources required of our approach we show that FeMoCo can be simulated using about four million physical qubits and under four days of runtime, assuming $1\,μ$s cycle times and physical gate error rates no worse than $0.1\%$.

I. INTRODUCTION

Quantum chemistry simulation seeks efficient phase-estimation circuits for arbitrary orbital bases, but prior approaches face costly basis, sparsity, and tensor-factorization trade-offs. Qubitization and tensor factorizations reduce these costs, motivating a more efficient arbitrary-basis approach.

  • Motivation and simulation framework: Arbitrary-basis Hamiltonians use N spin-orbital functions and include one-body terms T_pq and two-body Coulomb integrals V_pqrs.The Coulomb tensor is central to the factorization strategies compared in this work.
  • Motivation and simulation framework: Quantum phase estimation samples molecular Hamiltonian eigenstates by repeatedly applying a qubitized quantum walk, with repetition count scaling as O(λ/ε).The walk has eigenvalues proportional to e^±i arccos(H/λ), where λ relates to the Hamiltonian norm.
  • Need for arbitrary-basis algorithms: Arbitrary basis functions can reduce the number of functions needed for continuum accuracy, creating demand for efficient algorithms that do not require Coulomb-diagonalizing bases.Only three prior papers had fully determined error-corrected quantum costs for arbitrary-basis chemistry algorithms.
  • Prior approaches: The sparse approach has T-gate scaling approximately O(N^2S/ε^3/2), with S commonly O(N^4) in arbitrary bases, and required more than 10^14 T gates for FeMoCo.Surface-code implementation makes T or Toffoli counts important because these gates dominate time and physical-qubit requirements.
  • Prior approaches: Single low-rank factorization achieves e~O(N^3/2λ/ε) Toffolis and e~O(N^3/2) space, while double low rank depends on the second-factorization rank Ξ.For many small-system regimes, Ξ scales around O(N), although some thermodynamic-limit evidence suggests O(log N).
  • Prior approaches: The compared algorithms combine qubitization with unary iteration, QROM, coherent alias sampling, and related phase-estimation techniques.Their costs depend on Hamiltonian information size Γ, controlled-operation overhead, λ, and sometimes Ξ.

B. Overview of results

The paper introduces a tensor-hypercontraction-based qubitization algorithm for arbitrary orbital bases and reports favorable asymptotic and finite-resource costs. Its surface-code analysis estimates FeMoCo simulations at approximately four million physical qubits and under four days under stated hardware assumptions.

  • Algorithmic construction: THC compresses the Hamiltonian to Γ=e~O(N^2) information and, with the proposed representation, yields Toffoli complexity e~O(Nλ/ε) and space complexity e~O(N).Direct qubitization of THC has the same asymptotic form but a larger λ, so the paper develops a different THC-based construction.
  • Algorithmic construction: THC factors define a larger isospectral orbital basis that diagonalizes the Coulomb operator, while separate rotations mitigate complications from its non-orthogonality.This construction adapts qubitization to a diagonal, non-orthogonal THC Hamiltonian.
  • Finite-resource comparisons: The algorithm reduces FeMoCo spacetime volume by about 3× for the Reiher Hamiltonian and 6× for the Li Hamiltonian relative to [10].The study also reports lower finite spacetime volume than prior approaches for all molecules examined.
  • Asymptotic and empirical scaling: The THC approach has empirical Toffoli scaling e~O(N^3.1/ε) toward the continuum limit and space scaling e~O(N).These estimates come from hydrogen-system numerics summarized in the paper’s complexity comparisons.
  • Surface-code resource estimates: Approximately four million physical qubits and under four days are estimated for FeMoCo at 1-microsecond surface-code cycles and 0.1% gate error rates.At 0.01% error rates, the estimate becomes about one million physical qubits and under two days.
  • Stochastic phase-estimation analysis: Unmodified qDRIFT costs nearly 18 orders of magnitude more than optimized qubitization for the benchmark FeMoCo molecules under the reported analysis.Using an α-confidence region reduces the cost by twelve orders of magnitude, while the Hodges–Lehmann estimator provides another order-of-magnitude improvement.

2. Optimization

The paper constructs a diagonal Coulomb representation in an expanded, non-orthogonal THC basis and qubitizes it by rotating into each tensor factor separately. This avoids the larger λ incurred by directly qubitizing the THC Hamiltonian while retaining efficient controlled operations.

  • Motivation: Direct qubitization of the THC Hamiltonian has Toffoli complexity e O(Nλthc/ε), but its λthc is much larger than λV because coefficient sums remain outside the absolute value.The main approach therefore simulates a different Hamiltonian derived from the THC representation.
  • Diagonal representation: The THC factors define a larger orbital basis in which the Coulomb operator has a diagonal form, although the basis is non-orthogonal and increases the basis size roughly four- to tenfold.The resulting representation is called the non-orthogonal THC Hamiltonian.
  • Qubitization strategy: Qubitization handles the non-orthogonal basis by independently applying controlled basis rotations for each number operator rather than rotating all basis vectors globally.This reduces the required rotations from O(N^2) to N/2 Givens rotations in the relevant controlled procedure.
  • Qubitization strategy: The basis-rotation procedure is performed for both tensor indices, yielding e O(N) complexity for a single simulation step.The two-body contribution to λ is derived from the resulting representation, while one-body terms are treated separately.
  • Outcome: λζ scales better than the λ values associated with prior algorithms, including λDF from the doubled-factorized approach.The construction uses an LCU query model and qubitization to block encode the Hamiltonian eigenspectra.

B. State preparation for the non-orthogonal tensor hypercontraction Hamiltonian

State preparation encodes the non-orthogonal THC Hamiltonian using equal superpositions, coherent alias sampling, contiguous indexing, and controlled register swaps. The construction supports the one- and two-electron terms while tracking success and special-index flags.

  • Preparation structure: The prepare operation expresses the Hamiltonian in the non-orthogonal THC basis before constructing its coefficient-weighted control state.The preparation uses a three-step procedure: equal superposition, coherent alias sampling, and a controlled swap of μ and ν.
  • Equal superposition: The initial superposition covers μ ≤ ν ≤ M + 1, with μ ≤ N/2 when ν = M + 1, using inequality tests and an ancilla rotation.The ν = M + 1 value flags the first term associated with the one-electron component.
  • Alias sampling: A contiguous register is computed from the μ and ν registers, after which alternate values and sign information are produced for coherent alias sampling.The contiguous-register computation has complexity n2M + nM − 1.
  • Register control: The preparation circuit swaps μ and ν conditionally on a |+⟩ ancilla and the ν = M + 1 flag, using controlled phase operations instead of an explicit alternate-value swap.This modification removes one non-Clifford gate, and the controlled phase gates need not be repeated when inverting state preparation.
  • Precision: The keep-register precision is chosen as ℵ = ⌈2.5 + log(10λ/ε)⌉ in the referenced implementation, discretizing the required squared amplitudes.The amplitudes differ for diagonal and off-diagonal THC coefficients, with |ζμμ|/(2λ) for μ = ν.

C. Hamiltonian selection oracle for the non-orthogonal tensor hypercontraction Hamiltonian

The selection oracle applies the μ- and ν-controlled basis rotations and spin operations needed for the LCU representation. It is redesigned to be self-inverse, enabling efficient qubitized walk construction.

  • Controlled operations: The select operation applies Uμ or UT,μ for two- or one-electron terms, followed by Uν, using QROM-generated sequences of N/2 rotations.The procedure is performed once for μ and once for ν.
  • Self-inverse construction: The complete select operation bundles the controlled swaps into the oracle, making its symmetry explicit while retaining the ν = M + 1 flag for the one-electron component.This form is depicted as more clearly self-inverse than the separate state-preparation arrangement.
  • Cost structure: Spin-controlled swaps cost N/2, while QROM dominates the select-operation cost because it outputs large rotation databases.The μ step uses M + N/2 data sets, with separate handling for ν = M + 1.
  • Rotation implementation: The rotations are implemented through a phase-gradient state with cost N(ℶ − 2), and inverse rotations have the same cost.The Z operation contributes no Toffoli cost, apart from the control needed to suppress operations when ν = M + 1.
  • Self-inverse construction: The select circuit is made self-inverse by using an ancilla-controlled swap structure that produces VμVν + VνVμ.The simplified circuit has controlled swaps at the beginning and end, corresponding to the state-preparation swaps.

D. Overall costs of the non-orthogonal tensor hypercontraction Hamiltonian simulation

The overall simulation combines prepare, select, reflections, and phase-estimation control, with costs determined by the THC-register sizes, precision parameters, and QROM workspace. The resulting single-step Toffoli expression is linear in the dominant register-size parameter up to logarithmic factors.

  • Toffoli cost: A quantum-walk step requires prepare, inverse prepare, select, reflections, and unary-iteration controls, with additional cost 2nM + 5 beyond prepare and select.The phase-estimation total multiplies this per-step cost by the required number of iterations.
  • Logical-qubit cost: The phase-estimation control and unary-iteration registers each require ⌈log(I + 1)⌉-scale space, in addition to N system qubits and 2nM μ,ν-register qubits.Further ancillas store alias-sampling precision, spin controls, flags, phase-gradient data, and contiguous indices.
  • Workspace: QROM workspace includes mks1 + ⌈log d/ks1⌉ qubits, while rotation data require ℶN/2 output bits and ℶ − 2 temporary phase-gradient qubits.Ancillas used for erasing QROM can be reused and therefore need not add separately to the total.

E. Error metrics for approximate tensors

The paper evaluates Hamiltonian approximation error metrics against tractability, size scaling, consistency, and correlation with exact ground-state errors. It advocates CCSD(T) correlation-energy error while acknowledging that its relationship to exact errors remains uncertain.

  • Error metrics should be classically tractable, size-extensive, size-consistent, and correlated with exact ground-state energy error.The correlation requirement is difficult to verify because exact ground-state energies are generally unknown.
  • 1-norm and 2-norm tensor-difference metrics can rigorously bound energy shifts, but their bounds may be too loose and their scaling can violate size-extensivity.The authors report scaling up to quartically with system size and poor correlation in examples.
  • The incoherent error metric is not size-consistent, which the authors associate with poor correlation to exact ground-state energy error.
  • MP2-based error bounds satisfy size-consistency and size-extensivity, but MP2 correlation energy can behave erratically and correlate poorly with exact ground-state errors.The weighted metric uses orbital-energy differences for each orbital quartet.
  • The paper advocates CCSD(T) correlation-energy error because CCSD(T) is a classically tractable, size-consistent, and size-extensive reference method containing MP2 contributions.The authors caution that CCSD(T) can be quantitatively unreliable for strongly correlated systems and may not correlate with exact ground-state error.
  • Resource estimates additionally include errors from approximating tensor coefficients, state-preparation representations, and individual qubit rotations.Approximate representations are normalized before constructing the approximate block-encoding object.

IV. RESOURCE ESTIMATES FOR REAL SYSTEMS

The resource analysis benchmarks THC on FeMoCo active-space Hamiltonians and hydrogen-chain and H4 scaling studies. THC reaches chemical-accuracy targets at selected ranks and supports resource estimates under explicit surface-code assumptions.

  • A. Resource estimates for simulating active space models of FeMoCo molecule: The benchmarks use active-space FeMoCo models from Reiher et al. and Li et al., with Li designed to capture the open-shell ground-state character.
  • A. Resource estimates for simulating active space models of FeMoCo molecule: Chemical accuracy is achieved for both FeMoCo Hamiltonians at THC rank M ≥350.Figure 8 reports the same threshold for the Reiher and Li Hamiltonians, while the detailed discussion reports M ≥250 for Reiher and M ≥350 for Li.
  • A. Resource estimates for simulating active space models of FeMoCo molecule: 10 state-preparation bits and 16 rotation bits suffice for Reiher, while Li requires 10 state-preparation bits and 20 rotation bits.The recommended ranks are M = 350 for Reiher and M = 450 for Li.
  • B. Resource estimates and scaling analysis for hydrogen chain and H4 benchmarks: Hydrogen-chain scaling uses 1.4-Bohr spacing, the STO-6G basis, and systems grown by adding hydrogen atoms.
  • B. Resource estimates and scaling analysis for hydrogen chain and H4 benchmarks: A THC rank of 7 × N_H keeps CCSD(T) correlation-energy error below 50 µHartrees per atom in the hydrogen-chain calculations.The comparison uses method-specific thresholds for sparse, single-factorization, and double-factorization approaches.
  • B. Resource estimates and scaling analysis for hydrogen chain and H4 benchmarks: The λ values determine Toffoli-complexity scaling, while additional nonzero-element and eigenvector data determine space-complexity scaling for competing methods.The authors obtain asymptotic fits from hydrogen-chain and H4 data, using only the two-body contribution for asymptotic λ behavior.
  • Surface-code estimates assume a 0.1% physical gate error rate and a 10-microsecond control-system reaction time.Surface-code space-time tradeoffs allow runtime reduction through additional magic-state factories.

3. Diagram driven decisions

Resource-utilization diagrams guided space-saving changes to the quantum computation, trading modest Toffoli or time increases for substantially lower workspace. The compiled design is estimated at millions of physical qubits and days of runtime, with further reductions at lower physical error rates.

  • Resource diagrams: Floorplans estimate where computation components fit and provide routing space for data and magic states.The goal is a workable layout rather than a perfectly optimal one.
  • Resource diagrams: Qubit inventories over time expose allocation spikes and unused capacity that can guide resource optimizations.Unused capacity can support additional magic-state factories.
  • Inner-loop optimization: Loading half the phasing angles at a time halves required output qubits because QROM loading is faster than angle use.The change accepts a small time loss for substantial space savings.
  • Inner-loop optimization: Reducing QROM output expansion from 32 to 16 lowers workspace while slightly increasing the Toffoli count.The adjustment was made in the prepare subroutine because fewer qubits were available.
  • Resource estimates: 483,000 inner loops at 13,880 Toffolis each total approximately 6.7 billion Toffolis, taking 3 days with four CCZ factories.The stated factory throughput is 25 kHz.
  • Resource estimates: At a 0.01% physical error rate, the estimate falls from four million to one million physical qubits and from 3.5 days to 1.5 days.The code distance changes from 31 to 15, producing a fourfold qubit reduction.
  • Conclusions: The paper introduces THC-based arbitrary-basis simulation and reports lower asymptotic and finite-resource costs than prior algorithms.Its circuits use qubitization together with QROM, coherent alias sampling, and unary iteration.
  • Conclusions: Physical estimates are dominated by routing and distillation, so abstract circuit metrics such as Toffoli counts and data qubits can mislead.The paper treats these metrics as useful approximations that can fail in known ways.

Appendix A: The “sparse” algorithm of Berry et al.

The sparse algorithm expresses an arbitrary-basis electronic Hamiltonian as a linear combination of unitary operators and implements its state preparation, select operations, and associated cost reductions. Several algebraic simplifications remove identity terms and reduce controlled-operation overhead.

  • Hamiltonian representation: The arbitrary-basis Hamiltonian is mapped to qubits and expressed as a linear combination of unitary operators for qubitization.The representation separates one-body and two-body contributions into T′ and V′.
  • Hamiltonian representation: Removing the identity from Q_pqσ gives equal diagonal and off-diagonal weightings and simplifies the controlled select circuit.The identity contribution only produces a constant eigenvalue shift and can be omitted.
  • Cost parameters: The revised λ definitions correct convention and factor errors, changing the Reiher estimate to λ = 2,135 a.u. and the Li estimate to λ = 1,547 a.u.The tighter truncation thresholds are based on a more conservative CCSD(T) correlation-energy-error metric.
  • State preparation: State preparation uses controlled swaps and symmetry generation to prepare the sparse Hamiltonian state, with inverse preparation applied afterward.The prepared registers encode index and term information for one- and two-electron contributions.
  • Select implementation: The controlled select operation costs 2(N − 1) when controlled and 2(N − 2) when uncontrolled.Only one of the required select operations needs control because one-body terms use a single select.
  • State preparation: The total cost of the equal-superposition preparation is 3⌈log d⌉−3η + 2b_r − 9 Toffolis for each preparation direction.The same cost is incurred for preparation and inverse preparation.
  • Implementation costs: Additional costs include the select circuit, sparse-state inequality tests, and controlled swaps over index and term registers.Ancillas allocated for QROM can be reused to reduce the incremental workspace burden.

3. Counting the number of permutation-unique elements

The section counts permutation-unique two-electron integrals by classifying index redundancies, then uses thresholded nonzero counts to assess scaling and factorization-based circuit costs.

  • The two-electron tensor V_pqrs has 8-fold permutational symmetry, reducing the elements that must be counted.
  • The counting partitions V_pqrs into four classes: four, three, two, or one unique indices.
  • The total count adds the symmetry-unique one-body contribution (1/2)(N/2)(N/2 + 1) to thresholded two-body counts.
  • At truncation threshold 5 × 10^-5, Figure 14 reports nonzero V counts for hydrogen chains and H4.
  • The state-preparation implementation improves prior work by applying QROM directly to two registers without computing a contiguous register that also includes ℓ.

Appendix C: The “double low rank factorization” algorithm of von Burg et al.

The double low-rank algorithm further factorizes the Coulomb operator and uses eigenvector rotations with truncation of the second-factorization ranks to reduce simulation cost.

  • The double-factorization approach modifies the single-factorization method by applying a second factorization to the low-rank Coulomb operator.
  • The average second-factorization rank is generally below N, but may scale asymptotically below N only in special large-system regimes.
  • The one-body operator can remain T′ without truncation error when the first-factorization rank is sufficiently large.
  • The second factorization uses eigendecomposition, and the rank of each term can be truncated at Ξ(ℓ).
  • A truncation with L < N^2/4 is allowed for the two-body operator while leaving the one-body operator untruncated.
  • The key implementation of U_ℓ produces λ = λ_T′ + λ_DF, while the method’s efficiency comes from reducing λ.

2. Cost of qubitization of the double low rank factorized Hamiltonian

This section decomposes the double-factorization circuit cost into state preparation, QROM, rotations, swaps, reflections, and phase-estimation overhead, while identifying a register-separation issue in the original circuit.

  • The original circuit appears problematic because joint preparation does not cleanly divide qubits into registers needed for reflection on only one register.
  • Comparisons with [10] must account for differing conventions: here N counts spin-orbitals, whereas [10] counts orbitals.
  • The dominant double-factorization costs are QROM and rotations; the THC representation reduces QROM costs relative to [10], while rotation costs remain unchanged.
  • The double-factorization data structure contains LΞ coefficients, where L is the main rank and Ξ is the average second-factorization rank.
  • State preparation requires equal-superposition preparation, QROM, inequality tests, controlled swaps, and their corresponding uncomputation steps.
  • The implementation computes offsets and rotation angles through additional QROM calls, register additions, controlled rotations, and spin-controlled swaps.
  • The alternative performs state preparation separately on the two registers, either sequentially or with the second preparation controlled by the first.

3. Numerical determination of double low rank factorization

The numerical double-factorization procedure specifies how to obtain and truncate both factorizations using a single threshold, producing the data reported in Tables XIII and XIV.

  • This single-threshold procedure generates the numerical data presented in Tables XIII and XIV.
  • The first factorization uses either eigendecomposition or Cholesky decomposition of V, followed by sorting terms by eigenvalue magnitude.
  • The second factorization uses eigendecomposition of each W^(ℓ), following the approach of von Burg et al.
  • For each ℓ, eigenvectors are discarded when their magnitude falls below the selected threshold.
  • If no eigenvectors remain at ℓ0, all later vectors with ℓ > ℓ0 are discarded without further evaluation.

4. Numerical data for hydrogen chains and H4

For hydrogen chains and H4, the second-factorization rank grows approximately linearly with system size, while the qDRIFT analysis yields quartically unfavorable scaling in λ and ε. The resource count for the corresponding algorithm includes N target qubits plus logarithmic overhead.

  • Hydrogen chains and H4: O(N^1.29) scaling was obtained for the average second-factorization rank Ξ, with slope 1.29 and R2 = 0.9917 for the H4 fit.The fit excludes the last six points beyond N/2 = 35; the analysis assumes Ξ scales as O(N) for H4.
  • qDRIFT mean-square error: O(λ^4/ε^4) scaling results from the qDRIFT phase-estimation analysis and leads to large gate counts for the studied problems.The analysis attributes the large scaling to diamond-norm bounds permitting probability increases concentrated at the maximum error.
  • Resource estimates: Nqubits ≲ N + 2 log(Nexpr) + 2, combining the N target qubits with logarithmic ancilla overhead.The ancillae include the phase-gradient resource state, phase-estimation registers, and carry-logic workspace.

2. Confidence intervals for the eigenphases

The paper analyzes confidence-interval and robust-estimation strategies for phase estimation, including a Kaiser-window variant, and derives their qDRIFT simulation costs. These approaches retain λ^2/ε^2 scaling up to logarithmic factors, while optimized constants substantially reduce estimated costs for the Reiher and Li cases.

  • qDRIFT limitations and alternatives: qDRIFT analysis prevents low-cost fixed-mean-squared-error estimates for FeMoCo because the phase-estimation distribution may have fat tails.The paper instead considers confidence intervals, repeated sampling, the Hodges–Lehmann estimator, and prior-energy filtering.
  • Confidence-interval construction: 95% confidence intervals can be narrower than Gaussian intervals, with a standard-window ratio of 1.822849 versus 1.959964.Numerically solving gives a = 2.863325 for the standard window.
  • Confidence-interval construction: The Kaiser window yields the narrowest 95% confidence interval at a = 2.542853 with α = 2.179411.The parameter α is adjusted numerically to optimize the interval size.
  • qDRIFT cost optimization: Optimizing qDRIFT and phase-estimation errors shows Nexp proportional to λ^2/ε^2 up to logarithmic rotation-synthesis factors.The optimization sets a = εtr and δ = rλ^2t^2 before minimizing the repetition count.
  • Optimized resource estimates: The optimized estimates improve substantially over Campbell-bound predictions of 4.0 × 10^18 and 2.1 × 10^18 exponentials for the Reiher and Li Hamiltonians.The comparison assumes a 95% confidence interval and probability of failure P0 = 0.05.
  • qDRIFT limitations and alternatives: The Hodges–Lehmann estimator uses pairwise sample means and their median, achieving asymptotic mean-square error 2.38991, about 3% below an individual sample’s π^2/4.This estimator is considered for symmetric probability distributions and repeated algorithm runs.
  • Optimized resource estimates: For the Reiher case, optimized simulation costs are 1.8 × 10^15 Toffolis and 250 qubits, while Li requires 1.0 × 10^15 Toffolis and 296 qubits.These costs use adjusted truncations and convenient rotation angles.

2. Using the structure of tensor hypercontraction to implement the qubitization state preparation

The state-preparation procedure constructs the one- and two-body components required for qubitization using THC factors, symmetry restrictions, QROM, inequality tests, and controlled swaps. Numerical comparisons show that the proposed non-orthogonal THC formulation substantially reduces λ2 and its system-size scaling relative to the naïve formulation.

  • State preparation: The preparation first weights the one- and two-body terms, then prepares restricted superpositions over their THC indices.The two-body branch uses µ,ν over 1 ≤ µ ≤ ν ≤ M, while the one-body branch uses the corresponding N/2 restriction.
  • State preparation: Computing contiguous index registers and applying QROM provide the data needed for THC state preparation, followed by inequality tests and controlled swaps.The procedure includes computing µ(µ −1)/2 + ν, loading alternate values, testing keep probabilities, and swapping registers conditionally.
  • Cost accounting: The overall construction prepares and unprepares the χ state four times and the ζ state once, then adds select-operation and quantum-walk reflection costs.The resulting implementation accounts separately for state preparation, select, reflections, and logical-qubit requirements.
  • Cost accounting: For realistic parameters, the largest qubit demand occurs during ζ-state preparation.The logical-qubit accounting includes system, index, comparison, phase-gradient, QROM-output, and temporary registers.
  • Numerical comparison: More than an order of magnitude reduction in λ2 is observed for the proposed formulation, together with reduced scaling for hydrogen chains and H4.The comparisons use Eq. (13) for the proposed approach and Eq. (9) for the naïve approach; the paper attributes success to the non-orthogonal THC form.
  • Numerical comparison: The contiguous-register construction has Toffoli cost n^2 + n −1 for both odd and even bit counts.The appendix gives this cost for the even and odd cases, including examples with n = 6 and n = 7.

Appendix G: QROM applied to two registers

The appendix presents a two-register QROM method that iterates over blocked high-order bits and uses low-order bits to select among loaded outputs. Its ancilla and Toffoli costs are close to those of contiguous-register QROM while avoiding the cost of computing a contiguous register.

  • Method: Two-register QROM partitions x and y into high-order iteration bits and low-order block bits, with k1 and k2 chosen as powers of 2.The method loads outputs for all combinations within each low-order block and then uses controlled swaps to select the correct data.
  • Method: The procedure iterates through ⌈N1/k1⌉ values of x and controlled iterations through ⌈N2/k2⌉ values of y.The total iteration cost combines the first-register iteration with the nested controlled second-register iterations.
  • Cost: The output-selection stage costs b(k1k2 −1) for output size b, with a total cost obtained by adding iteration and controlled-swap costs.The presentation omits a possible −2 term for simplicity and consistency with customary QROM cost reporting.
  • Cost: The method uses ⌈log(N1/k1)⌉ + ⌈log(N2/k2)⌉ + bk1k2 ancillas.These ancillas support iteration on both registers and storage for the QROM outputs.
  • Comparison: For N1 = 350 and N2 = 72, choosing k1 = 16 and k2 = 8 increases the cost by only one Toffoli over contiguous-register QROM.A separate example shows that contiguous-register QROM saves only 4 Toffolis while computing the contiguous register costs 17.
Loading 2011.03494v3…