We introduce two methods for speeding up adiabatic quantum computations by increasing the energy between the ground and first excited states. Our methods are even more general. They can be used to shift a Hamiltonian's density of states away from the ground state, so that fewer states occupy the low-lying energies near the minimum, hence allowing for faster adiabatic passages to find the ground state with less risk of getting caught in an undesired low-lying excited state during the passage. Even more generally, our methods can be used to transform a discrete optimization problem into a new one whose unique minimum still encodes the desired answer, but with the objective function's values forming a different landscape. Aspects of the landscape such as the objective function's range, or the values of certain coefficients, or how many different inputs lead to a given output value, can be decreased *or* increased. One of the many examples for which these methods are useful is in finding the ground state of a Hamiltonian using NMR: If it is difficult to find a molecule such that the distances between the spins match the interactions in the Hamiltonian, the interactions in the Hamiltonian can be changed without at all changing the ground state. We apply our methods to an AQC algorithm for integer factorization, and the first method reduces the maximum runtime in our example by up to 754%, and the second method reduces the maximum runtime of another example by up to 250%. These two methods may also be combined.
We introduce two methods for speeding up adiabatic quantum computations by increasing the energy between the ground and first excited states. Our methods are even more general. They can be used to shift a Hamiltonian's density of states away from the ground state, so that fewer states occupy the low-lying energies near the minimum, hence allowing for faster adiabatic passages to find the ground state with less risk of getting caught in an undesired low-lying excited state during the passage. Even more generally, our methods can be used to transform a discrete optimization problem into a new one whose unique minimum still encodes the desired answer, but with the objective function's values forming a different landscape. Aspects of the landscape such as the objective function's range, or the values of certain coefficients, or how many different inputs lead to a given output value, can be decreased or increased. One of the many examples for which these methods are useful is in finding the ground state of a Hamiltonian using NMR: If it is difficult to find a molecule such that the distances between the spins match the interactions in the Hamiltonian, the interactions in the Hamiltonian can be changed without at all changing the ground state. We apply our methods to an AQC algorithm for integer factorization, and the first method reduces the maximum runtime in our example by up to 754%, and the second method reduces the maximum runtime of another example by up to 250%. These two methods may also be combined.
Adiabatic quantum computing has recently been used to factor 56153 [Dattani & Bryans, arXiv:1411.6758] at room temperature, which is orders of magnitude larger than any number attempted yet using Shor's algorithm (circuit-based quantum computation). However, this number is still vastly smaller than RSA-768 which is the largest number factored thus far on a classical computer. We address a major issue arising in the scaling of adiabatic quantum factorization to much larger numbers. Namely, the existence of many 4-qubit, 3-qubit and 2-qubit interactions in the Hamiltonians. We showcase our method on various examples, one of which shows that we can remove 94% of the 4-qubit interactions and 83% of the 3-qubit interactions in the factorization of a 25-digit number with almost no effort, without adding any auxiliary qubits. Our method is not limited to quantum factoring. Its importance extends to the wider field of discrete optimization. Any CSP (constraint-satisfiability problem), psuedo-boolean optimization problem, or QUBO (quadratic unconstrained Boolean optimization) problem can in principle benefit from the "deduction-reduction" method which we introduce in this paper. We provide an open source code which takes in a Hamiltonian (or a discrete discrete function which needs to be optimized), and returns a Hamiltonian that has the same unique ground state(s), no new auxiliary variables, and as few multi-qubit (multi-variable) terms as possible with deduc-reduc.
Quantum computing promises to efficiently and accurately solve many important problems in quantum chemistry which elude classical solvers, such as the electronic structure problem of highly correlated materials. Two leading methods in solving the ground state problem are the Variational Quantum Eigensolver (VQE) and Adiabatic Quantum Computing (AQC) algorithms. VQE often struggles with convergence due to the energy landscape being highly non-convex and the existence of barren plateaux, and implementing AQC is beyond the capabilities of current quantum devices as it requires deep circuits. Adiabatically-inspired algorithms aim to fill this gap. In this paper, we first present a unifying framework for these algorithms and then benchmark the following methods: the Adiabatically Assisted VQE (AAVQE) (Garcia-Saez and Latorre (2018)), the Variational Adiabatic Quantum Computing (VAQC) (Harwood et al (2022)), and the Adiabatic Quantum Computing with Parametrized Quantum Circuits (AQC-PQC) (Kolotouros et al (2025)) algorithms. Second, we introduce a novel hybrid approach termed G-AQC-PQC, which generalizes the AQC-PQC method, and combines adiabatic-inspired initialization with the low-memory BFGS optimizer, reducing the quantum computational cost of the method. Third, we compare the accuracy of the methods for chemistry applications using the beryllium hydride molecule (BeH2). We compare the approaches across a number of different choices (ansätze types, depth, discretization steps, initial Hamiltonian, adiabatic schedules and method used). Our results show that the G-AQC-PQC outperforms conventional VQE. We further discuss limitations such as the zero-gradient problem and identify regimes where adiabatically-inspired methods offer a tangible advantage for near-term quantum chemistry applications.
Quantum computing seeks to use the powers of quantum mechanics to accomplish tasks that classical computers cannot easily accomplish. Adiabatic quantum computing is one flavor of quantum computing that slowly changes a system with time in such a way that the state remains close to the ground state for the entire evolution. An easy way to implement and study adiabatic computing is using stoquastic Hamiltonians with no-sign problem. These Hamiltonians can be readily simulated on classical computers using quantum Monte Carlo schemes; though, it is unknown whether such simulation captures the speed and power of the quantum computation.In this work, I study stoquastic Hamiltonians, focusing on quantum mechanical tunneling through classically inaccessible regions and barriers. I study multi-qubit tunneling problems to determine what properties of the barrier make this problem quantum mechanically or classically hard or inefficient. I compare quantum adiabatic computing with a path-integral Quantum Monte Carlo algorithm, which is a classical algorithm designed to simulate the quantum mechanical dynamics of the adiabatic evolution. Limited numerical data shows strong correlation between adiabatic and Monte Carlo runtimes, but due to computational limits, only small system sizes could be sampled.Additionally, I study the properties of the quantum adiabatic algorithm in both the asymptotic limit of a large number of qubits and long runtimes and more realistic finite system sizes and non-adiabatic conditions. I develop a modification of the existing Villain transformation that allows it to find the asymptotic running time of the quantum evolution for different barrier sizes. Furthermore, I compare this to finite system sizes and discover the extremely large numbers of qubits are needed for these asymptotics to be useful.When the quantum dynamics are run faster than adiabatically, new behavior arises that could potentially lead to enhancements in the quantum runtimes. I explore these enhancements, discovering when they do and do not occur. I also develop a broad framework for determining the nature of the near-adiabatic behavior of any quantum evolution, using only information about the energy gap between the ground state and the first excited state.
QUBO problems are NP-hard and have wide applications in optimization, including finance, logistics, machine learning, and combinatorial problems. However, classical algorithms employed for solving them can often get stuck in local minima. This paper presents an Adiabatic Quantum Computing (AQC) approach towards finding an optimal solution for QUBO problems. The QUBO problem has been first encoded into Hamiltonians. The adiabatic theorem has been used to achieve success of an AQC solution with a rate which is found to be dependent on relative gap between the ground state and first exited state of the Hamiltonian.
Quantum adiabatic optimization is a quantum algorithm for solving classical optimization problems (E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum computation by adiabatic evolution, 2000. arXiv:quant-ph/0001106). The solution to an optimization prob-lem is encoded in the ground state of a "problem Hamiltonian " Hp which acts on the Hilbert space of n spin 1/2 particles and is diagonal in the Pauli z basis. To produce this ground state, one first initializes the quantum system in the ground state of a different Hamiltonian and then adiabatically changes the Hamiltonian into Hp. Farhi et al suggest the interpolating Hamiltonian i where the parameter s is slowly changed as a function of time between 0 and 1. The running time of this algorithm is related to the minimum spectral gap of H(s) for s E (0, 11. We study such transverse field spin Hamiltonians using both analytic and numerical techniques. Our approach is example-based, that is, we study some specific choices for the problem Hamiltonian Hp which illustrate the breadth of phenomena which can occur. We
Multivariable optimization problems belong to an interdisciplinary field of research connecting diverse fields like computer science, information theory and statistical physics. It involves finding an optimal solution out of the many available states or configurations, possibly satisfying a set of constraints. For physicists, the problem can be visualized as finding the global minima of the energy landscape of a given complex Hamiltonian, which is quite difficult to obtain by the obvious method of examining the energy of each state. This is due to the huge number of available states which grows exponentially with the system size (for N Ising spins, the configuration space grows as 2 N ). The search for such a global minimum becomes all the more complex when the landscape consists of several local minima separated by macroscopic barriers ( O ( N )) arising from frustrating constraints in the systems. To solve such an optimization problem in a stochastic case, the concept of simulated annealing (SA) was put forward by Kirkpatrick et al . [437]. In this method, a tunable noise is artificially induced (thermal-like fluctuations equivalent to that of a metallurgical annealing) which helps the system to escape from the local minima by hopping above the energy barriers, and staying longer in minimum energy valley(s) as the noise variable is slowly reduced to zero starting from a high value. At the same time, it is also known that in complex systems, due to many closely spaced low lying states, the annealing needs to be performed infinitely slowly to reach the true ground state; this is indeed a major drawback. We shall elaborate on this point later when we discuss the effect of system size on the minimum gap between the ground state and the first excited state of the quantum many body system under consideration. The numerical methods used in such studies are variants of Monte Carlo methods.