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%.
Accurately predicting the properties of molecules and materials from first principles requires solving the electronic structure problem. However, the computational cost of solving the electronic structure problem scales prohibitively in the number of atoms, and the usual approximate methods designed to reduce the overhead are often inaccurate for strongly correlated systems. For this reason, quantum algorithms have been developed as a promising alternative. In this work, we develop algebraic tools to improve the efficiency of three quantum algorithms for the electronic structure problem, addressing key bottlenecks for both near-term and fault-tolerant quantum computers. The first is the variational quantum eigensolver (VQE), which suffers from a large measurement overhead needed to estimate the Hamiltonian expectation value. To this end, we introduce a general class of measurable fragments of the electronic Hamiltonian, which enable partitioning schemes that significantly reduce the sampling cost for energy estimation. The second are quantum subspace methods (QSMs). We introduce a new QSM, the quantum seniority-based subspace expansion algorithm, which is a scalable alternative to VQE that alleviates VQE's state preparation, measurement, and optimization challenges while reducing qubit requirements. The third is quantum phase estimation (QPE), which requires an encoding of the electronic Hamiltonian directly on the quantum computer, the cost of which scales indirectly with the Hamiltonian spectral range. To address this, we develop linear programming approaches to implement the Block Invariant Symmetry Shift protocol, a method which reduces the spectral range of the Hamiltonian, improving its block-encoding cost for QPE. Collectively, these methods demonstrate that one can exploit the Hamiltonian's algebraic structure to mitigate computational costs, accelerating the path toward practical quantum advantage for electronic structure.
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.