Quantum Computing / Quantum Complexity Theory
Requirements for exponential speedup
Clifford circuits can (1) create superposition such as with Hadamard gates, (2) create entanglement such as with CNOT gates, (3) cause interference such as with Z gates. But the Gottesman-Knill theorem shows that circuits composed solely of Clifford gates can be classically simulated.
For decision problems in NP, the Aaronson-Ambainis conjecture (arXiv) proposes constraints on the amount of structure needed for exponential speedups. But, the Yamakawa-Zhandry problem (arXiv) provides a (black-box) exponential speedup for an NP search problem.
Restricted models of quantum computing
- The one clean qubit DQC1 complexity class can estimate values of the Jones polynomial (arXiv) which is not known to be efficient classically.
- The commuting Hamiltonian problem is not obviously in NP (they: they can have highly entangled ground states (such as for topologically ordered systems, e.g. the Toric Code), and thus, it is not clear how to provide an efficiently checkable classical description of the ground state).
