Source-linked AI summary
Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, Ryan Babbush
TL;DR
Quantum chemistry simulation needs resource-efficient methods that work with compact arbitrary basis sets, not only structured plane waves. The paper uses qubitized quantum walks with sparsity and low-rank Coulomb factorizations, achieving improved asymptotic complexity and roughly seven-hundred-fold lower FeMoco state-distillation spacetime volume than prior work.
Problem
Existing favorable chemistry simulation methods focus on plane waves, whereas compact arbitrary-basis methods have higher costs and prior rigorous scalings are limited.
Method
The paper uses qubitized quantum walks with linear-combination-of-unitaries oracles that exploit Coulomb-operator sparsity and low-rank tensor factorization.
Results
The approach achieves e O(N^3/2 λ) T complexity and reduces FeMoco state-distillation spacetime volume by roughly seven hundred times versus prior work.
Takeaways & Limitations
The reported algorithms support arbitrary-basis chemistry simulation with compact molecular orbitals and substantially lower FeMoco resource estimates than earlier approaches.
Takeaways & Limitations
The many-ancilla algorithm has O(N^3/2) spatial complexity, while its FeMoco execution remains bottlenecked by Toffoli-state distillation.
Abstract
from arXiv · showhide
Recent work has dramatically reduced the gate complexity required to quantum simulate chemistry by using linear combinations of unitaries based methods to exploit structure in the plane wave basis Coulomb operator. Here, we show that one can achieve similar scaling even for arbitrary basis sets (which can be hundreds of times more compact than plane waves) by using qubitized quantum walks in a fashion that takes advantage of structure in the Coulomb operator, either by directly exploiting sparseness, or via a low rank tensor factorization. We provide circuits for several variants of our algorithm (which all improve over the scaling of prior methods) including one with $\widetilde{\cal O}(N^{3/2} λ)$ T complexity, where $N$ is number of orbitals and $λ$ is the 1-norm of the chemistry Hamiltonian. We deploy our algorithms to simulate the FeMoco molecule (relevant to Nitrogen fixation) and obtain circuits requiring about seven hundred times less surface code spacetime volume than prior quantum algorithms for this system, despite us using a larger and more accurate active space.
1 Introduction
Quantum simulation is a promising but resource-intensive application, with chemistry requiring compact molecular representations that challenge existing algorithms. This work develops qubitized approaches for arbitrary basis sets and demonstrates substantially lower FeMoco resource estimates.
- Chemistry is a leading anticipated application of quantum simulation, with accurate solutions potentially benefiting batteries, pharmaceuticals, and industrial catalysts.
- Plane-wave Hamiltonians enable favorable scalings, but molecular systems often require many spin-orbitals for chemical accuracy.Reported second-quantized plane-wave algorithms achieve O(N^3) or O(N^2 log N) gate complexity, while first-quantized practicality remains unclear.
- Compact molecular orbitals reduce basis size but produce complex Hamiltonians with O(N^4) terms, motivating improved arbitrary-basis simulation methods.Early algorithms in this representation had O(N^11) gate complexity.
- The paper provides e O(N^3/2 λ) T complexity for arbitrary-basis chemistry, improving over prior rigorous scalings when λ = Ω(N^3/2).Prior bounds include e O(N^5) and e O(λ^2).
- The approach performs phase estimation on a qubitized quantum walk using linear-combination-of-unitaries oracles, QROM state preparation, coherent alias sampling, and Coulomb-operator structure.
- About 2 × 10^11 Toffoli gates for RWSWT orbitals and 8 × 10^10 for LLDUC orbitals yield FeMoco chemical-accuracy estimates with large ancilla counts.At 10^-3 error rates, state distillation still requires about three million qubitweeks, approximately seven hundred times less than prior results.
2 Low Rank Tensor Factorization of the Coulomb Operator
The paper factorizes the Coulomb interaction by matricizing the two-electron integral tensor and exploiting the resulting low-rank structure. Molecular integral structure reduces the effective rank and coefficient count, while careful representation choices preserve this advantage.
- The two-electron integral tensor V is reshaped into a symmetric positive-semidefinite matrix W with composite indices for electron pairs.This reshaping is called matricization.
- The factorization must retain the spatial-orbital chemist-ordering structure, because physicist ordering produces a full-rank matrix with no cost reduction.Introducing fermionic symmetries directly into the full spin-orbital coefficients can likewise destroy the useful structure.
- W is diagonalized into eigenvectors g^(ℓ) with nonnegative eigenvalues ω_ℓ, and its rank is denoted L.
- Molecular integral structure makes W non-full-rank, with L ∈ O(N) rather than the full-rank value N^2/4.The paper relates this reduction to the pairwise nature of Coulomb interactions and density-fitting techniques.
- The low-rank representation reduces seemingly O(N^4) coefficients to O(N^2L) = O(N^3) coefficients when L ∈ O(N).Symmetry gives L(N^2/8 + N/4) independent coefficients.
- The paper does not pursue a second factorization because it adds intricacies, is less understood, and may not improve T complexity given later QROAM improvements.
3 LCU based simulation
The Hamiltonian is expressed as a linear combination of unitaries and simulated through qubitization, with state preparation and controlled operations implementing the required LCU walk. Factorization, QROM/QROAM, unary iteration, and measurement-based uncomputation reduce the implementation cost.
- Hamiltonian representation: The LCU representation separates one-body and factorized two-body terms, with λ = λT + λW determining the simulation complexity.The overall cost scales with λ times the complexity of the select and prepare operations.
- State preparation and selection: There are O(N^3) unique coefficients, giving an expected O(N^3 + log(1/ϵ)) T complexity for basic QROM-based preparation.A more sophisticated preparation scheme further reduces the T-gate count.
- State preparation and selection: State preparation creates superpositions over the factorization and orbital indices, while controlled select operations apply the corresponding Pauli-string unitaries.The select operations have complexity linear in N, smaller than the state-preparation cost.
- State preparation and selection: Unary iteration yields a baseline state-preparation complexity of N/2 + LN^2/2 + O(L log(1/ϵ)).The dominant preparation steps are those associated with the factorized two-body terms.
- Cost reductions: QROAM and measurement-based uncomputation reduce Toffoli cost by removing the M dependence from lookup uncomputation and allowing temporary ancilla reuse.The QROAM construction trades spatial resources against gate complexity.
4 Complexity
The complexity analysis selects a rank truncation that preserves chemical accuracy and evaluates resource costs for FeMoco under different ancilla strategies and orbital choices. The resulting costs depend strongly on QROM implementation and available workspace.
- Implementation costs: The controlled select implementation costs 4N + 4⌈log N⌉ Toffoli gates after accounting for two applications of the controlled operations.The construction uses ranged operations and inequality tests.
- Implementation costs: QROAM-based preparation dominates the complexity, motivating the use of optimized compute and uncompute parameters and measurement-based uncomputation.The reported table summarizes approximate leading-term Toffoli costs using k = 4 for QROM compute circuits.
- FeMoco resource estimates: For LLDUC integrals, λ = 24,192 a.u., compared with 36,042 a.u. for RWSWT at the selected truncation.The figure caption gives the separate λT, λV, and maximum λW contributions for both orbital sets.
- Rank truncation: L = 200 is selected because CISD and MP2 correlation energies are well converged for both RWSWT and LLDUC integrals at that rank.The authors note that convergence near the same rank for the two integral sets may be coincidental.
- FeMoco resource estimates: For RWSWT integrals, λ = 36,042 a.u. and chemical accuracy is defined as ∆E = 0.0016 a.u.The corresponding phase-estimation precision is approximately 1.7 × 10^-8.
- Implementation costs: Using dirty ancillae, state preparation requires 310,688 Toffolis and the phase-estimation circuit uses 378 logical qubits.The preparation subtotal is 309,154 Toffolis before 1,534 minor costs are added.
5 Exploiting sparsity in the Coulomb operator
The section induces sparsity by truncating near-zero Coulomb-operator elements, then exploits the resulting nonzero structure and coefficient symmetries during state preparation. The truncation preserves chemical accuracy while reducing the entries that must be prepared.
- Truncating the Coulomb operator: Truncation removes near-zero Coulomb-operator elements to induce sparsity, with c chosen as large as possible while retaining chemical accuracy for CISD and other correlated approximations.The procedure is illustrated for FeMoco using the correlation-energy difference between truncated and untruncated operators.
- Truncating the Coulomb operator: The truncated operator is expected to retain O(N^4) nonzero terms asymptotically, but practical systems can exhibit additional sparsity with L(c)_V < N^4/16.The amount of practical sparsity is system dependent.
- FeMoco truncation: For FeMoco, safe truncation thresholds are c = 0.0002 a.u. for RWSWT and c = 0.0001 a.u. for LLDUC, corresponding to L(c)_V values of 3,300,568 and 1,291,648, respectively.The LLDUC threshold and corresponding count are stated in the Figure 3 caption; the RWSWT threshold is reported separately.
- Sparse state preparation: Sparse state preparation makes its cost depend on the number of nonzero entries rather than the full state dimension, using QROM to load indices, alternatives, and keep values.An additional inequality test and controlled swaps produce the desired amplitudes from the sparse representation.
- Symmetry reduction: Hamiltonian symmetries reduce the prepared entries to about one-eighth for V and one-half for T, after which controlled swaps regenerate equivalent terms.The preparation initially uses p ≤ q, r ≤ s, and pq ≤ rs for V, and p ≤ q for T.
6 Complexity for sparse preparation
The sparse-preparation implementation is evaluated for RWSWT and LLDUC FeMoco orbitals using Toffoli complexity, logical-qubit counts, and error-budget adjustments. The resulting approach is reported as the best-performing alternative considered and improves substantially over prior methods.
- 6.1 RWSWT orbitals: 13,783 Toffolis are required for the RWSWT state-preparation components and minor costs, with 5,103 logical qubits.The preparation and inverse-preparation costs are 11,672 and 1,365 Toffolis, respectively, before adding 746 minor-cost Toffolis.
- 6.2 LLDUC orbitals: For LLDUC orbitals, λ = 7,614 a.u. and N = 152, while truncation leaves 1,291,648 nonzero values and about 176,572 unique V values.The calculation uses a QROAM output size of M = 84 and 179,498 unique terms after adding the T terms.
- Comparison: The resulting Toffoli performance is described as the best among the alternatives considered, with a full order-of-magnitude improvement over low-rank factorization and three orders over.The comparison is reported for the resulting complexity after the error-budget optimization.
- 6.2 LLDUC orbitals: Allowing approximately 26% more phase-estimation error reduces m from 24 to 23 and the logical-qubit count from 2,904 to 2,903, with negligible gate cost for the compensating QFT error.The adjustment reallocates allowable error while keeping the total error budget controlled.
7 Discussion
The discussion compares resource costs for FeMoco simulation and identifies spacetime volume as the practical bottleneck. It also outlines possible future reductions through symmetries, improved representations, and lower λ.
- Resource comparison: 8×10^10 Toffoli gates give the lowest reported count, corresponding to about three megaqubitweeks for CCZ-state distillation.The estimate uses a 24 qubitsecond spacetime volume per distilled CCZ state.
- Resource comparison: The reported approach uses about seven hundred times less distillation spacetime volume than the prior FeMoco algorithm, despite a larger and more accurate active space.The comparison excludes storage, routing, and Clifford operations.
- Resource comparison: The algorithm is bottlenecked by Toffoli complexity rather than logical-qubit costs, despite the many-ancilla variant’s O(N^3/2) spatial complexity.The many-ancilla FeMoco simulation would require a few thousand logical qubits.
- Future directions: Further cost reductions may come from exploiting locality, molecular symmetries, group theory, additional Coulomb low-rank structure, or techniques that reduce λ.Alternative orbital choices and pseudopotentials are also suggested as possible ways to induce sparsity or lower λ.
- Future directions: Plane-wave first-quantized simulation remains potentially viable for FeMoco, but its constant factors and additional overheads require further analysis.For N = 10^6, η = 54, and ΔE = 0.0016 a.u., the estimated scaling quantity is roughly 10^9.
A Cost of computing table lookups assisted by dirty ancillae
The dirty-ancilla lookup computes a table output by combining address-controlled register swaps with a reduced lookup, then restores the borrowed registers. Its cost balances Toffoli gates against dirty workspace.
- Construction: The procedure allocates a clean output register r0 in |+⟩ and borrows r1 through r_k−1 as dirty ancillae.Dirty ancillae need not begin in a known state and are returned to their initial states.
- Construction: The low address bits select a register permutation S, while the high bits drive a lookup T that reads several possible outputs simultaneously.Register r_l at address h contains the original table entry at address h·k + l.
- Construction: The sequence applies S, T, S−1, then Hadamards and a second T to uncompute the dirt while leaving the output in r0.The other registers are restored before the borrowed ancillae are returned.
- Cost: 2⌈d/k⌉ + 4M(k − 1) Toffoli gates are required, with (k − 1)M dirty ancillae and ⌈log(d/k)⌉ clean ancillae.The count follows from two T operations and four S-related operations.
- Cost: The optimized parameter k is approximately 2d/M, but available dirty qubits can force a smaller value and k must exceed 2 to beat a standard lookup.The transformation also uses M qubits to store the output.
- Comparison: The operation sequence differs from the scheme in [44], reducing the number of registers needed.The present notation calls the corresponding operations S and T rather than Swap and Select.
B Cost of computing table lookups assisted by clean ancillae
The clean-ancilla lookup loads multiple table outputs into initialized registers, permutes them so the selected output reaches r0, and uncomputes the effective lookup. Its cost uses clean workspace instead of dirty registers.
- Construction: The procedure allocates r0 through r_k−1 as M-qubit registers initialized to |0⟩.The registers provide clean workspace for the parallelized lookup.
- Construction: A lookup addressed by the high address bits loads k possible outputs, after which low address bits determine a controlled permutation placing the selected value in r0.The lookup stores the entry at h·k + l in register r_l.
- Construction: The output remains in r0 while the other registers can be uncomputed using the effective-lookup strategy.The strategy begins by measuring all output qubits in the X basis.
- Cost: ⌈d/k⌉ + M(k − 1) Toffoli gates are required, with (k − 1)M clean workspace ancillae and ⌈log(d/k)⌉ additional clean ancillae.The lookup and swapping subroutines are each performed once.
- Cost: The Toffoli-minimizing value of k is approximately d/M, although available clean qubits may impose a smaller value.The transformation still uses M qubits to store the output.
C Efficient uncomputation of table lookups using measurement based uncomputation
Measurement-based uncomputation replaces direct reversal of table lookups with X-basis measurements and classically conditioned phase fixups. This reduces lookup-uncomputation costs while supporting clean- or dirty-ancilla implementations.
- Clean ancillae: With k additional clean ancillae, uncomputing a lookup costs ⌈d/k⌉+k Toffoli gates.The clean-ancilla circuit uses a one-hot unary encoding, phase gates, and a reverse controlled swap to erase that encoding.
- Dirty ancillae: With k−1 dirty ancillae and ⌈log(d/k)⌉+1 clean ancillae, the cost is 2⌈d/k⌉+4k Toffoli gates.The dirty-ancilla construction retains one clean register and uses the remaining registers as dirty qubits during phase fixup.
- Measurement-based uncomputation: Measurement-based uncomputation measures lookup outputs in the X basis and applies a classically conditioned phase fixup instead of reversing the lookup circuit.The deferred measurement principle replaces an X-axis interaction that clears a qubit with an X-basis measurement and phase correction.
- Reduced lookup dimensions: The phase-fixup task can be transformed from a table lookup of address size d and output size M into one with address size d/2 and output size 2.This reduction permits larger batching parameters k in the lookup-uncomputation constructions.
- Unary uncomputation: The binary-to-unary circuit uses controlled swaps, while its inverse expands controlled swaps into CNOT-Toffoli-CNOT constructions.The second CNOT in each group can be omitted in the inverse construction, simplifying the circuit.
D The scaling λ in general contexts
The paper examines λ scaling for hydrogen systems approaching thermodynamic and continuum limits. The observed exponents differ across Coulomb-operator components and remain relevant to whether the proposed scaling improves on prior methods.
- Thermodynamic limit: For hydrogen chains at fixed basis resolution, λV = O(N^2.2) and λW = O(N^2.5), with λT ≤ λV ≤ λW.The λW exponent is slightly worse, but low-rank truncation changes the scaling dependence from λV to λW while saving a factor of N.
- Continuum limit: For fixed H4 approaching the continuum limit, λV = O(N^2.7) and λW = O(N^3), while λW/λV scales roughly as O(N^0.3).The overall scaling is worse than for the hydrogen-chain experiment.
- Implications for algorithmic scaling: In both numerical experiments, λ scales worse than Ω(N^1.5), the condition required for Õ(N^3/2 λ) to outperform Õ(λ^2).The paper states that the relationship between λ, molecular structure, and basis size remains difficult to rigorously bound.
- Experimental settings: The hydrogen-chain experiment fixes basis resolution while increasing system size toward the thermodynamic limit.The paper uses atomic chains because they approach the thermodynamic limit faster than other atomic configurations.
E Detailed costings
This section introduces the accounting of minor Toffoli costs and logical-qubit requirements used in the detailed resource estimates.
- Resource accounting: The detailed costing tracks minor Toffoli costs and the numbers of logical qubits used.These quantities supplement the principal algorithmic resource estimates.
E.1 RWSWT orbitals
For the RWSWT orbitals, the paper reports detailed resource estimates for low-rank and sparse state-preparation variants. The variants trade ancillary-qubit requirements against Toffoli cost.
- System representation: The RWSWT resource estimates represent the system on N = 108 qubits.This register size is used in the detailed logical-qubit accounting.
- Low-rank approach with few dirty qubits: The low-rank approach with a small number of dirty qubits uses 378 logical qubits.The estimate includes the system, state-preparation, QROAM, inequality-test, and phase-estimation registers.
- Low-rank approach with many ancillae: The low-rank approach with many ancillae uses 3,024 logical qubits and has minor costs of 1,594 Toffolis.The large-ancilla variant increases μ to 28 and adds controlled swaps and inequality tests in state preparation.
- Sparse state preparation: The sparse state-preparation approach has minor costs totaling 746 Toffolis.Its accounting omits additional arithmetic costs because it does not use Eq. (20).
- Sparse resource requirements: The sparse approach uses 5,103 logical qubits, including 4,902 QROAM qubits and 24 Toffolis for symmetry controlled swaps.The system registers contain N = 108 qubits, and the phase-estimation register uses 24 qubits.
E.2 LLDUC orbitals
The LLDUC-orbital implementations use either clean-ancilla or sparse state preparation, with distinct Toffoli and logical-qubit costs. The reported totals range from 918 to 1,818 Toffolis and from 437 to 3,143 logical qubits across the variants.
- Toffoli costs: 1,818 Toffolis is the reported total for one LLDUC implementation, including four evaluations of Eq. (20) at 108 Toffolis each.The controlled operations cost 640 Toffolis, while evaluating Eq. (20) contributes 432 Toffolis.
- Logical-qubit costs: 437 logical qubits are required for the LLDUC implementation using a small number of dirty ancillae.The accounting includes 152 system qubits, 42 state-preparation qubits, 94 QROM output qubits, and 25 phase-estimation qubits, among other registers.
- Logical-qubit costs: 3,143 logical qubits are required for the LLDUC implementation with a large number of clean ancillae.The total includes 152 system qubits, 2,723 QROAM qubits, and 26 phase-estimation qubits.
- Toffoli costs: 918 Toffolis is the total minor cost for the LLDUC sparse state-preparation approach.Its components include 640 controlled-operation Toffolis, 142 for one amplitude-amplification step, 108 for preparation and inverse preparation, and 28 for controlled swaps.
- Logical-qubit costs: 2,904 logical qubits are reported for the LLDUC sparse state-preparation approach.The accounting includes 152 system qubits, 2,658 QROAM qubits, 13 clean QROAM qubits, and 24 phase-estimation qubits.
F Preparation of equal superposition states
The paper prepares equal superposition states by starting with power-of-two Hadamard superpositions, enforcing inequality constraints, and using amplitude amplification to increase success amplitude. The construction is applied separately or jointly to the orbital-index registers, with costs determined by the required comparisons and reflections.
- Preparation strategy: Hadamards create broad power-of-two superpositions, after which inequality tests enforce ℓ≤L, p≥q, p<N/2, r≥s, and r<N/2.The resulting state is flagged on success, and amplitude amplification brings its success amplitude close to one.
- LLDUC preparation: 310 Toffolis are required for the ℓ,p,q preparation after two amplitude-amplification steps.The cost combines state inequalities, an ancilla inequality, and reflections.
- LLDUC preparation: 534 Toffolis are required for the LLDUC preparation that separately handles ℓ,p,q and r,s.The first preparation costs 310 Toffolis and the second 224, including forward and reverse preparation.
- Sparse preparation: 160 Toffolis are required for sparse preparation and its inverse when k=2 amplitude-amplification steps are used.The underlying preparation costs 80 Toffolis, comprising inequality tests and reflections.
H Costs of addition, subtraction and inequality tests
The arithmetic circuits implement modular or non-modular addition, subtraction, and inequality testing with Toffoli costs that scale linearly in the register size. Known constants and powers-of-two structure reduce these costs.
- Addition and subtraction: n−1 Toffolis implement modular addition or subtraction on n-qubit variables without a carry qubit.Addition with a carry qubit costs n Toffolis, while subtraction costs n−1.
- Addition and subtraction: n Toffolis implement addition of n-qubit variables when a carry qubit is produced.The 4-qubit carry-output circuit shown in Figure 13 costs 4 Toffolis.
- Cost reductions: k Toffolis can be saved when a known operand is a multiple of 2^k.Trailing zero bits let the circuit omit the corresponding initial carry operations.
- Cost reductions: One Toffoli can be saved when a classically specified constant has least-significant bit i0=1.The first Toffoli can then be replaced by a CNOT.
- Inequality testing: n Toffolis implement an inequality test between n-qubit variables, with modular subtraction providing the comparison flag.Negative values of t−i become values whose most significant bit is 1, indicating t<i.