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:2301.01778 · Quantum

Expanding the reach of quantum optimization with fermionic embeddings

Andrew Zhao, Nicholas C. Rubin

Published Aug 28, 2024• 0 citations
arXivHTMLPDF

Abstract

Quadratic programming over orthogonal matrices encompasses a broad class of hard optimization problems that do not have an efficient quantum representation. Such problems are instances of the little noncommutative Grothendieck problem (LNCG), a generalization of binary quadratic programs to continuous, noncommutative variables. In this work, we establish a natural embedding for this class of LNCG problems onto a fermionic Hamiltonian, thereby enabling the study of this classical problem with the tools of quantum information. This embedding is accomplished by a new representation of orthogonal matrices as fermionic quantum states, which we achieve through the well-known double covering of the orthogonal group. Correspondingly, the embedded LNCG Hamiltonian is a two-body fermion model. Determining extremal states of this Hamiltonian provides an outer approximation to the original problem, a quantum analogue to classical semidefinite relaxations. In particular, when optimizing over the special orthogonal group our quantum relaxation obeys additional, powerful constraints based on the convex hull of rotation matrices. The classical size of this convex-hull representation is exponential in matrix dimension, whereas our quantum representation requires only a linear number of qubits. Finally, to project the relaxed solution back into the feasible space, we propose rounding procedures which return orthogonal matrices from appropriate measurements of the quantum state. Through numerical experiments we provide evidence that this rounded quantum relaxation can produce high-quality approximations.

DOI
10.22331/q-2024-08-28-1451

Related papers

Approximating the Little Grothendieck Problem over the Orthogonal Group

Afonso S. Bandeira, Christopher Kennedy, Amit Singer

The little Grothendieck problem (a special case of Boolean quadratic optimization) consists of maximizing P ij Cijxixj over binary variables xi 2 f 1g, where C is a positive semidenite matrix. In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given C 2 R dn dn a positive semidenite matrix, the objective is to maximize P ij tr C T ijOiO T restricting Oi to take values in the group of orthogonal matrices O(d), where Cij denotes the (ij)-th d d block of C. We propose an approximation algorithm, to which we refer as Orthogonal-Cut, to solve the little Grothendieck problem over the group of orthogonal matrices O(d) and show a constant approximation ratio. Our method is based on semidenite programming where the relaxation is inspired by the work of Goemans and Williamson in the context of the MaxCut problem. For a given d 1, we show a constant approximation ratio of 2, where d is the expected average singular value of a d d matrix with random GaussianN 0; 1 i.i.d. entries. For d = 1 we recover the known 2 = 2= approximation guarantee for the classical little Grothendieck problem. Orthogonal-Cut also serves as an approximation algorithm for several applications including the Procrustes problem where it improves over the best previously known approximation ratio of 1 2 p 2 . The little Grothendieck problem falls under the larger class of problems approximated by an algorithm recently proposed in the context of the non-commutative Grothendieck inequality. Nonetheless, our approach is simpler and gives a better approximation ratio.

•Aug 23, 2013•7 citations

Faster quantum and classical SDP approximations for quadratic binary optimization

Fernando G. S. L. Brandão, Richard Kueng, Daniel Stilck França

We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on Erdös-Rényi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem.

arXiv:1909.04613•Quantum•Jan 20, 2022•28 citations

Semidefinite Relaxation of Multimarginal Optimal Transport for Strictly Correlated Electrons in Second Quantization

Yuehaw Khoo, Lin Lin, Michael Lindsey +1 more

We consider the strictly correlated electron (SCE) limit of the fermionic quantum many-body problem in the second-quantized formalism. This limit gives rise to a multimarginal optimal transport (MMOT) problem. Here the marginal state space for our MMOT problem is the binary set 0,1, and the number of marginals is the number L of sites in the model. The costs of storing and computing the exact solution of the MMOT problem both scale exponentially with respect to L. We propose an efficient convex relaxation to the MMOT which can be solved by semidefinite programming (SDP). In particular, the semidefinite constraint is only of size 2 L X 2 L. We further prove that the SDP has dual attainment, in spite of the lack of Slater's condition (i.e., the primal SDP does not have any strictly feasible point). In the context of determining the lowest energy of electrons via density functional theory, such dual attainment implies the existence of an effective potential needed to solve a nonlinear Schrödinger equation via self-consistent field iteration. We demonstrate the effectiveness of our methods on computing the ground state energy of spinless and spinful Hubbard-type models. Numerical results indicate that our SDP formulation yields comparable results when using the unrelaxed MMOT formulation. We also describe how our relaxation methods generalize to arbitrary MMOT problems with pairwise cost functions.

arXiv:1905.08322•SIAM Journal on Scientific Computing•Jan 1, 2020•13 citations

Approximate Solutions of Combinatorial Problems via Quantum Relaxations

Bryce Fuller, Charles F. Hadfield, Jennifer R. Glick +8 more

Combinatorial problems are formulated to find optimal designs within a fixed set of constraints and are commonly found across diverse engineering and scientific domains. Understanding how to best use quantum computers for combinatorial optimization remains an ongoing area of study. Here, we propose new methods for producing approximate solutions to quadratic unconstrained binary optimization problems, which are based on relaxations to local quantum Hamiltonians. We look specifically at approximating solutions for the maximum cut problem and its weighted version. These relaxations are defined through commutative maps, which in turn are constructed borrowing ideas from quantum random access codes. We establish relations between the spectra of the relaxed Hamiltonians and optimal cuts of the original problems, via two quantum rounding protocols. The first one is based on projections to random magic states. It produces average cuts that approximate the optimal one by a factor of least 0.555 or 0.625, depending on the relaxation chosen, if given access to a quantum state with energy between the optimal classical cut and the maximal relaxed energy. The second rounding protocol is deterministic and is based on the estimation of Pauli observables. The proposed quantum relaxations inherit memory compression from quantum random access codes, which allowed us to test the performances of the methods presented for 3-regular random graphs and a design problem motivated by industry for sizes up to 40 nodes, on superconducting quantum processors.

arXiv:2111.03167•IEEE Transactions on Quantum Engineering•Jan 1, 2024•33 citations

Quantum Speedups for Group Relaxations of Integer Linear Programs

Brandon Augustino, Dylan Herman, Guneykan Ozgul +5 more

Integer Linear Programs (ILPs) are a flexible and ubiquitous model for discrete optimization problems. Solving ILPs is \textsf{NP-Hard} yet of great practical importance. Super-quadratic quantum speedups for ILPs have been difficult to obtain because classical algorithms for many-constraint ILPs are global and exhaustive, whereas quantum frameworks that offer super-quadratic speedup exploit local structure of the objective and feasible set. We address this via quantum algorithms for Gomory's group relaxation. The group relaxation of an ILP is obtained by dropping nonnegativity on variables that are positive in the optimal solution of the linear programming (LP) relaxation, while retaining integrality of the decision variables. We present a competitive feasibility-preserving classical local-search algorithm for the group relaxation, and a corresponding quantum algorithm that, under reasonable technical conditions, achieves a super-quadratic speedup. When the group relaxation satisfies a nondegeneracy condition analogous to, but stronger than, LP non-degeneracy, our approach yields the optimal solution to the original ILP. Otherwise, the group relaxation tightens bounds on the optimal objective value of the ILP, and can improve downstream branch-and-cut by reducing the integrality gap; we numerically observe this on several practically relevant ILPs. To achieve these results, we derive efficiently constructible constraint-preserving mixers for the group relaxation with favorable spectral properties, which are of independent interest.

quant-pharXiv:2602.13494•Feb 17, 2026•0 citations

Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming

Friedrich Wagner, Jonas Nüßlein, Frauke Liers

To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution. If the potential of quantum computing is realized, it can be expected that in particular finding high-quality solutions for hard problems can be done fast. Still, near-future quantum hardware considerably limits the size of treatable problems. In this work, we go one step into integrating the potentials of quantum and classical techniques for combinatorial optimization. We propose a hybrid heuristic for the weighted maximum-cut problem and for quadratic unconstrained binary optimization. The heuristic employs a linear programming relaxation, rendering it well-suited for integration into exact branch-and-cut algorithms. For large instances, we reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. Moreover, we improve the applicability of depth-1 QAOA, a parameterized quantum algorithm, by deriving a parameter estimate for arbitrary instances. We present numerous computational results from real quantum hardware.

arXiv:2302.05493•ACM Transactions on Quantum Computing•Jan 13, 2025•2 citations
Quadratic programming over orthogonal matrices encompasses a broad class of hard optimization problems that do not have an efficient quantum representation. Such problems are instances of the little noncommutative Grothendieck problem (LNCG), a generalization of binary quadratic programs to continuous, noncommutative variables. In this work, we establish a natural embedding for this class of LNCG problems onto a fermionic Hamiltonian, thereby enabling the study of this classical problem with the tools of quantum information. This embedding is accomplished by a new representation of orthogonal matrices as fermionic quantum states, which we achieve through the well-known double covering of the orthogonal group. Correspondingly, the embedded LNCG Hamiltonian is a two-body fermion model. Determining extremal states of this Hamiltonian provides an outer approximation to the original problem, a quantum analogue to classical semidefinite relaxations. In particular, when optimizing over the special orthogonal group our quantum relaxation obeys additional, powerful constraints based on the convex hull of rotation matrices. The classical size of this convex-hull representation is exponential in matrix dimension, whereas our quantum representation requires only a linear number of qubits. Finally, to project the relaxed solution back into the feasible space, we propose rounding procedures which return orthogonal matrices from appropriate measurements of the quantum state. Through numerical experiments we provide evidence that this rounded quantum relaxation can produce high-quality approximations.
The little Grothendieck problem (a special case of Boolean quadratic optimization) consists of maximizing P ij Cijxixj over binary variables xi 2 f 1g, where C is a positive semidenite matrix. In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given C 2 R dn dn a positive semidenite matrix, the objective is to maximize P ij tr C T ijOiO T restricting Oi to take values in the group of orthogonal matrices O(d), where Cij denotes the (ij)-th d d block of C. We propose an approximation algorithm, to which we refer as Orthogonal-Cut, to solve the little Grothendieck problem over the group of orthogonal matrices O(d) and show a constant approximation ratio. Our method is based on semidenite programming where the relaxation is inspired by the work of Goemans and Williamson in the context of the MaxCut problem. For a given d 1, we show a constant approximation ratio of 2, where d is the expected average singular value of a d d matrix with random GaussianN 0; 1 i.i.d. entries. For d = 1 we recover the known 2 = 2= approximation guarantee for the classical little Grothendieck problem. Orthogonal-Cut also serves as an approximation algorithm for several applications including the Procrustes problem where it improves over the best previously known approximation ratio of 1 2 p 2 . The little Grothendieck problem falls under the larger class of problems approximated by an algorithm recently proposed in the context of the non-commutative Grothendieck inequality. Nonetheless, our approach is simpler and gives a better approximation ratio.
We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on Erdös-Rényi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem.
We consider the strictly correlated electron (SCE) limit of the fermionic quantum many-body problem in the second-quantized formalism. This limit gives rise to a multimarginal optimal transport (MMOT) problem. Here the marginal state space for our MMOT problem is the binary set 0,1, and the number of marginals is the number L of sites in the model. The costs of storing and computing the exact solution of the MMOT problem both scale exponentially with respect to L. We propose an efficient convex relaxation to the MMOT which can be solved by semidefinite programming (SDP). In particular, the semidefinite constraint is only of size 2 L X 2 L. We further prove that the SDP has dual attainment, in spite of the lack of Slater's condition (i.e., the primal SDP does not have any strictly feasible point). In the context of determining the lowest energy of electrons via density functional theory, such dual attainment implies the existence of an effective potential needed to solve a nonlinear Schrödinger equation via self-consistent field iteration. We demonstrate the effectiveness of our methods on computing the ground state energy of spinless and spinful Hubbard-type models. Numerical results indicate that our SDP formulation yields comparable results when using the unrelaxed MMOT formulation. We also describe how our relaxation methods generalize to arbitrary MMOT problems with pairwise cost functions.
Combinatorial problems are formulated to find optimal designs within a fixed set of constraints and are commonly found across diverse engineering and scientific domains. Understanding how to best use quantum computers for combinatorial optimization remains an ongoing area of study. Here, we propose new methods for producing approximate solutions to quadratic unconstrained binary optimization problems, which are based on relaxations to local quantum Hamiltonians. We look specifically at approximating solutions for the maximum cut problem and its weighted version. These relaxations are defined through commutative maps, which in turn are constructed borrowing ideas from quantum random access codes. We establish relations between the spectra of the relaxed Hamiltonians and optimal cuts of the original problems, via two quantum rounding protocols. The first one is based on projections to random magic states. It produces average cuts that approximate the optimal one by a factor of least 0.555 or 0.625, depending on the relaxation chosen, if given access to a quantum state with energy between the optimal classical cut and the maximal relaxed energy. The second rounding protocol is deterministic and is based on the estimation of Pauli observables. The proposed quantum relaxations inherit memory compression from quantum random access codes, which allowed us to test the performances of the methods presented for 3-regular random graphs and a design problem motivated by industry for sizes up to 40 nodes, on superconducting quantum processors.
Integer Linear Programs (ILPs) are a flexible and ubiquitous model for discrete optimization problems. Solving ILPs is \textsf{NP-Hard} yet of great practical importance. Super-quadratic quantum speedups for ILPs have been difficult to obtain because classical algorithms for many-constraint ILPs are global and exhaustive, whereas quantum frameworks that offer super-quadratic speedup exploit local structure of the objective and feasible set. We address this via quantum algorithms for Gomory's group relaxation. The group relaxation of an ILP is obtained by dropping nonnegativity on variables that are positive in the optimal solution of the linear programming (LP) relaxation, while retaining integrality of the decision variables. We present a competitive feasibility-preserving classical local-search algorithm for the group relaxation, and a corresponding quantum algorithm that, under reasonable technical conditions, achieves a super-quadratic speedup. When the group relaxation satisfies a nondegeneracy condition analogous to, but stronger than, LP non-degeneracy, our approach yields the optimal solution to the original ILP. Otherwise, the group relaxation tightens bounds on the optimal objective value of the ILP, and can improve downstream branch-and-cut by reducing the integrality gap; we numerically observe this on several practically relevant ILPs. To achieve these results, we derive efficiently constructible constraint-preserving mixers for the group relaxation with favorable spectral properties, which are of independent interest.
To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution. If the potential of quantum computing is realized, it can be expected that in particular finding high-quality solutions for hard problems can be done fast. Still, near-future quantum hardware considerably limits the size of treatable problems. In this work, we go one step into integrating the potentials of quantum and classical techniques for combinatorial optimization. We propose a hybrid heuristic for the weighted maximum-cut problem and for quadratic unconstrained binary optimization. The heuristic employs a linear programming relaxation, rendering it well-suited for integration into exact branch-and-cut algorithms. For large instances, we reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. Moreover, we improve the applicability of depth-1 QAOA, a parameterized quantum algorithm, by deriving a parameter estimate for arbitrary instances. We present numerous computational results from real quantum hardware.