REVIEW 1 cited by
Merlinization of complexity classes above BQP
Not yet reviewed by Pith; the record is open.
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
Merlinization of complexity classes above BQP
read the original abstract
We study how complexity classes above BQP, such as postBQP, ${\rm postBQP}_{\rm FP}$, and SBQP, change if we "Merlinize" them, i.e., if we allow an extra input quantum state (or classical bit string) given by Merlin as witness. Main results are the following three: First, the Merlinized version of postBQP is equal to PSPACE. Second, if the Merlinized postBQP is restricted in such a way that the postselection probability is equal to all witness states, then the class is equal to PP. Finally, the Merlinization does not change the class SBQP.
Forward citations
Cited by 1 Pith paper
-
A slightly improved upper bound for quantum statistical zero-knowledge
QSZK and its non-interactive variant NIQSZK stay inside QIP(2)∩co-QIP(2), now with an honest prover that runs in quantum linear space and single-exponential time.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.