Approximation Algorithms for Noncommutative CSPs

Noncommutative constraint satisfaction problems (CSPs) are higher-dimensional operator extensions of classical CSPs. Their approximability remains largely unexplored. A notable example of a noncommutative CSP that is not solvable in polynomial time is NC-Max-3-Cut. We present a 0. 864-approximation algorithm for this problem. Our approach extends to a broader class of both classical and noncommutative CSPs. We introduce three key concepts: approximate isometry, relative distribution, and generalized anticommutation, which may be of independent interest.

Authors

• Eric Culf
• Hamoon Mousavi
• Taro Spirig

Keywords

• Computer science
• Quantum computing
• Approximation algorithms
• Polynomials
• Constraint Satisfaction Problem
• Isometry
• Operational Units
• Identity Matrix
• Unit Vector
• Value Of Solution
• Hilbert Space
• Set Of Operations
• Frobenius Norm
• Classical Solution
• Angle Distribution
• Relative Angle
• Unit Circle
• Approximate Ratio
• Eigenspace
• Root Of Unity
• Eigenvalue Distribution
• Pair Of Eigenvalues
• Haar Measure
• Dimensional Limit
• quantum complexity
• constraint satisfaction problems
• noncommutative polynomial optimization