DocumentCode
1780725
Title
On Physical Problems that are Slightly More Difficult than QMA
Author
Ambainis, Andris
Author_Institution
Univ. of Latvia, Ri̅ga, Latvia
fYear
2014
fDate
11-13 June 2014
Firstpage
32
Lastpage
43
Abstract
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).
Keywords
computational complexity; quantum computing; NP hard poblem; QMA oracle; computational complexity problems; natural computational problems; quantum computing; quantum physics; Computational complexity; Eigenvalues and eigenfunctions; Polynomials; Quantum computing; Stationary state; QMA; complexity of physical problems; quantum Hamiltonian complexity; quantum computing;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Complexity (CCC), 2014 IEEE 29th Conference on
Conference_Location
Vancouver, BC
Type
conf
DOI
10.1109/CCC.2014.12
Filename
6875473
Link To Document