Quantum Computing Achieves Sub-Exponential Speedup for 625-Bit QUBO Problems in Binary Optimization

Quadratic unconstrained binary optimization (QUBO) problems frequently arise in industrial applications, from optimising enzyme fermentation to designing complex systems, yet solving these problems efficiently remains a significant challenge. Tseng Ying-Wei, Kao Yu-Ting, and Chang Yeong-Jar from the Industrial Technology Research Institute, along with colleagues, demonstrate a new hybrid approach that combines the strengths of classical simulated annealing with the power of Grover’s algorithm in gate-based quantum computing. This work overcomes the limitations of existing quantum methods, which offer only quadratic speedups, and achieves a sub-exponential advantage for solving QUBO problems. By applying this method to a case study involving the optimisation of enzyme formulations, defined by 625 binary parameters, the team demonstrates a substantial improvement in computational efficiency, paving the way for practical applications of quantum computing in industrial optimisation.

This overcomes limitations of large-scale quantum hardware by combining Grover’s algorithm with Simulated Annealing, restricting the quantum search to a smaller portion of the problem and reducing required quantum resources. The team tested this approach on a 625-bit QUBO problem derived from optimising enzyme fermentation, a crucial process in biomanufacturing. Simulated Annealing provides the overall optimisation framework, while Grover’s algorithm accelerates the most time-consuming part: evaluating the cost function.

By focusing the quantum search on a subspace of the solution, the team significantly reduced computational demands and explored fixing subsets of variables to further minimise qubit requirements. Experiments demonstrate a substantial speedup with the hybrid approach. Increasing the number of qubits used in Grover’s algorithm decreased runtime, confirming the effectiveness of the quantum acceleration. The team identified an optimal range for qubit numbers where the benefits of Grover’s algorithm outweighed the classical overhead, achieving speedups of 477-fold, 750-fold, and 1051-fold with 32, 34, and 36 qubits, respectively, for the enzyme fermentation problem. This work demonstrates a practical quantum advantage for solving large-scale QUBO problems, even accounting for realistic overheads. The researchers argue that Grover’s algorithm is best viewed as a scalable enhancement to classical heuristics, rather than a complete replacement, and that combining the strengths of both classical and quantum computing is crucial for overcoming their individual limitations.

Hybrid Optimization Boosts Enzyme Fermentation Modelling

Scientists have created a hybrid optimisation framework that combines Simulated Annealing with Grover’s algorithm, achieving a speedup in solving complex combinatorial optimisation problems. This addresses limitations of both methods, where Simulated Annealing becomes slow in high-dimensional spaces and Grover’s algorithm offers only a quadratic speedup, insufficient for large problems. Researchers formulated a 625-bit QUBO model representing parameters of an enzyme fermentation process, including temperature, stirring speed, and ingredient concentrations, to maximise active ingredient production. The team engineered a methodology that compares performance against Simulated Annealing, accepting a degree of optimality loss for increased efficiency, and adopted a parallel configuration to reduce computational demands.

This innovative approach utilises a gate-based quantum computing framework to achieve a level of parallelism, significantly reducing computational demands when the number of qubits is much smaller than the total number of variables in the problem. This configuration delivers a sub-exponential enhancement compared to conventional Simulated Annealing methods. The framework incorporates segmentation, quantum acceleration, and circuit simplification to effectively bridge classical heuristic search and gate-based quantum computation. Experiments, conducted in a Python environment, used a QUBO model derived from prior work optimising enzyme fermentation in collaboration with a biopharmaceutical partner, previously requiring over an hour for each experiment. Previous studies demonstrated that active ingredient levels could be enhanced with fewer experiments using Simulated Annealing, and that the runtime does not grow exponentially with the number of variables. Building on these findings, the current work validates the sub-exponential speedup achieved through the hybrid approach, demonstrating its potential for industrial applications and contributing to a broader line of quantum innovations.

Quantum Grover Annealing Optimizes Enzyme Fermentation

Researchers have developed a novel hybrid approach combining Simulated Annealing with Grover’s quantum search algorithm to accelerate solutions for large-scale combinatorial optimisation problems, specifically demonstrated through enzyme fermentation optimisation. They encoded variables influencing enzyme formulation, including temperature, stirring speed, pH, and ingredient concentrations, as 625 binary parameters, defining a complex 625-bit QUBO problem, with the goal of identifying a binary configuration maximising active ingredient yield. The team achieved a significant reduction in computational complexity by strategically combining classical and quantum processing. Classical Simulated Annealing requires evaluating the QUBO cost function for every candidate solution, but this method reduces that demand by leveraging Grover’s algorithm to explore a reduced search space.

By dividing the 625-bit problem into subproblems and fixing most variables, the quantum module operates on a smaller subspace. Experiments demonstrated that this hybrid framework delivers sub-exponential speedup compared to traditional Simulated Annealing. Specifically, Grover’s algorithm reduces the search cost, effectively replacing sequential cost evaluations with a smaller number of Grover iterations. Varying the size of the explored subspace while keeping the total problem size fixed, researchers confirmed that subspace-based quantum parallelisation enables the use of limited qubit resources to tackle high-dimensional QUBO problems. Furthermore, fixing input variables significantly simplified the required quantum circuit, reducing the number of necessary qubits and gates, enhancing the scalability and efficiency of quantum QUBO cost evaluations, and paving the way for practical applications in industrial optimisation scenarios.

Hybrid Quantum Optimization Accelerates Enzyme Fermentation

This work demonstrates a hybrid optimisation framework integrating simulated annealing with Grover’s algorithm, enabling practical speedups in solving large-scale quadratic unconstrained binary optimisation (QUBO) problems. By redefining the performance baseline from brute-force approaches to simulated annealing and focusing the quantum search within a relevant subspace, the team achieved a sub-exponential acceleration, transforming Grover’s algorithm from a theoretical concept into a potentially viable tool for complex optimisation tasks. Results from a case study involving enzyme fermentation, a 625-bit QUBO problem, show significant runtime improvements, with speedups of 477-fold, 750-fold, and 1051-fold achieved using 32, 34, and 36 qubits, respectively, compared to traditional simulated annealing. Furthermore, the research highlights the potential for reducing the quantum resources required by fixing subsets of variables, thereby enhancing compatibility with current and near-term quantum hardware. This approach reframes the role of Grover’s algorithm, positioning it not as a direct replacement for classical methods, but as a scalable enhancement to existing heuristics. The authors acknowledge a conservative estimate of quantum overhead, accounting for factors such as slower gate speeds and data exchange, yet still observe clear performance gains.