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

QMA-complete problems

Adam D. Bookatz

Published May 1, 2014• 72 citations
arXivHTMLPDF

Abstract

In this paper we give an overview of the quantum computational complexity class QMA and a description of known QMA-complete problems to date (The reader is invited to share more proven QMA-complete problems with the author). Such problems are believed to be difficult to solve, even with a quantum computer, but have the property that if a purported solution to the problem is given, a quantum computer would easily be able to verify whether it is correct. An attempt has been made to make this paper as self-contained as possible so that it can be accessible to computer scientists, physicists, mathematicians, and quantum chemists. Problems of interest to all of these professions can be found here.

DOI
10.26421/qic14.5-6-1

Related papers

On perfect completeness for QMA

Scott Aaronson

Whether the class QMA (Quantum Merlin Arthur)\ is equal to QMA_1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult,\ by using ideas from real analysis to give a "quantum" relative to which QMA \neq QMA_1. As a byproduct, we find that there are facts about quantum complexity classes that are classically relativizing but not quantumly relativizing, among them such "trivial" containments as BQP \subseteq ZQEXP.

arXiv:0806.0450•Quantum Information and Computation•Jan 1, 2009•45 citations

On Perfect Completeness for QMA

Scott Aaronson

Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with onesided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a "quantum oracle" relative to which QMA ≠ QMA1. As a byproduct, we find that there are facts about quantum complexity classes that are classically relativizing but not quantumly relativizing, among them such "trivial" containments as BQP ⊆ ZQEXP.

•Jun 3, 2008•4 citations

On Physical Problems that are Slightly More Difficult than QMA

Andris Ambainis

We study the complexity of computational problems from quantum physics. Typically, they are studied using the complexity class QMA (quantum counterpart of NP) but some natural computational problems appear to be slightly harder than QMA. We introduce new complexity classes consisting of problems that are solvable with a small number of queries to a QMA oracle and use these complexity classes to quantify the complexity of several natural computational problems (for example, the complexity of estimating the spectral gap of a Hamiltonian).

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2014•32 citations

Quantum Computing: Solving Complex Problems

David Peter Divincenzo

One of the motivating ideas of quantum computation was that there could be a new kind of machine that would solve hard problems in quantum mechanics. There has been significant progress towards the experimental realization of these machines (which I will review), but there are still many questions about how such a machine could solve computational problems of interest in quantum physics. New categorizations of the complexity of computational problems have now been invented to describe quantum simulation. The bad news is that some of these problems are believed to be intractable even on a quantum computer, falling into a quantum analog of the NP class. The good news is that there are many other new classifications of tractability that may apply to several situations of physical interest.

•Apr 11, 2007•0 citations

The Deutsch-Josza algorithm for n-qudits

Gabriela Mogos

Abstract: Over the last decade has been a lot of interest in new types of computable machines, due partly over the fears on conventional, classical, computing. Research by leading physicists, mathematicians and computer scientists has shown quantum computers could be the future, as they may be able to solve some computationally difficult problems much faster than is currently possible on a classical computer. David Deutsch has already created a working model for a quantum computer, the quantum Turing machine or QTM Deutsch [1985]. This has been proved as a model for computation on a quantum and has allowed algorithms to be developed. Deutsch-Josza’s algorithm, as all known quantum algorithms that provide exponential speedup over classical systems do, answers a question about a global property of a solution space. This paper describes the generalization of the Deutsch-Josza algorithm to n d-dimensional quantum systems or qudits. Key–Words: quantum computing, quantum dits, quantum algorithm 1

•Nov 21, 2007•2 citations

Quantum Computing Explained

David McMahon

A self-contained treatment of the fundamentals of quantum computing This clear, practical book takes quantum computing out of the realm of theoretical physics and teaches the fundamentals of the field to students and professionals who have not had training in quantum computing or quantum information theory, including computer scientists, programmers, electrical engineers, mathematicians, physics students, and chemists. The author cuts through the conventions of typical jargon-laden physics books and instead presents the material through his unique how-to approach and friendly, conversational style. Readers will learn how to carry out calculations with explicit details and will gain a fundamental grasp of: * Quantum mechanics * Quantum computation * Teleportation * Quantum cryptography * Entanglement * Quantum algorithms * Error correction A number of worked examples are included so readers can see how quantum computing is done with their own eyes, while answers to similar end-of-chapter problems are provided for readers to check their own work as they learn to master the information. Ideal for professionals and graduate-level students alike, Quantum Computing Explained delivers the fundamentals of quantum computing readers need to be able to understand current research papers and go on to study more advanced quantum texts.

Wiley eBooks•Mar 23, 2007•331 citations
In this paper we give an overview of the quantum computational complexity class QMA and a description of known QMA-complete problems to date (The reader is invited to share more proven QMA-complete problems with the author). Such problems are believed to be difficult to solve, even with a quantum computer, but have the property that if a purported solution to the problem is given, a quantum computer would easily be able to verify whether it is correct. An attempt has been made to make this paper as self-contained as possible so that it can be accessible to computer scientists, physicists, mathematicians, and quantum chemists. Problems of interest to all of these professions can be found here.
Whether the class QMA (Quantum Merlin Arthur)\ is equal to QMA_1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult,\ by using ideas from real analysis to give a "quantum" relative to which QMA \neq QMA_1. As a byproduct, we find that there are facts about quantum complexity classes that are classically relativizing but not quantumly relativizing, among them such "trivial" containments as BQP \subseteq ZQEXP.
We study the complexity of computational problems from quantum physics. Typically, they are studied using the complexity class QMA (quantum counterpart of NP) but some natural computational problems appear to be slightly harder than QMA. We introduce new complexity classes consisting of problems that are solvable with a small number of queries to a QMA oracle and use these complexity classes to quantify the complexity of several natural computational problems (for example, the complexity of estimating the spectral gap of a Hamiltonian).
One of the motivating ideas of quantum computation was that there could be a new kind of machine that would solve hard problems in quantum mechanics. There has been significant progress towards the experimental realization of these machines (which I will review), but there are still many questions about how such a machine could solve computational problems of interest in quantum physics. New categorizations of the complexity of computational problems have now been invented to describe quantum simulation. The bad news is that some of these problems are believed to be intractable even on a quantum computer, falling into a quantum analog of the NP class. The good news is that there are many other new classifications of tractability that may apply to several situations of physical interest.
Abstract: Over the last decade has been a lot of interest in new types of computable machines, due partly over the fears on conventional, classical, computing. Research by leading physicists, mathematicians and computer scientists has shown quantum computers could be the future, as they may be able to solve some computationally difficult problems much faster than is currently possible on a classical computer. David Deutsch has already created a working model for a quantum computer, the quantum Turing machine or QTM Deutsch [1985]. This has been proved as a model for computation on a quantum and has allowed algorithms to be developed. Deutsch-Josza’s algorithm, as all known quantum algorithms that provide exponential speedup over classical systems do, answers a question about a global property of a solution space. This paper describes the generalization of the Deutsch-Josza algorithm to n d-dimensional quantum systems or qudits. Key–Words: quantum computing, quantum dits, quantum algorithm 1
A self-contained treatment of the fundamentals of quantum computing This clear, practical book takes quantum computing out of the realm of theoretical physics and teaches the fundamentals of the field to students and professionals who have not had training in quantum computing or quantum information theory, including computer scientists, programmers, electrical engineers, mathematicians, physics students, and chemists. The author cuts through the conventions of typical jargon-laden physics books and instead presents the material through his unique how-to approach and friendly, conversational style. Readers will learn how to carry out calculations with explicit details and will gain a fundamental grasp of: * Quantum mechanics * Quantum computation * Teleportation * Quantum cryptography * Entanglement * Quantum algorithms * Error correction A number of worked examples are included so readers can see how quantum computing is done with their own eyes, while answers to similar end-of-chapter problems are provided for readers to check their own work as they learn to master the information. Ideal for professionals and graduate-level students alike, Quantum Computing Explained delivers the fundamentals of quantum computing readers need to be able to understand current research papers and go on to study more advanced quantum texts.