Beim diesjährigen ACM Symposium on Theory of Computing (STOC) in Salt Lake City, Utah (USA) wurde Jonas Haferkamp mit dem Best Paper Award ausgezeichnet. Die renommierte Konferenz zählt zu den weltweit wichtigsten Veranstaltungen im Bereich der theoretischen Informatik. Ausgezeichnet wurde das Paper „Separating QMA from QCMA with a Classical Oracle“, das Haferkamp gemeinsam mit John Bostanci (Columbia University), Chinmay Nirkhe (University of Washington) und Mark Zhandry (NTT Research & Stanford University) verfasst hat.
Abstract:
We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decidable with access only to a classical witness (QCMA). The separating classical oracle we construct is for a decision problem we coin spectral Forrelation – the oracle describes two subsets of the boolean hypercube, and the computational task is to decide if there exists a quantum state whose standard basis measurement distribution is well supported on one subset while its Fourier basis measurement distribution is well supported on the other subset. This is equivalent to estimating the spectral norm of a “Forrelation” matrix between two sets that are accessible through membership queries.
Our lower bound derives from a simple observation that a query algorithm with a classical witness can be run multiple times to generate many samples from a distribution, while a quantum witness is a “use once” object. This observation allows us to reduce proving a QCMA lower bound to proving a sampling hardness result which does not simultaneously prove a QMA lower bound. To prove said sampling hardness result for QCMA, we observe that quantum access to the oracle can be compressed by expressing the problem in terms of bosons – a novel “second quantization” perspective on compressed oracle techniques, which may be of independent interest. Using this compressed perspective on the sampling problem, we prove the sampling hardness result, completing the proof.
Allgemeiner Hinweis: Mit einer möglichen Nennung von geschlechtszuweisenden Attributen implizieren wir alle, die sich diesem Geschlecht zugehörig fühlen, unabhängig vom biologischen Geschlecht.