Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2510.15334

Achieving Sub-Exponential Speedup in Gate-Based Quantum Computing for Quadratic Unconstrained Binary Optimization

Tseng Ying-Wei, Kao Yu-Ting, Yeong-Jar Chang, Chia‐Ho Ou, Chang Wen-Chih

Published Oct 17, 2025• 1 citation
arXivHTMLPDF

Abstract

Recent quantum-inspired methods based on the Simulated Annealing (SA) algorithm have shown strong potential for solving combinatorial optimization problems. However, Grover's algorithm [1] in gate-based quantum computing offers only a quadratic speedup, which remains impractical for large problem sizes. This paper proposes a hybrid approach that integrates SA with Grover's algorithm to achieve sub-exponential speedup, thereby improving its industrial applicability. In enzyme fermentation, variables such as temperature, stirring, wait time, pH, tryptophan, rice flour and so on are encoded by 625 binary parameters, defining the space of possible enzyme formulations. We aim to find a binary configuration that maximizes the active ingredient, formulated as a 625-bit QUBO which is generated by historical experiments and AI techniques. Minimizing the QUBO cost corresponds to maximizing the active ingredient. This case study demonstrates that our hybrid method achieves sub-exponential speedup through gate-based quantum computing.

DOI
10.48550/arxiv.2510.15334

Related papers

New QUBO Transformations to Improve Quantum and Simulated Annealing Performance for Quadratic Knapsack

Nicolás Borrajo, Juan Marcos Ramírez, Farzam Nosrati +3 more

Recent advances in quantum computing have shown great potential for solving combinatorial optimization problems. A notable example is the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum-inspired algorithms require Quadratic Unconstrained Binary Optimization (QUBO) formulations. Transforming constrained optimization into QUBO impacts the algorithms' speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess them by using Simulated Annealing (SA), and find that three of our approaches outperform existing methods in terms of execution time as well as quality and quantity of feasible solutions found. Also, we tested these transformations on a quantum annealer, which was unable to solve even small instances, due to limitations in connectivity and error rates. In general, our results highlight the advantages of the new approaches, which reduce the number of variables in the QUBO representation.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2025•0 citations

Integrating AI and Quantum-Inspired Techniques for Efficient Enzyme Fermentation Optimization

Ying-Wei Tseng, Yu-Ting Kao, Yeong-Jar Chang +4 more

This paper introduces a new method that combines Artificial Intelligence (AI) and quantum-inspired techniques to improve the efficiency of multi-variable optimization experiments. By using advanced software simulations, this approach significantly reduces the time and cost compared to traditional physical experiments. The research focuses on enzyme fermentation, demonstrating that this method can achieve better results with fewer experiments. The findings highlight the potential of this approach to more effectively identify optimal formulations, leading to advancements in enzyme fermentation and other fields that require complex optimization. Initially, the Active Ingredients (AIN) could not be improved even after 600 experiments. However, by adopting the method outlined in this paper, we were able to identify a better formula in just 405 experiments. This resulted in an increase of AIN from 8481 to 10068, representing an improvement of 18.7%.

quant-pharXiv:2602.06420•Feb 9, 2026

New QUBO Transformations to Improve Quantum and Simulated Annealing Performance for Quadratic Knapsack

Nicolás Borrajo, Juan Ramírez, Farzam Nosrati +3 more

Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.

International Conference on Agents and Artificial Intelligence (ICAART)•Jan 1, 2026•1 citation

New QUBO Transformations to Improve Quantum and Simulated Annealing Performance for Quadratic Knapsack

Nicolás Borrajo Carro, Juan Marcos Ramírez, Farzam Nosrati +3 more

Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.

•May 27, 2025•0 citations

Variational Amplitude Amplification for Solving QUBO Problems

Daniel Koch, Massimiliano Cutugno, Saahil Patel +2 more

We investigate the use of amplitude amplification on the gate-based model of quantum computing as a means for solving combinatorial optimization problems. This study focuses primarily on quadratic unconstrained binary optimization (QUBO) problems, which are well-suited for qubit superposition states. Specifically, we demonstrate circuit designs which encode QUBOs as ‘cost oracle’ operations UC, which distribute phases across the basis states proportional to a cost function. We then show that when UC is combined with the standard Grover diffusion operator Us, one can achieve high probabilities of measurement for states corresponding to optimal and near optimal solutions while still only requiring O(π42N/M) iterations. In order to achieve these probabilities, a single scalar parameter ps is required, which we show can be found through a variational quantum–classical hybrid approach and can be used for heuristic solutions.

arXiv:2301.13665•Quantum Reports•Oct 1, 2023•10 citations

Boosting quantum annealing performance through direct polynomial unconstrained binary optimization

Sebastian Nagies, Kevin T. Geier, Javed Akram +3 more

Abstract Quantum annealing aims at solving optimization problems of practical relevance using quantum-computing hardware. Problems of interest are typically formulated in terms of quadratic unconstrained binary optimization (QUBO) Hamiltonians. However, many optimization problems are much more naturally formulated in terms of polynomial unconstrained binary optimization (PUBO) functions of higher order. As we show with various problem examples, leveraging the PUBO formulation can bring considerable savings in terms of required number of qubits. Moreover, in numerical benchmarks for the paradigmatic 3-SAT problem, we find scenarios where the scaling of the minimum energy gap during the optimization sweep differs significantly, suggesting the possibility of an exponentially faster annealing time when using the PUBO as compared to the QUBO formulation. This advantage persists even when considering the overhead caused by the higher-order interactions necessary for PUBO cost Hamiltonians. As an interesting side effect, the analysis on minimum energy gaps of different 3-SAT instance generators reveals different degrees of hardness, which will be of interest also for classical benchmark calculations. Our findings show a promising path to improving the resource efficiency and sweeping speed of quantum annealing protocols on both analog and digital platforms, which are important prerequisites when aiming at solving larger optimization problems with relevance to industry.

arXiv:2412.04398•Quantum Science and Technology•Apr 9, 2025•8 citations
Recent quantum-inspired methods based on the Simulated Annealing (SA) algorithm have shown strong potential for solving combinatorial optimization problems. However, Grover's algorithm [1] in gate-based quantum computing offers only a quadratic speedup, which remains impractical for large problem sizes. This paper proposes a hybrid approach that integrates SA with Grover's algorithm to achieve sub-exponential speedup, thereby improving its industrial applicability. In enzyme fermentation, variables such as temperature, stirring, wait time, pH, tryptophan, rice flour and so on are encoded by 625 binary parameters, defining the space of possible enzyme formulations. We aim to find a binary configuration that maximizes the active ingredient, formulated as a 625-bit QUBO which is generated by historical experiments and AI techniques. Minimizing the QUBO cost corresponds to maximizing the active ingredient. This case study demonstrates that our hybrid method achieves sub-exponential speedup through gate-based quantum computing.
Recent advances in quantum computing have shown great potential for solving combinatorial optimization problems. A notable example is the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum-inspired algorithms require Quadratic Unconstrained Binary Optimization (QUBO) formulations. Transforming constrained optimization into QUBO impacts the algorithms' speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess them by using Simulated Annealing (SA), and find that three of our approaches outperform existing methods in terms of execution time as well as quality and quantity of feasible solutions found. Also, we tested these transformations on a quantum annealer, which was unable to solve even small instances, due to limitations in connectivity and error rates. In general, our results highlight the advantages of the new approaches, which reduce the number of variables in the QUBO representation.
This paper introduces a new method that combines Artificial Intelligence (AI) and quantum-inspired techniques to improve the efficiency of multi-variable optimization experiments. By using advanced software simulations, this approach significantly reduces the time and cost compared to traditional physical experiments. The research focuses on enzyme fermentation, demonstrating that this method can achieve better results with fewer experiments. The findings highlight the potential of this approach to more effectively identify optimal formulations, leading to advancements in enzyme fermentation and other fields that require complex optimization. Initially, the Active Ingredients (AIN) could not be improved even after 600 experiments. However, by adopting the method outlined in this paper, we were able to identify a better formula in just 405 experiments. This resulted in an increase of AIN from 8481 to 10068, representing an improvement of 18.7%.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
We investigate the use of amplitude amplification on the gate-based model of quantum computing as a means for solving combinatorial optimization problems. This study focuses primarily on quadratic unconstrained binary optimization (QUBO) problems, which are well-suited for qubit superposition states. Specifically, we demonstrate circuit designs which encode QUBOs as ‘cost oracle’ operations UC, which distribute phases across the basis states proportional to a cost function. We then show that when UC is combined with the standard Grover diffusion operator Us, one can achieve high probabilities of measurement for states corresponding to optimal and near optimal solutions while still only requiring O(π42N/M) iterations. In order to achieve these probabilities, a single scalar parameter ps is required, which we show can be found through a variational quantum–classical hybrid approach and can be used for heuristic solutions.
Abstract Quantum annealing aims at solving optimization problems of practical relevance using quantum-computing hardware. Problems of interest are typically formulated in terms of quadratic unconstrained binary optimization (QUBO) Hamiltonians. However, many optimization problems are much more naturally formulated in terms of polynomial unconstrained binary optimization (PUBO) functions of higher order. As we show with various problem examples, leveraging the PUBO formulation can bring considerable savings in terms of required number of qubits. Moreover, in numerical benchmarks for the paradigmatic 3-SAT problem, we find scenarios where the scaling of the minimum energy gap during the optimization sweep differs significantly, suggesting the possibility of an exponentially faster annealing time when using the PUBO as compared to the QUBO formulation. This advantage persists even when considering the overhead caused by the higher-order interactions necessary for PUBO cost Hamiltonians. As an interesting side effect, the analysis on minimum energy gaps of different 3-SAT instance generators reveals different degrees of hardness, which will be of interest also for classical benchmark calculations. Our findings show a promising path to improving the resource efficiency and sweeping speed of quantum annealing protocols on both analog and digital platforms, which are important prerequisites when aiming at solving larger optimization problems with relevance to industry.