Pith. sign in

REVIEW 4 cited by

Quantum NP - A Survey

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv quant-ph/0210077 v1 pith:YZJCN7YD submitted 2002-10-11 quant-ph

Dorit Aharonov , Tomer Naveh This is my paper
classification quant-ph
keywords quantumresultsurveyclasscomplexityextensionaharonovalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We describe Kitaev's result from 1999, in which he defines the complexity class QMA, the quantum analog of the class NP, and shows that a natural extension of 3-SAT, namely local Hamiltonians, is QMA complete. The result builds upon the classical Cook-Levin proof of the NP completeness of SAT, but differs from it in several fundamental ways, which we highlight. This result raises a rich array of open problems related to quantum complexity, algorithms and entanglement, which we state at the end of this survey. This survey is the extension of lecture notes taken by Naveh for Aharonov's quantum computation course, held in Tel Aviv University, 2001.

Discussion (0). Sign in to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On the complexity of estimating ground state entanglement and free energy

    quant-ph 2025-10 reject novelty 7.0 of 10

    Detecting high-entanglement ground states is claimed qq-QAM-complete and free-energy approximation in qq-QAM, but the main containment proofs mishandle the number of Hamiltonian terms.

  2. Quantum Differential Equation Solvers with Low State Preparation Cost: Eliminating the Time Dependence in Dissipative Equations

    quant-ph 2025-08 conditional novelty 7.0 of 10

    For strictly dissipative linear ODEs, quantum solvers based on time-marching or LCHS achieve query complexity O(polylog(1/ε)) that is independent of the evolution time T.

  3. Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete

    quant-ph 2025-08 unverdicted novelty 7.0 of 10

    Deciding if a classical-quantum channel can exactly preserve a single bit is QCMA-complete, with optimal witnesses characterized as computational basis states (minimum) and |+>, |-> states (maximum).

  4. En Route to a Standard QMA1 vs. QCMA Oracle Separation

    quant-ph 2026-04 unverdicted novelty 6.0 of 10

    A classical oracle is built such that a language is in QMA1 but not in QCMA under polynomially adaptive rounds and exponential parallel queries, plus a derandomized in-place separation.

Pith tools