Assessing the query complexity limits of quantum phase estimation using symmetry-aware spectral bounds
Cristian L. Cortes, Dario Rocca, Jérôme F. Gonthier, Pauline J. Ollitrault, Robert M. Parrish, Gian-Luca Anselmetti, Matthias Degroote, Nikolaj Moll, Raffaele Santagati, Michael Streif
The computational cost of quantum algorithms for physics and chemistry is closely linked to the spectrum of the Hamiltonian, a property that manifests in the necessary rescaling of its eigenvalues. The typical approach of using the 1-norm as an upper bound to the spectral norm to rescale the Hamiltonian suits the most general case of bounded Hermitian operators but neglects the influence of symmetries commonly found in chemical systems. In this work, we introduce a hierarchy of symmetry-aware spectral bounds that provide a unified understanding of the performance of quantum phase estimation algorithms using block-encoded electronic structure Hamiltonians. We present a variational and numerically tractable method for computing these bounds, based on orbital optimization, to demonstrate that the computed bounds are smaller than conventional spectral bounds for a variety of molecular benchmark systems. We also highlight the unique analytical and numerical scaling behavior of these bounds in the thermodynamic and complete basis set limits. Our work shows that there is room for improvement in reducing the 1-norm, not yet achieved through methods like double factorization and tensor hypercontraction, but highlights the potential challenges in improving the performance of current quantum algorithms beyond small constant factors through 1-norm reduction techniques alone.
The computational cost of quantum algorithms for physics and chemistry is closely linked to the spectrum of the Hamiltonian, a property that manifests in the necessary rescaling of its eigenvalues. The typical approach of using the 1-norm as an upper bound to the spectral norm to rescale the Hamiltonian suits the most general case of bounded Hermitian operators but neglects the influence of symmetries commonly found in chemical systems. In this work, we introduce a hierarchy of symmetry-aware spectral bounds that provide a unified understanding of the performance of quantum phase estimation algorithms using block-encoded electronic structure Hamiltonians. We present a variational and numerically tractable method for computing these bounds, based on orbital optimization, to demonstrate that the computed bounds are smaller than conventional spectral bounds for a variety of molecular benchmark systems. We also highlight the unique analytical and numerical scaling behavior of these bounds in the thermodynamic and complete basis set limits. Our work shows that there is room for improvement in reducing the 1-norm, not yet achieved through methods like double factorization and tensor hypercontraction, but highlights the potential challenges in improving the performance of current quantum algorithms beyond small constant factors through 1-norm reduction techniques alone.
Reducing the complexity of quantum algorithms to treat quantum chemistry problems is essential to demonstrate an eventual quantum advantage of noisy-intermediate scale quantum devices over their classical counterpart. Significant improvements have been made recently to simulate the time-evolution operator $U(t)={e}^{i\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{H}}t}$, where $\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{H}}$ is the electronic structure Hamiltonian, or to simulate $\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{H}}$ directly (when written as a linear combination of unitaries) by using block encoding or qubitization techniques. A fundamental measure quantifying the practical implementation complexity of these quantum algorithms is the so-called 1-norm of the qubit representation of the Hamiltonian, which can be reduced by writing the Hamiltonian in factorized or tensor-hypercontracted forms, for instance. In this paper, we investigate the effect of classical preoptimization of the electronic structure Hamiltonian representation, via single-particle basis transformation, on the 1-norm. Specifically, we employ several localization schemes and benchmark the 1-norm of several systems of different sizes (number of atoms and active space sizes). We also derive a formula for the 1-norm as a function of the electronic integrals and use this quantity as a cost function for an orbital-optimization scheme that improves over localization schemes. This paper gives more insights about the importance of the 1-norm in quantum computing for quantum chemistry and provides simple ways of decreasing its value to reduce the complexity of quantum algorithms.
High Resolution Image Download MS PowerPoint Slide Quantum phase estimation (QPE) is a promising quantum algorithm for obtaining molecular ground-state energies with chemical accuracy. However, its computational cost, dominated by the Hamiltonian 1-norm λ and the cost of the block encoding, scales at least quadratically with the number of molecular orbitals, making it challenging to incorporate dynamic correlation by enlarging the active space. In this work, we investigate two strategies to mitigate this cost through the optimization of the basis set. First, we investigate whether adjusting the coefficients of Gaussian basis functions can minimize the 1-norm while preserving the accuracy of the ground state energy. Although this method leads to a reduction in the 1-norm up to 10%, this reduction is system-dependent and diminishes with increasing molecular size. Second, we demonstrate that employing a large-basis-set frozen natural orbital (FNO) strategy results in a substantial reduction in QPE resources without compromising accuracy. We study a data set of 58 small organic molecules and the dissociation curve of N 2, and demonstrate that an active space constructed from orbitals derived from larger basis sets captures correlation effects more effectively. This approach yields up to an 80% reduction in the 1-norm λ and also leads to a 55% reduction in the number of orbitals. Our results highlight that improving the quality, not just the size, of the orbital basis is a viable strategy for extending QPE to include dynamical correlation, making progress toward scalable and chemically accurate quantum simulations with tractable resource requirements.
Computational cost of energy estimation for molecular electronic Hamiltonians via quantum phase estimation (QPE) grows with the difference between the largest and smallest eigenvalues of the Hamiltonian. In this work, we propose a preprocessing procedure that reduces the norm of the Hamiltonian without changing its eigenspectrum for the target states of a particular symmetry. The new procedure, block-invariant symmetry shift (BLISS), builds an operator T̂ such that the cost of implementing H ^ − T ^ is reduced compared to that of Ĥ, yet H ^ − T ^ acts on the subspaces of interest the same way as Ĥ does. BLISS performance is demonstrated for a linear combination of unitaries (LCU)-based QPE approaches on a set of small molecules. Using the number of electrons as the symmetry specifying the target set of states, BLISS provided a factor of 2 reduction of 1-norm for several LCU decompositions compared to their unshifted versions.
We describe quantum circuits with only O(N ) Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of N arbitrary (e.g., molecular) orbitals.With 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 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 work only 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 nonorthogonal basis defined by the THC factors.We then use qubitization to simulate the nonorthogonal THC Hamiltonian, in a fashion that avoids most complications of the nonorthogonal 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 space-time volume, compilation of our algorithm for challenging finitesized 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 4 days of runtime, assuming 1-μs cycle times and physical gate-error rates no worse than 0.1%.
The most advanced techniques using fault-tolerant quantum computers to estimate the ground-state energy of a chemical Hamiltonian involve compression of the Coulomb operator through tensor factorizations, enabling efficient block encodings of the Hamiltonian. A natural challenge of these methods is the degree to which block-encoding costs can be reduced. We address this challenge through the technique of spectral amplification, which magnifies the spectrum of the low-energy states of Hamiltonians that can be expressed as sums of squares. Spectral amplification enables estimating ground-state energies with significantly improved cost scaling in the block encoding normalization factor Λ to just 2 Λ E gap , where E gap ≪ Λ is the lowest energy of the sum-of-squares Hamiltonian. To achieve this, we show that sum-of-squares representations of the electronic structure Hamiltonian are efficiently computable by a family of classical simulation techniques that approximate the ground-state energy from below. In order to further optimize, we also develop a novel factorization that provides a trade-off between the two leading Coulomb integral factorization schemes—namely, double factorization and tensor hypercontraction—that when combined with spectral amplification yields a factor of 4 to 195 speedup over the state of the art in ground-state energy estimation for models of iron-sulfur complexes and a CO 2 -fixation catalyst.
The spectral condition number is a widely adopted measure of worst-case cost for quantum linear system solvers. Yet it can significantly overestimate the actual runtime for a typical problem instance. We present two quantum algorithms that produce the normalized solution ∣x⟩ of linear system Ax=∣b⟩ to accuracy ε with complexity independent of the condition number κ=∥A−1∥. We focus on the standard input model where A is accessed through a block encoding and ∣b⟩ is prepared by a unitary. But we also introduce an affine dilation model that encodes A and ∣b⟩ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to ∣b⟩ and O(κeffpolylog(εκeff)) queries to A. We prove a family of upper bounds on the effective condition number, including κeff≤ε1/t∥(A†A)−t/2∣x⟩∥1/t for positive even integer t and κeff≤ε1/t∥A−1†(A†A)−(t−1)/2∣x⟩∥1/t for positive odd t, overcoming the κ-barrier. Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity 3ε∥A−1†∣x⟩∥ to leading order when the solution norm is known. We then present a similarly simple solution norm estimator with the same asymptotic cost up to logarithmic factors. Our quantum linear system solvers thus substantially improve a recent algorithm of Li, enabling faster quantum linear system solving beyond the condition number.