Escaping Local Minima with Quantum Coherent Cooling

Optimization problems are prevalent in many areas, where the global minima of cost functions represent the optimal solutions. Classical algorithms are usually able to quickly identify local minima but get trapped due to the complexity of the cost function. As a result, they are inefficient at finding the global minima. This bottleneck is widely recognized in various fields, including computational physics and machine learning.

We proposed a hybrid quantum-classical algorithm to address this bottleneck. The entire algorithm functions as a heterogeneous cooling process to minimize the value of the cost function that encodes the given problem. The classical optimization is employed to find local minima, while the quantum cooling helps to escape the local minima by tunneling through energy barriers [1]. By alternating between classical optimization and quantum cooling, one can ultimately reach the global minimum. (See Fig.1 for a visualization of this process.)

In the classical part of the algorithm, well-established classical techniques, such as Monte Carlo or gradient descent, are used to identify a local minimum of the cost function with minor computational resources. In the quantum part of the algorithm, the quantum icebox algorithm (QIA) performs the quantum cooling, which has been shown to achieve quantum advantage in the unsorted search problem [2]. The framework of QIA is as follows. The cost function is encoded in a Hamiltonian system [3, 4], which is initialized in the state corresponding to the local minimum. A quantum bath has a trivial and easy-to-prepare ground states that is initialized within it. The system and the bath are coupled and maintain coherence, which facilitates coordinative quantum tunneling over high-energy barriers. The system will evolve to escape the local minimum and transition to a lower value. These two parts are complementary in order to prevent the algorithm from getting stuck.

Other hybrid quantum-classical algorithms [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] also combine classical and quantum methods as a compromise in the noisy intermediate-scale quantum (NISQ) era [16, 17], such as the variational quantum algorithm (VQA). In VQA, classical algorithms optimize the quantum gate parameters to reduce the number of quantum operations during the coherence time [18]. However, this approach faces challenges such as the barren plateau [9, 19] and the need to avoid local minima. In our scheme, the classical algorithm only needs to optimize the initial state and find local minima, which is less problematic. Furthermore, control channels are not required during QIA, which helps to minimize noise from external sources.

We specifically target a category of problems where the cost function involves $n$ Boolean variables [20, 21], such as the 3-SAT problem and independent sets [22, 23]. In physical terms, these cost functions represent Hamiltonians of (pseudo-)spins [24, 25]. The configuration space for these problems consists of binary strings of zeros and ones (or $\pm 1$ for spins), with each string representing a state $\psi_{\rm s}$. Local minima for this class of problems are defined as states where neighboring states within one Hamming distance have higher cost function values (or energies). The Hamming distance is calculated by counting the number of different bits between two binary strings [26]. To solve these problems, our hybrid quantum-classical algorithm operates as follows (see also Fig. 1) :

1. 1.

   Use arbitrary configuration $\psi_{\rm s0}$ as the initial condition to find out one of the local minima $\psi_{\rm s1}$ with classical algorithms.

2. 2.

   Prepare the quantum state $\psi_{\rm s1}$ in the computational basis, denoted as $|\psi_{\rm s1}\rangle$, and execute the QIA. Following quantum evolution, we obtain an entangled state $|\Psi\rangle$. We then proceed to measure the problem system in the computational basis, resulting in the random selection of a configuration denoted as $\psi_{\rm s2}$.

3. 3.

   Use the configuration $\psi_{\rm s2}$ as the initial condition to identify a different local minimum, represented as $\psi_{\rm s3}$, using classical algorithms.

4. 4.

   If $\langle\psi_{\rm s3}|H_{\rm s}|\psi_{\rm s3}\rangle\leqslant\langle\psi_{\rm s1}|H_{\rm s}|\psi_{\rm s1}\rangle$, then we update the initial configuration from $\psi_{\rm s1}$ to $\psi_{\rm s3}$. In any case, we repeat the process starting from step 2.

5. 5.

   Stop the iteration if $\langle\psi_{\rm s1}|H_{\rm s}|\psi_{\rm s1}\rangle$ is sufficiently small and no further update to $\psi_{\rm s1}$ is available.

This hybrid quantum-classical algorithm is robust to noise and errors. The long Hamming distance tunneling is divided into several shorter Hamming distance tunnelings among local minima, making it suitable for qubits with limited coherence time. Furthermore, it can identify errors in step 4 and correct them through multiple rounds of optimization. These properties make it feasible to apply them practically and implement them experimentally.

With the assistance of classical algorithms, it can efficiently reduce local energy. This hybrid algorithm achieves quantum acceleration in step 2 by utilizing the quantum bath for efficient global cooling. We can also implement continuous quantum error correction [27, 28] or insert discrete quantum error correction [29, 30] in step 2 to suppress errors. We will demonstrate that using the quantum bath leads to higher cooling efficiency.

Since classical algorithms are well-established, let us now focus on the quantum component. We will compare the cooling efficiency of the quantum coherence bath with that of the classical bath to demonstrate the quantum advantage, particularly in the context of spin glasses. Spin glasses are typically challenging to cool down because they often have numerous local minima. Our numerical calculations demonstrate that the quantum coherence bath has a faster cooling speed and a higher success rate in comparison to the classical bath (see Fig. 2).

To achieve cooling, ancilla interacting qubits are commonly used as the quantum bath [2, 31, 32, 33]. However, this approach often requires at least twice the number of qubits [2, 31], and maintaining entanglement among a large number of qubits is difficult in the NISQ era [16, 17]. As an alternative, we use a coherent cavity as the quantum bath, which is more feasible than using hundreds of qubits. The cavity is typically used in experiments to propagate interactions [34, 35] or measure states [36], and can take the form of a laser cavity [37, 38], inductor-capacitor ($LC$) oscillator [36], or nanomechanical resonator [39].

Our discussion will focus on the circuit quantum electrodynamics (cQED) systems [36], although our algorithm can also be applied to other systems. The basic setup is depicted in Fig. 3, where the cavity in the superconductor circuit can be modeled as an $LC$ oscillator. The angular frequency of the oscillator is given by $\omega_{\rm b}=1/\sqrt{LC}$, where $L$ is the inductance and $C$ is the capacitance. The quantum cavity acts as the bath, and its Hamiltonian is

where $\hat{b}^{\dagger}$ is the creator of the harmonic mode of the bath.

The qubits in Josephson junctions store the problem data, and their interactions are established through circuit connections. The Hamiltonian encoding the problem of $n_{s}$ qubits is given by [40, 41, 42, 43, 44]

which describes a spin glass that is difficult to cool down. The on-site energy is denoted by $J_{m}^{(1)}$, while $J_{m,m^{\prime}}^{(2)}$ represents the interaction between two qubits. This interaction can be spatially non-local, making the optimization problem more challenging. To facilitate quantum transitions, $J_{m}^{(1)}$ and $J_{m,m^{\prime}}^{(2)}$ are multiples of $\omega_{\rm b}/2$. The occurrence of integer multiple gaps is common when encoding discrete mathematical problems, including non-deterministic polynomial (NP) problems [3]. It also helps to suppress overflow errors caused by unencoded energy levels.

The interaction between the qubits and the cavity in the lumped-element circuit without spatial dependence is given by [45, 46, 36, 47, 48]

where $\lambda$ is the interaction strength proportional to the capacitance. The interconnected capacitor introduces additional on-site capacitance, which can be absorbed in the parameters of $H_{\rm s}$ and $H_{\rm b}$. Our scheme involves that $\langle H_{\lambda}\rangle$ is comparable to $\langle H_{\rm s}\rangle$, resulting in acceleration and novel phenomena beyond perturbation approach, including rotating wave approximation (RWA) [49, 50, 51].

The cooling process is governed by the fixed total Hamiltonian $H=H_{\rm s}+H_{\rm b}+H_{\lambda}$ with little additional control. The circuit diagram is available in Appendix A. The total parity conservation $e^{i\pi\left(b^{\dagger}b+0.5\sum_{m=0}^{n_{\rm s}-1}\hat{\sigma}_{m}^{z}\right)}$ can slightly simplify the numerical simulation.

The initial state of the bath is its ground state [52, 53], and the initial state of the problem system is set to be one of the high energy local minima of $H_{\rm s}$ in the $\sigma_{z}$-basis. Subsequently, the interaction $H_{\lambda}$ is turned on, and the state evolves according to the Schrödinger equation. The energy of the system is absorbed by the bath through quantum tunneling, leading to the transfer of the system’s state to other local minima with lower energy.

For comparison, we treat the cavity as a classical system by defining the generalized momentum $\hat{Q}_{\rm b}=i\sqrt{\hbar\omega_{\rm b}C/2}\left(\hat{b}^{\dagger}-\hat{b}\right)$ and the generalized position $\hat{\Phi}_{\rm b}=\sqrt{\hbar/2\omega_{\rm b}C}\left(\hat{b}^{\dagger}+\hat{b}\right)$ [36]. If the decoherence is strong, we can treat them as classical variables $Q$ and $\Phi$ [54, 55, 56, 57]. The Hamiltonians for the bath in Eq. (1) and the interaction in Eq. (3) can be rewritten, respectively, as

and

With the canonical equations $\partial Q_{\rm b}/\partial t=\partial\langle H\rangle/\partial\Phi_{\rm b}$ and $\partial\Phi_{\rm b}/\partial t=\partial\langle H\rangle/\partial Q_{\rm b}$ [58], we derive the total dynamical equations as

Notice that $Q_{\rm b}=\Phi_{\rm b}=0$ is the fixed point if all the qubits are aligned in the $\sigma_{z}$ direction. The classical bath can be treated as a classical probability ensemble. For a fair comparison, the initial state of $Q_{\rm b}$ and $\Phi_{\rm b}$ is set to have the same probability distribution as the quantum ground state, which is $\rho_{\rm c}=e^{-\left(\phi_{\rm b}^{2}+q_{\rm b}^{2}\right)}/\pi$ with $q_{\rm b}=Q_{\rm b}/\sqrt{2\hbar\omega_{\rm b}C_{\rm b}}$ and $\phi_{\rm b}=\Phi_{\rm b}\sqrt{\omega_{\rm b}C_{\rm b}/(2\hbar)}$ [55, 56]. The expectation value is considered as the average of all the independent evolution paths, i.e., $A=\iint a*\rho_{\rm c}{\rm d}q_{\rm b}{\rm d}\phi_{\rm b}$, where $a$ is the observable for one initial condition and $A$ is the expectation value.

No entanglement exists between the classical bath and the system, and the initial state of the bath $\rho_{\rm c}$ can be regarded as a mixed state. Throughout the evolution, the formation of entanglement is prohibited, and the total system remains in the product state $\left|\psi_{\rm s}\right\rangle\otimes\left|Q,\Phi\right\rangle$. Moreover, some high energy paths of the classical bath are also not allowed, even though they could help the problem system surmount barriers. The numerical results depicted in Fig. 2 demonstrate that the classical bath performs worse than its quantum counterpart.

We simulate a problem system with two local minima using Eq. (2). The initial state of the problem system is at the higher local minimum, while the bath is in its ground state. The Hamming distance between the local minima is $\lceil n_{\rm s}/2\rceil$, which increases the problem complexity. Cooling with the quantum bath does not always outperform the classical bath, but quantum resonance can strongly accelerate cooling when $\lambda$ is tuned suitably [59]. Fig. 2 shows the probability $P_{g}$ of the ground state changing over time. Cooling with the classical bath exhibits a modest increase over time, while the curve for the quantum bath shows a sharp increase due to quantum coherent enhancement. It indicates that QIA has an advantage in escaping local minima.

This quantum acceleration is related to the entanglement and correlation numerically calculated in Appendix B. In the continuous variable system, we also find a similar quantum acceleration (see Appendix C).

The eigenstates of the spin glass problem system $H_{\rm s}$ are represented by a hypercube whose vertices correspond to the eigenstates in the $\sigma_{z}$ basis as shown in Fig. 4(a). When the interaction is turned on, the wave function diffuses in the hypercube. As depicted in Fig. 4(b), the diffusion during quantum cooling is complex with peaks at the diffusion fronts, enabling faster reaching of the answers similar to diffusion in quantum walks (QWs) [59, 60, 61, 62]. On the other hand, the diffusion during classical cooling is weaker, and the probability distribution decreases monotonically with Hamming distance like the classical random walk (RW). These observations are depicted in Fig. 4(c).

Diffusion also occurs in the bath, leading to its state being driven away from its energy minimum. Better cooling performance is achieved when the bath is excited to higher energy states with greater probability and speed. Fig. 4(d) shows that the diffusion of the quantum bath is stronger with two peaks at the diffusion fronts, similar to the QW. On the other hand, the diffusion of the classical bath is weaker with monotonically decreasing fronts, as shown in Fig. 4(d). The classical bath diffuses very little without quantum coherence.

The diffusion in quantum cooling is similar to QW, as shown by the numerical results. To further illustrate this similarity, we consider a one qubit system with $H_{\rm s}=\hbar\omega_{\rm s}\hat{\sigma}_{z}/2$ and $\omega_{\rm s}=\omega_{\rm b}=\omega$. It is the Jaynes–Cummings model of non-rotating wave form [36]. There are analytical results in the regime that one of the parameters $\lambda$, $\hbar\omega_{\rm s}$ or $\hbar\omega_{\rm b}$ is much smaller than the others [63]. The non-perturbative resonant regime $\lambda\sim\hbar\omega_{\rm s}=\hbar\omega_{\rm b}$ has rare analytical results. When the interaction is strong enough, an effective QW is observed in the dynamics. For a small time interval $\Delta t$ [64], its unitary evolution is (see Appendix D for derivation)

where the on-site energy is $H_{0}=H_{\rm s}+H_{\rm b}$. For a typical Hadamard walk in a one-dimensional space with a coin qubit, its unitary operation of each iteration is $U_{\rm QW}=U_{p}U_{\rm H}$, where $U_{\rm H}$ is the Hadamard gate to the coin qubit and $U_{p}=e^{-\hat{\sigma}^{\prime}_{z}\Delta x\partial/\partial x}$ is the conditional walking operator controlled by the coin qubit. Therefore, in comparison, our system has an additional punishment term $e^{-i\frac{H_{0}\Delta t}{\hbar}}$ that may disturb the phase [59]. However, this punishment term disappears when the eigenstates of $H_{0}$ involved in the evolution are degenerate. This is exactly the case that we have studied where $H_{\rm s}$ and $H_{\rm b}$ are in resonance with matching energy gaps. It is well known that the average walking distance of RW is proportional to the square root of time $\Delta x\sim\sqrt{t}$ while that of QW is proportional to the time $\Delta x\sim t$ [61, 65]. The constructive interference makes QW diffuse faster than RW. It is also known that the entanglement between the coin qubit and the walking space is strong.

For the QW with multiple coin qubits, the situation is more complex (see Appendix D). The analytical results always require non-local operation, such as the Grover’s coin [66, 67]. However, in our physical model, all the interactions are two-local. The numerical results in Fig. 4 suggests that QW still makes contribution in this complex case.

The quantum advancement of escaping local minima can be quantitatively approach. The numerical simulation of time complexity can be seen in Fig. 5, which the size of the Hilbert space is $N_{\rm s}=2^{n_{\rm s}}$. The time required for QIA to transition between local minima is approximately $O\left(N_{\rm s}^{0.16}\right)$ when solving specific local interaction problems (further details in Appendix E). There are $O\left(n_{\rm s}^{O(1)}\right)$ energy levels for the degenerate Hamiltonian which is proportional to the number of iterations and calls of the classical algorithm. So the total time complexity is about $O\left(N_{\rm s}^{0.16}n_{\rm s}^{O(1)}\right)$. Besides, there are connections to each qubit, so the total space complexity is $O\left(n_{\rm s}^{2}\right)$.

The concept of using a cavity for cooling has similarities to the quantum-circuit refrigerator (QCR) [68, 69, 70], which utilizes an open cavity to cool a system. However, the QCR exhibits strong dissipation in the cavity, and some schemes utilize a dissipative qubit as the bath [71, 72]. Although an open bath can introduce steady energy loss, the lack of quantum coherence may hinder the cooling process. Recent research suggests that the non-Markovian baths could improve the performance of a quantum refrigerator [73, 74]. In Appendix F, we show that the dissipation in the quantum bath will slow down the cooling speed.

In conclusion, we proposed a hybrid quantum-classical algorithm of coherent cooling to address the issue of local minima. It encodes the cost function in a superconductor circuit cooled by a quantum cavity, which outperforms a classical cavity due to the coordinative tunneling effect. Our results suggest that the faster diffusion of QW over classical RW is the underlying physics of this quantum speed-up. While we have focused on discrete variable problems, our scheme can be extended to continuous variable problems. This hybrid algorithm is expected to streamline the control and reduce noise in quantum computing experiments.