Class Description

P||QMA: P With Parallel Queries To QMA

The class of decision problems solvable by a P machine that can make a polynomial number of non-adaptive queries to a QMA oracle.

Equals PQMA[log] [GPY19].

Linked From

PQMA[log]: P With Log QMA Queries

The class of decision problems solvable by a P machine, that can make O(log n) queries to a QMA oracle (where n is the length of the input).

Defined in [Amb14].

Equals P||QMA [GPY19].

Estimating local observables [Amb14], [GY16] and local correlation functions [GY16] against ground states of local Hamiltonians is PQMA[log]-complete.

Estimating local observables remains PQMA[log]-complete even on 2D physical systems and on the 1D line [GPY19].

PQMA[log] is contained in PP [GY16].

More about...