Kohji Nishimura, CTO of Jij, Yoshitaka Haribara, Senior Startup ML/Quantum Solutions Architect, and Perminder Singh, Senior Partner Solutions Architect, Quantum, at AWS, have demonstrated how Simulated Quantum Annealing (SQA) can be accelerated by AWS Graviton processors. SQA is a heuristic algorithm designed to approximate solutions for nonlinear optimization problems.
The team also showcased JijZept, a cloud service for numerical optimization using quantum technology. The Graviton3 processor offers up to 2x faster computation than the previous generation, Graviton2, allowing for faster computation for SQA-based optimization problems.
Understanding Quantum Annealing and Simulated Quantum Annealing
Numerical optimization, the process of minimizing or maximizing a given cost function subject to constraints, is a critical aspect of many industries, including manufacturing, logistics, and telecommunications. Combinatorial optimization, a subset of numerical optimization, involves solving complex problems such as minimizing traffic congestion in logistics or reducing overall production costs in manufacturing.
Traditional techniques are effective for optimization problems with linear cost functions and constraints. However, they fall short when dealing with problems with nonlinear cost functions and constraints. In such cases, heuristic algorithms like Simulated Annealing (SA), Quantum Annealing (QA), and Simulated Quantum Annealing (SQA) are used to approximate solutions.
This article explores how SQA can be accelerated using AWS Graviton processors, specifically Graviton2 and Graviton3. It also discusses how this solution can be integrated with JijZept, a cloud service for numerical optimization using quantum technology.
Quadratic Unconstrained Binary Optimization and Ising Model
Quadratic Unconstrained Binary Optimization (QUBO) is a type of combinatorial optimization problem. In QUBO, the goal is to minimize a cost function that is quadratic in binary decision variables. The QUBO model is equivalent to the Ising model in statistical physics, which describes the behavior of spin systems.
Finding the optimal spin configuration of the Ising model that minimizes the given Hamiltonian is typically an intractable NP-hard problem. SA, QA, and SQA are popular methods for finding approximate solutions to such problems.
Simulated Quantum Annealing and AWS Graviton Processors
Applying the QA algorithm to real-world optimization problems using quantum devices is challenging due to limitations in device topology and intrinsic noise. To overcome these challenges, developers created SQA, a classical method that simulates quantum annealing using conventional computers.
One of the main drawbacks of the SQA algorithm is its requirement for redundant computational resources to express Trotter slices. AWS Graviton processors, with their multi-core feature, provide an efficient parallelization solution. The latest generation, Graviton3, offers up to 2x faster computation than its predecessor, Graviton2, enabling faster computation for SQA-based optimization problems.
Jij’s JijZept Service and Real-World Optimization Applications
Despite the power of computing devices, there are still many obstacles to real-world optimization applications. These include constructing a mathematical model that accurately represents the problem, converting the model to the QUBO formulation, transferring the model to the solver in a memory-efficient manner, and tuning the hyperparameters of the QUBO-solving algorithm. Jij’s product, JijZept, helps overcome these bottlenecks.
The service was tested using the Traveling Salesman Problem (TSP), which aims to find the optimal traveling route given distances between each city to be visited. The problem was implemented in Python with the JijZept library, and the model was sent to the server for solving.
Benchmarking SQA with an Instance of the TSP
To evaluate the performance of the SQA algorithm, a specific QUBO model was used to solve the TSP. The results of the total traveling route obtained by running the SQA algorithm on Graviton2 and Graviton3 processors were compared with those obtained using a naive SA algorithm on a conventional CPU. The benchmark showed that the SQA algorithm produces a smaller traveling distance compared to the SA algorithm, and that the Graviton3 processor computes around 1.5x faster than the Graviton2 processor.
Conclusion: The Future of Quantum-Inspired Heuristics and Cloud-Based Platforms
The implementation of the SQA algorithm with TSP in QUBO formulation as a benchmark on Graviton processors demonstrates the benefits of using these processors, which have a multicore architecture that allows efficient handling of the SQA algorithm. The findings highlight the potential of cloud platforms to harness quantum-inspired algorithms effectively.
The cloud service JijZept enables customers to use the Ising solver without the need to consider the device-specific features of the underlying hardware. This approach can be applied to various types of real-world applications such as flight scheduling, last-mile package delivery, or work scheduling of workers.
The combination of quantum-inspired heuristics, such as SQA, and powerful cloud-based platforms, such as Graviton and JijZept, holds great promise for approximating solutions of complex optimization problems in a more efficient and scalable manner.
External Link: Click Here For More
