Expanding the reach of quantum optimization with fermionic embeddings

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 \emph{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.

References in corpus (33)

• Adiabatic Quantum Computing
• Hartree-Fock on a superconducting qubit quantum computer
• Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
• Perspectives of quantum annealing: Methods and implementations
• Classical simulation of noninteracting-fermion quantum circuits
• N-representability is QMA-complete
• Matchgates and classical simulation of quantum circuits
• $XY$-mixers: analytical and numerical results for QAOA
• Quantum Simulations of Classical Annealing Processes
• Quantum algorithms to simulate many-body physics of correlated fermions
• Fermionic partial tomography via classical shadows
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Nearly Optimal Measurement Scheduling for Partial Tomography of Quantum States
• Modeling Perceptual Aliasing in SLAM via Discrete-Continuous Graphical Models
• Orbitopes
• Estimation under group actions: recovering orbits from invariants
• Semidefinite descriptions of the convex hull of rotation matrices
• Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values
• Low depth mechanisms for quantum optimization
• Eigenvector Synchronization, Graph Rigidity and the Molecule Problem
• Moments of Wishart-Laguerre and Jacobi ensembles of random matrices: application to the quantum transport problem in chaotic cavities
• Product-state Approximations to Quantum Ground States
• Approximation algorithms for quantum many-body problems
• Group-theoretic error mitigation enabled by classical shadows and symmetries
• The generalized orthogonal Procrustes problem in the high noise regime
• An Improved Approximation Algorithm for Quantum Max-Cut
• Tight Hardness of the Non-commutative Grothendieck Problem
• Beyond product state approximations for a quantum analogue of Max Cut
• Efficient Rounding for the Noncommutative Grothendieck Inequality
• Application of the Level-$2$ Quantum Lasserre Hierarchy in Quantum Approximation Algorithms
• A convex solution to Psiaki's first joint attitude and spin-rate estimation problem
• Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems