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:2409.20028 · Leibniz international proceedings in informatics

A Quantum Unique Games Conjecture

Hamoon Mousavi, Taro Spirig

Published Sep 30, 2024• 6 citations
arXivHTMLPDF

Abstract

After the NP-hardness of computational problems such as 3SAT and MaxCut was established, a natural next step was to explore whether these problems remain hard to approximate. While the quantum extensions of some of these problems are known to be hard-indeed undecidable-their inapproximability remains largely unresolved. In this work, we introduce definitions for the quantum extensions of Label-Cover and Unique-Label-Cover. We show that these problems play a similarly crucial role in studying the inapproximability of quantum constraint satisfaction problems as they do in the classical setting.

DOI
10.4230/lipics.itcs.2025.76

Related papers

The Quantum Smooth Label Cover Problem Is Undecidable

Eric Culf, Kieran Mastel, Connor Paddock +1 more

We show that the quantum smooth label cover problem is undecidable and RE-hard. This sharply contrasts the quantum unique label cover problem, which can be decided efficiently by a result of Kempe, Regev, and Toner (FOCS'08). On the other hand, our result aligns with the RE-hardness of the quantum label cover problem, which follows from the celebrated MIP* = RE result of Ji, Natarajan, Vidick, Wright, and Yuen (ACM'21). Additionally, we show that the quantum oracularized smooth label cover problem is RE-hard. Our second result fits with the alternative quantum unique games conjecture recently proposed by Mousavi and Spirig (ITCS'25) on the RE-hardness of the quantum oracularized unique label cover problem. Our proof techniques include a quantum version of Feige's reduction from 3SAT to 3SAT5 (STOC'96) for BCSMIP*-protocols, which may be of independent interest.

arXiv:2510.03477•Leibniz international proceedings in informatics•Oct 3, 2025•2 citations

Quasi-quantum states and the quasi-quantum PCP theorem

Arad, Itai, Miklós Sántha

In this work we define a new classical constraint satisfaction problem that shares many of the properties of the quantum local Hamiltonian problem, distinguishing it from the usual classical k-SAT problem. The problem consists of minimizing the number of violated local constraints over a restricted set of distributions of assignments. We show that these distributions can be 1-to-1 mapped to a superset of the quantum states, which we call k-local quasi-quantum states. Nevertheless, we claim that our optimization problem is essentially classical, by proving that it is an NP-complete problem. Interestingly, the optimal distribution shares many of the properties of quantum states. In particular, it is not determined straightforwardly by its local marginals, and consequently, it can be used as a classical toy model to study several aspects of Hamiltonian complexity that are different from their classical counter parts. These include the complexity of 1D systems (which is in P for classical CSPs, but is QMA-hard for quantum systems), and the lack of an easy search-to-decision reduction. Finally, we believe that our model can be used to gain insights into the quantum PCP conjecture. Indeed, while we have shown that approximating the minimal number of unsatisfiable constraints to within an Θ(1) is NP-hard, it is not clear if the problem remains hard if we want to approximate the minimal fraction of unsatisfiable constraints to within an Θ(1); as in the quantum PCP conjecture, naive quantization of the classical proofs does not seem to work.

arXiv:2410.13549•Leibniz international proceedings in informatics•Oct 17, 2024•3 citations

Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT

Steven Heilman

Assuming the Unique Games Conjecture, we show it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of $α_3+ε$ for every $ε>0$, where $α_3\approx.83600811464$ is the approximation ratio of Frieze-Jerrum's polynomial-time algorithm from 1995. That is, we prove sharp hardness of approximation for MAX-3-CUT. This result resolves a conjecture of Khot-Kindler-Mossel-O'Donnell from 2004 by proving the three candidate Plurality is Stablest Conjecture for correlations in $[-1/2,2/5]$ and generalizes the Majority is Stablest Theorem of Mossel-O'Donnell-Oleszkiewicz [Annals of Math, 2010]. With a similar strategy we prove: assuming the Unique Games Conjecture, it is NP-hard to approximate the product-state value of Quantum MAX-CUT within a multiplicative factor of $α_{\rm BOV}+ε$ for every $ε>0$, where $α_{\rm BOV}\approx 0.9563372685$ is the approximation ratio of the Briët-de Oliveira Filho-Vallentin algorithm. This sharp hardness result completes the conjectured hardness of Hwang-Neeman-Parekh-Thompson-Wright from 2021 by proving their $S^{k-1}$-valued Borell inequality for correlations in $[-.5843,.5843]$ for all $k\geq3$.

cs.CCCross-listedarXiv:2608.00333•Aug 4, 2026•4 citations

Quantum versions of k-CSP algorithms: a first step towards quantum algorithms for interval-related constraint satisfaction problems

Evgeny Yakovlevich Dantsin, Alexander Wolpert, Владик Крейнович

In data processing, we input the results xi of measuring easy-to-measure quantities xi and use these results to find estimates y = f (x1, . . ., xn) for difficult-to-measure quantities y which are related to xi by a known relation y = f(x1, . . ., xn). Due to measurement inaccuracy, the measured values xi are, in general, different from the (unknown) actual values xi of the measured quantities, hence the result y of data processing is different from the actual value of the quantity y.In many practical situations, we only know the bounds Δi on the measurement errors Δxi [EQUATION] xi - xi. In such situations, we only know that the actual value xi belongs to the interval [xi - Δi, xi + Δi], and we want to know the range of possible values of y. The corresponding problems of interval computations are NP-hard, so solving these problems may take an unrealistically long time. One way to speed up computations is to use quantum computing, and quantum versions of interval computations algorithms have indeed been developed.In many practical situations, we also know some constraints on the possible values of the directly measured quantities x1, . . ., xn. In such situations, we must combine interval techniques with constraint satisfaction techniques. It is therefore desirable to extend quantum interval algorithms to such combinations. As a first step towards this combination, in this paper, we consider quantum algorithms for discrete constraint satisfaction problems.

ACM Symposium on Applied Computing•Apr 23, 2006•0 citations

Approximate Constraint Satisfaction in the Quantum Setting.

Sevag Gharibian

Approximation algorithms for constraint satisfaction problems are a central direction of study in theoretical computer science.In this work, we study approximation algorithms from a quantum perspective in two complementary settings: Classical approximation algorithms for quantum constraint satisfaction problems (quantum CSPs), and quantum algorithms for classical CSPs.Our results are as follows:

•Sep 5, 2018•0 citations

The QMA(2) UniverseComplexity, Entanglement, and Optimization

Fernando Granha Jeronimo, Pei Wu, Itai Leigh

The complexity class QMA(2), featuring two unentangled quantum provers, occupies a central yet poorly understood position in quantum complexity theory. While superficially a modest extension of QMA, unentanglement fundamentally changes both the algorithmic and complexitytheoretic landscape, connecting QMA(2) to deep questions in separability testing, polynomial optimization, and hardness of approximation. Over the past two decades, QMA(2) has inspired a rich body of work spanning restricted verification models, semidefinite and Sum-of-Squares hierarchies, and surprising links to classical problems such as the Unique Games Conjecture. This survey provides an overview of these developments, emphasizing structural insights, algorithmic techniques, and known barriers, while highlighting how progress on QMA(2) continues to illuminate the interplay between quantum information, convex optimization, and classical complexity theory.

ACM SIGACT News•Mar 31, 2026•5 citations
After the NP-hardness of computational problems such as 3SAT and MaxCut was established, a natural next step was to explore whether these problems remain hard to approximate. While the quantum extensions of some of these problems are known to be hard-indeed undecidable-their inapproximability remains largely unresolved. In this work, we introduce definitions for the quantum extensions of Label-Cover and Unique-Label-Cover. We show that these problems play a similarly crucial role in studying the inapproximability of quantum constraint satisfaction problems as they do in the classical setting.
We show that the quantum smooth label cover problem is undecidable and RE-hard. This sharply contrasts the quantum unique label cover problem, which can be decided efficiently by a result of Kempe, Regev, and Toner (FOCS'08). On the other hand, our result aligns with the RE-hardness of the quantum label cover problem, which follows from the celebrated MIP* = RE result of Ji, Natarajan, Vidick, Wright, and Yuen (ACM'21). Additionally, we show that the quantum oracularized smooth label cover problem is RE-hard. Our second result fits with the alternative quantum unique games conjecture recently proposed by Mousavi and Spirig (ITCS'25) on the RE-hardness of the quantum oracularized unique label cover problem. Our proof techniques include a quantum version of Feige's reduction from 3SAT to 3SAT5 (STOC'96) for BCSMIP*-protocols, which may be of independent interest.
In this work we define a new classical constraint satisfaction problem that shares many of the properties of the quantum local Hamiltonian problem, distinguishing it from the usual classical k-SAT problem. The problem consists of minimizing the number of violated local constraints over a restricted set of distributions of assignments. We show that these distributions can be 1-to-1 mapped to a superset of the quantum states, which we call k-local quasi-quantum states. Nevertheless, we claim that our optimization problem is essentially classical, by proving that it is an NP-complete problem. Interestingly, the optimal distribution shares many of the properties of quantum states. In particular, it is not determined straightforwardly by its local marginals, and consequently, it can be used as a classical toy model to study several aspects of Hamiltonian complexity that are different from their classical counter parts. These include the complexity of 1D systems (which is in P for classical CSPs, but is QMA-hard for quantum systems), and the lack of an easy search-to-decision reduction. Finally, we believe that our model can be used to gain insights into the quantum PCP conjecture. Indeed, while we have shown that approximating the minimal number of unsatisfiable constraints to within an Θ(1) is NP-hard, it is not clear if the problem remains hard if we want to approximate the minimal fraction of unsatisfiable constraints to within an Θ(1); as in the quantum PCP conjecture, naive quantization of the classical proofs does not seem to work.
Assuming the Unique Games Conjecture, we show it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of α3+εα_3+εα3​+ε for every ε>0ε>0ε>0, where α3≈.83600811464α_3\approx.83600811464α3​≈.83600811464 is the approximation ratio of Frieze-Jerrum's polynomial-time algorithm from 1995. That is, we prove sharp hardness of approximation for MAX-3-CUT. This result resolves a conjecture of Khot-Kindler-Mossel-O'Donnell from 2004 by proving the three candidate Plurality is Stablest Conjecture for correlations in [−1/2,2/5][-1/2,2/5][−1/2,2/5] and generalizes the Majority is Stablest Theorem of Mossel-O'Donnell-Oleszkiewicz [Annals of Math, 2010]. With a similar strategy we prove: assuming the Unique Games Conjecture, it is NP-hard to approximate the product-state value of Quantum MAX-CUT within a multiplicative factor of αBOV+εα_{\rm BOV}+εαBOV​+ε for every ε>0ε>0ε>0, where αBOV≈0.9563372685α_{\rm BOV}\approx 0.9563372685αBOV​≈0.9563372685 is the approximation ratio of the Briët-de Oliveira Filho-Vallentin algorithm. This sharp hardness result completes the conjectured hardness of Hwang-Neeman-Parekh-Thompson-Wright from 2021 by proving their Sk−1S^{k-1}Sk−1-valued Borell inequality for correlations in [−.5843,.5843][-.5843,.5843][−.5843,.5843] for all k≥3k\geq3k≥3.
In data processing, we input the results xi of measuring easy-to-measure quantities xi and use these results to find estimates y = f (x1, . . ., xn) for difficult-to-measure quantities y which are related to xi by a known relation y = f(x1, . . ., xn). Due to measurement inaccuracy, the measured values xi are, in general, different from the (unknown) actual values xi of the measured quantities, hence the result y of data processing is different from the actual value of the quantity y.In many practical situations, we only know the bounds Δi on the measurement errors Δxi [EQUATION] xi - xi. In such situations, we only know that the actual value xi belongs to the interval [xi - Δi, xi + Δi], and we want to know the range of possible values of y. The corresponding problems of interval computations are NP-hard, so solving these problems may take an unrealistically long time. One way to speed up computations is to use quantum computing, and quantum versions of interval computations algorithms have indeed been developed.In many practical situations, we also know some constraints on the possible values of the directly measured quantities x1, . . ., xn. In such situations, we must combine interval techniques with constraint satisfaction techniques. It is therefore desirable to extend quantum interval algorithms to such combinations. As a first step towards this combination, in this paper, we consider quantum algorithms for discrete constraint satisfaction problems.
The complexity class QMA(2), featuring two unentangled quantum provers, occupies a central yet poorly understood position in quantum complexity theory. While superficially a modest extension of QMA, unentanglement fundamentally changes both the algorithmic and complexitytheoretic landscape, connecting QMA(2) to deep questions in separability testing, polynomial optimization, and hardness of approximation. Over the past two decades, QMA(2) has inspired a rich body of work spanning restricted verification models, semidefinite and Sum-of-Squares hierarchies, and surprising links to classical problems such as the Unique Games Conjecture. This survey provides an overview of these developments, emphasizing structural insights, algorithmic techniques, and known barriers, while highlighting how progress on QMA(2) continues to illuminate the interplay between quantum information, convex optimization, and classical complexity theory.