Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0007001 · Physical Review A

Scaling considerations in ground-state quantum computation

Ari Mizel, Morgan W. Mitchell, Marvin L. Cohen

Published Jan 15, 2002• 20 citations
arXivHTMLPDF

Abstract

We study design challenges associated with realizing a ground-state quantum computer. In such a computer, it is necessary that the energy gap between the ground state and first excited state be sufficiently large to prevent disruptive excitations. Here, an estimate of this gap is provided as a function of computer size. We then address the problem of detecting the output of a ground-state quantum computer. It is shown that the exponential detection difficulties that appear to be present at first can be overcome by small design changes.

DOI
10.1103/physreva.65.022315

Related papers

Near-optimal ground state preparation

Lin Lin, Yu Tong

Preparing the ground state of a given Hamiltonian and estimating its ground energy are important but computationally hard tasks. However, given some additional information, these problems can be solved efficiently on a quantum computer. We assume that an initial state with non-trivial overlap with the ground state can be efficiently prepared, and the spectral gap between the ground energy and the first excited energy is bounded from below. With these assumptions we design an algorithm that prepares the ground state when an upper bound of the ground energy is known, whose runtime has a logarithmic dependence on the inverse error. When such an upper bound is not known, we propose a hybrid quantum-classical algorithm to estimate the ground energy, where the dependence of the number of queries to the initial state on the desired precision is exponentially improved compared to the current state-of-the-art algorithm proposed in [Ge et al. 2019]. These two algorithms can then be combined to prepare a ground state without knowing an upper bound of the ground energy. We also prove that our algorithms reach the complexity lower bounds by applying it to the unstructured search problem and the quantum approximate counting problem.

arXiv:2002.12508•Quantum•Dec 14, 2020•189 citations

Feasibility of performing quantum chemistry calculations on quantum computers

Thibaud Louvet, Thomas Ayral, Xavier Waintal

Quantum chemistry is envisioned as an early and disruptive application for quantum computers. Yet, closer scrutiny of the proposed algorithms shows that there are considerable difficulties along the way. Here, we propose two criteria for evaluating two leading quantum approaches for finding the ground state of molecules. The first criterion applies to the variational quantum eigensolver (VQE) algorithm. It sets an upper bound to the level of imprecision/decoherence that can be tolerated in quantum hardware as a function of the targeted precision, the number of gates and the typical energy contribution from states populated by decoherence processes. We find that decoherence is highly detrimental to the accuracy of VQE and performing relevant chemistry calculations would require performances that are expected for fault-tolerant quantum computers, not mere noisy hardware, even with advanced error mitigation techniques. Physically, the sensitivity of VQE to decoherence originates from the fact that, in VQE, the spectrum of the studied molecule has no correlation with the spectrum of the quantum hardware used to perform the computation. The second criterion applies to the quantum phase estimation (QPE) algorithm, which is often presented as the go-to replacement of VQE upon availability of (noiseless) fault-tolerant quantum computers. QPE requires an input state with a large enough overlap with the sought-after ground state. We provide a criterion to estimate quantitatively this overlap based on the energy and the energy variance of said input state. Using input states from a variety of state-of-the-art classical methods, we show that the scaling of this overlap with system size does display the standard orthogonality catastrophe, namely an exponential suppression with system size. This in turns leads to an exponentially reduced QPE success probability.

arXiv:2306.02620•Physical review. B./Physical review. B•Dec 19, 2025•5 citations

On fixed-gap adiabatic quantum computation

Ari Mizel

Quantum computation has revolutionary potential for speeding algorithms and for simulating quantum systems such as molecules. We report here a quantum computer design that performs universal quantum computation within a single non-degenerate ground state protected from decohering noise by an energy gap that we argue is system-size-independent. Closely analogous to a traditional electric circuit, it substantially changes the requirements for quantum computer construction, easing measurement, timing, and heating problems. Using the standard adiabatic condition, we present evidence that this design permits "quantum concurrent processing" distributing a quantum computation among extra qubits to perform a quantum algorithm of N gates in an amount of time that scales with the square root of N. One consequence of our work is a fixed gap version of adiabatic quantum computation, which several arguments hinted could be impossible.

arXiv:1002.0846•Feb 4, 2010•1 citation

Efficient ground-state-energy estimation and certification on early fault-tolerant quantum computers

Guoming Wang, Daniel Stilck França, Gumaro Rendon +1 more

A major thrust in quantum algorithm development over the past decade has been the search for the quantum algorithms that will deliver practical quantum advantage first. Today's quantum computers---and even early fault-tolerant quantum computers---are limited in the number of operations they can implement per circuit. We introduce quantum algorithms for ground-state-energy estimation (GSEE) that accommodate this design constraint. The first algorithm estimates ground-state energies, offering a quadratic improvement on the ground-state overlap parameter compared to other methods in this regime. The second algorithm certifies that the estimated ground-state energy is within a specified error tolerance of the true ground-state energy, addressing the issue of gap estimation that beleaguers several ground-state preparation and energy estimation algorithms. We note, however, that the scaling of this certification technique is currently less favorable than that of the GSEE algorithm. To develop the certification algorithm, we propose an alternative use of quantum computers to facilitate rejection sampling. After a classical computer generates initial samples, the quantum computer is used to accept or reject these samples, resulting in a set of accepted samples that approximate draws from a target distribution. Although we apply this technique specifically for ground-state-energy certification, it may find broader applications. Our paper pushes the boundaries of what operation-limited quantum computers can achieve, bringing the prospect of quantum advantage closer to realization.

arXiv:2304.09827•Physical Review A•Jan 17, 2025•8 citations

Exponential complexity of an adiabatic algorithm for an NP-complete problem

Marko Žnidarič, Martin Horvat

We prove an analytical expression for the size of the gap between the ground and the first excited state of quantum adiabatic algorithm for the 3-satisfiability, where the initial Hamiltonian is a projector on the subspace complementary to the ground state. For large problem sizes the gap decreases exponentially and as a consequence the required running time is also exponential.

arXiv:quant-ph/0509162•Physical Review A•Feb 17, 2006•61 citations

General error estimate for adiabatic quantum computing

Gernot Schaller, Sarah Mostame, Ralf Schützhold

Most investigations devoted to the conditions for adiabatic quantum computing are based on the first-order correction $⟨{\ensuremath{\Psi}}_{\mathrm{ground}}(t)\ensuremath{\mid}\stackrel{\ifmmode \dot{}\else \.{}\fi{}}{H}(t)\ensuremath{\mid}{\ensuremath{\Psi}}_{\mathrm{excited}}(t)⟩∕\mathrm{\ensuremath{\Delta}}{E}^{2}(t)⪡1$. However, it is demonstrated that this first-order correction does not yield a good estimate for the computational error. Therefore, a more general criterion is proposed, which includes higher-order corrections as well, and shows that the computational error can be made exponentially small---which facilitates significantly shorter evolution times than the above first-order estimate in certain situations. Based on this criterion and rather general arguments and assumptions, it can be demonstrated that a run-time $T$ of order of the inverse minimum energy gap $\mathrm{\ensuremath{\Delta}}{E}_{\mathrm{min}}$ is sufficient and necessary, i.e., $T=O(\mathrm{\ensuremath{\Delta}}{E}_{\mathrm{min}}^{\ensuremath{-}1})$. For some examples, these analytical investigations are confirmed by numerical simulations.

arXiv:quant-ph/0510183•Physical Review A•Jun 7, 2006•64 citations
We study design challenges associated with realizing a ground-state quantum computer. In such a computer, it is necessary that the energy gap between the ground state and first excited state be sufficiently large to prevent disruptive excitations. Here, an estimate of this gap is provided as a function of computer size. We then address the problem of detecting the output of a ground-state quantum computer. It is shown that the exponential detection difficulties that appear to be present at first can be overcome by small design changes.
Preparing the ground state of a given Hamiltonian and estimating its ground energy are important but computationally hard tasks. However, given some additional information, these problems can be solved efficiently on a quantum computer. We assume that an initial state with non-trivial overlap with the ground state can be efficiently prepared, and the spectral gap between the ground energy and the first excited energy is bounded from below. With these assumptions we design an algorithm that prepares the ground state when an upper bound of the ground energy is known, whose runtime has a logarithmic dependence on the inverse error. When such an upper bound is not known, we propose a hybrid quantum-classical algorithm to estimate the ground energy, where the dependence of the number of queries to the initial state on the desired precision is exponentially improved compared to the current state-of-the-art algorithm proposed in [Ge et al. 2019]. These two algorithms can then be combined to prepare a ground state without knowing an upper bound of the ground energy. We also prove that our algorithms reach the complexity lower bounds by applying it to the unstructured search problem and the quantum approximate counting problem.
Quantum chemistry is envisioned as an early and disruptive application for quantum computers. Yet, closer scrutiny of the proposed algorithms shows that there are considerable difficulties along the way. Here, we propose two criteria for evaluating two leading quantum approaches for finding the ground state of molecules. The first criterion applies to the variational quantum eigensolver (VQE) algorithm. It sets an upper bound to the level of imprecision/decoherence that can be tolerated in quantum hardware as a function of the targeted precision, the number of gates and the typical energy contribution from states populated by decoherence processes. We find that decoherence is highly detrimental to the accuracy of VQE and performing relevant chemistry calculations would require performances that are expected for fault-tolerant quantum computers, not mere noisy hardware, even with advanced error mitigation techniques. Physically, the sensitivity of VQE to decoherence originates from the fact that, in VQE, the spectrum of the studied molecule has no correlation with the spectrum of the quantum hardware used to perform the computation. The second criterion applies to the quantum phase estimation (QPE) algorithm, which is often presented as the go-to replacement of VQE upon availability of (noiseless) fault-tolerant quantum computers. QPE requires an input state with a large enough overlap with the sought-after ground state. We provide a criterion to estimate quantitatively this overlap based on the energy and the energy variance of said input state. Using input states from a variety of state-of-the-art classical methods, we show that the scaling of this overlap with system size does display the standard orthogonality catastrophe, namely an exponential suppression with system size. This in turns leads to an exponentially reduced QPE success probability.
Quantum computation has revolutionary potential for speeding algorithms and for simulating quantum systems such as molecules. We report here a quantum computer design that performs universal quantum computation within a single non-degenerate ground state protected from decohering noise by an energy gap that we argue is system-size-independent. Closely analogous to a traditional electric circuit, it substantially changes the requirements for quantum computer construction, easing measurement, timing, and heating problems. Using the standard adiabatic condition, we present evidence that this design permits "quantum concurrent processing" distributing a quantum computation among extra qubits to perform a quantum algorithm of N gates in an amount of time that scales with the square root of N. One consequence of our work is a fixed gap version of adiabatic quantum computation, which several arguments hinted could be impossible.
A major thrust in quantum algorithm development over the past decade has been the search for the quantum algorithms that will deliver practical quantum advantage first. Today's quantum computers---and even early fault-tolerant quantum computers---are limited in the number of operations they can implement per circuit. We introduce quantum algorithms for ground-state-energy estimation (GSEE) that accommodate this design constraint. The first algorithm estimates ground-state energies, offering a quadratic improvement on the ground-state overlap parameter compared to other methods in this regime. The second algorithm certifies that the estimated ground-state energy is within a specified error tolerance of the true ground-state energy, addressing the issue of gap estimation that beleaguers several ground-state preparation and energy estimation algorithms. We note, however, that the scaling of this certification technique is currently less favorable than that of the GSEE algorithm. To develop the certification algorithm, we propose an alternative use of quantum computers to facilitate rejection sampling. After a classical computer generates initial samples, the quantum computer is used to accept or reject these samples, resulting in a set of accepted samples that approximate draws from a target distribution. Although we apply this technique specifically for ground-state-energy certification, it may find broader applications. Our paper pushes the boundaries of what operation-limited quantum computers can achieve, bringing the prospect of quantum advantage closer to realization.
Most investigations devoted to the conditions for adiabatic quantum computing are based on the first-order correction $⟨{\ensuremath{\Psi}}_{\mathrm{ground}}(t)\ensuremath{\mid}\stackrel{\ifmmode \dot{}\else \.{}\fi{}}{H}(t)\ensuremath{\mid}{\ensuremath{\Psi}}_{\mathrm{excited}}(t)⟩∕\mathrm{\ensuremath{\Delta}}{E}^{2}(t)⪡1$. However, it is demonstrated that this first-order correction does not yield a good estimate for the computational error. Therefore, a more general criterion is proposed, which includes higher-order corrections as well, and shows that the computational error can be made exponentially small---which facilitates significantly shorter evolution times than the above first-order estimate in certain situations. Based on this criterion and rather general arguments and assumptions, it can be demonstrated that a run-time TTT of order of the inverse minimum energy gap $\mathrm{\ensuremath{\Delta}}{E}_{\mathrm{min}}$ is sufficient and necessary, i.e., $T=O(\mathrm{\ensuremath{\Delta}}{E}_{\mathrm{min}}^{\ensuremath{-}1})$. For some examples, these analytical investigations are confirmed by numerical simulations.