Comprehensive coverage

# Quantum computation using hybrid algorithms

The quantum systems are in the stage of "small and noisy computers." Until we create noise-free quantum systems, a lot of work is being done combining classical systems with an emphasis on algorithms that will allow quantum calculations to be performed in existing systems

By: Tamuz Danzig, PhD student in quantum algorithms

You must have heard a lot about quantum computers, which fifteen years ago sounded like science fiction. Today, superpowers, small countries and giant companies are investing huge sums in the race for the first quantum computer to perform practical calculations. Despite the enormous scope of research in the field, the volume of calculation and especially the noise in the systems that exist today do not allow to reach "quantum superiority", that is, an improvement of the quantum computer over the classical computer in solving certain problems. The hope is that in the coming decades quantum technology will improve, and a quantum computer will gain a distinct advantage. Until we create noise-free quantum systems, a lot of work is being done combining classical systems with an emphasis on algorithms that will allow quantum calculations to be performed in existing systems. Those involved in the field refer to the current period as "the era of small and noisy computers" (in short, NISQ-Era [1]). One of the most promising methods to perform quantum computation in the current era is quantum-classical hybrid circuits, which this post will focus on [2].

We will recall from previous posts that classical calculation is performed using logic gates (see link [6]); In analogy to this, a quantum calculation is carried out using quantum gates that are operated on the qubits, these are the bits of the quantum computer [7]. A quantum gate is an operation that changes the quantum wave function of the system such as rotation, phase addition, entanglement between different qubits, etc.

Today, the amount of qubits in quantum computers is limited. The leading computer in terms of the amount of qubits, contains only about 127 of them. These qubits are noisy, and the noise increases exponentially as the number of quantum gates applied to the qubits increases, which change the quantum state of the system. Think of the game "Broken Phone", where the first player starts with a certain message, and each player increases the probability of an error. Each player slightly changes the message conveyed, and in the end you get a completely different message. If five players play, it is likely that the final message will be close to the initial message - which corresponds to a quantum state that has undergone few operations and is characterized by low noise. Conversely, if there are five hundred participants, there is no doubt that there will be no connection between the messages. In this you have to be careful, since a few operations are not enough for the calculation of complex things.

There are many problems that a classic computer has trouble doing in a reasonable amount of time. Among the famous ones is the traveling agent problem (an optimization problem in which the fastest route between many cities must be found), logistics problems such as supply chains, economic forecasts of the market, problems in the field of chemistry such as the study of large molecules, the creation of new drugs, and more. So how do you do it with a quantum computer in the NISQ era? In order to overcome the noise and perform calculations while performing a minimal number of operations, two hybrid algorithms were published that combine a quantum computer and a classical computer and are pioneers in their field. The algorithm used to solve optimization problems is called Quantum Approximate Optimization Algorithm (QAOA) [3], and the algorithm used mainly to find the ground states of molecules is called Variational Quantum Eigensolver (VQE) [4]. We note that both articles were published in 2014, a reminder that the field is developing at a tremendous speed. So great, that these algorithms are already implemented in the most advanced quantum computers that exist today [5].

The structure of the hybrid algorithms is described in the attached figure. On the left side is shown the quantum circuit in which the qubits are initialized in the ground state (denoted as |0⟩). The set of quantum gates then act to change the quantum state (denoted as U(θ)) and a measurement is then made. θ is a set of continuously adjustable parameters. The solution to the problem will be obtained when the correct parameters are entered into the system, and finding these parameters is the classic part of the hybrid system. After each quantum calculation, a measurement is performed, and the measurement results (output) are entered into the objective function. The role of the objective function is to give a measure of the quality of the obtained result. The function of the optimizer (update) is to update the parameters before another run of the integrated circuit to find a minimum of the objective function. Finding the parameters is done using machine learning methods such as gradient descent (a method of changing parameters to find a minimum for the objective function)[8], and other methods. The integrated circuit repeats iteratively until a minimum is obtained.

The choice of the quantum gates U(θ) is a broad topic and deserves its own post. Correct selection of the type of gates, the order of their operation and how the measurement is interpreted affects the speed and quality of the calculation. Good gate design focuses on the problem that you want to solve and stems from physical theory. For example, the Hartree-Fock method is an approximation method for finding the ground state in many-body problems. By using the variation principle it is possible to obtain a solution of the wave function and the energy of the system, both of which are approximations to the exact quantities. In the VQE algorithm, this method is used to find the ground state of molecules.

The choice of QAOA's quantum circuit structure is based on Adiabatic Quantum Computation[9]. In the quantum-adiabatic calculation, the system is described by the time-dependent Hamiltonian passing from a known ground state to the ground state of the Hamiltonian that defines the problem, the transition to the new Hamiltonian constitutes the solution of the problem. If the calculation time is long enough the adiabatic approximation is valid. In practice, as the number of gates increases, the chances of measuring the desired ground state increase - this is on the assumption that the quantum calculation is free of noise. As you already understood, the noise cannot be neglected in quantum systems, but the QAOA algorithm offers a small set of gates and parameters that will allow reaching an approximate and good enough solution, although it will not meet the adiabatic criterion. QAOA uses the time-dependent Hamiltonian within the quantum circuit, but instead of the time-continuous evolution, there is the set of parameters. Therefore, QAOA is considered one of the promising hybrid algorithms [10]. Despite the use of the physical jargon, it is common to solve non-physical problems with this algorithm, such as problems in combinatorics, economics and more.

The relationship between classical and quantum computing is mutual. As we have seen, classical computation is a spice that only enhances quantum computation. Similarly, many of the fields in "classical" machine learning have been converted to hybrid algorithms [11]. Those interested are advised to read about the field called quantum neural networks (Quantum Neural Network [12] and it made a lot of noise. Since the publication of VQE and QAOA, the variety of hybrid algorithms has expanded greatly, and many have hopes that these algorithms will be the first to reach a "quantum advantage" over the computer the classic.

Sources

[1] Preskill, John. "Quantum computing in the NISQ era and beyond." Quantum 2 (2018): 79.
[2] Bharti, Kishor, et al. "Noisy intermediate-scale quantum algorithms." Reviews of Modern Physics 94.1 (2022): 015004.
[3] Farhi, E., Goldstone, J., & Gutmann, S. (2014). A quantum approximate optimization algorithm
[4] Peruzzo, A., McClean, J., Shadbolt, P. et al. A variational eigenvalue solver on a photonic quantum processor. Nat Commun 5, 4213 (2014).
[5] Harrigan, Matthew P., et al. "Quantum approximate optimization of non-planar graph problems on a planar superconducting processor." Nature Physics 17.3 (2021): 332-336.
[6]https://he.wikipedia.org/wiki/%D7%A9%D7%A2%D7%A8_%D7%9C%D7%95%D7%92%D7%99

[7] https://en.wikipedia.org/wiki/Quantum_logic_gate