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:1810.01440

A Novel Algebraic Geometry Compiling Framework for Adiabatic Quantum Computations

Raouf Dridi, Hedayat Alghassi, SRIDHAR R. TAYUR

Published Oct 2, 2018• 10 citations
arXivHTMLPDF

Abstract

Adiabatic Quantum Computing (AQC) is an attractive paradigm for solving hard integer polynomial optimization problems. Available hardware restricts the Hamiltonians to be of a structure that allows only pairwise interactions. This requires that the original optimization problem to be first converted -- from its polynomial form -- to a quadratic unconstrained binary optimization (QUBO) problem, which we frame as a problem in algebraic geometry. Additionally, the hardware graph where such a QUBO-Hamiltonian needs to be embedded -- assigning variables of the problem to the qubits of the physical optimizer -- is not a complete graph, but rather one with limited connectivity. This "problem graph to hardware graph" embedding can also be framed as a problem of computing a Groebner basis of a certain specially constructed polynomial ideal. We develop a systematic computational approach to prepare a given polynomial optimization problem for AQC in three steps. The first step reduces an input polynomial optimization problem into a QUBO through the computation of the Groebner basis of a toric ideal generated from the monomials of the input objective function. The second step computes feasible embeddings. The third step computes the spectral gap of the adiabatic Hamiltonian associated to a given embedding. These steps are applicable well beyond the integer polynomial optimization problem. Our paper provides the first general purpose computational procedure that can be used directly as a $translator$ to solve polynomial integer optimization. Alternatively, it can be used as a test-bed (with small size problems) to help design efficient heuristic quantum compilers by studying various choices of reductions and embeddings in a systematic and comprehensive manner. An added benefit of our framework is in designing Ising architectures through the study of $\mathcal Y-$minor universal graphs.

DOI
10.48550/arxiv.1810.01440

Related papers

Template-Based Minor Embedding for Adiabatic Quantum Optimization

Thiago Serra, Teng Huang, Arvind U. Raghunathan +1 more

Quantum annealing (QA) can be used to quickly obtain near-optimal solutions for quadratic unconstrained binary optimization (QUBO) problems. In QA hardware, each decision variable of a QUBO should be mapped to one or more adjacent qubits in such a way that pairs of variables defining a quadratic term in the objective function are mapped to some pair of adjacent qubits. However, qubits have limited connectivity in existing QA hardware. This has spurred work on preprocessing algorithms for embedding the graph representing problem variables with quadratic terms into the hardware graph representing qubits adjacencies, such as the Chimera graph in hardware produced by D-Wave Systems. In this paper, we use integer linear programming to search for an embedding of the problem graph into certain classes of minors of the Chimera graph, which we call template embeddings. One of these classes corresponds to complete bipartite graphs, for which we show the limitation of the existing approach based on minimum odd cycle transversals (OCTs). One of the formulations presented is exact and thus can be used to certify the absence of a minor embedding using that template. On an extensive test set consisting of random graphs from five different classes of varying size and sparsity, we can embed more graphs than a state-of-the-art OCT-based approach, our approach scales better with the hardware size, and the runtime is generally orders of magnitude smaller. Summary of Contribution: Our work combines classical and quantum computing for operations research by showing that integer linear programming can be successfully used as a preprocessing step for adiabatic quantum optimization. We use it to determine how a quadratic unconstrained binary optimization problem can be solved by a quantum annealer in which the qubits are coupled as in a Chimera graph, such as in the quantum annealers currently produced by D-Wave Systems. The paper also provides a timely introduction to adiabatic quantum computing and related work on minor embeddings.

arXiv:1910.02179•INFORMS journal on computing•Sep 21, 2021•12 citations

Mapping NP-Hard Problems to Restricted Adiabatic Quantum Architectures

Gary J. Mooney, Sam U.Y. Tonetto, Charles D. Hill +1 more

We introduce a framework for mapping NP-Hard problems to adiabatic quantum computing (AQC) architectures that are heavily restricted in both connectivity and dynamic range of couplings, for which minor-embedding -- the standard problem mapping method -- cannot be directly applied. Separating the mapping into two distinct stages, we introduce problem-specific reductions for both quadratic unconstrained binary optimisation (QUBO) and satisfiability (SAT) and develop the subdivision-embedding method that is suitable for directly embedding onto these heavily restricted architectures. The theory underpinning this framework provides tools to aid in the manipulation of Ising Hamiltonians for the purposes of Ising energy minimisation, and could be used to assist in developing and optimising further problem mapping techniques. For each of the problem mapping methods presented, we examine how the physical qubit count scales with problem size on architectures of varying connectivity.

arXiv:1911.00249•Nov 1, 2019•2 citations

Minimizing polynomial functions on quantum computers

Raouf Dridi, Hedayat Alghassi, SRIDHAR R. TAYUR

This expository paper reviews some of the recent uses of computational algebraic geometry in classical and quantum optimization. The paper assumes an elementary background in algebraic geometry and adiabatic quantum computing (AQC), and concentrates on presenting concrete examples (with Python codes tested on a quantum computer) of applying algebraic geometry constructs: solving binary optimization, factoring, and compiling. Reversing the direction, we also briefly describe a novel use of quantum computers to compute Groebner bases for toric ideals. We also show how Groebner bases play a role in studying AQC at a fundamental level within a Morse theory framework. We close by placing our work in perspective, by situating this leg of the journey, as part of a marvelous intellectual expedition that began with our ancients over 4000 years ago.

arXiv:1903.08270•Mar 19, 2019•4 citations

Hard combinatorial problems and minor embeddings on lattice graphs

Andrew Lucas

Today, hardware constraints are an important limitation on quantum adiabatic optimization algorithms. Firstly, computational problems must be formulated as quadratic unconstrained binary optimization (QUBO) in the presence of noisy coupling constants. Secondly, the interaction graph of the QUBO must have an effective minor embedding into a two-dimensional nonplanar lattice graph. We describe new strategies for constructing QUBOs for NP-complete/hard combinatorial problems that address both of these challenges. Our results include asymptotically improved embeddings for number partitioning, filling knapsacks, graph coloring, and finding Hamiltonian cycles. These embeddings can be also be found with reduced computational effort. Our new embedding for number partitioning may be more effective on next-generation hardware.

arXiv:1812.01789•Dec 5, 2018•1 citation

Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization

Hartmut Neven, Geordie Rose, William G. Macready

Many artificial intelligence (AI) problems naturally map to NP-hard optimization problems. This has the interesting consequence that enabling human-level capability in machines often requires systems that can handle formally intractable problems. This issue can sometimes (but possibly not always) be resolved by building special-purpose heuristic algorithms, tailored to the problem in question. Because of the continued difficulties in automating certain tasks that are natural for humans, there remains a strong motivation for AI researchers to investigate and apply new algorithms and techniques to hard AI problems. Recently a novel class of relevant algorithms that require quantum mechanical hardware have been proposed. These algorithms, referred to as quantum adiabatic algorithms, represent a new approach to designing both complete and heuristic solvers for NP-hard optimization problems. In this work we describe how to formulate image recognition, which is a canonical NP-hard AI problem, as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The QUBO format corresponds to the input format required for D-Wave superconducting adiabatic quantum computing (AQC) processors.

arXiv:0804.4457•Apr 28, 2008•55 citations

Adiabatic Quantum Linear Optimal Control for Discrete Time Dynamical Systems

Mayank Jha, Prasanna Date

This paper presents a novel approach for solving finite-horizon linear optimal control based on block-Toeplitz least-squares problem, by recasting the latter as Quadratic Unconstrained Binary Optimization (QUBO) suitable for adiabatic quantum computing (AQC). Classical block-Toeplitz leastsquares problem, scales as$O\left((N m)^{3}\right)$for horizon length$N$and control dimension$m$. We demonstrate that this Toeplitzstructured least-squares cost can be transformed into a QUBO formulation by introducing binary precision vectors that encode each continuous control parameter into finite number of bits. We establish the general case in mathematically rigorous manner wherein the total number of binary decision variables remain dependent on$N$. To respect current quantum annealer capabilities, we propose a basis-function parametrization that approximates the full control sequence with a small set of basis coefficients, reducing the total number of binary-variables and rendering the latter independent of$N$. Through simulation study, we show that, for large datasets, the QUBO pipeline, comprising of hardware-constant anneal step outperforms classical least square based solvers by several factors whilst demonstrating acceptable accuracy.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations
Adiabatic Quantum Computing (AQC) is an attractive paradigm for solving hard integer polynomial optimization problems. Available hardware restricts the Hamiltonians to be of a structure that allows only pairwise interactions. This requires that the original optimization problem to be first converted -- from its polynomial form -- to a quadratic unconstrained binary optimization (QUBO) problem, which we frame as a problem in algebraic geometry. Additionally, the hardware graph where such a QUBO-Hamiltonian needs to be embedded -- assigning variables of the problem to the qubits of the physical optimizer -- is not a complete graph, but rather one with limited connectivity. This "problem graph to hardware graph" embedding can also be framed as a problem of computing a Groebner basis of a certain specially constructed polynomial ideal. We develop a systematic computational approach to prepare a given polynomial optimization problem for AQC in three steps. The first step reduces an input polynomial optimization problem into a QUBO through the computation of the Groebner basis of a toric ideal generated from the monomials of the input objective function. The second step computes feasible embeddings. The third step computes the spectral gap of the adiabatic Hamiltonian associated to a given embedding. These steps are applicable well beyond the integer polynomial optimization problem. Our paper provides the first general purpose computational procedure that can be used directly as a translatortranslatortranslator to solve polynomial integer optimization. Alternatively, it can be used as a test-bed (with small size problems) to help design efficient heuristic quantum compilers by studying various choices of reductions and embeddings in a systematic and comprehensive manner. An added benefit of our framework is in designing Ising architectures through the study of Y−\mathcal Y-Y−minor universal graphs.
Quantum annealing (QA) can be used to quickly obtain near-optimal solutions for quadratic unconstrained binary optimization (QUBO) problems. In QA hardware, each decision variable of a QUBO should be mapped to one or more adjacent qubits in such a way that pairs of variables defining a quadratic term in the objective function are mapped to some pair of adjacent qubits. However, qubits have limited connectivity in existing QA hardware. This has spurred work on preprocessing algorithms for embedding the graph representing problem variables with quadratic terms into the hardware graph representing qubits adjacencies, such as the Chimera graph in hardware produced by D-Wave Systems. In this paper, we use integer linear programming to search for an embedding of the problem graph into certain classes of minors of the Chimera graph, which we call template embeddings. One of these classes corresponds to complete bipartite graphs, for which we show the limitation of the existing approach based on minimum odd cycle transversals (OCTs). One of the formulations presented is exact and thus can be used to certify the absence of a minor embedding using that template. On an extensive test set consisting of random graphs from five different classes of varying size and sparsity, we can embed more graphs than a state-of-the-art OCT-based approach, our approach scales better with the hardware size, and the runtime is generally orders of magnitude smaller. Summary of Contribution: Our work combines classical and quantum computing for operations research by showing that integer linear programming can be successfully used as a preprocessing step for adiabatic quantum optimization. We use it to determine how a quadratic unconstrained binary optimization problem can be solved by a quantum annealer in which the qubits are coupled as in a Chimera graph, such as in the quantum annealers currently produced by D-Wave Systems. The paper also provides a timely introduction to adiabatic quantum computing and related work on minor embeddings.
We introduce a framework for mapping NP-Hard problems to adiabatic quantum computing (AQC) architectures that are heavily restricted in both connectivity and dynamic range of couplings, for which minor-embedding -- the standard problem mapping method -- cannot be directly applied. Separating the mapping into two distinct stages, we introduce problem-specific reductions for both quadratic unconstrained binary optimisation (QUBO) and satisfiability (SAT) and develop the subdivision-embedding method that is suitable for directly embedding onto these heavily restricted architectures. The theory underpinning this framework provides tools to aid in the manipulation of Ising Hamiltonians for the purposes of Ising energy minimisation, and could be used to assist in developing and optimising further problem mapping techniques. For each of the problem mapping methods presented, we examine how the physical qubit count scales with problem size on architectures of varying connectivity.
This expository paper reviews some of the recent uses of computational algebraic geometry in classical and quantum optimization. The paper assumes an elementary background in algebraic geometry and adiabatic quantum computing (AQC), and concentrates on presenting concrete examples (with Python codes tested on a quantum computer) of applying algebraic geometry constructs: solving binary optimization, factoring, and compiling. Reversing the direction, we also briefly describe a novel use of quantum computers to compute Groebner bases for toric ideals. We also show how Groebner bases play a role in studying AQC at a fundamental level within a Morse theory framework. We close by placing our work in perspective, by situating this leg of the journey, as part of a marvelous intellectual expedition that began with our ancients over 4000 years ago.
Today, hardware constraints are an important limitation on quantum adiabatic optimization algorithms. Firstly, computational problems must be formulated as quadratic unconstrained binary optimization (QUBO) in the presence of noisy coupling constants. Secondly, the interaction graph of the QUBO must have an effective minor embedding into a two-dimensional nonplanar lattice graph. We describe new strategies for constructing QUBOs for NP-complete/hard combinatorial problems that address both of these challenges. Our results include asymptotically improved embeddings for number partitioning, filling knapsacks, graph coloring, and finding Hamiltonian cycles. These embeddings can be also be found with reduced computational effort. Our new embedding for number partitioning may be more effective on next-generation hardware.
Many artificial intelligence (AI) problems naturally map to NP-hard optimization problems. This has the interesting consequence that enabling human-level capability in machines often requires systems that can handle formally intractable problems. This issue can sometimes (but possibly not always) be resolved by building special-purpose heuristic algorithms, tailored to the problem in question. Because of the continued difficulties in automating certain tasks that are natural for humans, there remains a strong motivation for AI researchers to investigate and apply new algorithms and techniques to hard AI problems. Recently a novel class of relevant algorithms that require quantum mechanical hardware have been proposed. These algorithms, referred to as quantum adiabatic algorithms, represent a new approach to designing both complete and heuristic solvers for NP-hard optimization problems. In this work we describe how to formulate image recognition, which is a canonical NP-hard AI problem, as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The QUBO format corresponds to the input format required for D-Wave superconducting adiabatic quantum computing (AQC) processors.
This paper presents a novel approach for solving finite-horizon linear optimal control based on block-Toeplitz least-squares problem, by recasting the latter as Quadratic Unconstrained Binary Optimization (QUBO) suitable for adiabatic quantum computing (AQC). Classical block-Toeplitz leastsquares problem, scales asO((Nm)3)O\left((N m)^{3}\right)O((Nm)3)for horizon lengthNNNand control dimensionmmm. We demonstrate that this Toeplitzstructured least-squares cost can be transformed into a QUBO formulation by introducing binary precision vectors that encode each continuous control parameter into finite number of bits. We establish the general case in mathematically rigorous manner wherein the total number of binary decision variables remain dependent onNNN. To respect current quantum annealer capabilities, we propose a basis-function parametrization that approximates the full control sequence with a small set of basis coefficients, reducing the total number of binary-variables and rendering the latter independent ofNNN. Through simulation study, we show that, for large datasets, the QUBO pipeline, comprising of hardware-constant anneal step outperforms classical least square based solvers by several factors whilst demonstrating acceptable accuracy.