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:2309.12887 · Quantum Information and Computation

New Approaches to Complexity via Quantum Graphs

Eric Culf, Arthur Mehta

Published Dec 1, 2025• 12 citations
arXivHTMLPDF

Abstract

Abstract Problems based on the structure of graphs—for example, finding cliques, independent sets, or colorings—are of fundamental importance in classical complexity. Defining well-formulated decision problems for quantum graphs, which are an operator system generalization of graphs, presents several technical challenges. Consequently, the connections between quantum graphs and complexity have been underexplored. In this work, we introduce and study the clique problem for quantum graphs. Our approach utilizes a well-known connection between quantum graphs and quantum channels. The inputs for our problems are presented as quantum channels induced by circuits, which implicitly determine a corresponding quantum graph. We show that when quantifying over all channels, this problem is complete for QMA(2); in fact, it remains QMA(2) -complete when restricted to channels that are probabilistic mixtures of entanglement-breaking and partial trace channels. Quantifying over a subset of entanglementbreaking channels, this problem becomes QMA-complete, and restricting further to deterministic or classical noisy channels gives rise to complete problems for NP and MA, respectively. In this way, we exhibit a classical complexity problem whose natural quantization is QMA(2), rather than QMA, and provide the first problem that allows for a direct comparison of the classes QMA(2), QMA, MA, and NP by quantifying over increasingly larger families of instances. We use methods that are inspired by self-testing to provide a direct proof of QMA(2)-completeness, rather than reducing to a previously studied complete problem. We also give a new proof of the celebrated reduction of QMA( k ) to QMA(2). In parallel, we study a version of the closely related independent set problem for quantum graphs, and provide preliminary evidence that it may be in general weaker in complexity, contrasting to the classical case.

DOI
10.2478/qic-2025-0026

Related papers

On the Complexity of Computing Zero-Error and Holevo Capacity of Quantum Channels

Salman Beigi, Peter W. Shor

One of the main problems in quantum complexity theory is that our understanding of the theory of QMA-completeness is not as rich as its classical analogue, the NP- completeness. In this paper we consider the clique problem in graphs, which is NP- complete, and try to find its quantum analogue. We show that, quantum clique problem can be defined as follows; Given a quantum channel, decide whether there are k states that are distinguishable, with no error, after passing through channel. This definition comes from reconsidering the clique problem in terms of the zero-error capacity of graphs, and then redefining it in quantum information theory. We prove that, quantum clique problem is QMA-complete. In the second part of paper, we consider the same problem for the Holevo capacity. We prove that computing the Holevo capacity as well as the minimum entropy of a quantum channel is NP-complete. Also, we show these results hold even if the set of quantum channels is restricted to entanglement breaking ones.

arXiv:0709.2090•Sep 13, 2007•82 citations

On the Complexity of Computing Zero-Error and Holevo Capacity of Quantum Channels

Salman BeigiPeter, W. Shor

One of the main problems in quantum complexity theory is that our understanding of the theory of QMA-completeness is not as rich as its classical analogue, the NPcompleteness. In this paper we consider the clique problem in graphs, which is NPcomplete, and try to find its quantum analogue. We show that, quantum clique problem can be defined as follows; Given a quantum channel, decide whether there are k states that are distinguishable, with no error, after passing through channel. This definition comes from reconsidering the clique problem in terms of the zero-error capacity of graphs, and then redefining it in quantum information theory. We prove that, quantum clique problem is QMA-complete. In the second part of paper, we consider the same problem for the Holevo capacity. We prove that computing the Holevo capacity as well as the minimum entropy of a quantum channel is NP-complete. Also, we show these results hold even if the set of quantum channels is restricted to entanglement breaking ones.

•Jan 1, 2008•63 citations

The Power of Unentangled Quantum Proofs with Non-negative Amplitudes

Fernando Granha Jeronimo, Pei Wu

Quantum entanglement is a fundamental property of quantum mechanics and it serves as a basic resource in quantum computation and information. Despite its importance, the power and limitations of quantum entanglement are far from being fully understood. Here, we study entanglement via the lens of computational complexity. This is done by studying quantum generalizations of the class NP with multiple unentangled quantum proofs, the so-called QMA(2) and its variants. The complexity of QMA(2) is known to be closely connected to a variety of problems such as deciding if a state is entangled and several classical optimization problems. However, determining the complexity of QMA(2) is a longstanding open problem, and only the trivial complexity bounds ⊆ (2) ⊆ are known.

arXiv:2402.18790•ACM Symposium on Theory of Computing (STOC)•May 16, 2023•16 citations

Unification of Quantum Graph Properties

Gian Luca Spitzer

Many properties of classical graphs are defined in terms of subsets of the vertex set. Examples include connected components, which are subsets $X \subseteq V(G)$ such that $X \times X^c$ and $E(G)$ are disjoint, or independent sets, for which $X \times X$ and $E(G)$ are disjoint. Direct generalisations of these definitions to quantum graphs are difficult to achieve, since the natural notion of subsets of a quantum set is much too rigid. As a consequence, approaches to generalising these classical properties to the quantum setting have been eclectic. In some cases, multiple inequivalent definitions of the same notion are in use. We introduce a natural and well-motivated alternative definition of subsets of a quantum set. Building on this, we propose unified definitions of quantum graph properties as straightforward generalisations of the classical definitions. We recover this way the established notions of colourings and connected components. For independent sets and cliques, our approach suggests variations that diverge from existing definitions, but address some of their counterintuitive properties. We nevertheless show how to recover an important existing definition of independent sets in our framework.

math.OACross-listedarXiv:2607.28024•Jul 31, 2026

Two QCMA-complete problems

Paweł Wocjan, Dominik Janzing, T. Beth

QMA and QCMA are possible quantum analogues of the complexity class NP. In QMA the proof is a quantum state and the verification is a quantum circuit. In contrast, in QCMA the proof is restricted to be a classical state. It is not known whether QMA strictly contains QCMA. Here we show that two known QMA-complete problems can be modified to QCMA-complete problems in a natural way: (1) Deciding whether a 3-local Hamiltonian has low energy states (with energy smaller than a given value) that can be prepared with at most k elementary gates is QCMA-complete, whereas it is QMA-complete when the restriction on the complexity of preparation is dropped. (2) Deciding whether a (classically described) quantum circuit does not act as the identity on all basis states is QCMA-complete. It is QMA-complete to decide whether it does not act on all states as the identity.

arXiv:quant-ph/0305090•Quantum Information and Computation•Nov 1, 2003•34 citations

Quantum proof systems and entanglement theory

Salman Abolfathe Beikidezfuli

Quantum complexity theory is important from the point of view of not only theory of computation but also quantum information theory. In particular, quantum multi-prover interactive proof systems are defined based on complexity theory notions, while their characterization can be formulated using LOCC operations. On the other hand, the main resource in quantum information theory is entanglement, which can be considered as a monotonic decreasing quantity under LOCC maps. Indeed, any result in quantum proof systems can be translated to entanglement theory, and vice versa. In this thesis I mostly focus on quantum Merlin-Arthur games as a proof system in quantum complexity theory. I present a new complete problem for the complexity class QMA. I also show that computing both the Holevo capacity and the minimum output entropy of quantum channels are NP-hard. Then I move to the multiple-Merlin-Arthur games and show that assuming some additivity conjecture for entanglement of formation, we can amplify the gap in QMA(2) protocols. Based on the same assumption, I show that the QMA(k)-hierarchy collapses to QMA(2). I also prove that QMAlog(2), which is defined the same as QMA(2) except that the size of witnesses is logarithmic, with the gap n-(3+e) contains NP. Finally, motivated by the previous results, I show that the positive partial transpose test gives no bound on the trace distance of a given bipartite state from the set of separable states.

•Jan 1, 2009•0 citations
Abstract Problems based on the structure of graphs—for example, finding cliques, independent sets, or colorings—are of fundamental importance in classical complexity. Defining well-formulated decision problems for quantum graphs, which are an operator system generalization of graphs, presents several technical challenges. Consequently, the connections between quantum graphs and complexity have been underexplored. In this work, we introduce and study the clique problem for quantum graphs. Our approach utilizes a well-known connection between quantum graphs and quantum channels. The inputs for our problems are presented as quantum channels induced by circuits, which implicitly determine a corresponding quantum graph. We show that when quantifying over all channels, this problem is complete for QMA(2); in fact, it remains QMA(2) -complete when restricted to channels that are probabilistic mixtures of entanglement-breaking and partial trace channels. Quantifying over a subset of entanglementbreaking channels, this problem becomes QMA-complete, and restricting further to deterministic or classical noisy channels gives rise to complete problems for NP and MA, respectively. In this way, we exhibit a classical complexity problem whose natural quantization is QMA(2), rather than QMA, and provide the first problem that allows for a direct comparison of the classes QMA(2), QMA, MA, and NP by quantifying over increasingly larger families of instances. We use methods that are inspired by self-testing to provide a direct proof of QMA(2)-completeness, rather than reducing to a previously studied complete problem. We also give a new proof of the celebrated reduction of QMA( k ) to QMA(2). In parallel, we study a version of the closely related independent set problem for quantum graphs, and provide preliminary evidence that it may be in general weaker in complexity, contrasting to the classical case.
One of the main problems in quantum complexity theory is that our understanding of the theory of QMA-completeness is not as rich as its classical analogue, the NP- completeness. In this paper we consider the clique problem in graphs, which is NP- complete, and try to find its quantum analogue. We show that, quantum clique problem can be defined as follows; Given a quantum channel, decide whether there are k states that are distinguishable, with no error, after passing through channel. This definition comes from reconsidering the clique problem in terms of the zero-error capacity of graphs, and then redefining it in quantum information theory. We prove that, quantum clique problem is QMA-complete. In the second part of paper, we consider the same problem for the Holevo capacity. We prove that computing the Holevo capacity as well as the minimum entropy of a quantum channel is NP-complete. Also, we show these results hold even if the set of quantum channels is restricted to entanglement breaking ones.
One of the main problems in quantum complexity theory is that our understanding of the theory of QMA-completeness is not as rich as its classical analogue, the NPcompleteness. In this paper we consider the clique problem in graphs, which is NPcomplete, and try to find its quantum analogue. We show that, quantum clique problem can be defined as follows; Given a quantum channel, decide whether there are k states that are distinguishable, with no error, after passing through channel. This definition comes from reconsidering the clique problem in terms of the zero-error capacity of graphs, and then redefining it in quantum information theory. We prove that, quantum clique problem is QMA-complete. In the second part of paper, we consider the same problem for the Holevo capacity. We prove that computing the Holevo capacity as well as the minimum entropy of a quantum channel is NP-complete. Also, we show these results hold even if the set of quantum channels is restricted to entanglement breaking ones.
Quantum entanglement is a fundamental property of quantum mechanics and it serves as a basic resource in quantum computation and information. Despite its importance, the power and limitations of quantum entanglement are far from being fully understood. Here, we study entanglement via the lens of computational complexity. This is done by studying quantum generalizations of the class NP with multiple unentangled quantum proofs, the so-called QMA(2) and its variants. The complexity of QMA(2) is known to be closely connected to a variety of problems such as deciding if a state is entangled and several classical optimization problems. However, determining the complexity of QMA(2) is a longstanding open problem, and only the trivial complexity bounds ⊆ (2) ⊆ are known.
Many properties of classical graphs are defined in terms of subsets of the vertex set. Examples include connected components, which are subsets X⊆V(G)X \subseteq V(G)X⊆V(G) such that X×XcX \times X^cX×Xc and E(G)E(G)E(G) are disjoint, or independent sets, for which X×XX \times XX×X and E(G)E(G)E(G) are disjoint. Direct generalisations of these definitions to quantum graphs are difficult to achieve, since the natural notion of subsets of a quantum set is much too rigid. As a consequence, approaches to generalising these classical properties to the quantum setting have been eclectic. In some cases, multiple inequivalent definitions of the same notion are in use. We introduce a natural and well-motivated alternative definition of subsets of a quantum set. Building on this, we propose unified definitions of quantum graph properties as straightforward generalisations of the classical definitions. We recover this way the established notions of colourings and connected components. For independent sets and cliques, our approach suggests variations that diverge from existing definitions, but address some of their counterintuitive properties. We nevertheless show how to recover an important existing definition of independent sets in our framework.
QMA and QCMA are possible quantum analogues of the complexity class NP. In QMA the proof is a quantum state and the verification is a quantum circuit. In contrast, in QCMA the proof is restricted to be a classical state. It is not known whether QMA strictly contains QCMA. Here we show that two known QMA-complete problems can be modified to QCMA-complete problems in a natural way: (1) Deciding whether a 3-local Hamiltonian has low energy states (with energy smaller than a given value) that can be prepared with at most k elementary gates is QCMA-complete, whereas it is QMA-complete when the restriction on the complexity of preparation is dropped. (2) Deciding whether a (classically described) quantum circuit does not act as the identity on all basis states is QCMA-complete. It is QMA-complete to decide whether it does not act on all states as the identity.
Quantum complexity theory is important from the point of view of not only theory of computation but also quantum information theory. In particular, quantum multi-prover interactive proof systems are defined based on complexity theory notions, while their characterization can be formulated using LOCC operations. On the other hand, the main resource in quantum information theory is entanglement, which can be considered as a monotonic decreasing quantity under LOCC maps. Indeed, any result in quantum proof systems can be translated to entanglement theory, and vice versa. In this thesis I mostly focus on quantum Merlin-Arthur games as a proof system in quantum complexity theory. I present a new complete problem for the complexity class QMA. I also show that computing both the Holevo capacity and the minimum output entropy of quantum channels are NP-hard. Then I move to the multiple-Merlin-Arthur games and show that assuming some additivity conjecture for entanglement of formation, we can amplify the gap in QMA(2) protocols. Based on the same assumption, I show that the QMA(k)-hierarchy collapses to QMA(2). I also prove that QMAlog(2), which is defined the same as QMA(2) except that the size of witnesses is logarithmic, with the gap n-(3+e) contains NP. Finally, motivated by the previous results, I show that the positive partial transpose test gives no bound on the trace distance of a given bipartite state from the set of separable states.