Source-linked AI summary
QMA-complete problems
Adam D. Bookatz
TL;DR
QMA-complete problems are presented as difficult to solve but readily verifiable when a purported solution is supplied. This paper surveys known problems and their categories, concluding with a collection that is broad but not necessarily complete.
Problem
The paper addresses the need for an overview of known QMA-complete problems, a class of problems described as difficult to solve but easy for a quantum computer to verify given a purported solution.
Source: §1.1 · p. 2Method
The paper surveys QMA and describes known QMA-complete problems, including circuit, channel, and Hamiltonian examples.
Source: §1.1 · p. 2, §2 · pp. 5–6, §3 · p. 7Results
The survey presents QMA-complete problems across quantum circuit and channel verification, channel-based clique structure, and Hamiltonian ground-state estimation.
Source: §2 · pp. 3, 5, 6, §3 · p. 7Takeaways & Limitations
The paper collects problems of interest to computer scientists, physicists, mathematicians, and quantum chemists in an effort to make the survey self-contained.
Source: §1.2 · p. 3The collection may not include every known QMA- or QMA1-complete problem and excludes classes such as QMA(2) and QCMA.
Source: §1.2 · p. 3
Abstract
from arXiv · showhide
In this paper we give an overview of the quantum computational complexity class QMA and a description of known QMA-complete problems to date. 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.
1 Introduction
The introduction presents QMA as the quantum analogue of witness-verification classes and surveys known QMA-complete problems. It then gives a formal definition and states the paper’s scope and limits.
1.1 Background
- QMA extends the witness-verification idea of NP to quantum computing, using small quantum witnesses checked by an efficient quantum verifier.The verifier’s acceptance decision establishes whether a string belongs to the language with high probability.Source: §1.1 · p. 1
- QMA-completeness began with 5-local Hamiltonian, but far fewer QMA-complete problems are known than NP-complete problems, motivating this survey.The introduction also identifies QCSAT as trivially QMA-complete because QMA is defined using quantum circuits.Source: §1.1 · p. 2
- The paper groups known problems into categories including density matrix consistency, circuit or channel property verification, and Hamiltonian ground-state estimation.The supplied group labels also identify density matrix consistency as C, circuit or channel verification as V, and Hamiltonian estimation as H.Source: §1.1 · p. 2
1.2 Formal definition of QMA
- The formal definition uses a polynomial-time quantum verifier, a polynomial-size witness, and completeness and soundness probabilities separated by an inverse polynomial.The paper describes QMA as a promise-problem class and notes that QMA1 requires perfect acceptance in the yes case.Source: §1.2 · pp. 2–3
- The survey aims to include as many known QMA- and QMA1-complete problems as possible, but acknowledges it may be incomplete and excludes classes such as QMA(2) and QCMA.For fuller problem descriptions and motivations, it directs readers to the cited references.Source: §1.2 · p. 3
2 Quantum circuit/channel property verification
This section surveys QMA-complete problems that test quantum circuits and channels. The examples cover circuit satisfiability, channel properties, encryption, channel-based clique structure, and quantum expansion.
2 Quantum circuit/channel property verification
- Non-equivalence check generalizes non-identity check by comparing two circuits on a chosen common invariant subspace, which may represent an error-correcting code.The section’s other circuit-property examples include mixed-state circuit checks and testing whether a channel is not almost a linear isometry.Source: §2 · p. 4
- QCSAT is QMA-complete, as are small-depth quantum circuit satisfiability and non-identity check.The section also lists quantum circuit satisfiability as a hardness-reduction source for other problems.Source: §2 · pp. 3–4
- Mixed-state non-identity check and quantum circuit testing are listed as hardness sources, while non-isometry testing is QMA-complete for 0 < ϵ < 1/19.Non-isometry testing asks whether a channel fails to be an approximate isometry, defined through its outputs with a reference system.Source: §2 · pp. 4–5
- Detecting insecure quantum encryption is QMA-complete for 0 < ϵ < 1/8, with channels represented as mixed-state circuits.The yes case concerns a large subspace on which encryption outputs remain close to the inputs; the alternative is an ϵ-private channel.Source: §2 · p. 5
- Quantum clique asks for a large set of input states whose outputs under an entanglement-breaking channel are almost orthogonal.The problem is QMA-complete, and its q-c-channel restriction is QMA1-complete when a = 0.Source: §2 · p. 6
- Quantum non-expander asks whether a superoperator fails to rapidly drive density matrices toward the maximally mixed state, and is QMA-complete.The section describes a good expander as rapidly suppressing traceless matrices.Source: §2 · pp. 6–7
3 Hamiltonian ground-state energy estimation
This section defines Hamiltonian energy-estimation problems and surveys their QMA-completeness across locality, geometry, physical constraints, and related variants. It also covers quantum k-SAT as a projector-restricted form of the k-local Hamiltonian problem, including QMA1-completeness results and qudit and stochastic formulations.
3 Hamiltonian ground-state energy estimation
- Estimating the ground-state energy of a k-local Hamiltonian is QMA-complete for k ≥ 2 [23], while the 1-local problem is in P [23].The promise distinguishes an eigenvalue below a from all eigenvalues above b, with b − a ≥ 1/poly(n).Source: §3 · pp. 7–8
- QMA-completeness persists for k = O(log n), for k = 3 with constant-norm terms, and under line, 2D-lattice, and dense-Hamiltonian restrictions.The line result uses 2-local interactions on 8-dimensional qudits; dense instances have ground energy of magnitude Ω(n^k).Source: §3 · pp. 7–8
- The cited results establish QMA-completeness even for interacting bosons under two-body interactions [37], interacting fermions under two-body interactions [38], and Hamiltonians restricted to be real and 2-local.Source: §3 · pp. 7–8
- Estimating the cth eigenvalue is QMA-complete for constant c and k ≥ 3 [18].This is the low-lying excited-energy problem; the cited hardness reduction is from 2-local Hamiltonian.Source: §3 · p. 8
- Estimating the highest energy of a k-local stoquastic Hamiltonian is QMA-complete for k ≥ 3 [18], while finding its lowest energy is in AM.The highest-energy result follows because negating a stochastic Hamiltonian gives a stoquastic Hamiltonian.Source: §3 · pp. 8–9
- The separable k-local Hamiltonian problem is QMA-complete [9] for product states across a specified bipartition.The state must be separable between the two sets of qubits; the hardness reduction is from k-local Hamiltonian.Source: §3 · p. 9
- Several physically relevant 2-local models are QMA-complete, including Ising-type, Heisenberg, Hubbard, and universal-functional DFT problems.The Heisenberg result holds for both signs of its coupling constant; the universal DFT functional problem is QMA-complete by a Turing reduction from the Hubbard model.Source: §3 · pp. 9, 10, 12
- Translationally invariant Hamiltonians are QMA-complete for 3-local interactions on 22-state qudits without necessarily geometric locality, 2-local interactions on poly(n)-state qudits, and O(log n)-local interactions.Separately, 2-local Hamiltonians on a line of 49-state qudits are also QMA-complete.Source: §3 · p. 11
3.1 Quantum k-SAT and its variations
- Quantum k-SAT is QMA1-complete for k ≥ 3 [13], and remains so when projectors are replaced by positive-semidefinite operators with zero ground-state energies and constant norms.The problem is specified using polynomially many k-local projection operators.Source: §3.1 · pp. 12–13
- For k ≥ 3, qudit quantum k-SAT is QMA1-complete because qubit quantum 3-SAT is QMA1-complete.The passage describes this qudit case as trivial; the k = 2 cases are not fully understood.Source: §3.1 · pp. 12–13
- For qudit k-SAT with k = 2, QMA1-completeness holds when d1 ≥ 5 and d2 ≥ 3.Cases with d1 < 5 or d2 = 2 remain open and are known to be NP-hard, except d1 = d2 = 2, which is in P [10].Source: §3.1 · p. 13
- Stochastic k-SAT uses k-local stochastic, Hermitian, positive-semidefinite operators and is QMA1-complete for k = 6 [18].The operators act on n qubits and have norms bounded by poly(n).Source: §3.1 · p. 13
- Stoquastic quantum k-SAT is in MA and MA-complete for k ≥ 6, whereas no connection to projectors is known for stochastic k-SAT.The passage notes that stoquastic operators can be converted to equivalent projectors, unlike the stochastic case.Source: §3.1 · pp. 13–14
4 Density matrix consistency
Density matrix consistency asks whether specified local density matrices can arise from a single global state. Its general, fermionic, and bosonic forms are described as QMA-complete.
4 Density matrix consistency
- Given local density matrices on constant-size qubit subsystems, k-local density matrix consistency asks whether one global density matrix has those marginals.The promise separates exact consistency from cases where every candidate global state has some marginal at trace distance at least b, with b ≥ 1/poly(n).Source: §4 · p. 14
- The general problem is QMA-complete even for k = 2, with a hardness reduction from k-local Hamiltonian [H-1].Its classical analogue, consistency of marginal distributions, is NP-hard.Source: §4 · p. 14
- The fermionic N-representability problem specializes 2-local density matrix consistency to antisymmetric N-fermion states and is QMA-complete [37].The listed setting has N ≤ d ≤ poly(N); its hardness reduction is from 2-local Hamiltonian [H-1] and is a Turing reduction.Source: §4 · pp. 14–15
- Bosonic N-representability specializes 2-local density matrix consistency to symmetric N-boson states and is QMA-complete [37].The listed setting has d ≥ cN for a constant c > 0; its hardness reduction is from 2-local Hamiltonian [H-1] and is a Turing reduction.Source: §4 · pp. 14–15
A Glossary
The glossary records conventions and definitions for recurring mathematical and quantum-computing terms used in the paper. It cautions that these definitions need only suffice for the paper’s purposes.
A Glossary
- The glossary’s definitions are not necessarily the most general or precise possible, but suffice for this paper.Source: A Glossary · p. 15
- A Hamiltonian is Hermitian, generates quantum time evolution, and specifies interactions; its eigenvalues are allowable energies.The ground-state energy is its smallest eigenvalue, and its ith energy is its ith-smallest eigenvalue.Source: A Glossary · p. 15
- The operator norm is the largest singular value and, for a normal matrix, the largest absolute eigenvalue.The trace norm of a normal matrix is the sum of the absolute values of its eigenvalues.Source: A Glossary · p. 15
- A positive-semidefinite matrix is Hermitian with non-negative eigenvalues, while a Hermitian matrix equals its conjugate transpose.A k-local projector is a Hermitian projector acting nontrivially on k qubits; stochastic matrices are non-negative with rows summing to 1, and doubly stochastic matrices also have columns summing to 1.Source: A Glossary · p. 15
- A stoquastic Hamiltonian has non-positive off-diagonal matrix elements in the standard basis.Source: A Glossary · p. 15
- A qudit is a d-state quantum system represented by a unit-normalized vector in C^d, with global phase irrelevant.The glossary calls the d = 2 and d = 3 cases qubits and qutrits, respectively.Source: A Glossary · p. 15
B QMA-hard theorems
The appendix gives a theorem for proving QMA-hardness of quantum-circuit verification problems, then defines quantum circuit testing. It reports that testing is QMA-hard for constant δ.
B QMA-hard theorems
- Quantum circuit testing asks whether a circuit behaves like a member of one circuit family on a large input subspace or like a member of another family on all inputs.The two uniform circuit families must be significantly different; the promise compares circuit actions in trace norm, including reference systems.Source: B QMA-hard theorems · pp. 15–16
- Quantum circuit testing is QMA-hard for constant δ, with a reduction from QCSAT [V-1].The appendix theorem establishes hardness, not QMA-completeness.Source: B QMA-hard theorems · pp. 15–16
C Diagram of QMA-complete problems
Figure 1 schematically groups the QMA-complete problems listed in the paper and shows hardness reductions between them.
C Diagram of QMA-complete problems
- Figure 1 groups the listed QMA-complete problems by category and uses lines to indicate hardness reductions.Source: Figure 1 · p. 16