6533b81ffe1ef96bd1278772

RESEARCH PRODUCT

On Physical Problems that are Slightly More Difficult than QMA

Andris Ambainis

subject

Discrete mathematicsFOS: Computer and information sciencesQuantum PhysicsTheoretical computer scienceCompleteNP-easyFOS: Physical sciences0102 computer and information sciencesComputer Science::Computational ComplexityComputational Complexity (cs.CC)01 natural sciencesPHStructural complexity theoryComputer Science - Computational Complexity010201 computation theory & mathematics0103 physical sciencesAsymptotic computational complexityComplexity classF.1.2Low010306 general physicsQuantum Physics (quant-ph)Quantum complexity theoryMathematics

description

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).

yearjournalcountryeditionlanguage
2013-12-172014 IEEE 29th Conference on Computational Complexity (CCC)
10.1109/ccc.2014.12http://dx.doi.org/10.1109/CCC.2014.12