A revolutionary quantum-classical hybrid approach has been discovered through new computational research that may answer large-scale, complex Mixed-Integer Quadratic Problems (MIQP) at previously unheard-of speeds. For some problem cases, this approach may even achieve exponential speedups over existing commercial classical solvers.
Takuma Yoshihara and Masayuki Ohzeki of Tohoku University’s Graduate School of Information Sciences and their colleagues made the breakthrough by including a D-Wave Constrained Quadratic Model (CQM) solver straight into the well-known Extended Benders Decomposition (EBD) framework. By successfully avoiding a significant computational barrier in traditional optimisation, this invention shows promise as a method for addressing challenging mixed-integer optimisation problem
You can also read What is Gaussian Wave Packet, How it Works and Types
The Challenge of Mixed-Integer Quadratic Programming
Optimization converts complicated real-world situations into mathematical models, which offers a basic framework for decision-making. With its combination of continuous modifications (continuous variables) and discrete decisions (integer variables), Mixed-Integer Programming (MIP) is incredibly flexible. This adaptability is crucial for modelling situations like cardinality-constrained portfolio optimisation, which takes risk-return correlations into account, and the unit commitment problem in power systems, which optimizes generator schedules.
The current focus is on Mixed-Integer Quadratic Programming (MIQP), which captures important relationships between variables by using quadratic terms in the objective function or restrictions. MIQP issues are extremely difficult because to the mix of discrete structure and quadratic complexity. Even though there are traditional methods like branch-and-bound, extended cutting-plane, and Extended Benders Decomposition (EBD), there are still practical challenges.
EBD is a popular and effective technique that breaks the problem down into a master problem and a subproblem, then iteratively converges to the best solution. The convergence guarantees of EBD are constrained, though, and most importantly solving the master issue frequently accounts for the majority of the computational expense. When the master issue in MIQP calls for optimizing the quadratic form over discrete variables, this bottleneck becomes particularly problematic. The larger the scale, the more difficult such problems become for traditional solvers.
You can also read Photonic Integrated Circuits PIC For Optical Processing
The Quantum-Classical Integration
The researchers suggested a unique optimisation technique that makes use of the Constrained Quadratic Model (CQM) solver created by D-Wave Systems in order to speed up this bottleneck. A hybrid framework that combines quantum annealing with classical optimisation, the CQM solver is made especially to produce high-quality solutions for NP-hard mixed-integer quadratic problems in an economical manner.
The decomposition is handled by EBD in this EBD+CQM approach, while the iterative master problem is solved by the CQM solver. When binary variables are represented by continuous variables, the general master problem for MIQP is represented by minimizing the objective function subject to linear constraints. The quadratic term with discrete variables is the computationally demanding part, and quantum annealing (QA) is a natural method for solving it.
The master problem and two subproblems are solved iteratively during the decomposition phase. The lower-level subproblem pertaining to the continuous variable is defined by substituting the presumed solution from the master problem into the objective and constraints. The subproblem is subjected to Lagrange relaxation, and the dual variable is used to examine the dual problem. When this dual problem is resolved, an extreme line or point is produced.
The new master problem, which consists of an integer variable and an auxiliary continuous variable, is then constructed using these dual answers. In order to guarantee that the objective function value of the dual problem does not surpass that of the original problem, the optimality constraint which is derived from the weak duality theorem is appended to the master problem.
You can also read EELS Electron Energy-Loss spectroscopy in nanoscale dynamics
Conversion to QUBO and Convergence
When the master problem is solved classically, the quadratic term and its objective function account for most of the computing complexity because they are NP-hard. The master problem must be transformed into the Quadratic Unconstrained Binary Optimization (QUBO) form in order to be solved effectively with Quantum Annealing (QA), a general-purpose combinatorial optimisation solver that is naturally suited to quadratic objectives. Only discrete, binary variables can be handled by QA; restrictions cannot be included.
There are multiple steps involved in this conversion:
- Discretization: A linear sum of binary variables is used to discretize the continuous auxiliary variable. This binary expression can be partially converted to QUBO form by substituting it into the master objective function.
- Constraint Handling: By adding a non-negative slack variable, which is represented as a linear sum of binary variables, inequality constraints like the optimality constraint are first transformed into equality constraints.
- Penalty Term: A quadratic penalty term is produced and added to the objective function by shifting all of the equality constraint’s terms to one side and squaring them. This term enforces the restriction when minimizing the overall objective by taking a positive value if the constraint is not satisfied and zero if it is.
When the duality gap, which is determined by comparing the objective values of the dual subproblems and the master problem, drops below a predetermined threshold (0.5 in this study), EBD convergence is reached.
You can also read Quantegrity E-Voting System lets Quantum-Resistant Elections
Experimental Results: Scalability and Speedup
To assess the suggested method’s quantum computing time and convergence behaviour, the researchers ran experiments. The CQM hybrid solver, Simulated Annealing (SA), Quantum Annealing (QA), and Gurobi Optimizer were the four solvers that were put to the test.
The EBD algorithm’s capacity to converge was confirmed by early convergence tests, which revealed that SA, CQM, and Gurobi all followed essentially the same convergence trajectories. Quantum Annealing (QA), on the other hand, did not converge, indicating that its precision at this time is inadequate for EBD criteria.
Importantly, SA lost the capacity to converge completely at size 220, but it continued to converge reliably up to a problem size of 20. After that, its success probability drastically declined. The intrinsic limits of SA (and QA) in preserving the accuracy needed by EBD are the cause of this poor scalability.
The two solvers that regularly converged CQM and Gurobi were the subject of the primary comparison. As the problem size increased, Gurobi’s computing time increased quickly, while CQM’s increase was greatly reduced, according to experiments that varied the amount of integer variables.
This discrepancy shows how much faster the EBD+CQM approach can solve the EBD master problem, especially for large-scale MIQP instances. In some cases, the hybrid technique delivers exponential speedups over the top commercial classical solver and effectively produces near-optimal solutions. Large-scale problems that have proven challenging for traditional classical solutions can be effectively tackled with the EBD+CQM technique. This benefit, which combines the iterative power of EBD with CQM’s capacity to handle quadratic formulations, offers natural scalability without performance deterioration.
In order to define its scalability boundaries, future research will concentrate on extending this methodology into a general-purpose framework and examining how it behaves under increasingly intricate continuous variables and constraints. In order to establish EBD+CQM as a flexible and promising approach for both scholarly research and real-world applications, researchers intend to assess its efficacy on representative real-world challenges such as power system optimisation and cardinality-constrained portfolio optimisation.
You can also read Maximally Entangled States For Arbitrary N Qubit Systems
