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

Two Combinatorial MA-Complete Problems

Dorit Aharonov, Alex B. Grilo

Published Mar 29, 2020• 9 citations
arXivHTMLPDF

Abstract

Despite the interest in the complexity class MA, the randomized analog of NP, just a few natural MA-complete problems are known. The first problem was found by (Bravyi and Terhal, SIAM Journal of Computing 2009); it was then followed by (Crosson, Bacon and Brown, PRE 2010) and (Bravyi, Quantum Information and Computation 2015). Surprisingly, two of these problems are defined using terminology from quantum computation, while the third is inspired by quantum computation and keeps a physical terminology. This prevents classical complexity theorists from studying these problems, delaying potential progress, e.g., on the NP vs. MA question. Here, we define two new combinatorial problems and prove their MA-completeness. The first problem, ACAC, gets as input a succinctly described graph, with some marked vertices. The problem is to decide whether there is a connected component with only unmarked vertices, or the graph is far from having this property. The second problem, SetCSP, generalizes standard constraint satisfaction problem (CSP) into constraints involving sets of strings. Technically, our proof that SetCSP is MA-complete is based on an observation by (Aharonov and Grilo, FOCS 2019), in which it was noted that a restricted case of Bravyi and Terhal's problem (namely, the uniform case) is already MA-complete; a simple trick allows to state this restricted case using combinatorial language. The fact that the first, more natural, problem of ACAC is MA-hard follows quite naturally from this proof, while the containment of ACAC in MA is based on the theory of random walks. We notice that the main result of Aharonov and Grilo carries over to the SetCSP problem in a straightforward way, implying that finding a gap-amplification procedure for SetCSP (as in Dinur's PCP proof) is equivalent to MA=NP. This provides an alternative new path towards the major problem of derandomizing MA.

DOI
10.4230/lipics.itcs.2021.36

Related papers

Stoquastic PCP vs. Randomness

Dorit Aharonov, Alex B. Grilo

The derandomization of MA, the probabilistic version of NP, is a long standing open question. In this work, we connect this problem to a variant of another major problem: the quantum PCP conjecture. Our connection goes through the surprising quantum characterization of MA by Bravyi and Terhal. They proved the MA-completeness of the problem of deciding whether the groundenergy of a uniform stoquastic local Hamiltonian is zero or inverse polynomial. We show that the gapped version of this problem, i.e. deciding if a given uniform stoquastic local Hamiltonian is frustration-free or has energy at least some constant ε, is in NP. Thus, if there exists a gap-amplification procedure for uniform stoquastic Local Hamiltonians (in analogy to the gap amplification procedure for constraint satisfaction problems in the original PCP theorem), then MA = NP (and vice versa). Furthermore, if this gap amplification procedure exhibits some additional (natural) properties, then P = RP. We feel this work opens up a rich set of new directions to explore, which might lead to progress on both quantum PCP and derandomization. We also provide two small side results of potential interest. First, we are able to generalize our result by showing that deciding if a uniform stoquastic Local Hamiltonian has negligible or constant frustration can be also solved in NP. Additionally, our work reveals a new MA-complete problem which we call SetCSP, stated in terms of classical constraints on strings of bits, which we define in the appendix. As far as we know this is the first (arguably) natural MA-complete problem stated in non-quantum CSP language.

arXiv:1901.05270•Annual Symposium on Foundations of Computer Science•Nov 1, 2019•23 citations

Complexity Classification of Local Hamiltonian Problems

Toby S. Cubitt, Ashley Montanaro

The calculation of ground-state energies of physical systems can be formalized as the $k$-local Hamiltonian problem, which is a natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set $\mathcal{S}$ and scaling them by arbitrary weights. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterize the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset $\mathcal{S}$, the problem falls into one of the following categories: in $\mathsf{ P}$; $\mathsf{NP}$-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or $\mathsf{QMA}$-complete. The third of these classes has been shown to be $\mathsf{StoqMA}$-complete by Bravyi and Hastings. The characterization holds even if $\mathcal{S}$ does not contain any 1-local terms; for example, we prove for the first time $\mathsf{QMA}$-completeness of the Heisenberg and XY interactions in this setting. If $\mathcal{S}$ is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterization that goes beyond 2-local interactions: for any constant $k$, all $k$-local qubit Hamiltonians whose terms are picked from a fixed set $\mathcal{S}$ correspond to problems either in $\mathsf{P}$; polynomial-time equivalent to the Ising model with transverse magnetic fields; or $\mathsf{QMA}$-complete. These results are a quantum analogue of the maximization variant of Schaefer's dichotomy theorem for Boolean constraint satisfaction problems.

arXiv:1311.3161•SIAM Journal on Computing•Jan 1, 2016•129 citations

The status of the quantum PCP conjecture (games version)

Anand Natarajan, Chinmay Nirkhe

In classical complexity theory, the two definitions of probabilistically checkable proofs -- the constraint satisfaction and the nonlocal games version -- are computationally equal in power. In the quantum setting, the situation is far less clear. The result MIP* = RE of Ji et. al. (arXiv:2001.04383) and refinements by Natarajan and Zhang (arXiv:2302.04322) show that multiprover interactive proof systems with polylogarithmically long messages can solve any decision problem in RE, including undecidable problems like the halting problem. These results show that any connection between the "constraint satisfaction" or "Hamiltonian" quantum PCP conjecture and nonlocal games must involve restricting the players in the game to be computationally efficient. This note contains two main results: (1) we give a "quantum games PCP for AM" in the form of a new construction of a succinct MIP* protocol with efficient provers for the canonical AM-complete problem, and (2) we explain an error in the energy amplification procedure of Natarajan and Vidick (arXiv:1710.03062) which invalidates their claim to have constructed a quantum games PCP for a QMA-complete problem. In surveying the obstacles remaining towards a quantum games PCP for QMA, we highlight the importance and challenge of understanding gap amplification for Hamiltonians even when locality is replaced by much weaker constraints, such as bounds on the "Pauli spectrum" of the Hamiltonian. We hope these questions will motivate progress towards new "baby versions" of Hamiltonian quantum PCP conjecture.

arXiv:2403.13084•Mar 19, 2024•12 citations

Approximation Algorithms for QMA-Complete Problems

Sevag Gharibian, Julia Kempe

Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. Here we define a natural approximation version of the QMA-complete local Hamiltonian problem and initiate its study. We present two main results. The first shows that a non-trivial approximation ratio can be obtained in the class NP using product states. The second result (which builds on the first one), gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the "exhaustive sampling method" by Arora et al. [J. Comp. Sys. Sci. 58, p.193 (1999)] to the quantum setting, and might be of independent interest.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2011•11 citations

Quantum Computation, Markov Chains and Combinatorial Optimisation

Danial Dervovic

This thesis addresses two questions related to the title, Quantum Computation, Markov Chains and Combinatorial Optimisation. The first question involves an algorithmic primitive of quantum computation, quantum walks on graphs, and its relation to Markov Chains. Quantum walks have been shown in certain cases to mix faster than their classical counterparts. Lifted Markov chains, consisting of a Markov chain on an extended state space which is projected back down to the original state space, also show considerable speedups in mixing time. We design a lifted Markov chain that in some sense simulates any quantum walk. Concretely, we construct a lifted Markov chain on a connected graph G with n vertices that mixes exactly to the average mixing distribution of a quantum walk on G. Moreover, the mixing time of this chain is the diameter of G. We then consider practical consequences of this result. In the second part of this thesis we address a classic unsolved problem in combinatorial optimisation, graph isomorphism. A theorem of Kozen states that two graphs on n vertices are isomorphic if and only if there is a clique of size n in the weak modular product of the two graphs. Furthermore, a straightforward corollary of this theorem and Lovász’s sandwich theorem is if the weak modular product between two graphs is perfect, then checking if the graphs are isomorphic is polynomial in n. We enumerate the necessary and sufficient conditions for the weak modular product of two simple graphs to be perfect. Interesting cases include complete multipartite graphs and disjoint unions of cliques. We find that all perfect weak modular products have factors that fall into classes of graphs for which testing isomorphism is already known to be polynomial in the number of vertices. Open questions and further research directions are discussed.

•Mar 28, 2020•1 citation

Quantum Expanders: Motivation and Constructions

Avraham Ben-Aroya, Oded Schwartz, Amnon Ta‐Shma

We define quantum expanders in a natural way. We give two constructions of quantum expanders, both based on classical expander constructions. The first construction is algebraic, and is based on the construction of Cayley Ramanujan graphs over the group PGL(2, q) given by Lubotzky et al. (1988). The second construction is combinatorial, and is based on a quantum variant of the Zig-Zag product introduced by Reingold et al. (2000). Both constructions are of constant degree, and the second one is explicit. Using quantum expanders, we characterize the complexity of comparing and estimating quantum entropies. Specifically, we consider the following task: given two mixed states, each given by a quantum circuit generating it, decide which mixed state has more entropy. We show that this problem is QSZK-complete (where QSZK is the class of languages having a zero-knowledge quantum interactive protocol). This problem is very well motivated from a physical point of view. Our proof resembles the classical proof that the entropy difference problem is SZK-complete, but crucially depends on the use of quantum expanders.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2008•16 citations
Despite the interest in the complexity class MA, the randomized analog of NP, just a few natural MA-complete problems are known. The first problem was found by (Bravyi and Terhal, SIAM Journal of Computing 2009); it was then followed by (Crosson, Bacon and Brown, PRE 2010) and (Bravyi, Quantum Information and Computation 2015). Surprisingly, two of these problems are defined using terminology from quantum computation, while the third is inspired by quantum computation and keeps a physical terminology. This prevents classical complexity theorists from studying these problems, delaying potential progress, e.g., on the NP vs. MA question. Here, we define two new combinatorial problems and prove their MA-completeness. The first problem, ACAC, gets as input a succinctly described graph, with some marked vertices. The problem is to decide whether there is a connected component with only unmarked vertices, or the graph is far from having this property. The second problem, SetCSP, generalizes standard constraint satisfaction problem (CSP) into constraints involving sets of strings. Technically, our proof that SetCSP is MA-complete is based on an observation by (Aharonov and Grilo, FOCS 2019), in which it was noted that a restricted case of Bravyi and Terhal's problem (namely, the uniform case) is already MA-complete; a simple trick allows to state this restricted case using combinatorial language. The fact that the first, more natural, problem of ACAC is MA-hard follows quite naturally from this proof, while the containment of ACAC in MA is based on the theory of random walks. We notice that the main result of Aharonov and Grilo carries over to the SetCSP problem in a straightforward way, implying that finding a gap-amplification procedure for SetCSP (as in Dinur's PCP proof) is equivalent to MA=NP. This provides an alternative new path towards the major problem of derandomizing MA.
The derandomization of MA, the probabilistic version of NP, is a long standing open question. In this work, we connect this problem to a variant of another major problem: the quantum PCP conjecture. Our connection goes through the surprising quantum characterization of MA by Bravyi and Terhal. They proved the MA-completeness of the problem of deciding whether the groundenergy of a uniform stoquastic local Hamiltonian is zero or inverse polynomial. We show that the gapped version of this problem, i.e. deciding if a given uniform stoquastic local Hamiltonian is frustration-free or has energy at least some constant ε, is in NP. Thus, if there exists a gap-amplification procedure for uniform stoquastic Local Hamiltonians (in analogy to the gap amplification procedure for constraint satisfaction problems in the original PCP theorem), then MA = NP (and vice versa). Furthermore, if this gap amplification procedure exhibits some additional (natural) properties, then P = RP. We feel this work opens up a rich set of new directions to explore, which might lead to progress on both quantum PCP and derandomization. We also provide two small side results of potential interest. First, we are able to generalize our result by showing that deciding if a uniform stoquastic Local Hamiltonian has negligible or constant frustration can be also solved in NP. Additionally, our work reveals a new MA-complete problem which we call SetCSP, stated in terms of classical constraints on strings of bits, which we define in the appendix. As far as we know this is the first (arguably) natural MA-complete problem stated in non-quantum CSP language.
The calculation of ground-state energies of physical systems can be formalized as the kkk-local Hamiltonian problem, which is a natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S\mathcal{S}S and scaling them by arbitrary weights. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterize the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S\mathcal{S}S, the problem falls into one of the following categories: in P\mathsf{ P}P; NP\mathsf{NP}NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA\mathsf{QMA}QMA-complete. The third of these classes has been shown to be StoqMA\mathsf{StoqMA}StoqMA-complete by Bravyi and Hastings. The characterization holds even if S\mathcal{S}S does not contain any 1-local terms; for example, we prove for the first time QMA\mathsf{QMA}QMA-completeness of the Heisenberg and XY interactions in this setting. If S\mathcal{S}S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterization that goes beyond 2-local interactions: for any constant kkk, all kkk-local qubit Hamiltonians whose terms are picked from a fixed set S\mathcal{S}S correspond to problems either in P\mathsf{P}P; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA\mathsf{QMA}QMA-complete. These results are a quantum analogue of the maximization variant of Schaefer's dichotomy theorem for Boolean constraint satisfaction problems.
In classical complexity theory, the two definitions of probabilistically checkable proofs -- the constraint satisfaction and the nonlocal games version -- are computationally equal in power. In the quantum setting, the situation is far less clear. The result MIP* = RE of Ji et. al. (arXiv:2001.04383) and refinements by Natarajan and Zhang (arXiv:2302.04322) show that multiprover interactive proof systems with polylogarithmically long messages can solve any decision problem in RE, including undecidable problems like the halting problem. These results show that any connection between the "constraint satisfaction" or "Hamiltonian" quantum PCP conjecture and nonlocal games must involve restricting the players in the game to be computationally efficient. This note contains two main results: (1) we give a "quantum games PCP for AM" in the form of a new construction of a succinct MIP* protocol with efficient provers for the canonical AM-complete problem, and (2) we explain an error in the energy amplification procedure of Natarajan and Vidick (arXiv:1710.03062) which invalidates their claim to have constructed a quantum games PCP for a QMA-complete problem. In surveying the obstacles remaining towards a quantum games PCP for QMA, we highlight the importance and challenge of understanding gap amplification for Hamiltonians even when locality is replaced by much weaker constraints, such as bounds on the "Pauli spectrum" of the Hamiltonian. We hope these questions will motivate progress towards new "baby versions" of Hamiltonian quantum PCP conjecture.
Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. Here we define a natural approximation version of the QMA-complete local Hamiltonian problem and initiate its study. We present two main results. The first shows that a non-trivial approximation ratio can be obtained in the class NP using product states. The second result (which builds on the first one), gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the "exhaustive sampling method" by Arora et al. [J. Comp. Sys. Sci. 58, p.193 (1999)] to the quantum setting, and might be of independent interest.
This thesis addresses two questions related to the title, Quantum Computation, Markov Chains and Combinatorial Optimisation. The first question involves an algorithmic primitive of quantum computation, quantum walks on graphs, and its relation to Markov Chains. Quantum walks have been shown in certain cases to mix faster than their classical counterparts. Lifted Markov chains, consisting of a Markov chain on an extended state space which is projected back down to the original state space, also show considerable speedups in mixing time. We design a lifted Markov chain that in some sense simulates any quantum walk. Concretely, we construct a lifted Markov chain on a connected graph G with n vertices that mixes exactly to the average mixing distribution of a quantum walk on G. Moreover, the mixing time of this chain is the diameter of G. We then consider practical consequences of this result. In the second part of this thesis we address a classic unsolved problem in combinatorial optimisation, graph isomorphism. A theorem of Kozen states that two graphs on n vertices are isomorphic if and only if there is a clique of size n in the weak modular product of the two graphs. Furthermore, a straightforward corollary of this theorem and Lovász’s sandwich theorem is if the weak modular product between two graphs is perfect, then checking if the graphs are isomorphic is polynomial in n. We enumerate the necessary and sufficient conditions for the weak modular product of two simple graphs to be perfect. Interesting cases include complete multipartite graphs and disjoint unions of cliques. We find that all perfect weak modular products have factors that fall into classes of graphs for which testing isomorphism is already known to be polynomial in the number of vertices. Open questions and further research directions are discussed.
We define quantum expanders in a natural way. We give two constructions of quantum expanders, both based on classical expander constructions. The first construction is algebraic, and is based on the construction of Cayley Ramanujan graphs over the group PGL(2, q) given by Lubotzky et al. (1988). The second construction is combinatorial, and is based on a quantum variant of the Zig-Zag product introduced by Reingold et al. (2000). Both constructions are of constant degree, and the second one is explicit. Using quantum expanders, we characterize the complexity of comparing and estimating quantum entropies. Specifically, we consider the following task: given two mixed states, each given by a quantum circuit generating it, decide which mixed state has more entropy. We show that this problem is QSZK-complete (where QSZK is the class of languages having a zero-knowledge quantum interactive protocol). This problem is very well motivated from a physical point of view. Our proof resembles the classical proof that the entropy difference problem is SZK-complete, but crucially depends on the use of quantum expanders.