Introduction to QMA and Quantum Complexity

Introduction

Classical complexity has a hero problem: NP. A solution is hard to find but easy to check — zip through the candidates and verify. When researchers moved computation into the quantum realm, they asked: what happens to NP?

The answer is QMA — Quantum Merlin Arthur. The name tells you the story: Merlin (the all-powerful prover) sends Arthur (the skeptical verifier) a quantum state as a proof. Arthur runs a polynomial-time quantum computation on it, and with high probability he correctly decides whether the answer is yes or no.

QMA sits above NP in the complexity landscape. Every NP problem is in QMA (a classical bit-string proof is just a boring quantum state), but QMA can harness quantum superposition and entanglement in both the proof and the verification. The landmark hardness result — the Local Hamiltonian problem — shows that QMA has its own NP-complete analogue: a canonical, maximally hard problem from which everything else in QMA can be reduced.

Understanding QMA means understanding the limits of what even quantum computers can do — the frontier where quantum speedups run out of room.

Try It: Verify a Quantum Proof

Below is a 2-local Hamiltonian on 4 qubits. Each edge carries an interaction energy between two qubits. Your task is to assign each qubit a state — |0⟩ or |1⟩ — to minimize the total energy. This is exactly what QMA's central problem asks about quantum systems, but here we restrict to classical bit assignments so you can explore the verification step by hand.

<p class="hint">A <b>2-local Hamiltonian</b> on 4 qubits: each edge has an interaction
energy between two qubits. Click qubits to toggle |0⟩ / |1⟩ and watch the energy
change. Can you reach the <b>minimum energy</b> (ground state)?</p>
<div id="canvas-wrap"><canvas id="canvas" width="340" height="220"></canvas></div>
<div class="energy-row">
  <span>Total energy: <b id="energy-val">—</b></span>
  <span id="energy-label" class="label"></span>
</div>
<div class="btns">
  <button id="btn-find" type="button">Find ground state</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
#canvas-wrap { display: flex; justify-content: center; margin: .4rem 0 .2rem; }
canvas { border-radius: 10px; background: #f4f7fa; border: 1px solid #dde3ea; cursor: pointer; }
.energy-row { display: flex; align-items: center; gap: .8rem; font-size: 1rem; margin: .4rem 0; }
.energy-row b { font-size: 1.15rem; }
.label { font-size: .82rem; font-weight: 600; padding: .15rem .55rem; border-radius: 12px; }
.label.ground { background: #d1fae5; color: #065f46; }
.label.high { background: #fee2e2; color: #991b1b; }
.label.mid { background: #fef3c7; color: #92400e; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin: .4rem 0; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-top: .2rem; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// 2-Local Hamiltonian demo on 4 qubits.
// Each term H_{ij}(s_i, s_j) penalizes certain qubit configurations.
// We use an Ising-like model: H = sum_{(i,j)} J_{ij} * (1 - 2*s_i) * (1 - 2*s_j)
// where s_i in {0,1} and J_{ij} is the coupling strength.
// Negative J -> ferromagnetic (same spin preferred), Positive J -> antiferromagnetic.
// Total energy = sum of all edge terms.

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

// 4 qubits positioned at corners of a square, centered
const qpos = [
  { x: 90,  y: 70 },   // qubit 0
  { x: 250, y: 70 },   // qubit 1
  { x: 250, y: 160 },  // qubit 2
  { x: 90,  y: 160 },  // qubit 3
];

// Edges: [i, j, J_ij, label]
// Negative = ferromagnetic (same-spin = low energy), Positive = antiferromagnetic
const edges = [
  [0, 1, -1.0, '-1'],   // top
  [1, 2,  2.0, '+2'],   // right
  [2, 3, -1.5, '-1.5'], // bottom
  [0, 3,  1.5, '+1.5'], // left
  [0, 2,  1.0, '+1'],   // diagonal
];

// Qubit states: 0 = |0⟩, 1 = |1⟩
const state = [0, 0, 0, 0];
const R = 24; // qubit radius

function spin(s) { return 1 - 2 * s; } // 0->+1, 1->-1

function totalEnergy(st) {
  let E = 0;
  for (const [i, j, J] of edges) E += J * spin(st[i]) * spin(st[j]);
  return E;
}

function groundState() {
  let best = Infinity, bestMask = 0;
  for (let mask = 0; mask < 16; mask++) {
    const st = [mask >> 3 & 1, mask >> 2 & 1, mask >> 1 & 1, mask & 1];
    const E = totalEnergy(st);
    if (E < best) { best = E; bestMask = mask; }
  }
  return bestMask;
}

function edgeEnergy(i, j, J) {
  return J * spin(state[i]) * spin(state[j]);
}

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Draw edges
  for (const [i, j, J, lbl] of edges) {
    const pi = qpos[i], pj = qpos[j];
    const ee = edgeEnergy(i, j, J);
    // Color edge: negative contribution = green tint, positive = red tint
    const t = Math.min(1, Math.abs(ee) / 3);
    if (ee < 0) {
      ctx.strokeStyle = `rgba(16,185,129,${0.3 + 0.5 * t})`;
    } else if (ee > 0) {
      ctx.strokeStyle = `rgba(239,68,68,${0.3 + 0.5 * t})`;
    } else {
      ctx.strokeStyle = '#c0cdd8';
    }
    ctx.lineWidth = 2.5 + 2 * t;
    ctx.beginPath(); ctx.moveTo(pi.x, pi.y); ctx.lineTo(pj.x, pj.y); ctx.stroke();

    // Edge label: coupling constant and contribution
    const mx = (pi.x + pj.x) / 2, my = (pi.y + pj.y) / 2;
    const dx = pj.x - pi.x, dy = pj.y - pi.y;
    const len = Math.sqrt(dx * dx + dy * dy);
    // Offset label perpendicular to edge
    const ox = -dy / len * 14, oy = dx / len * 14;
    ctx.font = '600 11px system-ui, sans-serif';
    ctx.fillStyle = '#555';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText('J=' + lbl, mx + ox, my + oy);
  }

  // Draw qubits
  for (let i = 0; i < 4; i++) {
    const p = qpos[i];
    const s = state[i];
    ctx.beginPath();
    ctx.arc(p.x, p.y, R, 0, 2 * Math.PI);
    ctx.fillStyle = s === 0 ? '#dbeafe' : '#fde68a';
    ctx.fill();
    ctx.strokeStyle = s === 0 ? '#2563eb' : '#d97706';
    ctx.lineWidth = 2.2;
    ctx.stroke();

    ctx.font = '700 15px system-ui, monospace';
    ctx.fillStyle = s === 0 ? '#1e40af' : '#92400e';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(s === 0 ? '|0⟩' : '|1⟩', p.x, p.y);

    // Qubit index
    ctx.font = '500 11px system-ui, sans-serif';
    ctx.fillStyle = '#888';
    ctx.fillText('q' + i, p.x, p.y + R + 12);
  }

  updateEnergy();
}

function updateEnergy() {
  const E = totalEnergy(state);
  const minE = totalEnergy([0,1,1,0]); // we'll compute properly
  document.getElementById('energy-val').textContent = E.toFixed(2);

  // Compute true minimum for comparison
  let best = Infinity;
  for (let mask = 0; mask < 16; mask++) {
    const st = [mask >> 3 & 1, mask >> 2 & 1, mask >> 1 & 1, mask & 1];
    const e = totalEnergy(st); if (e < best) best = e;
  }
  const lbl = document.getElementById('energy-label');
  const status = document.getElementById('status');
  if (Math.abs(E - best) < 0.001) {
    lbl.textContent = 'Ground state!'; lbl.className = 'label ground';
    status.textContent = fmt('✓ You found the ground state energy (%best%)!', { best: best.toFixed(2) });
  } else if (E > best + 4) {
    lbl.textContent = 'High energy'; lbl.className = 'label high';
    status.textContent = fmt('Energy %E%. Ground state is %best%. Keep exploring.', { E: E.toFixed(2), best: best.toFixed(2) });
  } else {
    lbl.textContent = 'Not minimal'; lbl.className = 'label mid';
    status.textContent = fmt('Energy %E%. Ground state is %best%. Can you do better?', { E: E.toFixed(2), best: best.toFixed(2) });
  }
}

canvas.addEventListener('click', function(e) {
  const rect = canvas.getBoundingClientRect();
  const mx = (e.clientX - rect.left) * (W / rect.width);
  const my = (e.clientY - rect.top) * (H / rect.height);
  for (let i = 0; i < 4; i++) {
    const p = qpos[i];
    if ((mx - p.x) ** 2 + (my - p.y) ** 2 < R * R) {
      state[i] ^= 1;
      draw();
      return;
    }
  }
});

document.getElementById('btn-find').addEventListener('click', function() {
  const mask = groundState();
  for (let i = 0; i < 4; i++) state[i] = (mask >> (3 - i)) & 1;
  draw();
  const E = totalEnergy(state);
  document.getElementById('status').textContent =
    fmt('✓ Ground state found by exhaustive search over all 16 configurations. Energy = %E%.', { E: E.toFixed(2) });
  console.log('Ground state:', state.map((s, i) => 'q' + i + '=' + s).join(', '), '| Energy:', E);
});

document.getElementById('btn-reset').addEventListener('click', function() {
  state.fill(0); draw();
  document.getElementById('status').textContent = '';
});

draw();

<p class="hint">A <b>2-local Hamiltonian</b> on 4 qubits: each edge has an interaction
energy between two qubits. Click qubits to toggle |0⟩ / |1⟩ and watch the energy
change. Can you reach the <b>minimum energy</b> (ground state)?</p>
<div id="canvas-wrap"><canvas id="canvas" width="340" height="220"></canvas></div>
<div class="energy-row">
  <span>Total energy: <b id="energy-val">—</b></span>
  <span id="energy-label" class="label"></span>
</div>
<div class="btns">
  <button id="btn-find" type="button">Find ground state</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
#canvas-wrap { display: flex; justify-content: center; margin: .4rem 0 .2rem; }
canvas { border-radius: 10px; background: #f4f7fa; border: 1px solid #dde3ea; cursor: pointer; }
.energy-row { display: flex; align-items: center; gap: .8rem; font-size: 1rem; margin: .4rem 0; }
.energy-row b { font-size: 1.15rem; }
.label { font-size: .82rem; font-weight: 600; padding: .15rem .55rem; border-radius: 12px; }
.label.ground { background: #d1fae5; color: #065f46; }
.label.high { background: #fee2e2; color: #991b1b; }
.label.mid { background: #fef3c7; color: #92400e; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin: .4rem 0; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-top: .2rem; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// 2-Local Hamiltonian demo on 4 qubits.
// Each term H_{ij}(s_i, s_j) penalizes certain qubit configurations.
// We use an Ising-like model: H = sum_{(i,j)} J_{ij} * (1 - 2*s_i) * (1 - 2*s_j)
// where s_i in {0,1} and J_{ij} is the coupling strength.
// Negative J -> ferromagnetic (same spin preferred), Positive J -> antiferromagnetic.
// Total energy = sum of all edge terms.

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

// 4 qubits positioned at corners of a square, centered
const qpos = [
  { x: 90,  y: 70 },   // qubit 0
  { x: 250, y: 70 },   // qubit 1
  { x: 250, y: 160 },  // qubit 2
  { x: 90,  y: 160 },  // qubit 3
];

// Edges: [i, j, J_ij, label]
// Negative = ferromagnetic (same-spin = low energy), Positive = antiferromagnetic
const edges = [
  [0, 1, -1.0, '-1'],   // top
  [1, 2,  2.0, '+2'],   // right
  [2, 3, -1.5, '-1.5'], // bottom
  [0, 3,  1.5, '+1.5'], // left
  [0, 2,  1.0, '+1'],   // diagonal
];

// Qubit states: 0 = |0⟩, 1 = |1⟩
const state = [0, 0, 0, 0];
const R = 24; // qubit radius

function spin(s) { return 1 - 2 * s; } // 0->+1, 1->-1

function totalEnergy(st) {
  let E = 0;
  for (const [i, j, J] of edges) E += J * spin(st[i]) * spin(st[j]);
  return E;
}

function groundState() {
  let best = Infinity, bestMask = 0;
  for (let mask = 0; mask < 16; mask++) {
    const st = [mask >> 3 & 1, mask >> 2 & 1, mask >> 1 & 1, mask & 1];
    const E = totalEnergy(st);
    if (E < best) { best = E; bestMask = mask; }
  }
  return bestMask;
}

function edgeEnergy(i, j, J) {
  return J * spin(state[i]) * spin(state[j]);
}

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Draw edges
  for (const [i, j, J, lbl] of edges) {
    const pi = qpos[i], pj = qpos[j];
    const ee = edgeEnergy(i, j, J);
    // Color edge: negative contribution = green tint, positive = red tint
    const t = Math.min(1, Math.abs(ee) / 3);
    if (ee < 0) {
      ctx.strokeStyle = `rgba(16,185,129,${0.3 + 0.5 * t})`;
    } else if (ee > 0) {
      ctx.strokeStyle = `rgba(239,68,68,${0.3 + 0.5 * t})`;
    } else {
      ctx.strokeStyle = '#c0cdd8';
    }
    ctx.lineWidth = 2.5 + 2 * t;
    ctx.beginPath(); ctx.moveTo(pi.x, pi.y); ctx.lineTo(pj.x, pj.y); ctx.stroke();

    // Edge label: coupling constant and contribution
    const mx = (pi.x + pj.x) / 2, my = (pi.y + pj.y) / 2;
    const dx = pj.x - pi.x, dy = pj.y - pi.y;
    const len = Math.sqrt(dx * dx + dy * dy);
    // Offset label perpendicular to edge
    const ox = -dy / len * 14, oy = dx / len * 14;
    ctx.font = '600 11px system-ui, sans-serif';
    ctx.fillStyle = '#555';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText('J=' + lbl, mx + ox, my + oy);
  }

  // Draw qubits
  for (let i = 0; i < 4; i++) {
    const p = qpos[i];
    const s = state[i];
    ctx.beginPath();
    ctx.arc(p.x, p.y, R, 0, 2 * Math.PI);
    ctx.fillStyle = s === 0 ? '#dbeafe' : '#fde68a';
    ctx.fill();
    ctx.strokeStyle = s === 0 ? '#2563eb' : '#d97706';
    ctx.lineWidth = 2.2;
    ctx.stroke();

    ctx.font = '700 15px system-ui, monospace';
    ctx.fillStyle = s === 0 ? '#1e40af' : '#92400e';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(s === 0 ? '|0⟩' : '|1⟩', p.x, p.y);

    // Qubit index
    ctx.font = '500 11px system-ui, sans-serif';
    ctx.fillStyle = '#888';
    ctx.fillText('q' + i, p.x, p.y + R + 12);
  }

  updateEnergy();
}

function updateEnergy() {
  const E = totalEnergy(state);
  const minE = totalEnergy([0,1,1,0]); // we'll compute properly
  document.getElementById('energy-val').textContent = E.toFixed(2);

  // Compute true minimum for comparison
  let best = Infinity;
  for (let mask = 0; mask < 16; mask++) {
    const st = [mask >> 3 & 1, mask >> 2 & 1, mask >> 1 & 1, mask & 1];
    const e = totalEnergy(st); if (e < best) best = e;
  }
  const lbl = document.getElementById('energy-label');
  const status = document.getElementById('status');
  if (Math.abs(E - best) < 0.001) {
    lbl.textContent = 'Ground state!'; lbl.className = 'label ground';
    status.textContent = fmt('✓ You found the ground state energy (%best%)!', { best: best.toFixed(2) });
  } else if (E > best + 4) {
    lbl.textContent = 'High energy'; lbl.className = 'label high';
    status.textContent = fmt('Energy %E%. Ground state is %best%. Keep exploring.', { E: E.toFixed(2), best: best.toFixed(2) });
  } else {
    lbl.textContent = 'Not minimal'; lbl.className = 'label mid';
    status.textContent = fmt('Energy %E%. Ground state is %best%. Can you do better?', { E: E.toFixed(2), best: best.toFixed(2) });
  }
}

canvas.addEventListener('click', function(e) {
  const rect = canvas.getBoundingClientRect();
  const mx = (e.clientX - rect.left) * (W / rect.width);
  const my = (e.clientY - rect.top) * (H / rect.height);
  for (let i = 0; i < 4; i++) {
    const p = qpos[i];
    if ((mx - p.x) ** 2 + (my - p.y) ** 2 < R * R) {
      state[i] ^= 1;
      draw();
      return;
    }
  }
});

document.getElementById('btn-find').addEventListener('click', function() {
  const mask = groundState();
  for (let i = 0; i < 4; i++) state[i] = (mask >> (3 - i)) & 1;
  draw();
  const E = totalEnergy(state);
  document.getElementById('status').textContent =
    fmt('✓ Ground state found by exhaustive search over all 16 configurations. Energy = %E%.', { E: E.toFixed(2) });
  console.log('Ground state:', state.map((s, i) => 'q' + i + '=' + s).join(', '), '| Energy:', E);
});

document.getElementById('btn-reset').addEventListener('click', function() {
  state.fill(0); draw();
  document.getElementById('status').textContent = '';
});

draw();

Result

Console

Notice the asymmetry: verifying that a given assignment achieves a claimed energy takes one quick scan. Finding the minimum-energy configuration requires searching all $2^{n}$ assignments — this classical version is already NP-hard (it is equivalent to MAX-CUT and related problems). For genuine quantum states, even a polynomial-time quantum computer may not find the ground state — that is QMA-hardness.

The Real Complexity

How hard is QMA, really? Here is the landscape:

QMA contains NP. A classical witness is just a product state, so any NP problem can be verified by an Arthur who ignores the quantum structure.
QMA is probably bigger than NP. If QMA = NP, then quantum proofs would offer no advantage over classical ones — an unlikely collapse. Most experts believe QMA ⊋ NP, meaning there are problems where a quantum witness is genuinely more powerful.
The Local Hamiltonian Problem is QMA-complete (Kitaev, 1999; published 2002). Given a Hamiltonian $H = \sum H_i$ where each $H_i$ acts on at most $k$ qubits, and two energy thresholds $a < b$ , decide: is the ground-state energy $\le a$ or $\ge b$ ? Kitaev proved this is QMA-complete for $k = 5$ ; subsequent work (Kempe, Kitaev, Regev, 2006) showed 2-local suffices — just pairwise qubit interactions make the problem maximally hard.
QMA has a complete problem just like NP does. The analogy to P vs NP is: is QMA solvable in polynomial quantum time? Nobody knows. Resolving this may be harder than resolving P vs NP.
The quantum PCP conjecture asks whether QMA hardness survives even approximate ground-state energy — a quantum analogue of the classical PCP theorem that underpins NP hardness of approximation. It remains wide open.

The verdict: QMA is the correct quantum analogue of NP, the 2-Local Hamiltonian problem is its canonical complete problem, and the gap between NP and QMA is a major open question in quantum complexity.

Where It Matters

QMA-hardness has direct consequences for real science and technology:

Quantum chemistry and materials science: computing the ground-state energy of a molecule is a Local Hamiltonian problem. QMA-hardness explains why even a quantum computer may not efficiently solve arbitrary instances — the problem is intrinsically hard, not just an engineering challenge.
Variational Quantum Eigensolvers (VQE): heuristic algorithms that search for low-energy states without a guarantee of finding the true ground state. Their limitations are predicted by QMA theory — they work well on structured instances but can fail on worst-case QMA-hard ones.
Condensed matter physics: understanding phase transitions, topological order, and quantum spin liquids requires analyzing Hamiltonians. QMA sets the boundary of what is provably tractable.
Quantum algorithm design: knowing that a problem is QMA-complete tells researchers it likely cannot be solved efficiently even by a quantum computer, steering effort toward approximation algorithms and special-case tractability.
Cryptography and quantum proof systems: QMA proof techniques underlie quantum interactive proofs (QIP = PSPACE) and multiprover entangled games (MIP* = RE), the latter proved in 2020 using QMA ideas.

Just as NP-completeness reshaped classical algorithm design, QMA-completeness shapes the quantum computing roadmap — separating what quantum computers can do from what lies beyond even them.

Conclusion

QMA draws the line where quantum verification ends. Classical NP says: "a brilliant classical prover can convince an efficient classical verifier." QMA says: "a brilliant quantum prover — with access to entangled quantum states — can convince an efficient quantum verifier." The Local Hamiltonian problem is that line's canonical landmark: QMA-complete, proven by Kitaev in 1999, tightened to just pairwise qubit interactions by 2006.

The deepest question — is QMA = NP, or is quantum witnessing genuinely more powerful? — sits alongside P vs NP as one of the most profound open problems in all of theoretical computer science. And unlike most open problems, its resolution would reshape our understanding of both computation and the physical universe, because the hardness of Local Hamiltonian is ultimately a statement about the complexity of nature itself.

Comments

Loading comments...

https://www.kipuhub.com/en/article/qma/Content licensed under CC BY-NC 4.0.

Cookies & privacy

QMA – Quantum Merlin Arthur

When a quantum proof is the best help you can get