Quantum processing units (QPUs) executing annealing algorithms have shown promise in optimization and simulation applications. Hybrid algorithms are a natural bridge to larger applications. We present a simple greedy method for solving larger-than-QPU lattice-structured Ising optimization problems. The method, implemented in the open source D-Wave Hybrid framework, uses a QPU coprocessor operating with generic parameters. Performance is evaluated for standard spin-glass problems on two lattice types with up to 11,616 spin variables, double the size that is directly programmable on any available QPU. The proposed method is shown to converge to low-energy solutions faster than an open source simulated annealing method that is either directly employed or substituted as a coprocessor in the hybrid method. Using newer Advantage QPUs in place of D-Wave 2000Q QPUs is shown to enhance convergence of the hybrid method to low energies and to achieve a lower final energy.
Quantum processing units (QPUs) executing annealing algorithms have shown promise in optimization and simulation applications. Hybrid algorithms are a natural bridge to larger applications. We present a simple greedy method for solving larger-than-QPU lattice-structured Ising optimization problems. The method, implemented in the open source D-Wave Hybrid framework, uses a QPU coprocessor operating with generic parameters. Performance is evaluated for standard spin-glass problems on two lattice types with up to 11,616 spin variables, double the size that is directly programmable on any available QPU. The proposed method is shown to converge to low-energy solutions faster than an open source simulated annealing method that is either directly employed or substituted as a coprocessor in the hybrid method. Using newer Advantage QPUs in place of D-Wave 2000Q QPUs is shown to enhance convergence of the hybrid method to low energies and to achieve a lower final energy.
Ising machines have the potential to realize fast and highly accurate solvers for combinatorial optimization problems. They are classified based on their internal algorithms. Examples include simulated-annealing-based Ising machines (non-quantum-type Ising machines) and quantum-annealing-based Ising machines (quantum annealers). Herein we propose a hybrid optimization method, which utilizes the advantages of both types. In this hybrid optimization method, the preprocessing step is performed by solving the non-quantum-annealing Ising machine multiple times. Then sub-Ising models with a reduced size by spin fixing are solved using a quantum annealer. The performance of the hybrid optimization method is evaluated via simulations using Simulated Annealing (SA) as a non-quantum-type Ising machine and D-Wave Advantage as a quantum annealer. Additionally, we investigate the parameter dependence of the proposed hybrid optimization method. The hybrid optimization method outperforms the preprocessing SA and the quantum annealing machine alone in fully connected random Ising models.
Quantum annealing has shown promise for finding solutions to difficult optimization problems, including protein folding. Recently, we used the D-Wave Advantage quantum annealer to explore the folding problem in a coarse-grained lattice model, the HP model, in which amino acids are classified into two broad groups: hydrophobic (H) and polar (P). Using a set of 22 HP sequences with up to 64 amino acids, we demonstrated the fast and consistent identification of the correct HP model ground states using the D-Wave hybrid quantum-classical solver. An equally relevant biophysical challenge, called the protein design problem, is the inverse of the above, where the task is to predict protein sequences that fold to a given structure. Here, we approach the design problem by a two-step procedure implemented and executed on a D-Wave machine. In the first step, we perform a pure sequence-space search by varying the type of amino acid at each sequence position, and seek sequences which minimize the HP-model energy of the target structure. After mapping this task onto an Ising spin-glass representation, we employ a hybrid quantum-classical solver to deliver energy-optimal sequences for structures with 30–64 amino acids, with a 100% success rate. In the second step, we filter the optimized sequences from the first step according to their ability to fold to the intended structure. In addition, we try solving the sequence optimization problem using only the quantum processing unit (QPU), which confines us to sizes ≤20 , due to exponentially decreasing success rates. To shed light on the pure QPU results, we investigate the effects of control errors caused by an imperfect implementation of the intended Hamiltonian on the QPU, by numerically analyzing the Schrödinger equation. We find that the simulated success rates in the presence of control noise semiquantitatively reproduce the modest pure QPU results for larger chains. Published by the American Physical Society 2024
To enhance the performance of quantum annealing machines, several methods have been proposed to reduce the number of spins by fixing spin values through preprocessing. We proposed a hybrid optimization method that combines a simulated annealing (SA)-based non-quantum-type Ising machine with a quantum annealing machine. However, its applicability remains unclear. Therefore, we evaluated the performance of the hybrid method on large-size Ising models and analyzed its characteristics. The results indicate that the hybrid method improves upon solutions obtained by the preprocessing SA, even if the Ising models cannot be embedded in the quantum annealing machine. We analyzed the method from three perspectives: preprocessing, spin-fixed sub-Ising model generation method, and the accuracy of the quantum annealing machine. From the viewpoint of the minimum energy gap, we found that solving the sub-Ising model with a quantum annealing machine results in a higher solution accuracy than solving the original Ising model. Additionally, we demonstrated that the number of fixed spins and the accuracy of the quantum annealing machine affect the dependency of the solution accuracy on the sub-Ising model size.
Recent work [Sachdeva et al.] presented an iterative hybrid quantum variational optimization algorithm designed by Q-CTRL and executed on IBM gate-based quantum processing units (QPUs), claiming a significant performance advantage against a D-Wave quantum annealer. Here we point out major methodological problems with this comparison. Using a simple unoptimized workflow for quantum annealing, we show success probabilities multiple orders of magnitude higher than those reported by [Sachdeva et al.]. These results, which can be reproduced using open-source code and free trial access to a D-Wave quantum annealer, contradict Q-CTRL's claims of superior performance. We also provide a direct comparison between quantum annealing and a recent demonstration of digitized quantum annealing on an IBM processor, showing that analog quantum annealing on a D-Wave QPU reaches far lower energies than digitized quantum annealing on an IBM QPU.
We show how to leverage quantum annealers to better select candidates in greedy algorithms. Unlike conventional greedy algorithms that employ problem-specific heuristics for making locally optimal choices at each stage, we use quantum annealers that sample from the ground state of Ising Hamiltonians at cryogenic temperatures and use retrieved samples to estimate the probability distribution of problem variables. More specifically, we look at each spin in the Ising model as a random variable and contract all problem variables whose corresponding uncertainties are negligible. Our empirical results on a D-Wave 2000Q quantum processor revealed that the proposed quantum-assisted greedy algorithm (QAGA) can find remarkably better solutions, compared to the state-of-the-art techniques in the realm of quantum annealing.
A combinatorial optimization problem is the problem of minimizing the energy function among many combinations of variables, which is often difficult to solve with conventional classical computers. Recently, Ising machines, including quantum annealers, have gained attention as a promising architecture for efficiently solving combinatorial optimization problems. Among various methods for solving such problems using Ising machines, one prominent approach is the three-stage annealing method. The approach effectively solves a combinatorial optimization problem, utilizing an initial solution, but it performs the annealing process only once. Repeating the annealing process several times may enhance the solution more efficiently. In this paper, we propose a novel hybrid iterative annealing method that consists of an initial process using a classical computer, an annealing process using a quantum annealer, and a correction process/selection process using a classical computer. The proposed method repeats the annealing process and the correction process/selection process until the solution is sufficiently converged. In the experimental evaluations through the two types of typical combinatorial optimization problems, the proposed method shows improvements by up to 50.5% compared to the three-stage annealing method.