Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity

Ryan Babbush; Craig Gidney; Dominic W. Berry; Nathan Wiebe; Jarrod McClean; Alexandru Paler; Austin Fowler; Hartmut Neven

Source-linked AI summary

Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity

Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, Hartmut Neven

arXiv:1805.03662v2May 9, 2018quant-phcond-mat.str-elphysics.chem-ph

TL;DR

Classical methods struggle to model strongly correlated electrons because accurately capturing their entanglement can require seemingly exponential resources. This work constructs efficient quantum-walk circuits for phase estimation, obtaining linear-in-basis-size T complexity and fault-tolerant estimates beyond known classical capabilities.

Problem
Modeling superconductivity and molecular electronic structure remains difficult for classical algorithms because strong electron correlation can require seemingly exponentially growing entanglement.
Method
The paper realizes quantum-walk phase-estimation unitaries based on ei arccos(H/λ), constructing explicit circuits for Hubbard and second-quantized electronic-structure Hamiltonians with f = O(N+log(1/ϵ)).
Results
The circuits have T complexity linear in basis size, and the electronic-structure estimates are roughly a million times below prior upper estimates for comparable classically intractable problems.
Takeaways & Limitations
Fault-tolerant phase estimation is estimated to reach interesting Hubbard and molecular instances beyond known classical algorithms using roughly one million physical qubits.
Takeaways & Limitations
The paper does not provide a tighter physical-qubit upper bound and uses conservative surface-code constructions that are not necessarily optimal.

Abstract

from arXiv · show

We construct quantum circuits which exactly encode the spectra of correlated electron models up to errors from rotation synthesis. By invoking these circuits as oracles within the recently introduced "qubitization" framework, one can use quantum phase estimation to sample states in the Hamiltonian eigenbasis with optimal query complexity $O(λ/ ε)$ where $λ$ is an absolute sum of Hamiltonian coefficients and $ε$ is target precision. For both the Hubbard model and electronic structure Hamiltonian in a second quantized basis diagonalizing the Coulomb operator, our circuits have T gate complexity $O({N + \log (1/ε}))$ where $N$ is number of orbitals in the basis. This enables sampling in the eigenbasis of electronic structure Hamiltonians with T complexity $O(N^3 /ε+ N^2 \log(1/ε)/ε)$. Compared to prior approaches, our algorithms are asymptotically more efficient in gate complexity and require fewer T gates near the classically intractable regime. Compiling to surface code fault-tolerant gates and assuming per gate error rates of one part in a thousand reveals that one can error correct phase estimation on interesting instances of these problems beyond the current capabilities of classical methods using only about a million superconducting qubits in a matter of hours.

I. INTRODUCTION

The paper targets spectral estimation for correlated-electron Hamiltonians, replacing time-evolution encodings with qubitization-based quantum walks and efficient fault-tolerant circuits. It gives explicit complexity bounds for electronic-structure and Hubbard models and estimates million-qubit feasibility.

Strong electron correlation makes classical prediction of superconductivity and molecular electronic structure difficult because accurately representing entanglement can grow seemingly exponentially.
Quantum phase estimation traditionally uses time-evolution operators, but quantum-walk encodings W(H) = e^{i arccos(H/λ)} can achieve query complexity O(λ/ε).Here λ is the absolute sum of Hamiltonian coefficients in the weighted-unitary query model.
The paper constructs electronic-structure and Hubbard circuits whose oracle T complexity scales as O(N + log(1/ε)).N denotes the number of orbitals or spin-orbitals, depending on the model.
Fault-tolerant phase estimation is estimated to exceed known classical capabilities on interesting instances using roughly one million physical qubits with two-qubit error rates near 10^-3.The analysis uses surface-code fault tolerance and explicit compiled constructions.
Electronic structure Hamiltonian: 24πNλ/ε + O((λ/ε) log(N/ε)) T gates and log(λ^3N^5/ε^3) + O(1) ancillas suffice for electronic-structure phase estimation.
Hubbard model: 10πNλ/ε + O(λ log(N/ε)/ε) T gates and log(λN^3/ε) + O(1) ancillas suffice for the square planar Hubbard model.

II. PHASE ESTIMATING SPECTRA OF HERMITIAN LINEAR COMBINATIONS OF UNITARIES

The section explains how LCU preparation and selection oracles form a Szegedy quantum walk whose eigenphases encode the Hamiltonian spectrum. Direct phase estimation on this walk provides the same eigenbasis information without simulating time evolution.

The paper’s general strategy uses LCU oracle circuits to implement spectral estimation for correlated-electron Hamiltonians.The approach is presented as a general framework for spectral estimation, with electronic systems providing the specialized constructions.
An LCU decomposition represents H as a weighted sum of self-inverse operators H_ℓ, with preparation and Hamiltonian-selection oracles implementing the decomposition.The preparation oracle creates an ancilla superposition, while the selection oracle applies H_ℓ controlled by the selection register.
The direct walk-based phase-estimation method can learn as quickly as traditional phase estimation when the eigenphase is bounded away from zero.The stated condition excludes frustration-free Hamiltonians from this guarantee.
The quantum-walk operator is built from two reflections, including R_L and the reflection implemented through select, and can be controlled on an ancilla.
For each Hamiltonian eigenstate with eigenvalue E_k, the walk has eigenphases ± arccos(E_k/λ), so phase estimation on W recovers the spectrum of H.The relevant invariant subspace is two-dimensional and contains |L⟩|k⟩ and an orthogonal state |φ_k⟩.

B. Heisenberg-Limited Phase Estimation of the Qubitized Quantum Walk

The paper uses entanglement-based phase estimation to estimate eigenphases at the Heisenberg limit while reducing controlled-unitary applications. A modified circuit removes phase ambiguity and prepares the required resource state with negligible overhead.

Heisenberg-limited phase estimation: The entanglement-based approach reaches the Heisenberg limit with 2^(m+1) − 1 applications of the unitary for m control qubits.Its Holevo variance is tan^2(π/(2^(m+1) + 1)).
Modified phase estimation: Applying the inverse unitary on the ancilla |0⟩ branch doubles the effective phase difference without changing complexity.Controlled inverse operations are implemented using reflection operators R_L inserted into the circuit.
Modified phase estimation: An additional controlled-W operation removes the modulo-π ambiguity while reducing the unitary-query complexity to approximately 2^m.The modified trick alone cannot distinguish phases separated by π.
Circuit costs: The resource-state preparation χ_m and inverse QFT have gate complexity eO(m), negligible compared with the O(2^m) phase-estimation cost.The circuit uses 2^m − 1 applications of R_L and the same number of select operations.

C. Error Scaling and Query Complexity

The error analysis separates phase-estimation, prepare-oracle, and inverse-QFT errors, then relates these errors to energy accuracy and oracle-query costs. The implementation targets minimize select and prepare costs without increasing λ, while coefficient errors can become singular for frustration-free Hamiltonians.

Error sources: Three error sources are considered: finite-precision phase estimation, approximate prepare coefficients, and inverse-QFT synthesis.The analysis measures total error using the root-mean-square error of the phase-estimation estimator.
Error propagation: For unitary phase estimation, the energy-estimation error is at most the error from implementing the unitary.The estimated phase is decomposed into random phase-estimation error, systematic prepare error, and the true phase.
Error budgeting: The equal-error allocation between phase estimation and circuit synthesis is explicitly suboptimal because reducing phase-estimation error costs exponentially more.The paper adopts the equal allocation for simplicity.
Query and gate complexity: The simulation uses at most the stated number of select queries and twice as many prepare queries to estimate spectra within energy error ΔE.With select cost S and prepare cost P, the resulting gate complexity is bounded by the expression following Eq. (15).
Query and gate complexity: The implementations minimize select and prepare costs without increasing λ, while inverse-QFT synthesis contributes O(m log(m/ε_QFT)) T gates.The inverse QFT cost is additive to the O(2^m) phase-estimation cost.
Error propagation: Coefficient errors can diverge for frustration-free Hamiltonians because arccos is singular.This makes propagation from prepare-oracle coefficient errors to phase error nonlinear.

III. LOW T COMPLEXITY PRIMITIVES FOR LCU ORACLES

The paper introduces low-T-complexity primitives for LCU oracles, centered on unary iteration, efficient QROM, and amplitude preparation. These constructions reduce controlled-index operations from O(L log L) T gates to 4L −4 while using only log L ancillae.

Unary Iteration: O(L) T gates replace O(L log L) for coherently applying operations controlled by a log L-qubit register.The streaming technique enables controlled indexed operations with T complexity O(L).
Quantum Read-Only Memory: 4L−4 T gates implement QROM lookup for L words without dependence on word length.The paper describes this as an asymptotic and constant-factor improvement over prior black-box constructions.
Amplitude Preparation: 4L+O(log(1/ϵ)) T gates initialize amplitudes for L unique coefficients while avoiding an increase in λ.The largest tolerated absolute amplitude error is ϵ.
Unary Iteration: Unary iteration gradually produces and uncomputes one-hot indicator qubits for values stored in an index register.It is built by simplifying total controls, nesting and operations, and optimizing adjacent operations.
Unary Iteration: 4L −4 T gates and log L ancillae implement unary iteration, improving space over the usual L-qubit unary-register conversion.The construction can be parallelized without increasing its T-count.
Unary Iteration: Adjacent and-operation mergers replace uncomputation and recomputation with CNOT and NOT operations, saving 4 T gates per merger.This optimization produces the sawtooth-to-unary-iteration transformation used for controlled indexed Xℓ operations.

C. Quantum Read-Only Memory (QROM) for Low T Complexity Data Lookup

The paper develops fault-tolerant QROM for read-only classical data lookup and uses it in a low-T-count coefficient-preparation procedure. The resulting preparation cost is additive in the number of unique coefficients and precision, rather than multiplicative.

QROM definition: QROM permits reading classical data associated with a quantum index but does not allow writing during computation.Its implementation is designed for fault-tolerant cost models based on T gates and ancilla qubits.
QROM cost: 4L T gates and log L ancillae implement the paper’s QROM construction for L classical words.This improves space usage exponentially and T-count by a constant factor relative to the cited bucket-brigade QRAM construction.
Coefficient preparation: 4L + O(log(1/ϵ)) T gates initialize a state with L unique coefficients, with amplitude error bounded by ϵ.The construction achieves additive dependence on coefficient count and precision, improving over O(L log(L/ϵ)).
Coefficient preparation: The preparation scheme starts from a uniform index superposition, loads keep_ℓ and alt_ℓ from QROM, and conditionally swaps the index with its alias.A µ-qubit comparison register σ implements the swap probability encoded by keep_ℓ.
Uniform initialization: If L is not a power of two, amplitude amplification prepares the initial uniform superposition over L indices.The controlled circuit has T-count 2k + 10 log L + O(log(1/ϵ)) in the stated odd-L construction.
Alias construction: The alias-sampling interpretation selects ℓ uniformly, looks up alt_ℓ and keep_ℓ, then returns either ℓ or alt_ℓ according to keep_ℓ/2^µ.The alias data are constructed by shifting probabilities until the distribution becomes uniform.

IV. CONSTRUCTIONS FOR THE ELECTRONIC STRUCTURE HAMILTONIAN

The electronic structure Hamiltonian is represented in a spin-orbital basis and mapped to qubits using Jordan–Wigner operators. Its relevant structure contains only a small set of Pauli-term types and O(N) unique coefficients, supporting efficient oracle constructions.

Hamiltonian representation: The molecular electronic structure Hamiltonian models electrons interacting through the Coulomb potential with kinetic and external-potential terms in a finite basis.The basis uses N spin-orbitals.
Qubit mapping: Jordan–Wigner mapping converts the fermionic creation, annihilation, and number operators into qubit operators.The paper uses a Jordan–Wigner-indexed notation for the resulting Pauli strings.
Basis compatibility: The Hamiltonian form is compatible with finite-difference, finite-element, and Gausslet representations, provided they satisfy the same structural form.Gausslets are derived from a ternary wavelet transformation of Gaussian orbitals.
Term structure: The Hamiltonian contains four types of terms, including Z_p, Z_pZ_q, and Jordan–Wigner-dressed X and Y terms.The listed term structure is the basis for the simulation procedures.
Coefficient structure: 3N/2 unique coefficient values suffice despite O(N^2) different Hamiltonian terms.The algorithms exploit the repeated-coefficient structure rather than additional special structure of the dual-basis representation.

A. Electronic Structure Hamiltonian Selection Oracle

The electronic structure selection oracle indexes Hamiltonian terms with control and orbital registers, then applies the corresponding Pauli operation and phase. Its construction uses controlled Pauli-string primitives with linear T complexity.

Register indexing: The selection oracle indexes terms using θ, U, V, p, α, q, and β registers.The orbital registers use log N − 1 qubits each, while the remaining control and spin registers are single bits.
Term selection: U and V distinguish single-Z, ZZ, and off-diagonal Jordan–Wigner-dressed X or Y operations based on orbital indices and spin labels.The cases depend on whether p is less than or greater than q and whether the spin labels match.
Phase control: θ controls whether the selected unitary receives a negative phase.The oracle applies the phase factor (−1)^θ to the indexed operation.
Circuit primitives: The oracle relies on subroutines that selectively apply Pauli strings to an N-qubit system using controls on log N qubits.These primitives have T complexity O(L) when there are L possible index values.
Resource cost: The selectchem circuit has T-count 12N + 8 log N + O(1).The construction explicitly includes Majorana and indexed-operation unitaries, each requiring 4N T gates.

B. Electronic Structure Coefficient Preparation Oracle

The coefficient-preparation oracle builds the electronic-structure coefficient state from a subprepare routine, uniform superpositions, and register transformations. Its overall T complexity is O(N + log(1/ϵ)).

Coefficient state: Only O(N) unique coefficients need to be prepared even though the electronic structure Hamiltonian has O(N^2) terms.The preparation oracle uses this repeated-coefficient structure to reduce its data-loading cost.
State preparation: Subprepare initializes the coefficient-dependent part of the state, after which uniform registers and spin controls complete the indexed superposition.The construction handles the p = q, α ≠ β case separately before converting difference indices into orbital indices.
Subprepare cost: The subprepare routine has T complexity O(N + log(1/ϵ)), improving over the prior O(N log(1/ϵ)) approach.The implementation uses modular vector indices for three-dimensional orbital indexing.
Register conversion: Fredkin gates and addition convert the difference register into the desired p and q orbital registers.When U = 1, the registers are swapped before addition; when U = 0, q is added so that p − q + q = p.
Overall cost: The full prepare oracle retains the same asymptotic T complexity, O(N + log(1/ϵ)), because all other components cost O(log N).The subprepare subroutine is the dominant cost.
Uncomputation: Potentially uncomputed registers must be retained and reused as inputs to the next preparechem operation.This accounts for the imperfect exact uncomputation of the U, V, p, q, α, and β qubits.

C. Resources Required for Electronic Structure Simulation

The electronic-structure resource analysis relates T complexity to λ, basis and material parameters, and estimates costs for jellium and real materials. It also identifies extrapolation and modeling choices left for future work.

λ scales linearly into circuit size, while practical scaling depends on basis choice, geometry, composition, and continuum or thermodynamic limits.
O(N^3/∆E) rigorously bounds the T complexity for electronic-structure Hamiltonian simulation.
Jellium: λ = O(∼N^5/3) is observed for jellium at rs = 10 Bohr radii and half-filling, a classically challenging regime.
Jellium: Twenty million T gates are estimated for jellium with 54 orbitals at chemical accuracy ∆E = 0.0016 Hartree.
Real materials: At fixed plane-wave count, increasing supercell volume empirically decreases λ as λ = O(∼Ω^-1/2).
Scope: Molecule-specific resource estimates require pseudopotentials, continuum and thermodynamic-limit extrapolation, and embedding methods.

V. CONSTRUCTIONS FOR THE HUBBARD MODEL

The Hubbard-model selection oracle exploits planar translational structure and periodic boundaries to implement indexed Hamiltonian terms efficiently. Its specialized construction reduces the T cost while preserving the required operator actions.

The planar Hubbard model uses periodic boundary conditions and can be viewed as a restricted electronic-structure Hamiltonian.
The construction indexes terms with U, V, px, py, α, qx, qy, and β registers, omitting θ because coefficient signs are known.
The selection oracle applies −Z, ZZ, −XZX, and −YZY operators according to control-register values and site or spin-index relations.
10N + O(log N) T gates are achieved for selecthub by exploiting translational invariance and separating planar coordinates.

B. Hubbard Model Coefficient Preparation Oracle

The Hubbard coefficient-preparation oracle uses the model’s three distinct coefficients to prepare LCU weights with logarithmic precision dependence. The resulting resource estimates include T gates, ancillae, and representative challenging-regime instances.

O(log(1/ϵ)) T complexity implements the Hubbard prepare circuit because only three coefficient values require preparation.
S = 10N + O(log N) and P ∈ O(log(N/ϵ)) determine the Hubbard algorithm’s T-cost scaling.
The Hubbard implementation requires 3 log N + O(1) ancillae beyond the phase-estimation contribution.
The resource table targets periodic spinful Hubbard systems with u/t = 4 and ∆E = t/100.

D. Exploiting Locality in Simulations of Lattice Hamiltonians

The paper uses locality and fault-tolerant resource modeling to reduce lattice-simulation overheads and estimate complete phase-estimation implementations. Automated and manual surface-code estimates are broadly consistent, with million-qubit and hour-scale costs for most cases.

Locality: Lieb-Robinson bounds enable recursive patching of local evolution into separated subregions with exponentially controllable approximation error.
Locality: The Hubbard model satisfies the locality conditions, allowing the circuits to reduce constant and some logarithmic T-complexity factors while attaining e O(τN) scaling.
Fault tolerance: Surface-code estimates assume planar nearest-neighbor arrays, with T-state preparation supplying the dominant non-Clifford resource overhead.
Resource estimation: Automated surface-code estimates generally exceed manual estimates by 10–20%, while their time estimates are practically identical.
Resource estimation: Physical-qubit counts are of order a million and execution times are hours for all but the largest cases considered.
Resource estimation: Compactly storing mostly idle system qubits could reduce overall physical-qubit requirements conservatively by a factor of two.

VII. CONCLUSION

The paper develops efficient fault-tolerant phase-estimation circuits for electronic Hamiltonian spectra and evaluates their resource requirements. It identifies extensions to molecular representations and tighter physical-qubit estimates as important future work.

VII. CONCLUSION: The circuits implement quantum-walk phase estimation for electronic Hamiltonians, with explicit Clifford + T constructions and surface-code resource estimates.The approach targets both electronic structure and Hubbard Hamiltonians.
VII. CONCLUSION: The method estimates eigenvalues to additive error ϵ using O(λ/ϵ) quantum-walk queries and achieves T complexity linear in basis size for both target models.These results rely on encoding the quantum walk ei arccos(H/λ).
VII. CONCLUSION: Roughly a million times fewer T gates were required than prior estimates for the compared classically intractable electronic-structure problems.The comparison is against approximately 10^15–10^16 T gates estimated for a 10^8-qubit FeMoco active-space simulation.
VII. CONCLUSION: Extending the techniques to single molecules requires more suitable basis representations, while Gausslet functions for heavy nuclei such as iron require further research.The dual basis is described as well suited to solid-state materials, not single molecules.
VII. CONCLUSION: A tighter physical-qubit upper bound remains needed because the validated surface-code constructions and resource choices used here are conservative rather than necessarily optimal.Lattice surgery and alternative trade-offs could reduce physical-qubit requirements.

Appendix A: Propagating Errors from Hamiltonian Coefficients into Phase Estimate

The appendix analyzes how coefficient-approximation errors in the Hamiltonian preparation oracle affect phase-estimation accuracy. It emphasizes heightened sensitivity when eigenvalues lie near the singularity of arccos.

Appendix A: Propagating Errors from Hamiltonian Coefficients into Phase Estimate: The analysis asks how accurately Hamiltonian coefficients must be prepared to estimate eigenvalues to precision ϵ.The phase-estimation scheme uses phases induced by ei arccos(H/λ).
Appendix A: Propagating Errors from Hamiltonian Coefficients into Phase Estimate: Errors in the Hamiltonian can substantially affect the encoded phase near the singularity of arccos.This sensitivity motivates propagating coefficient errors into eigenphase errors.
Appendix A: Propagating Errors from Hamiltonian Coefficients into Phase Estimate: The appendix introduces δ as an upper bound on approximation errors in the prepared coefficients.The subsequent derivation uses this bound to relate Hamiltonian-encoding errors to eigenphase errors.
Appendix A: Propagating Errors from Hamiltonian Coefficients into Phase Estimate: An inductive bound for the double-factorial expression is established and then substituted into the preceding error relations.The supplied derivation states the intermediate substitutions but does not include the resulting equations.