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:1308.5207 · Mathematical Programming

Approximating the little Grothendieck problem over the orthogonal and unitary groups

Afonso S. Bandeira, Christopher Kennedy, Amit Singer

Published Mar 25, 2016• 45 citations
arXivHTMLPDF
DOI
10.1007/s10107-016-0993-7

Related papers

Approximating the Little Grothendieck Problem over the Unitary and Orthogonal Groups

Afonso S. Bandeira, Christopher Kennedy, Amit Singer

•Aug 23, 2013•2 citations

Representations of orthogonal and unitary groups and nuclear models

V.V. Vanagas

Journal of Mathematical Sciences•Mar 1, 1987•0 citations

The rational approximations of the unitary groups

Ming-Xing Luo, Yun Deng, Xiu‐Bo Chen +1 more

Quantum Information Processing•May 23, 2013•1 citation

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•8 citations

Expanding the reach of quantum optimization with fermionic embeddings

Andrew Zhao, Nicholas C. Rubin

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.

arXiv:2301.01778•Quantum•Aug 28, 2024•2 citations

On the Unitary Group and Associated Operators

Atri Mukhopadhyay

Lecture notes in chemistry•Jan 1, 1989•0 citations
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.
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.