Engineering & Technology
May 30, 2022

Discovering the optimal schedule for adiabatic quantum computation

Quantum computers outperform classic machines when it comes to solving complex calculations. Commercial quantum computers are now available, and these perform quantum computation via a process called ‘adiabatic evolution’. The quantum adiabatic theorem states that if a quantum mechanical system is subjected to external conditions that are gradually changing, it can adapt its configuration. Dr Stefan Isermann from T-Systems International GmbH, Germany, examines the adiabatic theorem and ascertains the conditions for an optimal schedule, reducing the computation time.

Since their inception in the 1980s, when a quantum computer was first proposed by physicist and Nobel laureate Roger Feynman, quantum computers have used complex quantum mechanics to perform calculations that classic computers are unable to solve. Google announced their quantum supremacy in 2019, when the company developed the first quantum machine capable of outperforming a traditional computer, performing a calculation that would take a classic supercomputer 10,000 years (while IBM claims they can solve this task in 2.5 days). While Google’s circuit-based quantum gate computer can map suitable complex quantum algorithms, commercial quantum computers are intended for solving optimisation problems and performing quantum computations via adiabatic evolution.

The quantum adiabatic theorem suggests that if a quantum mechanical system is subjected to external conditions that are gradually changing, it can adapt its configurations, which means that the probability distribution of this configuration is changed during the process. On the other hand, if the external conditions are rapidly changing, the configuration has insufficient time to adapt, so the initial probability distribution of the configuration will remain almost unchanged, leading to a completely erratic result.

ZinetroN/Shutterstock.com

The Quantum Annealer from D-Wave is the only commercially available quantum computer to date. First launched in 2011, the D-Wave machine is a version of adiabatic quantum computing designed to solve optimisation problems. By way of a Python-based software development kit and a web interface, students can interact with a D-Wave quantum computer without the need for a thorough knowledge of quantum mechanics.

Dr Stefan Isermann from T-Systems International GmbH examines the adiabatic theorem in detail and derives the conditions for an optimal schedule that reduces the computational time. He determines the computation time required for an adiabatic quantum search algorithm with an optimal schedule and provides the supporting numerical verification.

The system’s time evolution is controlled by the Schrödinger equation, the quantum equivalent of Newton’s second law.

Adiabatic quantum computation
Quantum annealing is a quantum computing technique that is employed to find the optimal solution to problems that have a large range of possible solutions. Quantum annealing takes advantage of properties that are specific to quantum physics, such as quantum tunnelling (where particles penetrate a potential energy barrier), entanglement (when two particles become entangled and remain connected even when they are far apart), and superposition (two or more quantum states can be added together, ie, superposed, to make another valid quantum state). A quantum annealer solves optimisation problems using adiabatic quantum computing. In theory, it can check 2n possible configurations of n qubits (a basic unit of quantum information), even when n is a very large number – a feat that cannot be performed by a classical computer. Adiabatic quantum computation involves translating the problem into a Hamiltonian operator.

Hamiltonian operators

In quantum mechanics, a system’s ‘Hamiltonian’ corresponds to the total energy of the system. The system’s energy spectrum is the set of possible outcomes, in the form of energy eigenvalues, which can be obtained from a measurement of the system’s total energy.

To find a problem’s optimal solution, the system is initially brought into an easy-to-prepare ground state, which is a superposition of all 2n possible configurations and in which all configurations are uniformly distributed. The ground state of the final Hamiltonian describes the specific problem’s solution. The Hamiltonian’s ground state is the state of lowest energy, known as the system’s zero-point energy. This initial ‘simple’ Hamiltonian is adiabatically (that is, slowly and steadily) evolved into the required final complex Hamiltonian. Employing the adiabatic theorem means that the system remains in the ground state throughout the evolution process. When the evolution is complete, the end state of the system describes the solution to the problem.

Adiabatic evolution begins with the system in the ground state of the initial Hamiltonian and finishes with the system in the ground state of the final Hamiltonian. It is hoped that after traversing through an adiabatic evolution path, or schedule, starting with the initial Hamiltonian, the system terminates in the ground state of the problem Hamiltonian. This unknown ground state has the smallest energy eigenvalue and corresponds to the configuration of the problem’s optimal solution. It is reached by moving adiabatically from the initial Hamiltonian with its known ground state. If the transition happens slowly enough, the system will remain in the ground state, resulting in the problem Hamiltonian’s optimal configuration, ie, moving from an initially uniform probability of all configurations to a probability distribution that is peaked around the unknown configuration of the solution.

Isermann describes how the system’s time evolution is controlled by the Schrödinger equation, a linear partial differential equation that is the quantum equivalent of Newton’s second law in classical mechanics, which regulates the time evolution of the quantum-mechanical system’s wave function. The wave function is a mathematical description of the quantum state of an isolated quantum system in the form of a time-dependent complex probability amplitude function. The transition amplitude is a complex number derived from the interacting part of the Hamiltonian that can induce transitions from one energetic state to another. He demonstrates that the sum of all local transition amplitudes is constant, regardless of the selected schedule. The square of the local transition amplitude times a small time interval gives the probability for a transition from the ground state to the first exited state. Should a smaller transition amplitude be present at a particular time, it must then be balanced with the presence of a larger amplitude at another time, which leads to a higher probability of transition. This led to the condition that the amplitudes should be constant throughout the time evolution. Isermann also determined that while the conditions for an optimal schedule are satisfied, the computation time is proportional to the inverse of the minimum energy gap, where the minimum energy gap is the difference between the ground state and the first excited state (when the system’s energy state is increased) during the Hamiltonian’s time evolution.

The advantage of the quantum annealing process over the classical annealing algorithm is quantum mechanical tunnelling through high-energy barriers.

Adiabatic quantum search
Isermann confirms the results with numerical simulations of a search algorithm together with those from a toy problem (a small problem used for education or development purposes). He applied the optimal schedule conditions to a search for one of a number, denoted as N, items in an unsorted database. The classical algorithm has complexity of order N, so linear time complexity which means the speed the algorithm runs for is proportional to the number of inputs, N. More inputs equal greater time. Grover’s algorithm, a quantum search algorithm for unstructured searches where the system evolution is based on quantum gates, has complexity of order √N.

Other researchers have suggested that an optimal schedule could be obtained for an adiabatic quantum search by applying the quantum mechanical adiabatic theorem locally in terms of time. Local means that the change rate is not constant, so at any given time the adiabatic evolution path, or schedule, depends on the energy gap at that particular instance. However, Isermann questions the validity of this proposal, as the quantum mechanical adiabatic theorem conveys only a global statement (meaning the entire computation time, where local refers to portions or instances of this time), in the form of an estimate of the probability of the transition from the ground state to the first excited state over the entire computation time. Moreover, his example calculations demonstrate that the precise application of this approach does not achieve an optimal schedule.

Examining adiabatic quantum computation to reduce computation time
Artistdesign29/Shutterstock.com

Calculations confirmed
Isermann calculated the associated transition amplitudes for all the schedules in a quantum search, revealing that they summed to π/2. He also calculated the transition probability of the searched state for the various schedules. Isermann verified his results by solving the Schrödinger equation numerically with the same initial condition. The evolution corresponding to the optimal schedule confirms that only an oscillation with small amplitude and a frequency with an order of asinh(√N)/√N reached 99% after a time T = 6√N and confirms analytical results where the transition probability, ε2, is calculated exactly and the computation time is T = 2√N asech ε, where N is the number of items to be searched. The minimal energy gap is ω1,0 = 1/√N.

Quantum leap forward
Isermann found that the schedule is governed by both the magnitude and location of the minimum energy gap, or the difference between the ground state and the first excited state. Discovering an optimal schedule ensures that while optimal schedule conditions are satisfied, the computation time is proportional to the inverse of the minimum energy gap. This represents a quadratic speedup of computation time, since the adiabatic theorem estimates a computing time that is proportional to the inverse square of the minimum energy gap. This speedup applies not only to a system of qubits but to every quantum mechanical system, which Isermann shows using the example of an anharmonic oscillator. Isermann remarks that ‘this is an important result because the advantage of the quantum annealing process over the classical annealing algorithm is quantum mechanical tunnelling through high energy barriers, but this is only given as long as the system is in a quantum state.’ Overall, while an optimal schedule cannot be specified exactly in most cases, given the structural knowledge of the Hamiltonian problem, it can be approximated.

Personal Response

What triggered your interest in adiabatic quantum computing and inspired this research?

Quantum computing will become increasingly important in information technology over the next few years. And since the Quantum Annealer is the first commercially available quantum computer, it is important to understand its possibilities as well as its limitations.

This feature article was created with the approval of the research team featured. This is a collaborative production, supported by those featured to aid free of charge, global distribution.

Want to read more articles like this?

Sign up to our mailing list and read about the topics that matter to you the most.
Sign Up!

Leave a Reply

Your email address will not be published. Required fields are marked *