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:2406.05958 · Communications Physics

Speedup of high-order unconstrained binary optimization using quantum $${{\mathbb{Z}}}_{2}$$ lattice gauge theory

Bi-Ying Wang, Xiaopeng Cui, Qingguo Zeng, Yemin Zhan, Man‐Hong Yung, Yu Shi

Published Apr 10, 2025• 10 citations
arXivHTMLPDF

Abstract

An important and difficult problem in optimization is the high-order unconstrained binary optimization, which can represent many optimization problems more efficiently than quadratic unconstrained binary optimization, but how to quickly solve it has remained difficult. Here, we present an approach by mapping the high-order unconstrained binary optimization to quantum $${{\mathbb{Z}}}_{2}$$ lattice gauge theory and propose the gauged local quantum annealing, which is the local quantum annealing protected by the gauge symmetry. We present the quantum algorithm and its corresponding quantum-inspired classical algorithm for this problem and achieve algorithmic speedup by using gauge symmetry. By running the quantum-inspired classical algorithm, we demonstrate that the gauged local quantum annealing reduces the computational time by one order of magnitude from that of the local quantum annealing. The authors propose a quantum annealing scheme for solving a higher-order unconstrained binary optimization problem by mapping it to a quantum Z2 lattice gauge theory on a dual graph. This scheme is shown to achieve a speed-up of at least one order of magnitude in finding the ground state compared to other methods.

DOI
10.1038/s42005-025-02072-7

Related papers

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

Quadratic Unconstrained Binary Optimization via Quantum-Inspired Annealing

Joseph Bowles, Alexandre Dauphin, Patrick Huembeli +2 more

We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimization. The algorithm can be seen as an analog of quantum annealing under the restriction of a product-state space, where the dynamical evolution in quantum annealing is replaced with a gradient-descent-based method. This formulation is able to quickly find high-quality solutions to large-scale problem instances and can naturally be accelerated by dedicated hardware such as graphics processing units. We benchmark our approach for large-scale problem instances with tunable hardness and planted solutions. We find that our algorithm offers a similar performance to current state-of-the-art approaches within a comparably simple gradient-based and nonstochastic setting.

arXiv:2108.08064•Physical Review Applied•Sep 7, 2022•27 citations

Quantum-Inspired Optimization of Graph Partitioning Algorithms

Jincheng Zhang

Graph partitioning is a fundamental problem in various fields, including computer graphics, high-performance computing, and network design. Traditional graph partitioning algorithms often suffer from high computational complexity, particularly when dealing with large and complex graphs. This research investigates the potential of quantum-inspired optimization techniques, specifically leveraging concepts from quantum annealing, to accelerate the graph partitioning process. We formulate the graph partitioning problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem, allowing us to simulate the behavior of a quantum annealer on classical hardware. The core of our approach involves mapping the graph's connectivity structure onto a QUBO, representing nodes as binary variables and edges as constraints. By exploiting the inherent parallelism of quantum annealing, we aim to find optimal or near-optimal partitions significantly faster than conventional methods. The results demonstrate the feasibility and potential advantages of this quantum-inspired strategy for graph partitioning, offering a promising direction for tackling computationally intensive graph problems.

•Sep 5, 2026•0 citations

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

Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms

Gian Giacomo Guerreschi

Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.

arXiv:2101.07813•Jan 19, 2021•25 citations

Left-deep join order selection with higher-order unconstrained binary optimization on quantum computers

Valter Uotila

Join order optimization is among the most crucial query optimization problems, and its central position is also evident in the new research field where quantum computing is applied to database optimization and data management. In this field, join order optimization is the most studied database problem, typically tackled with a quadratic unconstrained binary optimization model, which is solved using various meta-heuristics, such as quantum and digital annealing, the quantum approximate optimization algorithm, or the variational quantum eigensolver. In this study, we continue developing quantum computing techniques for left-deep join order optimization by presenting three novel quantum optimization algorithms. These algorithms are based on a higher-order unconstrained binary optimization model, which is a generalization of the quadratic model and has not previously been applied to database problems. Theoretically, these optimization problems naturally map to universal quantum computers and quantum annealers. Compared to previous studies, two of our algorithms are the first quantum algorithms to model the join order cost function precisely. We prove theoretical bounds by showing that these two methods encode the same plans as the dynamic programming algorithm with respect to the query graph, which provides the optimal result up to cross products. The third algorithm achieves plans at least as good as those of the greedy algorithm with respect to the query graph. These results establish a meaningful theoretical connection between classical and quantum algorithms for selecting left-deep join orders. To demonstrate the practical usability of our algorithms, we have conducted an extensive experimental evaluation on thousands of clique, cycle, star, tree, and chain query graphs using both quantum and classical solvers.

arXiv:2502.00362•Frontiers in Computer Science•Oct 7, 2025•11 citations
Speedup of high-order unconstrained binary optimization using quantum Z2{{\mathbb{Z}}}_{2}Z2​ lattice gauge theory
An important and difficult problem in optimization is the high-order unconstrained binary optimization, which can represent many optimization problems more efficiently than quadratic unconstrained binary optimization, but how to quickly solve it has remained difficult. Here, we present an approach by mapping the high-order unconstrained binary optimization to quantum Z2{{\mathbb{Z}}}_{2}Z2​ lattice gauge theory and propose the gauged local quantum annealing, which is the local quantum annealing protected by the gauge symmetry. We present the quantum algorithm and its corresponding quantum-inspired classical algorithm for this problem and achieve algorithmic speedup by using gauge symmetry. By running the quantum-inspired classical algorithm, we demonstrate that the gauged local quantum annealing reduces the computational time by one order of magnitude from that of the local quantum annealing. The authors propose a quantum annealing scheme for solving a higher-order unconstrained binary optimization problem by mapping it to a quantum Z2 lattice gauge theory on a dual graph. This scheme is shown to achieve a speed-up of at least one order of magnitude in finding the ground state compared to other methods.
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.
We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimization. The algorithm can be seen as an analog of quantum annealing under the restriction of a product-state space, where the dynamical evolution in quantum annealing is replaced with a gradient-descent-based method. This formulation is able to quickly find high-quality solutions to large-scale problem instances and can naturally be accelerated by dedicated hardware such as graphics processing units. We benchmark our approach for large-scale problem instances with tunable hardness and planted solutions. We find that our algorithm offers a similar performance to current state-of-the-art approaches within a comparably simple gradient-based and nonstochastic setting.
Graph partitioning is a fundamental problem in various fields, including computer graphics, high-performance computing, and network design. Traditional graph partitioning algorithms often suffer from high computational complexity, particularly when dealing with large and complex graphs. This research investigates the potential of quantum-inspired optimization techniques, specifically leveraging concepts from quantum annealing, to accelerate the graph partitioning process. We formulate the graph partitioning problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem, allowing us to simulate the behavior of a quantum annealer on classical hardware. The core of our approach involves mapping the graph's connectivity structure onto a QUBO, representing nodes as binary variables and edges as constraints. By exploiting the inherent parallelism of quantum annealing, we aim to find optimal or near-optimal partitions significantly faster than conventional methods. The results demonstrate the feasibility and potential advantages of this quantum-inspired strategy for graph partitioning, offering a promising direction for tackling computationally intensive graph problems.
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.
Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.
Join order optimization is among the most crucial query optimization problems, and its central position is also evident in the new research field where quantum computing is applied to database optimization and data management. In this field, join order optimization is the most studied database problem, typically tackled with a quadratic unconstrained binary optimization model, which is solved using various meta-heuristics, such as quantum and digital annealing, the quantum approximate optimization algorithm, or the variational quantum eigensolver. In this study, we continue developing quantum computing techniques for left-deep join order optimization by presenting three novel quantum optimization algorithms. These algorithms are based on a higher-order unconstrained binary optimization model, which is a generalization of the quadratic model and has not previously been applied to database problems. Theoretically, these optimization problems naturally map to universal quantum computers and quantum annealers. Compared to previous studies, two of our algorithms are the first quantum algorithms to model the join order cost function precisely. We prove theoretical bounds by showing that these two methods encode the same plans as the dynamic programming algorithm with respect to the query graph, which provides the optimal result up to cross products. The third algorithm achieves plans at least as good as those of the greedy algorithm with respect to the query graph. These results establish a meaningful theoretical connection between classical and quantum algorithms for selecting left-deep join orders. To demonstrate the practical usability of our algorithms, we have conducted an extensive experimental evaluation on thousands of clique, cycle, star, tree, and chain query graphs using both quantum and classical solvers.